1、1第二章 基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算2第二章基本數(shù)據(jù)結(jié)構(gòu)及運(yùn)算第二章基本數(shù)據(jù)結(jié)構(gòu)及運(yùn)算 1 數(shù)據(jù)結(jié)構(gòu)的基本概念 2 線性表及其順序存儲(chǔ)結(jié)構(gòu) 3 線性鏈表及其運(yùn)算 4 數(shù)組 5 樹(shù)與二叉樹(shù) 6 圖32. 1 數(shù)據(jù)結(jié)構(gòu)基本概念41. 數(shù)據(jù)結(jié)構(gòu)舉例數(shù)據(jù)結(jié)構(gòu)舉例 無(wú)序表和有序表351678854329332154461621293335434654788551. 數(shù)據(jù)結(jié)構(gòu)舉例數(shù)據(jù)結(jié)構(gòu)舉例 學(xué)生成績(jī)表：學(xué)號(hào) 姓名 性別 年齡 成績(jī) 01 張三 男 20 86 02 李四 男 19 83 03 王五 女 19 70 04 趙六 男 21 91 05 錢(qián)七 女 18 78 06 劉八 女 19 80 07 朱九

2、男 18 95 08 孫十 女 21 89 61. 數(shù)據(jù)結(jié)構(gòu)舉例數(shù)據(jù)結(jié)構(gòu)舉例樹(shù)結(jié)構(gòu) a1 a b c b1 a2 Tt b2 c1 c2 d d1 d2 d3 一層二層三層四層71. 數(shù)據(jù)結(jié)構(gòu)舉例數(shù)據(jù)結(jié)構(gòu)舉例圖結(jié)構(gòu) 1 2 3 4 5 6 82. 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)： 是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。 定義理解數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)元素前后件關(guān)系數(shù)據(jù)元素（data element）： 是組成數(shù)據(jù)的基本單位。前后件關(guān)系： 數(shù)據(jù)元素的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。93. 數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵數(shù)據(jù)結(jié)構(gòu)的內(nèi)涵 數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的存貯結(jié)構(gòu);對(duì)數(shù)據(jù)所施加的運(yùn)算。數(shù)據(jù)的邏輯結(jié)構(gòu)

3、獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身固有的。是邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的映像必須依賴于計(jì)算機(jī)。指所施加的一組操作總稱(chēng)。運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必依賴于存貯結(jié)構(gòu)。104. 數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu) 1.反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)表示：B（D，R）其中D:數(shù)據(jù)元素集合； R:D中各數(shù)據(jù)元素之間的前后件關(guān)系。舉例： E.g.1 一年四季數(shù)據(jù)邏輯結(jié)構(gòu)； E.g.2 家庭成員數(shù)據(jù)邏輯結(jié)構(gòu)； E.g.3 mxn矩陣數(shù)據(jù)邏輯結(jié)構(gòu)；11例2.1 一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成B = (D,R)D = 春,夏,秋,冬R = (春,夏),(夏,秋),(秋,冬)例2.2 家庭成員B = (D,R)

4、D = 父親,兒子,女兒R = (父親,兒子),(父親,女兒)12 例2.3 n維向量X = (x1,x2,xn) 也是一種數(shù)據(jù)結(jié)構(gòu)。即X = (D,R)，其中數(shù)據(jù)元素的集合為：D = x1,x2,xn關(guān)系為：R = (x1,x2),(x2,x3),(x n 1, xn)13 例如，mn的矩陣在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，矩陣的每一行在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，矩陣的每一行Ai = (ai1，ai2，ain)，i = 1,2,m可以看成是它的一個(gè)數(shù)據(jù)元素?？梢钥闯墒撬囊粋€(gè)數(shù)據(jù)元素。即數(shù)據(jù)元素的集合為：即數(shù)據(jù)元素的集合為：D = A1，A2，AmD上的一個(gè)關(guān)系為：上的一個(gè)關(guān)系為：R = (A1，A2)，(A2，A3

5、)，(Ai，Ai+1)，Am 1，Am14顯然，數(shù)據(jù)結(jié)構(gòu)A中的每一個(gè)數(shù)據(jù)元素Ai（i = 1,2,m）又是另一個(gè)數(shù)據(jù)結(jié)構(gòu)，即數(shù)據(jù)元素的集合為：Di = ai1，ai2, ，ainDi上的一個(gè)關(guān)系為：Ri = (ai1，ai2)，(ai2，ai3)，(ai，ai,j + 1)，(ai,n 1，ain)15一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。如：一年中四季的變化如：一年中四季的變化再如：反映家庭成員間輩份再如：反映家庭成員間輩份關(guān)系的數(shù)據(jù)結(jié)構(gòu)可以用圖關(guān)系的數(shù)據(jù)結(jié)構(gòu)可以用圖2.2所示的圖形表示。所示的圖形表示。 16 例

6、2.4 用圖形表示數(shù)據(jù)結(jié)構(gòu)B =（D，R），其中D = di |1i7 = d1，d2，d3，d4，d5，d6，d7R = (d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5) 這個(gè)數(shù)據(jù)結(jié)構(gòu)的圖形表示如圖2.3所示。174. 數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu) 2. 數(shù)據(jù)邏輯結(jié)構(gòu)類(lèi)型 線性結(jié)構(gòu) 線性結(jié)構(gòu)判定條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多一個(gè)后件。 線性結(jié)構(gòu)插入或刪除任一結(jié)點(diǎn)后還是線性結(jié)構(gòu)。非線性結(jié)構(gòu)e.g. 樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)185. 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式 常用的存儲(chǔ)結(jié)構(gòu)包括： 順序存儲(chǔ)： 鏈?zhǔn)酱?/p>

7、儲(chǔ)： 索引存儲(chǔ)： 散列存儲(chǔ)： 一種邏輯結(jié)構(gòu)可根據(jù)需要表示成多種存儲(chǔ)結(jié)構(gòu)e.g. 順序存儲(chǔ)結(jié)構(gòu)或鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。19順序存儲(chǔ)結(jié)構(gòu)主要用于線性結(jié)構(gòu)。在這種存儲(chǔ)方式中，把邏輯上相鄰的數(shù)據(jù)元素結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中，各結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。圖2.5是將線性結(jié)構(gòu)(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)順序地存放在存儲(chǔ)單元中的示意圖。 20 在鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)存儲(chǔ)結(jié)點(diǎn)要有兩部分組成：一部分用于存放數(shù)據(jù)信息，另一部分用于存放指針。 其中指針用于指向該結(jié)點(diǎn)的前件或后件。 216. 數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)的運(yùn)算 基本運(yùn)算：插入

8、刪除 其它運(yùn)算：查找分類(lèi)合并復(fù)制修改 空數(shù)據(jù)結(jié)構(gòu)222.2 線性表及其順序存儲(chǔ)結(jié)構(gòu)線性表及其運(yùn)算棧及其運(yùn)算隊(duì)列及其運(yùn)算232.2.1 線性表及其運(yùn)算241. 什么是線性表什么是線性表 線性表：是由n(n0)個(gè)數(shù)據(jù)元素組成的有限序列，邏輯上為一個(gè)一維向量：(a1,a2,a3,an)特征： 有且只有一個(gè)根結(jié)點(diǎn)a1，其無(wú)前件； 有且只有一個(gè)終結(jié)點(diǎn)an，其無(wú)后件； 其它結(jié)點(diǎn)有且只有一個(gè)前件及后件。線性表的長(zhǎng)度： n252. 線性表順序存儲(chǔ)結(jié)構(gòu) 對(duì)應(yīng)到程序設(shè)計(jì)語(yǔ)言中的一維數(shù)組 第i個(gè)元素的存儲(chǔ)地址：ADR(ai)= ADR(a1) (i-1)k序號(hào) 內(nèi)容 序 號(hào) 內(nèi)容 插入前 插入后 a1 a2 a3

9、aiai+1ai+2 ai+3 an 26 建立一個(gè)空線性表的順序存儲(chǔ)空間（即初始化線性表的順序存儲(chǔ)空間）的C語(yǔ)言描述如下：#include stdlib.hET * initsl(int m,int *n) /*函數(shù)返回順序表空間的首地址*/*ET表示元素的數(shù)據(jù)類(lèi)型*/*m為順序表的空間容量,n返回線性表的長(zhǎng)度*/ ET *v=(ET *)malloc(m*sizeof(ET)；/*申請(qǐng)順序表空間*/ *n=0； /*線性表長(zhǎng)度為0*/ return v；27 2.2.2 順序表的插入與刪除順序表的插入與刪除 1順序表的插入運(yùn)算28 設(shè)長(zhǎng)度為n的線性表為： 要在線性表的第i個(gè)元素ai之前插入

10、一個(gè)新元素b，插入后得到長(zhǎng)度為n + 1的線性表為：則插入前后的兩線性表中的元素滿足如下關(guān)系：則插入前后的兩線性表中的元素滿足如下關(guān)系：29 在線性表順序存儲(chǔ)的情況下，要插入一個(gè)新元素，由于數(shù)據(jù)元素的移動(dòng)而消耗較多的處理時(shí)間，因此其效率是很低的，特別是在線性表比較大的情況下更為突出。 下面是線性表在順序存儲(chǔ)結(jié)構(gòu)下插入算法的C語(yǔ)言描述。30void insl(ET v,int m,int *n,int i, ET b) /*順序表的插入*/* v為順序表空間,b為插入的元素 */*m為順序表空間容量,n為指向線性表長(zhǎng)度的指針, i為插入元素的序號(hào)*/ if (*n=m) return； /*順序

11、表空間已滿,不能插入,返回*/ if (i*n1) i=*n+1； /*在線性表的最后插入*/ if (i1) i=1； /*在線性表的第1個(gè)元素之前插入*/ for (j=*n；j=i；j ) /*插入位置后的元素依次后移一個(gè)位置*/ vj=vj1； vi1=b； *n= *n+1； /*插入元素b, 線性表長(zhǎng)度加1 */31 2順序表的刪除運(yùn)算32 設(shè)長(zhǎng)度為n的線性表為： 現(xiàn)要?jiǎng)h除第i個(gè)元素，刪除后得到長(zhǎng)度為n 1的線性表為： 則刪除前后的兩線性表中的元素滿足如下關(guān)系：則刪除前后的兩線性表中的元素滿足如下關(guān)系： 33 在線性表順序存儲(chǔ)的情況下，要?jiǎng)h除一個(gè)元素，由于數(shù)據(jù)元素的移動(dòng)而消耗較多的

12、處理時(shí)間，其效率也是很低的，特別是在線性表比較大的情況下更為突出。 下面是線性表在順序存儲(chǔ)結(jié)構(gòu)下刪除算法的C語(yǔ)言描述。34void desl(ET v, int m, int *n,int i) /*順序表的刪除*/*v順序表空間*/*m為順序表空間容量,n為指向線性表長(zhǎng)度的指針,i為刪除元素的序號(hào)*/ if (*n=0) return； /*線性表為空,下溢錯(cuò)誤,返回*/ if (i1) | | (i*n) return; /*線性表中沒(méi)有該下標(biāo)的元素,返回*/ for (j=i；j=*n1；j+) vj1=vj；/*第i后的元素依次前移一個(gè)位置*/ *n= *n1； /*線性表長(zhǎng)度減1*/

13、 return；353. 線性表線性表C語(yǔ)言描述語(yǔ)言描述const int maxsize=maxlen；struct sequenlist Elemtype amaxsize; int len; ；表示線性表（a1，a2， .,a an）len表示線性表的實(shí)際長(zhǎng)度maxlen表示線性表允許的最大長(zhǎng)度364.線性表基本運(yùn)算插入線性表基本運(yùn)算插入int Insert_list(int i, Element x, Element s, int *n_pointer, int M) int j,n; n=*n_pointer; if (n=M)|(in+1) return (0); n+; *n_p

14、ointer=n; return (1); 算法描述： 在長(zhǎng)度為n的線性表中第i個(gè)元素后插入新元素xMM 為線性表最大長(zhǎng)度；為線性表最大長(zhǎng)度；n_pointern_pointer存放線性表已有存放線性表已有的記錄數(shù)的記錄數(shù)n n為線性表實(shí)為線性表實(shí)際長(zhǎng)度際長(zhǎng)度從從i i開(kāi)始的元素后移開(kāi)始的元素后移注意“上溢”錯(cuò)誤37 0 1 2 3 i-1 i i+1 n maxsize-1 a1 a2 a3 ai-1 x ai an-1 an 0 1 2 3 i-1 i i+1 n maxsize-1 a1 a2 a3 ai-1 ai ai+1 an 序號(hào) 內(nèi)容 序 號(hào) 內(nèi)容 插入前 插入后 385. 線性

15、表基本運(yùn)算刪除線性表基本運(yùn)算刪除int Delete_list(int i, int s , int *n_pointer) int j,n; n=*n_pointer; if (in) return (0); for (j=i+1; j=n; j+) sj-1=sj; n-; *n_pointer=n; return (1); 算法描述 在長(zhǎng)度為n的線性表中刪除第i個(gè)元素n_pointern_pointer存放線性表已有存放線性表已有的記錄數(shù)的記錄數(shù)n n為線性表實(shí)為線性表實(shí)際長(zhǎng)度際長(zhǎng)度從從i i開(kāi)始的元素前移開(kāi)始的元素前移注意“下溢”錯(cuò)誤396. 線性表運(yùn)算線性表運(yùn)算查找查找在線性表中查找

16、關(guān)鍵字為在線性表中查找關(guān)鍵字為x x的元素，并返回位置：的元素，并返回位置： int Locate_list(int s, int n, int x) int i; for (i=1; itop=0; 棧判空IntStackEmpty(SQSTACK stack) if (stack.top=0) return (1); return (0);465. 棧運(yùn)算棧運(yùn)算入棧入棧 pushint Push(SQSTACK *stack, int x) if (stack-top=M-1) return (1); stack-top+; stack-elemstack-top=x; return (0

17、);注意棧上溢修改棧頂指針數(shù)據(jù)入棧476. 棧運(yùn)算棧運(yùn)算出棧出棧 popint Pop(SQSTACK *stack, int *x) if (StackEmpty(*stack) return (1); *x=stack-elemstack-top; stack-top-; return (0);先判?？招薷臈ｍ斨羔様?shù)據(jù)出棧487. 棧運(yùn)算棧運(yùn)算讀棧頂（讀棧頂（top）int GetTop(SQSTACK stack, int *x) if (stack-top=-1) return (1); *x=stack-elemstack-top; /stack-top-; return (0);不

18、出棧！ 8 棧的應(yīng)用棧的應(yīng)用1兩個(gè)例子兩個(gè)例子例：火車(chē)出庫(kù)轉(zhuǎn)軌調(diào)度例：火車(chē)出庫(kù)轉(zhuǎn)軌調(diào)度,1,2,3,4四個(gè)車(chē)次不可能出四個(gè)車(chē)次不可能出站的順序是：站的順序是：(a)4321(b)3241(c)1432(d)3124 例 有一字符串，次序?yàn)?*-b+a/c?2，利用棧排出將次序改為3b-*ac2?/+的操作步驟，可用x代表掃描該字符串過(guò)程中取一字符進(jìn)棧的操作，用s代表從棧中取出一字符加入到新字符串尾的出棧操作。例如，通過(guò)操作步驟xxsxss,可將字符串ABC變成BCA。512.2.3 隊(duì)列及其運(yùn)算521. 隊(duì)列（隊(duì)列（queue） ：一種特殊的線性表，遵守FIFO(First In First

19、Out)規(guī)則。隊(duì)列的數(shù)據(jù)元素總是從表末尾加入，從表頭取出。 隊(duì)列的物理存儲(chǔ)可以用順序存儲(chǔ)結(jié)構(gòu)，也可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)尾指針隊(duì)頭指針532. 隊(duì)列操作隊(duì)列操作ABCDfrontrearBCDfrontrearBCDEfrontrear一個(gè)隊(duì)列取出元素加入元素地址增加543. 3. 隊(duì)列實(shí)際應(yīng)用循環(huán)隊(duì)列隊(duì)列實(shí)際應(yīng)用循環(huán)隊(duì)列隊(duì)尾指針rear指向隊(duì)尾元素隊(duì)頭指針指向隊(duì)頭元素的前一個(gè)元素位置553. 3. 循環(huán)隊(duì)列的插入與刪除循環(huán)隊(duì)列的插入與刪除87 F6 E5 D4 C3 B2 A1frontrear8 X7 F6 E5 D4 C3 B2 A1 Yfrontrear8 X 7 F6 E5 D4 C3 B

20、21 Y frontrear一個(gè)隊(duì)列加入X,Y元素取出元素564. 4. 循環(huán)隊(duì)列的空滿狀態(tài)循環(huán)隊(duì)列的空滿狀態(tài)隊(duì)列空隊(duì)列滿都是rear= front！隊(duì)列判空標(biāo)志S575. 隊(duì)列結(jié)構(gòu)的隊(duì)列結(jié)構(gòu)的C語(yǔ)言描述語(yǔ)言描述#define MAXSIZE 50typedef struct elemtype elemMAXSIZE; int front； int rear； int s; SQQUEUE;586. 隊(duì)列的運(yùn)算隊(duì)列的運(yùn)算初始化與判空初始化與判空 初始化 判空void InitQueue (SQQUEUE *q) q-front = ; q-rear = ;q-s = 0；int QueueIsEmpty (SQQUEUE q) if (q.front=q.rear)&s=0 return (1); return (0);597. 隊(duì)列運(yùn)算隊(duì)列運(yùn)算入隊(duì)入隊(duì) 入隊(duì)運(yùn)算；尾指針入隊(duì)運(yùn)算；尾指針rear