第四章 數(shù)據(jù)結(jié)構(gòu)

1、13第第1章章 緒論緒論第第2章章 線性表線性表第第3章章 棧和隊列棧和隊列 第第4章章 串串第第5章章 數(shù)組和廣義表數(shù)組和廣義表第第6 6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖第第8章章 查找查找第第9章章 排序排序目目 錄錄45（a1, a2, ai-1，ai, ai1 ，, an）2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示n=0時稱為時稱為數(shù)據(jù)元素數(shù)據(jù)元素線性起點(diǎn)線性起點(diǎn)ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總為元素總個數(shù)，即表個數(shù)，即表

2、長。長?？毡砜毡砭€性終點(diǎn)線性終點(diǎn)6 （ A, B, C, D, , Z）學(xué)號學(xué)號姓名姓名性別性別年齡年齡班級班級012003010622陳建武陳建武男男 192003級電信級電信0301班班012003010704趙玉鳳趙玉鳳女女 182003級電信級電信0302班班012003010813王王 澤澤男男 192003級電信級電信0303班班012003010906薛薛 荃荃男男 192003級電信級電信0304班班012003011018王 春男 19 192003級電信級電信0305班班： ：例例2 分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析：分析：數(shù)據(jù)元素都是同類型

3、（數(shù)據(jù)元素都是同類型（記錄記錄），元素間關(guān)系是線性的。），元素間關(guān)系是線性的。分析：分析： 數(shù)據(jù)元素都是同類型（數(shù)據(jù)元素都是同類型（字母字母），）， 元素間關(guān)系是線性的。元素間關(guān)系是線性的。例例1 分析分析26 個英文字母組成的英文表是什么結(jié)構(gòu)。個英文字母組成的英文表是什么結(jié)構(gòu)。返回本章目錄返回本章目錄72.2 線性表的順序表示和運(yùn)算線性表的順序表示和運(yùn)算2.2.1 順序表的表示順序表的表示2.2.2 順序表的運(yùn)算順序表的運(yùn)算2.2.3 順序表的運(yùn)算效率分析順序表的運(yùn)算效率分析返回本章目錄返回本章目錄82.2.1 順序表的表示順序表的表示用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次

4、存儲線性表的元素。存儲線性表的元素。把邏輯上相鄰的數(shù)據(jù)元素存儲在物把邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。理上相鄰的存儲單元中的存儲結(jié)構(gòu)。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或順序映像?；蝽樞蛴诚瘛ｍ樞虼鎯Χx：順序存儲定義：順序存儲方法：順序存儲方法：特點(diǎn)：特點(diǎn)：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰可以利用可以利用數(shù)組數(shù)組VnVn來實(shí)現(xiàn)來實(shí)現(xiàn)注意：在注意：在C C語言中數(shù)組的下標(biāo)是從語言中數(shù)組的下標(biāo)是從0 0開始，即：開始，即： VnVn的有效范圍是從的有效范圍是從 V0V0Vn-1Vn-191. 邏輯上相鄰的數(shù)據(jù)

5、元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其他元若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組VnVn的的下標(biāo)下標(biāo)）。）。設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為LOC(a1)（稱為稱為首地址首地址），），設(shè)每個元素占用存儲空間（地址長度）為設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對上述公式的解釋如圖所示對上述公式的解釋如圖所示線性表順序存儲特點(diǎn)：線

6、性表順序存儲特點(diǎn)：10a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L L線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(jié)構(gòu)示意圖11設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個數(shù)，每個數(shù)組元素用相鄰的組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素設(shè)存儲數(shù)組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是，則則 的第一個字

7、節(jié)的地址是多少？的第一個字節(jié)的地址是多少？113但此題要注意下標(biāo)起點(diǎn)略有不同：但此題要注意下標(biāo)起點(diǎn)略有不同：LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址計算通式為：已知地址計算通式為：LOC(ai) = LOC(a1) + L *（i-1）例例1 112 char V30;void build() /*字母線性表的生成，即字母線性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 核心語句：核心語句：1)1)用數(shù)組用數(shù)組V來存放來存放26個英文字母組成的線性表（個英文字母組成的線性表（a，b，c

8、，z），寫出在順序結(jié)構(gòu)上），寫出在順序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語言語言程序。程序。2.2.2 2.2.2 順序表的運(yùn)算（或操作）順序表的運(yùn)算（或操作）13void main(void) /*主函數(shù)主函數(shù)，字母線性表的，字母線性表的生成和輸出生成和輸出*/ n=26; /* n n是表長，是數(shù)據(jù)元素的個數(shù)，而不是是表長，是數(shù)據(jù)元素的個數(shù)，而不是V V的的 實(shí)際下標(biāo)實(shí)際下標(biāo)*/build( );display( );void display( ) /*字母線性表的顯示，即字母線性表的顯示，即讀表操作讀表操作*/ int i;for( i=0; i=i; j )aj+1=a j ;

9、a i =x; n+;/ / 元素后移一個位置元素后移一個位置/ / 插入插入x x / / 表長加表長加1 1 核核心心語語句：句：3)3)插入插入16實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟：將第將第i+1 至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置；表長減表長減1。注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?應(yīng)當(dāng)有應(yīng)當(dāng)有1in 或或 i=1, n刪除線性表的第刪除線性表的第i i個位置上的元素個位置上的元素for ( j=i+1; j=n; j+ )aj-1=aj; n-;/ / 元素前移一個位置元素前移一個位置/ / 表長減表長減1 1 核心語句：核心語

10、句：4)4)刪除刪除順序表插入和刪除的完整程序請同學(xué)們自編。順序表插入和刪除的完整程序請同學(xué)們自編。172.2.3 順序表的運(yùn)算效率分析順序表的運(yùn)算效率分析在插入或刪除運(yùn)算中在插入或刪除運(yùn)算中,算法時間主要耗費(fèi)在算法時間主要耗費(fèi)在移動元素移動元素的操作上，因此計算時間復(fù)雜度的大小取決于移動元素的操作上，因此計算時間復(fù)雜度的大小取決于移動元素的個數(shù)的個數(shù),而移動元素的個數(shù)取決于插入或刪除元素的位置而移動元素的個數(shù)取決于插入或刪除元素的位置.思考：思考：若插入在尾結(jié)點(diǎn)之后，則根本無需移動（特別快）；若插入在尾結(jié)點(diǎn)之后，則根本無需移動（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；若

11、插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；討論討論1：若在長度為若在長度為 n 的線性表的第的線性表的第 i 位前位前 插入插入一個元素，一個元素，則向后移動元素的次數(shù)則向后移動元素的次數(shù)f(n)為為:f(n) = n i + 1時間效率分析時間效率分析:注意注意順序表在存儲結(jié)構(gòu)中是均勻有序的順序表在存儲結(jié)構(gòu)中是均勻有序的, ,所以只要知道順?biāo)灾灰理樞虮淼牡刂泛蛿?shù)據(jù)元素的長度和序號序表的地址和數(shù)據(jù)元素的長度和序號, ,就能知道每個就能知道每個數(shù)據(jù)元素的實(shí)際地址數(shù)據(jù)元素的實(shí)際地址. .因此因此, ,對表內(nèi)數(shù)據(jù)元素進(jìn)行訪對表內(nèi)數(shù)據(jù)元素進(jìn)行訪問、修改運(yùn)算的速度快問、修改運(yùn)算的速度快.

12、.所以順序表多用于查找頻繁、所以順序表多用于查找頻繁、很少增刪的場合很少增刪的場合, ,例如工程手冊中的數(shù)據(jù)表例如工程手冊中的數(shù)據(jù)表. .18鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)本節(jié)小結(jié)本節(jié)小結(jié)線性表線性表順序存儲結(jié)構(gòu)特點(diǎn)順序存儲結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個元素：邏輯關(guān)系上相鄰的兩個元素在物理存儲位置上也相鄰；在物理存儲位置上也相鄰；優(yōu)點(diǎn)：優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，查找方便快捷；可以隨機(jī)存取表中任一元素，查找方便快捷；缺點(diǎn)：缺點(diǎn)：在插入或刪除某一元素時，需要移動大量元素。在插入或刪除某一元素時，需要移動大量元素。解決問題的思路：解決問題的思路：改用另一種線性存儲方式：改用另一種線性存儲方式：返回本

13、章目錄返回本章目錄192.3 線性表的鏈?zhǔn)奖硎竞瓦\(yùn)算線性表的鏈?zhǔn)奖硎竞瓦\(yùn)算2.3.1 鏈表的表示鏈表的表示2.3.2 鏈表的運(yùn)算鏈表的運(yùn)算2.3.3 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析返回本章目錄返回本章目錄20鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)：鏈?zhǔn)酱鎯Y(jié)構(gòu)特點(diǎn)：其結(jié)點(diǎn)在存儲器中的位置是其結(jié)點(diǎn)在存儲器中的位置是隨意隨意的，的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。如何實(shí)現(xiàn)？通過來實(shí)現(xiàn)！讓每個存儲結(jié)點(diǎn)都包含兩部分：讓每個存儲結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域數(shù)據(jù)域和和指針域指針域指針指針指針指針指針指針或或樣式樣式:數(shù)據(jù)域：數(shù)據(jù)域：存儲存儲元素數(shù)值數(shù)據(jù)元素數(shù)值數(shù)據(jù)指針域：指針域：存儲直接后繼或存儲直接后繼或者直接前

14、驅(qū)的存儲位置者直接前驅(qū)的存儲位置2.3.1 鏈表的表示鏈表的表示21例：請畫出例：請畫出26 26 個英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。個英文字母表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下：該字母表在內(nèi)存中鏈?zhǔn)酱娣诺臉邮脚e例如下： 解：解：該字母表的邏輯結(jié)構(gòu)為：該字母表的邏輯結(jié)構(gòu)為：（ a, b, ,y, za, b, ,y, z）鏈表存放示意圖如下：鏈表存放示意圖如下： a1heada2/an 討論討論1 ：每個存儲結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和：每個存儲結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和 。討論討論2：在單鏈表中，除了在單鏈表中，除了首元結(jié)點(diǎn)首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲位置外，任一結(jié)點(diǎn)的存儲位置

15、由由 指示。指示。 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指針域指針域(鏈域鏈域)221）結(jié)點(diǎn)：）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；數(shù)據(jù)元素的存儲映像。由數(shù)據(jù)域和指針域兩部分組成；2）鏈表：）鏈表： n n 個結(jié)點(diǎn)由個結(jié)點(diǎn)由指針鏈指針鏈組成一個鏈表。它是線性表的鏈?zhǔn)浇M成一個鏈表。它是線性表的鏈?zhǔn)酱鎯τ诚翊鎯τ诚?，稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。3）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表）單鏈表、雙鏈表、多鏈表、循環(huán)鏈表： 結(jié)點(diǎn)只有一個指針域的鏈表，稱為結(jié)點(diǎn)只有一個指針域的鏈表，稱為單鏈表單鏈表或或線性鏈表線性鏈表；有兩個指針域的鏈表，稱為有兩個指針域的

16、鏈表，稱為雙鏈表雙鏈表；有多個指針域的鏈表，稱為有多個指針域的鏈表，稱為多鏈表多鏈表；首尾相接的鏈表稱為首尾相接的鏈表稱為循環(huán)鏈表循環(huán)鏈表。a1heada2an循環(huán)鏈表循環(huán)鏈表示圖：示圖：(2) 與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語：與鏈?zhǔn)酱鎯τ嘘P(guān)的術(shù)語：234）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別）頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)的區(qū)別頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)a1heada2infoan頭指針頭指針是指向鏈表中第一個結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自侵赶蜴湵碇械谝粋€結(jié)點(diǎn)（或?yàn)轭^結(jié)點(diǎn)、或?yàn)槭自Y(jié)點(diǎn)）的指針；結(jié)點(diǎn)）的指針；頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前是在鏈表的首元結(jié)點(diǎn)之前附設(shè)附設(shè)的一個結(jié)點(diǎn)；數(shù)據(jù)域的一個結(jié)點(diǎn)；

17、數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息，它不計入表長度。內(nèi)只放空表標(biāo)志和表長等信息，它不計入表長度。首元結(jié)點(diǎn)首元結(jié)點(diǎn)是指鏈表中存儲線性表第一個數(shù)據(jù)元素是指鏈表中存儲線性表第一個數(shù)據(jù)元素a a1 1的結(jié)點(diǎn)。的結(jié)點(diǎn)。 示意圖如下：示意圖如下：24 對于指向結(jié)構(gòu)類型的指針變量，可說明為：對于指向結(jié)構(gòu)類型的指針變量，可說明為： *p, *q; /或用或用 struct *p , *q; /注：上面已經(jīng)定義了注：上面已經(jīng)定義了node為用戶自定義的為用戶自定義的lilylily類型。類型。 類型定義和變量說明可以合寫為：類型定義和變量說明可以合寫為： lily /lilylily是自定義結(jié)構(gòu)類型名稱是自定義結(jié)

18、構(gòu)類型名稱 char data; /定義數(shù)據(jù)域的變量名及其類型定義數(shù)據(jù)域的變量名及其類型 lily *next; /定義指針域的變量名及其類型定義指針域的變量名及其類型node，*pointer; /nodenode是是lilylily結(jié)構(gòu)類型的類型替代結(jié)構(gòu)類型的類型替代, , * *pointerpointer是指針型的是指針型的lilylily結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型結(jié)構(gòu)類型的替代，也是數(shù)據(jù)類型* */ /附：附： 補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的補(bǔ)充結(jié)構(gòu)數(shù)據(jù)類型的C表示法表示法如何具體編程來建立如何具體編程來建立和訪問鏈表？和訪問鏈表？鏈表的實(shí)現(xiàn)鏈表的實(shí)現(xiàn)252.3.2 鏈表的運(yùn)算鏈表的運(yùn)算（1

19、1） 單鏈表的建立和輸出單鏈表的建立和輸出（2 2） 單鏈表的修改單鏈表的修改（3 3） 單鏈表的插入單鏈表的插入（4 4） 單鏈表的刪除單鏈表的刪除26（1） 單鏈表的建立和輸出單鏈表的建立和輸出例：用例：用單鏈表單鏈表結(jié)構(gòu)來存放結(jié)構(gòu)來存放26個英文字母組成的線個英文字母組成的線性表（性表（a，b，c，z）,請寫出請寫出C語言程序。語言程序。實(shí)現(xiàn)思路：實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個結(jié)點(diǎn)開辟存儲先開辟頭指針，然后陸續(xù)為每個結(jié)點(diǎn)開辟存儲空間并及時賦值，后繼結(jié)點(diǎn)的地址要空間并及時賦值，后繼結(jié)點(diǎn)的地址要提前提前送給前面的指針。送給前面的指針。先挖先挖“坑坑”, ,后種后種“蘿蘿卜卜”！27t

20、ypedef struct nodechar data; struct node *next;node; node *p,*q,*head; /一般需要一般需要3 3個指針變量個指針變量int n ; / / 數(shù)據(jù)元素的個數(shù)數(shù)據(jù)元素的個數(shù)int m=sizeof(node); / /* *結(jié)構(gòu)類型定義好之后，每個變量結(jié)構(gòu)類型定義好之后，每個變量的長度就固定了，的長度就固定了，m m求一次即可求一次即可* */ /將全局變量及函數(shù)提前說明：將全局變量及函數(shù)提前說明：28新手特別容易忘記！新手特別容易忘記！ int i;head=(node*)malloc(m); /m=sizeof(node)

21、前面已求出前面已求出p=head;for( i=1; idata=i+a-1; / 第一個結(jié)點(diǎn)值為字符第一個結(jié)點(diǎn)值為字符ap-next=(node*)malloc(m); /為后繼結(jié)點(diǎn)為后繼結(jié)點(diǎn)“挖坑挖坑”！p=p-next； /讓指針變量讓指針變量P指向后一個結(jié)點(diǎn)指向后一個結(jié)點(diǎn)p-data=i+a-1; /最后一個元素要單獨(dú)處理最后一個元素要單獨(dú)處理p-next=NULL ; / /單鏈表尾結(jié)點(diǎn)的指針域要置空！單鏈表尾結(jié)點(diǎn)的指針域要置空！void build( ) /字母鏈表的生成字母鏈表的生成。要一個個慢慢鏈入要一個個慢慢鏈入29p=head;while (p) /當(dāng)指針不空時循環(huán)當(dāng)指針不

22、空時循環(huán) printf(%c,p-data); p=p-next; /讓指針不斷讓指針不斷“順藤摸瓜順藤摸瓜” 討論：要統(tǒng)計鏈表中數(shù)據(jù)元素的個數(shù)，該如何改寫？討論：要統(tǒng)計鏈表中數(shù)據(jù)元素的個數(shù)，該如何改寫？ sum+;sum+;sum=0;sum=0;void display() /*字母鏈表的輸出字母鏈表的輸出*/30（2） 單鏈表的修改單鏈表的修改(或讀?。┗蜃x?。┧悸罚核悸罚阂薷牡谝薷牡趇個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)個數(shù)據(jù)元素，必須從頭指針起一直找到該結(jié)點(diǎn)的指針點(diǎn)的指針p，然后才能執(zhí)行，然后才能執(zhí)行p-data=new_value 。修改修改第第i i個數(shù)據(jù)元素的操作函數(shù)可寫

23、為：個數(shù)據(jù)元素的操作函數(shù)可寫為：GetElem_L(LinkList L, int i, ElemType &e)p=L-next; int j=1; /帶頭結(jié)點(diǎn)的鏈表帶頭結(jié)點(diǎn)的鏈表while(p&jnext; +j; /p非空且非空且ji ) return ERROR; /p為空或?yàn)榭栈騤i p-data =e; /若是讀取則為：若是讀取則為：e=p-data; return OK;/ GetElem_L缺點(diǎn)：缺點(diǎn)：想尋找單鏈表中第想尋找單鏈表中第i i個元素，只能從頭指針開始逐一個元素，只能從頭指針開始逐一查詢（查詢（順藤摸瓜順藤摸瓜），無法隨機(jī)存?。?，無法隨機(jī)存取 。31

24、在鏈表中插入一個元素在鏈表中插入一個元素X X 的示意圖如下：的示意圖如下：X Xsabp鏈表插入的核心語句：鏈表插入的核心語句：p-nexts-nextX X 結(jié)點(diǎn)的生成方式：結(jié)點(diǎn)的生成方式：s=(node*)malloc(m);s-data=X X ;s-next= ?bapX X （3） 單鏈表的插入單鏈表的插入32在鏈表中刪除某元素在鏈表中刪除某元素b b的示意圖如下：的示意圖如下：c a bp刪除動作的核心語句刪除動作的核心語句（要借助輔助指針變量（要借助輔助指針變量q q）：）：q = p-next; /首先保存首先保存b b的指針，靠它才能找的指針，靠它才能找c c；p-next

25、=q-next; /將將a a、c c兩結(jié)點(diǎn)相連，淘汰兩結(jié)點(diǎn)相連，淘汰b b結(jié)點(diǎn)；結(jié)點(diǎn)；free(q) ； /徹底釋放徹底釋放b b結(jié)點(diǎn)空間結(jié)點(diǎn)空間p-next(p-next) - nextq（4） 單鏈表的刪除單鏈表的刪除332.3.3 鏈表的運(yùn)算效率分析鏈表的運(yùn)算效率分析（1） 查找查找 因線性鏈表只能順序存取，即在查找時要從頭指針找起，因線性鏈表只能順序存取，即在查找時要從頭指針找起，查找的時間復(fù)雜度查找的時間復(fù)雜度遠(yuǎn)遠(yuǎn)大于順序表遠(yuǎn)遠(yuǎn)大于順序表。時間效率分析時間效率分析（2） 插入和刪除插入和刪除 因線性鏈表不需要移動元素，只要修改指針，一般情況下時因線性鏈表不需要移動元素，只要修改指針

26、，一般情況下時間復(fù)雜度間復(fù)雜度 遠(yuǎn)遠(yuǎn)小于順序表遠(yuǎn)遠(yuǎn)小于順序表。34結(jié) 束35第第4 4章章 樹和二叉樹樹和二叉樹（Tree & Binary Tree）4.1 樹的基本概念樹的基本概念4.2 二叉樹二叉樹4.3 遍歷二叉樹遍歷二叉樹特點(diǎn)：特點(diǎn)：非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個非線性結(jié)構(gòu)，一個直接前驅(qū)，但可能有多個直接后繼。直接后繼。（一對多或（一對多或1:n1:n）364.14.1 樹的基本概念4.1.1 樹的定義樹的定義4.1.2 若干術(shù)語若干術(shù)語4.1.3 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)4.1.4 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4.1.5 樹的運(yùn)算樹的運(yùn)算37注注1：過去許多書籍中都定義樹為過去許多書籍

27、中都定義樹為n1，曾經(jīng)有，曾經(jīng)有“空樹不是空樹不是樹樹”的說法，但現(xiàn)在樹的定義已修改。的說法，但現(xiàn)在樹的定義已修改。注注2：樹的定義具有樹的定義具有遞歸性遞歸性，即，即“樹中還有樹樹中還有樹”。由一個或多個由一個或多個( (n0n0) )結(jié)點(diǎn)組成的有限集合結(jié)點(diǎn)組成的有限集合T T，有且僅有，有且僅有一一個結(jié)點(diǎn)稱為根個結(jié)點(diǎn)稱為根（rootroot），），當(dāng)當(dāng)n1n1時，其余的結(jié)點(diǎn)分為時，其余的結(jié)點(diǎn)分為m m(m0)(m0)個個互不相交互不相交的有限集合的有限集合T1,T2T1,T2，TmTm。每個集合本身又是棵樹，。每個集合本身又是棵樹，被稱作這個根的被稱作這個根的子樹子樹 。38結(jié)點(diǎn)的直接前驅(qū)

28、結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的直接后繼同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）同一雙親下的同層結(jié)點(diǎn)（孩子之間互稱兄弟）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即雙親位于同一層的結(jié)點(diǎn)（但并非同一雙親）即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即從根到該結(jié)點(diǎn)所經(jīng)分支的所有結(jié)點(diǎn)即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)即該結(jié)點(diǎn)下層子樹中的任一結(jié)點(diǎn)ABCGEIDHFJFLK 根根 葉子葉子 森林森林有序樹有序樹無序樹無序樹即根結(jié)點(diǎn)即根結(jié)點(diǎn)(沒有前驅(qū)沒有前驅(qū))即終端結(jié)點(diǎn)即終端結(jié)點(diǎn)(沒有后繼沒有后繼)指指m棵不相交的樹的集棵不相交的樹的集合合(例如刪除例如刪除A后的子樹個數(shù)后的子樹個數(shù))雙親雙親孩子孩子兄弟兄弟堂兄弟堂兄弟祖

29、先祖先子孫子孫結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹從左至右有序，不能互換（左為第一）結(jié)點(diǎn)各子樹可互換位置。結(jié)點(diǎn)各子樹可互換位置。39即樹的數(shù)據(jù)元素即樹的數(shù)據(jù)元素結(jié)點(diǎn)的孩子數(shù)量結(jié)點(diǎn)的孩子數(shù)量結(jié)點(diǎn)結(jié)點(diǎn)結(jié)點(diǎn)的度結(jié)點(diǎn)的度結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次終端結(jié)點(diǎn)終端結(jié)點(diǎn)分支結(jié)點(diǎn)分支結(jié)點(diǎn)樹的度樹的度樹的深度樹的深度(或高度或高度)ABCGEIDHFJFLK從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）從根到該結(jié)點(diǎn)的層數(shù)（根結(jié)點(diǎn)算第一層）即度為即度為0的結(jié)點(diǎn)，即葉子的結(jié)點(diǎn)，即葉子即度不為即度不為0的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）的結(jié)點(diǎn)（也稱為內(nèi)部結(jié)點(diǎn)）所有結(jié)點(diǎn)度中的最大值（所有結(jié)點(diǎn)度中的最大值（Max各結(jié)點(diǎn)的度各結(jié)點(diǎn)的

30、度）指所有結(jié)點(diǎn)中最大的層數(shù)（指所有結(jié)點(diǎn)中最大的層數(shù)（Max各結(jié)點(diǎn)的層次各結(jié)點(diǎn)的層次）問：問：右上圖中的結(jié)點(diǎn)數(shù)右上圖中的結(jié)點(diǎn)數(shù) ；樹的度；樹的度 ；樹的深度；樹的深度13133 34 4（有幾個直接后繼就是幾度，亦稱（有幾個直接后繼就是幾度，亦稱“次數(shù)次數(shù)”）40一對多（一對多（1:n1:n），），有多個直接后繼（如家譜有多個直接后繼（如家譜樹、目錄樹等等），但只有一個根結(jié)點(diǎn)，樹、目錄樹等等），但只有一個根結(jié)點(diǎn)，且且子樹之間互不相交。子樹之間互不相交。 討論討論1：樹是非線性結(jié)構(gòu)，該怎樣存儲？樹是非線性結(jié)構(gòu)，該怎樣存儲？特點(diǎn)：特點(diǎn)：仍然有順序存儲、鏈?zhǔn)酱鎯Φ确绞健Ｈ匀挥许樞虼鎯?、鏈?zhǔn)酱鎯Φ确绞健?/p>

31、 41討論討論3：樹的樹的鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Ψ桨笐?yīng)該怎樣制定？方案應(yīng)該怎樣制定？復(fù)原困難復(fù)原困難可用多重鏈表：可用多重鏈表：一個前趨指針，一個前趨指針，n n個后繼指針。個后繼指針。 細(xì)節(jié)問題：細(xì)節(jié)問題： 樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計？樹中結(jié)點(diǎn)的結(jié)構(gòu)類型樣式該如何設(shè)計？ 即應(yīng)該設(shè)計成即應(yīng)該設(shè)計成“等長等長”還是還是“不等長不等長”？ 缺點(diǎn)：缺點(diǎn)： 等長結(jié)構(gòu)太浪費(fèi)（每個結(jié)點(diǎn)的度不一定相同）；等長結(jié)構(gòu)太浪費(fèi)（每個結(jié)點(diǎn)的度不一定相同）； 不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。不等長結(jié)構(gòu)太復(fù)雜（要定義好多種結(jié)構(gòu)類型）。先研究最簡單、最有規(guī)律的樹，然先研究最簡單、最有規(guī)律的樹，然后設(shè)法把一般的樹轉(zhuǎn)

32、化為簡單樹。后設(shè)法把一般的樹轉(zhuǎn)化為簡單樹?？梢?guī)定為：可規(guī)定為： 從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。從上至下、從左至右將樹的結(jié)點(diǎn)依次存入內(nèi)存。重大缺陷：重大缺陷：解決思路：解決思路：不能唯一復(fù)原就沒有實(shí)用價值！不能唯一復(fù)原就沒有實(shí)用價值！討論討論2：樹的樹的順序存儲順序存儲方案應(yīng)該怎樣制定？方案應(yīng)該怎樣制定？42多叉樹轉(zhuǎn)為多叉樹轉(zhuǎn)為了二叉樹了二叉樹轉(zhuǎn)換的步驟: 1. 保留每個結(jié)點(diǎn)與最左邊孩子的邊，去掉其余的邊。 2. 連接每個結(jié)點(diǎn)與其原相鄰兄弟結(jié)點(diǎn)的邊。 3. 以樹根結(jié)點(diǎn)為軸心，將整棵樹順時針旋轉(zhuǎn)45度，即 可得到轉(zhuǎn)換后的二叉樹。43要明確：要明確：1. 普通樹（即多叉樹）若不轉(zhuǎn)化為二叉

33、樹，則運(yùn)算很難實(shí)現(xiàn)。普通樹（即多叉樹）若不轉(zhuǎn)化為二叉樹，則運(yùn)算很難實(shí)現(xiàn)。2. 二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序等，二叉樹的運(yùn)算仍然是插入、刪除、修改、查找、排序等，但這些操作必須建立在但這些操作必須建立在對樹結(jié)點(diǎn)能夠?qū)浣Y(jié)點(diǎn)能夠“遍歷遍歷”的基礎(chǔ)上！的基礎(chǔ)上！444.2 二叉樹二叉樹為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個 “ “叉叉” ” 的樹？的樹？二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；二叉樹的結(jié)構(gòu)最簡單，規(guī)律性最強(qiáng)；可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，可以證明，所有樹都能轉(zhuǎn)為唯一對應(yīng)的二叉樹，不失一般性。不失一般性。4.2.1 二叉樹的定義二叉樹的定

34、義4.2.2 二叉樹的類型二叉樹的類型4.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)45定義：定義：是是n（n0）個結(jié)點(diǎn)的有限集合，由一個根結(jié)點(diǎn)以及兩棵）個結(jié)點(diǎn)的有限集合，由一個根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為互不相交的、分別稱為左子樹和右子樹左子樹和右子樹的二叉樹組成的二叉樹組成 。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 一對二（一對二（1:2） 基本特征基本特征: 每個結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于每個結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2 2的結(jié)點(diǎn)）；的結(jié)點(diǎn)）； 左子樹和右子樹左子樹和右子樹次序不能顛倒次序不能顛倒。 基本形態(tài)：基本形態(tài)：46順序二叉樹：順序二叉樹：深度為深度為k 的的、有有n個結(jié)點(diǎn)個結(jié)

35、點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點(diǎn)都與深度為深度為k 的滿二叉樹中編號從的滿二叉樹中編號從1至至n的結(jié)的結(jié)點(diǎn)一一對應(yīng)。點(diǎn)一一對應(yīng)。AOBCGEKDJFIHNML深度為深度為4 4的滿二叉樹的滿二叉樹順序二叉樹順序二叉樹ABCGEIDHFJ為何要研究為何要研究這順序二叉這順序二叉樹形式？樹形式？滿二叉樹：滿二叉樹：一棵深度為一棵深度為k 且有且有2k -1個結(jié)點(diǎn)的二叉樹。個結(jié)點(diǎn)的二叉樹。 （特點(diǎn)：每層都（特點(diǎn)：每層都“充滿充滿”了結(jié)點(diǎn)）了結(jié)點(diǎn)）完全二叉樹：完全二叉樹：結(jié)點(diǎn)的度數(shù)或者為結(jié)點(diǎn)的度數(shù)或者為0、或、或者為者為2的二叉樹的二叉樹 完全二叉樹完全二叉樹ABCE

36、IDH474.2.3 4.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu)按二叉樹的結(jié)點(diǎn)按二叉樹的結(jié)點(diǎn)“自上而自上而下、從左至右下、從左至右”編號，用編號，用一組連續(xù)的存儲單元存儲。一組連續(xù)的存儲單元存儲。123456789問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？問：順序存儲后能否復(fù)原成唯一對應(yīng)的二叉樹形狀？答：答：若是順序若是順序/ /滿二叉樹則可以做到唯一復(fù)原。滿二叉樹則可以做到唯一復(fù)原。 而且有規(guī)律：下標(biāo)值為而且有規(guī)律：下標(biāo)值為i i的雙親，其左孩子的下標(biāo)值必為的雙親，其左孩子的下標(biāo)值必為2i2i，其右孩子的下標(biāo)值必為，其右孩子的下標(biāo)值必為2i2i1 1 例如，對應(yīng)例如，對應(yīng)22的兩個孩子必為的兩個孩子必為44和和5,5,即即B B的左孩子必的左孩子必是是D,D,右孩子必為右孩子必為E E。48討論：討論：不