常用數(shù)據(jù)結構及其運算1

1、會計學1常用數(shù)據(jù)結構及其運算常用數(shù)據(jù)結構及其運算1第1頁/共170頁2022-6-2122.1 概述概述2.1.1 什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構 程序程序=數(shù)據(jù)結構數(shù)據(jù)結構+算法算法數(shù)據(jù)結構示例數(shù)據(jù)結構示例 學號 姓名 性別 籍貫 電 話 通 訊 地 址 01 張三 男 長沙 8639000 麓山南路 327 號 02 李四 男 北京 23456789 學院路 435 號 03 王五 女 廣州 30472589 天河路 478 號 04 趙六 男 上海 41237568 南京路 1563 號 05 錢七 女 南京 5013472 南京大學 06 劉八 女 武漢 61543726 武漢大學 07

2、 朱九 男 昆明 4089651 云南大學 08 孫十 女 杭州 6154372 西湖路 635 號 圖 1-1 學生數(shù)據(jù)表 1.線性表示例線性表示例第2頁/共170頁2022-6-2132.樹形結構示例樹形結構示例 a1 a b c b1 a2 Tt b2 c1 c2 d d1 d2 d3 圖 1-2 樹形結構示意圖 一層二層三層四層第3頁/共170頁2022-6-2143.圖形結構示例圖形結構示例 1 2 3 4 5 6 圖 1-3 圖形結構示意圖 第4頁/共170頁2022-6-215第5頁/共170頁2022-6-2162.1.2 基本術語基本術語1 數(shù)據(jù)（數(shù)據(jù)（data）數(shù)據(jù)是信息的

3、載體,它可以用計算機表示并加工。例如：數(shù)字、字母、漢字、圖形、圖像、聲音都稱為數(shù)據(jù)。 第6頁/共170頁2022-6-217第7頁/共170頁2022-6-2183 數(shù)據(jù)對象（數(shù)據(jù)對象（data object）是性質(zhì)相同的數(shù)據(jù)元素組成的集合，是數(shù)據(jù)的一個子集。例如，整數(shù)數(shù)據(jù)對象是集合N0，1，2.，字母字符數(shù)據(jù)對象是集合C=A,B,Z。第8頁/共170頁2022-6-219第9頁/共170頁2022-6-2110第10頁/共170頁2022-6-2111第11頁/共170頁2022-6-2112a. 集合結構(set)：數(shù)據(jù)元素的有限集合。數(shù)據(jù)元素之間除了“屬于同一個集合”的關系之外沒有其他關

4、系。元素順序是隨意的。 b. 線性結構(linear) ：數(shù)據(jù)元素的有序集合。數(shù)據(jù)元素之間形成一對一的關系。c. 樹形結構(tree)：樹是層次數(shù)據(jù)結構，樹中數(shù)據(jù)元素之間存在一對多的關系。d. 圖結構(graph)：圖中數(shù)據(jù)元素之間的關系是多對多的。從邏輯結構劃分數(shù)據(jù)結構從邏輯結構劃分數(shù)據(jù)結構第12頁/共170頁2022-6-2113圖12 四種基本結構示意圖 (a) 集合結構； (b) 線性結構； (c) 樹形結構； (d) 圖結構(a)(b)(c)(d)第13頁/共170頁2022-6-2114 上述四種基本的結構關系可分為兩類：線性結構(linear structure)和非線性結構(n

5、on-linear structure)。我們把除了線性結構以外的幾種結構關系樹、圖和集合歸入非線性結構一類。第14頁/共170頁2022-6-2115第15頁/共170頁2022-6-2116第16頁/共170頁2022-6-2117第17頁/共170頁2022-6-21181.基本概念基本概念算法（算法（algorithm）算法是解決某一特定類型問題的有限運算序列。它必須滿足下述條件（也稱為算法的五大特性）：1）有窮性有窮性 一個算法必須總是在執(zhí)行有窮步之后結束，一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內(nèi)完成。且每一步都在有窮時間內(nèi)完成。2）確定性確定性 算法中每一條指令

6、必須有確切的含義。不存算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。在二義性。且算法只有一個入口和一個出口。3）可行性可行性 一個算法是可行的。即算法描述的操作都是一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。4）輸入輸入 一個算法有零個或多個輸入，這些輸入取自于一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。某個特定的對象集合。5）輸出輸出 一個算法有一個或多個輸出，這些輸出是同輸一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量入有著某些特定關系的量。

7、第18頁/共170頁2022-6-2119算法和程序的關系算法和程序的關系算法的含義與程序十分相似，但二者是有區(qū)別的。一個程序不一定滿足有窮性（死循環(huán)），另外，程序中的指令必須是機器可執(zhí)行的，而算法中的指令則無此限制。一個算法若用計算機語言來書寫，則它就可以是一個程序。第19頁/共170頁2022-6-2120用流程圖描述算法用流程圖描述算法一個算法可以用流程圖的方式來描述，輸入輸出、判斷、處理分別用不同的框圖表示，用箭頭表示流程的流向。這是一種描述算法的較好方法，目前在一些高級語言程序設計中仍然采用。用自然語言描述算法用自然語言描述算法用我們?nèi)粘Ｉ钪械淖匀徽Z言（可以是中文形式，也可以是英文

8、形式）也可以描述算法。 第20頁/共170頁2022-6-2121用其它方式描述算法用其它方式描述算法我們還可以用數(shù)學語言或約定的符號語言來描述算法。用用C語言描述算法語言描述算法第21頁/共170頁2022-6-2122第22頁/共170頁2022-6-2123第23頁/共170頁2022-6-2124第24頁/共170頁2022-6-2125第25頁/共170頁2022-6-2126第26頁/共170頁2022-6-2127第27頁/共170頁2022-6-2128第28頁/共170頁2022-6-2129第29頁/共170頁2022-6-2130練習1.是數(shù)據(jù)的基本單位，.是具有獨立含義

9、的最小標識單位。2.什么是數(shù)據(jù)結構?3.數(shù)據(jù)的.與數(shù)據(jù)的存儲無關，它是獨立于計算機的。4.通常數(shù)據(jù)結構分為.、 .、 .、 .四類。5.數(shù)據(jù)的存儲結構包括順序存儲結構、鏈式存儲結構、.、.第30頁/共170頁2022-6-2131下面給出幾個線性表的例子：例例2-1 26個大寫的英文字母表：(A，B，C，.，Z) 例例2-2 某校從1996年到2002年各種型號計算機擁有量的變化情況，可以用線性表給出： (200，220，250，300，400，700，1200)2.2 線線 性性 表表 一、 線性表的定義和運算1.定義第31頁/共170頁2022-6-2132n 數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)

10、 表的長度表的長度n = 0 空表空表n0 非空表非空表 第32頁/共170頁2022-6-2133線性表的結構僅涉及諸元素的相對位置，即第i個元素ai處在第i-1個元素ai-1的后面和第i+1個元素ai+1的前面，這種位置上的有序性就是一種線性關系，所以線性表是一種線性結構。線性表中每個數(shù)據(jù)元素數(shù)據(jù)元素ai的具體含義的具體含義，在不同情況下各不相同，它可以是一個數(shù)，或是一個符號，或者一個記錄，甚至是其它更復雜的信息。但在同一個線性表中的數(shù)據(jù)元素必須具有相同的特性(或者說具有相同的類型)。若線性表中的數(shù)據(jù)元素相互之間可比較,且 則該線性表稱為有序表否則稱為無序表。,.,3 , 2,1niaai

11、i 第33頁/共170頁2022-6-2134第34頁/共170頁2022-6-2135線性表是一種典型的線性結構，用二元組表示為 L=（D，R）其中：D=a1，a2, ., an2 ,|,11niDaaaaRiiii對應的邏輯結構圖如圖2-1所示。 a1 a2 an 圖 2-1 線性表邏輯結構示意圖 第35頁/共170頁2022-6-21362、線性表的運算、線性表的運算常見線性表的運算有：1) 置空表 SETNULL（&L）將線性表L置成空表2) 求長度 LENGTH（L） 求給定線性表L的長度3) 取元素 GET（L，i） 若1ilength(L),則取第i個位置上的元素，否則取得的元素

12、為NULL。 4) 求直接前趨 PRIOR（L，X）求線性表L中元素值為X的直接前趨，若X為第一個元素，前驅(qū)為NULL。第36頁/共170頁2022-6-21375) 求直接后繼 NEXT（L，X）求線性表L中元素值為X直接后繼，若X為最后一個元素，后繼為NULL。6) 定位函數(shù) LOCATE（L，X） 在線性表L中查找值為X的元素位置，若有多個值為X，則以第一個為準，若沒有，位置為0。7) 插入 INSERT（&L，X，i）在線性表L中第i個位置上插入值為X的元素。8) 刪除 DELETE（&L，i） 刪除線性表L中第i個位置上的元素。線性表的運算線性表的運算第37頁/共170頁2022-6

13、-2138例2-1 假設線性表L=(23,56,89,76,18),i=3,x=56,y=88,則對L的一組操作及結果如下：Length(L); /所得結果為5Get(L,i) /所得結果為89Prior(L,x) /所得結果為23Next(L,x) /所得結果為89Locate(L,x) /所得結果為2Insert(&L,y,i) /所得結果為(23,56,88,89,76,18)Delete(&L,i+1) /所得結果為(23,56,88,76,18)第38頁/共170頁2022-6-2139二、二、 順序存儲線性表順序存儲線性表1.順序存儲結構順序存儲結構線性表的順序存儲結構,也稱為順序

14、表。其存儲方式為：在內(nèi)存中開辟一片連續(xù)存儲空間，但該連續(xù)存儲空間的大小要大于或等于順序表的長度，然后讓線性表中第一個元素存放在連續(xù)存儲空間第一個位置，第二個元素緊跟著第一個之后，其余依此類推。第39頁/共170頁2022-6-2140圖2-2 線性表順序存儲結構示意圖(設每個數(shù)據(jù)元素占有1個存儲單元) a1a2aian內(nèi) 存 狀 態(tài)存 儲 地 址元 素 序 號12in空 閑bb 1b (maxlen 1)b ( i 1)b ( n 1)第40頁/共170頁2022-6-2141第41頁/共170頁2022-6-2142第42頁/共170頁2022-6-21432.順序存儲結構的插入、刪除運算順

15、序存儲結構的插入、刪除運算第43頁/共170頁2022-6-2144結構結構 結構(structure)是C語言提供的聚合數(shù)據(jù)的機制。使用結構可以將不同類型的數(shù)據(jù)組合成一個整體，便于使用。 一個結構(在許多其他程序設計語言中稱為記錄record)是數(shù)據(jù)項的聚集(collection)。每個數(shù)據(jù)項有名稱和類型，它們可以是不同的數(shù)據(jù)類型。補充內(nèi)容補充內(nèi)容第44頁/共170頁2022-6-2145例如：struct student char name20; char sex; int age; 第45頁/共170頁2022-6-2146 該語句定義了一個結構類型 struct student，可以使

16、用它作為定義結構變量的類型，如 struct student studA;，這里，變量studA是一個結構?？梢允褂贸蓡T運算符“.”對結構變量的成員賦值。如，strcpy(studA.name, Wang); /*字符串賦值函數(shù)*/studA.age=19; studA.sex=M; 對成員變量可以像對普通變量一樣進行其類型所允許的各種運算。 ANSI C允許將一個結構變量整體賦值給另一個具有相同結構的結構變量，但不能將一個結構變量作為一個整體進行輸入和輸出，也不能直接判定兩個結構是否相同。第46頁/共170頁2022-6-2147 為了能像使用C語言類型int一樣使用一個結構類型，我們可以用

17、typedef創(chuàng)建自己的結構類型Student如下：typedef struct student char name20; char sex; int age; Student； 這里，student是結構名，Student是結構類型名，我們可以像使用類型int一樣用Student定義結構變量。定義變量的語句為Student studA; ，無須加保留字struct。事實上，結構名稱與結構類型的名稱可以相同。第47頁/共170頁2022-6-2148第48頁/共170頁2022-6-2149求線性表的長度求線性表的長度length(L) #define maxlen 100typedef st

18、ruct int elemmaxlen; int last; sqlisttp;int length(sqlisttp L) return L. last; 該算法的語句頻度為1，時間復雜度為O(1)。第49頁/共170頁2022-6-2150（1）插入第50頁/共170頁2022-6-2151.a2a1an.ai+1ai01i-1in-1在線性表的第在線性表的第i i個元素之前插入一個新的元素，先移動，后插入。個元素之前插入一個新的元素，先移動，后插入。ai-1.a2a1alast ai+1ai x ai-1. a2 a1 ai ai+1 alast alast ai+1 ai x第51頁/

19、共170頁2022-6-2152#define maxlen 100typedef struct int elemmaxlen; int last; sqlisttp;第52頁/共170頁2022-6-2153nv.elemk+1 = v.elemk;nv.elemi-1 = x;nv.last+;n n第53頁/共170頁2022-6-2154（2）刪除第54頁/共170頁2022-6-2155.a2a1an.ai+1ai01i-1in-1刪除線性表的第刪除線性表的第i i個元素，后面所有元素前移。個元素，后面所有元素前移。ai-1.a2a1alastai+1ai ai-1. a2 a1 a

20、i ai+1 alast刪除刪除結點結點a ai i ai+1 alast第55頁/共170頁2022-6-2156第56頁/共170頁2022-6-21572n1)i(n1n11n1i(3)運算的時間分析第57頁/共170頁2022-6-215821ni)(nn1n1i第58頁/共170頁2022-6-2159第59頁/共170頁2022-6-2160第60頁/共170頁2022-6-2161datadatanextnext NODE； 數(shù)據(jù)元素的結點結構結點結構如下：第61頁/共170頁2022-6-2162補充內(nèi)容補充內(nèi)容指針指針 C語言中，指針(pointer)也稱為鏈(link)或引

21、用(reference)。C語言使用下列語句定義一個整型變量i 和一個指向整型變量的指針變量pi： int i, *pi; 第62頁/共170頁2022-6-2163 事實上，對任意類型T，都可定義指向該類型的指針類型。指針類型變量的值是一個存儲地址。C語言中有兩個十分重要的與指針類型相關的運算符：取地址運算符(address operator)& 和間接引用運算符(dereferencing operator) *。間接引用運算符用來對指針變量所指示的變量進行操作。第63頁/共170頁2022-6-2164看下面的程序段： int i, *pi; /* 定義整型變量 i 和指向整型的指針變量

22、pi */ pi=&i; /* 將變量i 的地址賦給指針(變量)pi */ i=5; /* 對變量i 賦整數(shù)值5 */ printf(%d ，i); /* 輸出 i 的值 5 和逗號 */ *pi=10; /* 對指針pi所指示的存儲位置(變量i)賦值10 */ printf(%d ，*pi); /* 輸出 i 的當前值 10 */運行上面的程序段將顯示：5，10。第64頁/共170頁2022-6-2165 C語言有一個特殊的指針值NULL，它不指向任何數(shù)據(jù)對象和函數(shù)。一般地，NULL由整數(shù)0表示。上述程序段的執(zhí)行過程可以對照圖22來理解。應注意的是：指針變量pi的值是整型變量i的地址，這里假

23、定分配給變量i的地址是254。 第65頁/共170頁2022-6-2166圖 22 指針定義和運算254piipi&i;2545piii5;25410piipi10;pi&i254inti, *pi;*第66頁/共170頁2022-6-2167 指向結構的指針 前面介紹了結構和結構類型。一個結構的成員可以是多種類型的，也可以是指針類型的。這個指針可以指向其他結構類型，也可以指向它所在的結構類型。例如， struct node int Data;struct node *Link; ; Link是結構的成員名，它是指向struct node類型的指針。當一個結構中有一個或多個成員是指向它自身的指

24、針時，稱這種結構為自引用結構。第67頁/共170頁2022-6-2168 定義一個指向結構的指針可以使用定義語句：struct node *p;。使用typedef定義指向結構的指針類型的方法更靈活。例如： typedef struct node *Nodeptr; typedef struct node int Data;Nodeptr *Link; Node; 這里，我們定義了一個結構類型Node（node為結構名稱），以及指向該結構類型的指針類型Nodeptr。第68頁/共170頁2022-6-2169datadatanextnext NODE； 數(shù)據(jù)元素的結點結構結點結構如下：第69頁

25、/共170頁2022-6-2170n個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。由于每個結點中只有一個一個指針域，故稱此鏈表為線性鏈表線性鏈表或或單鏈表單鏈表。第70頁/共170頁2022-6-2171第71頁/共170頁2022-6-2172圖2-4 線性鏈表的邏輯狀態(tài)邏輯狀態(tài)示意圖圖2-3 線性鏈表的物理狀態(tài)物理狀態(tài)示意圖 第72頁/共170頁2022-6-2173第73頁/共170頁2022-6-2174圖2-5 帶頭結點的單鏈表 第74頁/共170頁2022-6-2175第75頁/共170頁2022-6-2176第76頁/共170頁2022-6-2177第77頁/共170頁2022

26、-6-2178第78頁/共170頁2022-6-2179struct nodeint data;struct node *next; ;typedef struct node NODE;第79頁/共170頁2022-6-2180n return p; /* 找到,1=inext = null ) return 0;/鏈表為空，返回0 else while(p-next) p = p-next; j+; return j; /返回鏈表的長度while(p-next) p=p-next; j+;return j;第83頁/共170頁2022-6-2184第84頁/共170頁2022-6-2185圖

27、2-6 帶頭結點單鏈表的邏輯狀態(tài)a1ai1headanai第85頁/共170頁2022-6-2186第86頁/共170頁2022-6-2187圖2-7 在單鏈表中插入結點S 第87頁/共170頁2022-6-2188i-1n s - d a t a = x ; /* */n s - n e x t = p - n e x t ; /* */n p - n e x t = s ; /* */nn第88頁/共170頁2022-6-2189第89頁/共170頁2022-6-2190第90頁/共170頁2022-6-2191圖2-8 帶頭結點的單鏈表a1ai1headanaiai1p圖2-9 在單鏈表

28、中刪除一個結點第91頁/共170頁2022-6-2192n第92頁/共170頁2022-6-2193第93頁/共170頁2022-6-2194第94頁/共170頁2022-6-2195圖2-10 循環(huán)單鏈表第95頁/共170頁2022-6-2196第96頁/共170頁2022-6-2197第97頁/共170頁2022-6-2198圖2-11 雙向鏈表結點結構第98頁/共170頁2022-6-2199圖2-12 帶頭結點的空雙向鏈表 head 和循環(huán)單鏈表類似，也可將雙向鏈表的頭結點和尾結點鏈接起來組成雙向循環(huán)鏈表。 雙向鏈表的幾種不同狀態(tài)如圖2-12，圖2-13，圖2-14和圖2-15所示。h

29、eada1a2an圖2-13 帶頭結點的非空雙向鏈表 第99頁/共170頁2022-6-21100圖2-14 空的雙向循環(huán)鏈表 headheada1a2an圖2-15 非空雙向循環(huán)鏈表第100頁/共170頁2022-6-21101第101頁/共170頁2022-6-21102第102頁/共170頁2022-6-21103第103頁/共170頁2022-6-21104第104頁/共170頁2022-6-21105第105頁/共170頁2022-6-21106第106頁/共170頁2022-6-21107第107頁/共170頁2022-6-21108第108頁/共170頁2022-6-21109圖

30、2-19 棧頂指示器和棧中元素之間的關系 第109頁/共170頁2022-6-21110第110頁/共170頁2022-6-21111第111頁/共170頁2022-6-21112第112頁/共170頁2022-6-21113第113頁/共170頁2022-6-21114第114頁/共170頁2022-6-21115 其中top為棧頂指針，指示棧頂元素位置，若top=Null，則表示空棧。鏈棧一般不會出現(xiàn)“上溢”，除非內(nèi)存中已不存在可用空間。 下面給出鏈棧的定義，鏈棧的出、入棧操作類似于單鏈表，下面給出相應的算法。第115頁/共170頁2022-6-21116 SNODE ；第116頁/共17

31、0頁2022-6-21117第117頁/共170頁2022-6-21118topdatalink棧頂棧底第118頁/共170頁2022-6-21119第119頁/共170頁2022-6-21120topdata link棧頂棧底第120頁/共170頁2022-6-21121第121頁/共170頁2022-6-21122圖2-22 隊列的示意圖第122頁/共170頁2022-6-21123第123頁/共170頁2022-6-21124第124頁/共170頁2022-6-21125第125頁/共170頁2022-6-21126圖2-23 順序隊列中頭、尾指針變化(設MAXSIZE=m=6 )012

32、34m-1=5rearfront(a)空隊列DCBArearfront(b)A,B,C,D 相繼入隊rearfront(c)A,B,C,D 相繼出隊FErearfront(d)E,F 入隊-1第126頁/共170頁2022-6-21127第127頁/共170頁2022-6-21128第128頁/共170頁2022-6-21129圖2-24 循環(huán)隊列示意圖第129頁/共170頁2022-6-21130第130頁/共170頁2022-6-21131第131頁/共170頁2022-6-21132第132頁/共170頁2022-6-21133第133頁/共170頁2022-6-21134第134頁/共

33、170頁2022-6-21135第135頁/共170頁2022-6-21136圖2-25 鏈隊列示意圖 鏈隊列的邏輯狀態(tài)如圖2-25所示。第136頁/共170頁2022-6-21137第137頁/共170頁2022-6-21138第138頁/共170頁2022-6-21139第139頁/共170頁2022-6-21140第140頁/共170頁2022-6-21141第141頁/共170頁2022-6-21142第142頁/共170頁2022-6-21143第143頁/共170頁2022-6-21144A =a11 a12 . a1n a21 a22 . a2n am1 am2 . amn 如下

34、所示，就是一個m行n列的二維數(shù)組(也稱為矩陣)，記作Am, n。第144頁/共170頁2022-6-21145第145頁/共170頁2022-6-21146第146頁/共170頁2022-6-21147第147頁/共170頁2022-6-21148第148頁/共170頁2022-6-21149第149頁/共170頁2022-6-21150第150頁/共170頁2022-6-21151圖2-31 二維數(shù)組的兩種存儲方式第151頁/共170頁2022-6-21152第152頁/共170頁2022-6-21153第153頁/共170頁2022-6-21154第154頁/共170頁2022-6-21155第155頁/共170頁2022-6-21156A=a11 0 0 a21 a22 0 an1 an2 ann 在下三角矩陣中，對角線以上元素全部為0，我們只需存儲下三角的元素。第156頁/共170頁2022-6-21157 假設以一維數(shù)組S