江蘇省計(jì)算機(jī)三級(jí)偏軟

1、江蘇省計(jì)算機(jī)等級(jí)考試三級(jí)偏軟,欣誠(chéng)教育,第2章 數(shù)據(jù)結(jié)構(gòu),主要內(nèi)容,算法及其描述數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)結(jié)構(gòu)線性表?xiàng)：完?duì)列數(shù)組樹圖查找排序,算法及其描述,算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。算法特性：有窮性確定性可行性輸入，零個(gè)或多個(gè)輸入。輸出，一個(gè)或多個(gè)輸出。,程序并不需要滿足有窮性,算法及其描述,算法的描述方式流程圖自然語言偽代碼程序設(shè)計(jì)語言,C

2、++,算法及其描述,算法設(shè)計(jì)要求（評(píng)價(jià)指標(biāo)）：正確性健壯性 （如對(duì)非法數(shù)據(jù)的處理和反應(yīng)）可讀性簡(jiǎn)單性 （采用的數(shù)據(jù)結(jié)構(gòu)和方法的簡(jiǎn)單程度）時(shí)間效率高存儲(chǔ)空間少,算法分析,算法復(fù)雜度語句頻度，算法中該語句執(zhí)行的次數(shù)。一個(gè)算法中所有語句的頻度之和構(gòu)成該算法的運(yùn)行時(shí)間。一個(gè)算法的語句頻度是其求解問題規(guī)模n的函數(shù)，記為T(n)。如果有某個(gè)函數(shù)F(n)，使得當(dāng)問題規(guī)模n趨于無窮大時(shí)，有：則將O(F(n))稱作算法的時(shí)間

3、復(fù)雜度。,算法分析,算法復(fù)雜度例：下面算法為求n個(gè)自然數(shù)的和S=1+2+3+…+n。請(qǐng)給出該算法的語句頻度。 sum(int n) { int i, s=0; for (i=1;i<=n;i++) // n+1次 s=s+i; // n次 printf(“%d\n”, s); // 1次 } /*s

4、um*/,T(n) = (n+1)+n+1=2n+2,算法復(fù)雜度為O(F(n)) = O(n),基本概念,數(shù)據(jù)（Data）：能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的的符號(hào)的集合，是計(jì)算機(jī)操作對(duì)象的總稱。 數(shù)值、字符? 圖形、圖像?聲音、視頻數(shù)據(jù)元素（Data Element） ：數(shù)據(jù)的基本單位，亦稱為結(jié)點(diǎn)、元素、頂點(diǎn)和記錄等。在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理。（例如：一個(gè)學(xué)生記錄）數(shù)據(jù)項(xiàng)（Data Item）：數(shù)據(jù)結(jié)

5、構(gòu)中討論的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合。亦稱為域、字段等。（例如：學(xué)生記錄中的學(xué)號(hào)。）,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。是相互間存在關(guān)系的數(shù)據(jù)元素集合。數(shù)據(jù)結(jié)構(gòu)包括3部分內(nèi)容：邏輯結(jié)構(gòu),指數(shù)據(jù)之間的相互關(guān)系。存儲(chǔ)結(jié)構(gòu),指數(shù)據(jù)及其關(guān)系在計(jì)算機(jī)中的存儲(chǔ)方式，或數(shù)據(jù)的物理結(jié)構(gòu)。運(yùn)算,指對(duì)數(shù)據(jù)進(jìn)行檢索、插入、刪除、合并、排序、統(tǒng)計(jì)、簡(jiǎn)單計(jì)算、轉(zhuǎn)換、輸入和輸出等操作過程。,數(shù)據(jù)結(jié)構(gòu),邏輯結(jié)構(gòu)例如，2行3列的二維數(shù)組D

6、 = {a1,a2,a3,a4,a5,a6}R = {row, col} row={,,,} col={,,}不同的關(guān)系構(gòu)成不同的結(jié)構(gòu)： 集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖（網(wǎng)狀）結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),邏輯結(jié)構(gòu)線性結(jié)構(gòu)：,,數(shù)據(jù)結(jié)構(gòu),邏輯結(jié)構(gòu)樹形結(jié)構(gòu)：,數(shù)據(jù)結(jié)構(gòu),邏輯結(jié)構(gòu)圖結(jié)構(gòu)：,數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的表示（映像），又稱物理結(jié)構(gòu)。

7、存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和關(guān)系的表示。順序鏈接索引散列,數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)將邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上也相鄰的存儲(chǔ)單元里，也就是將所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)相鄰的存儲(chǔ)區(qū)里。用存儲(chǔ)結(jié)點(diǎn)間的位置關(guān)系來表示結(jié)點(diǎn)之間的邏輯關(guān)系。計(jì)算機(jī)的存儲(chǔ)器是由很多存儲(chǔ)單元組成的，每個(gè)存儲(chǔ)單元都有惟一的地址（編號(hào)）。每個(gè)存儲(chǔ)單元的地址編號(hào)都是線性連續(xù)的。順序存儲(chǔ)結(jié)構(gòu)通?？梢杂肅/C++語言的數(shù)組來描述。,數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)

8、結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)例：用順序存儲(chǔ)方式表示一周7天，設(shè)這7天的數(shù)據(jù)結(jié)構(gòu)為：DS＝（D, R）D＝{Sun, Mon, Tue, Wed, Thu, Fri, Sat}R = {, , , , , },數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu)在存儲(chǔ)每個(gè)結(jié)點(diǎn)信息的同時(shí)，需要增加一個(gè)指針來表示結(jié)點(diǎn)間的邏輯關(guān)系。該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。鏈接存儲(chǔ)結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)由兩部分組成：一

9、部分用于存儲(chǔ)結(jié)點(diǎn)本身的信息，稱為數(shù)據(jù)域；另一部分用于存儲(chǔ)該結(jié)點(diǎn)的后繼結(jié)點(diǎn)（或前驅(qū)結(jié)點(diǎn)）的存儲(chǔ)單元地址，稱為指針域。,數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)鏈接存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)方式索引存儲(chǔ)方法是在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立一個(gè)附加的索引表。索引表中每一項(xiàng)稱為一個(gè)索引項(xiàng)。索引項(xiàng)的一般形式是：（關(guān)鍵字，地址）,數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)方式,（b）索引表,（a）文件數(shù)據(jù)區(qū),數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)散列方式基本思想：根據(jù)結(jié)點(diǎn)的關(guān)鍵字Ke

10、y直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。即以線性表中的每個(gè)結(jié)點(diǎn)的關(guān)鍵字Key為自變量，通過一個(gè)確定的函數(shù)關(guān)系f，計(jì)算出對(duì)應(yīng)的函數(shù)值f(key)，然后把這個(gè)值解釋為一塊連續(xù)存儲(chǔ)空間的存儲(chǔ)地址，將結(jié)點(diǎn)存儲(chǔ)到f(key)所指的存儲(chǔ)單元中，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)的存儲(chǔ)地址相對(duì)應(yīng)。,數(shù)據(jù)結(jié)構(gòu),存儲(chǔ)結(jié)構(gòu)散列方式例：已知一組待存儲(chǔ)的關(guān)鍵字為（40，68，6，20，49，24，53，16，1，45，14，88），散列地址為T[0..12]。假設(shè)用除留取余

11、法構(gòu)造的散列函數(shù)為：H(key) = f(key) = key%13。,線性表,線性表是由n（n>=0）個(gè)具有相同特性的數(shù)據(jù)元素（結(jié)點(diǎn)）a1, a2, a3, …, an組成的有限序列。通常記作： L =（a1, a2, a3, …, an）n=0 時(shí)稱為空表；表中 ai-1 是ai 的直接前驅(qū)，ai+1 是ai 的直接后繼；線性表中，除第一個(gè)元素和最后一個(gè)元素之外，其他元素都有且僅有一個(gè)直接前驅(qū)和直接后繼；ai是線性表

12、的第 i 個(gè)元素，稱 i 為數(shù)據(jù)元素ai 的序號(hào)，每一個(gè)元素在線性表中的位置，取決于其序號(hào)。,線性表,例1：一組實(shí)驗(yàn)數(shù)據(jù)（41, 21, 34, 53, 62, 71, 76, 45） 例2：26個(gè)大寫英文字母組成的字母表（A, B, C, …, Z） 例3：學(xué)生成績(jī)統(tǒng)計(jì)表也是一個(gè)線性表。,線性表,順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。,,,,,,,,,,a1a2ai-1aiai+1an,…,

13、…,Loc(ai ) = Loc( a1 )+ ( i – 1)* L,Loc( a1 ),Loc(ai ),每個(gè)元素占L個(gè)存儲(chǔ)單元,,,…,…,順序表通過元素的存儲(chǔ)順序反映線性表元素間的邏輯關(guān)系,線性表,順序存儲(chǔ)結(jié)構(gòu) #define max 100 // 線性表可能的最大長(zhǎng)度 typedef struct sequenlist { ElemType e[max];

14、 //定義線性表為一維數(shù)組 int n; //當(dāng)前線性表長(zhǎng)度 } SqList;,線性表,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組地址任意的存儲(chǔ)單元來存放表中各數(shù)據(jù)元素。特點(diǎn)：數(shù)據(jù)元素的邏輯次序和物理次序不一定相同。在存儲(chǔ)數(shù)據(jù)元素時(shí)，除了要存儲(chǔ)數(shù)據(jù)元素本身的信息外，還必須附加一個(gè)或多個(gè)指針用于指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)或前驅(qū)結(jié)點(diǎn)的存儲(chǔ)地址（或位置）。常見的鏈表有3種：?jiǎn)捂?/p>

15、表、循環(huán)鏈表、雙鏈表,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表單鏈表中結(jié)點(diǎn)：,Typedef struct Node{ ElemType data; Struct Node *next;} slink;,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表,head=NULL，則該鏈表稱為空表。,（不帶表頭結(jié)點(diǎn)）,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)單鏈表,head是頭指針,,,ai-1,,,,a2,,,,a1,,,,,頭結(jié)點(diǎn),he

16、ad,（帶表頭結(jié)點(diǎn)）,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)雙向鏈表雙向鏈表中結(jié)點(diǎn)：,,∧,∧,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)循環(huán)鏈表,,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)循環(huán)鏈表,,線性表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)雙向循環(huán)鏈表,,head,,,,,(b)空的雙向循環(huán)鏈表,,,（c）非空的雙向循環(huán)鏈表,,,,,head,a,b,,,C,線性表的基本運(yùn)算,線性表的插入運(yùn)算是指在表的第i（1≤i≤n+1）個(gè)（或符合要求的）位置上，插入一個(gè)新的結(jié)點(diǎn)x，

17、使長(zhǎng)度為n的線性表： ( a1, …, ai?1 , ai , ai+1 ,…, an ) 變成為長(zhǎng)度為n+1的線性表：( a1, …, ai?1, x, ai, ai+1,…, an ),線性表的基本運(yùn)算,順序表的插入由于順序表中結(jié)點(diǎn)在計(jì)算機(jī)中是連續(xù)存放的，若在第i個(gè)結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)x，就必須將表中下標(biāo)位置為i, i+1, …, n上的結(jié)點(diǎn)依次向后移動(dòng)到i+1, i+2, …, n+1的位置上，空出第i個(gè)位置，然后在該

18、位置上插入新結(jié)點(diǎn)x。僅當(dāng)插入位置i=n+1時(shí)，才無須移動(dòng)結(jié)點(diǎn)，直接將x插到表的末尾。新結(jié)點(diǎn)插入后，線性表的長(zhǎng)度變成n+1。,線性表的基本運(yùn)算,順序表的插入在順序表中插入一個(gè)新結(jié)點(diǎn)的過程如下：① 檢查順序表的存儲(chǔ)空間是否已滿，若滿則停止插入，退出程序運(yùn)行；② 將第i～n個(gè)結(jié)點(diǎn)之間的所有結(jié)點(diǎn)依次向后移動(dòng)一個(gè)位置，空出第i個(gè)位置；③ 將新結(jié)點(diǎn)x插入第i個(gè)位置；修改線性表的長(zhǎng)度，使其加1；④ 若插入成功，則函數(shù)返回值為1，否則函數(shù)值

19、返回值為0。見教材p.45算法2-1,線性表的基本運(yùn)算,單鏈表的插入假設(shè)指針p指向單鏈表中某個(gè)結(jié)點(diǎn)，指針s指向值為x的新待插結(jié)點(diǎn)。若將新結(jié)點(diǎn)s插入結(jié)點(diǎn)p之后，則稱為后插；若將新結(jié)點(diǎn)s插到結(jié)點(diǎn)p之前，則稱為前插。后插運(yùn)算,,,,y,,,x,,,,p,,,,,,head,,,s,,線性表的基本運(yùn)算,單鏈表的插入后插運(yùn)算,線性表的基本運(yùn)算,單鏈表的插入前插運(yùn)算,見教材p64算法2-10,,線性表的基本運(yùn)算,雙向鏈表的插入前插運(yùn)

20、算,線性表的基本運(yùn)算,雙向鏈表的插入后插運(yùn)算,線性表的基本運(yùn)算,線性表的刪除運(yùn)算將線性表中第i個(gè)（或符合要求）的數(shù)據(jù)元素刪除，使長(zhǎng)度為n的線性表： ( a1, …, ai?1 , ai , ai+1 ,…, an ) 變成為長(zhǎng)度為n-1的線性表：( a1, …, ai?1, ai+1,…, an ),線性表的基本運(yùn)算,順序表的刪除過程：① 檢查給定結(jié)點(diǎn)的刪除位置是否正確，若刪除位置有錯(cuò)，則顯示出錯(cuò)信息，退出程序運(yùn)行；②

21、 把表中第i+1～n個(gè)結(jié)點(diǎn)之間的所有結(jié)點(diǎn)依次向前移動(dòng)一個(gè)位置；③ 將線性表的長(zhǎng)度減1。 見教材p46算法2-2,線性表的基本運(yùn)算,單鏈表的刪除,,見教材p65算法2-11,線性表的基本運(yùn)算,雙向鏈表的刪除,順序表插入和刪除運(yùn)算的時(shí)間分析,在線性表順序存儲(chǔ)結(jié)構(gòu)中某個(gè)位置上插入和刪除一個(gè)數(shù)據(jù)元素時(shí)，其插入與刪除算法的主要執(zhí)行時(shí)間都耗費(fèi)在移動(dòng)數(shù)據(jù)元素上，而移動(dòng)元素的個(gè)數(shù)則取決于插入或刪除元素的位置。假設(shè)pi是在第i個(gè)元素之前插入

22、一個(gè)元素的概率，則在長(zhǎng)度為n的線性表中插入一個(gè)元素時(shí)，所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）應(yīng)為：,順序表插入和刪除運(yùn)算的時(shí)間分析,同理，假設(shè)qi是刪除第i個(gè)元素的概率，則在長(zhǎng)度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）應(yīng)為：,順序表插入和刪除運(yùn)算的時(shí)間分析,假定在線性表任何位置上插入或刪除元素都是等概率的，則: pi=1/(n+1) qi = 1/n在等概率情況下，上式可以分別簡(jiǎn)化為：

23、若順序表的長(zhǎng)度為n，則順序表的插入算法和刪除算法的時(shí)間復(fù)雜度均為O(n)。,單鏈表上查找、插入和刪除運(yùn)算的時(shí)間分析,設(shè)Pi是單鏈表上查找第i個(gè)元素的概率，在長(zhǎng)度為n的帶頭結(jié)點(diǎn)的單鏈表中可能進(jìn)行查找的位置為i=0, 1, 2, …, n。在等概率情況下P1=P2=…=Pi=1/(n+1)。若查找成功時(shí)，則單鏈表中查找任意位置上數(shù)據(jù)元素的平均比較次數(shù)為：?jiǎn)捂湵砩喜檎?、插入、刪除算法的平均時(shí)間復(fù)雜度為O(n)。,順序表和鏈表的比

24、較,空間性能的比較存儲(chǔ)密度：存儲(chǔ)結(jié)點(diǎn)中數(shù)據(jù)域占用的存儲(chǔ)量與存儲(chǔ)結(jié)點(diǎn)所占用的存儲(chǔ)量之比稱為存儲(chǔ)密度。存儲(chǔ)密度越大，則存儲(chǔ)空間的利用率就越高。順序表的存儲(chǔ)密度是高于鏈表的存儲(chǔ)密度。但是，順序表要求事先估計(jì)容量，這是比較困難的。,順序表和鏈表的比較,時(shí)間性能的比較當(dāng)線性表的主要操作是查找運(yùn)算時(shí)，最好采用順序存儲(chǔ)結(jié)構(gòu)。對(duì)于需要頻繁地進(jìn)行插入和刪除操作的線性表，最好采用鏈接存儲(chǔ)結(jié)構(gòu)。若鏈表的插入和刪除操作主要發(fā)生在表的首、尾兩端，采用

25、尾指針表示的單循環(huán)鏈表則是最好的選擇。,棧,棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表。,（a1, a2, ... , ai -1, ai , ai+1, …, an ）,,插入,刪除,,棧,允許進(jìn)行插入和刪除運(yùn)算的這一端稱為棧頂，不允許進(jìn)行插入和刪除運(yùn)算的另一端則稱為棧底；向棧中插入一個(gè)新元素稱為入?；驂簵?，從棧中刪除一個(gè)元素稱為出棧或退棧；記錄棧頂元素位置的變量稱為棧頂指針，處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素；不含

26、任何數(shù)據(jù)元素的棧則稱為空棧。,棧,棧的特點(diǎn)后進(jìn)先出,棧,棧的順序存儲(chǔ)結(jié)構(gòu)利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。順序?？梢杂靡粋€(gè)一維數(shù)組和一個(gè)記錄棧頂位置的整型變量來實(shí)現(xiàn)，數(shù)組用于順序存儲(chǔ)棧中所有的數(shù)據(jù)元素，棧頂指針用于存儲(chǔ)棧頂元素的位置。,e[max],top,stack,棧,棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以某種形式的鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，其組織形式與單鏈表類似。,棧,順序棧

27、的基本運(yùn)算,見教材p48 算法2-3，算法2-4,棧,鏈棧的基本運(yùn)算,棧,共享?xiàng)?棧在遞歸過程中的作用,所謂遞歸，是指一個(gè)函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)，若在其定義的內(nèi)部又直接或者間接出現(xiàn)有定義自身的應(yīng)用，則稱其是遞歸的或者是遞歸定義的。在調(diào)用一個(gè)函數(shù)（程序）的過程中又直接或間接地調(diào)用該函數(shù)（程序）本身，稱為函數(shù)的遞歸調(diào)用。,棧在遞歸過程中的作用,一般函數(shù)的調(diào)用機(jī)制,,函數(shù)調(diào)用順序 A B C,,,函數(shù)返回順序 C B

28、 A,,,后調(diào)用的函數(shù)先返回,函數(shù)調(diào)用機(jī)制可通過棧來實(shí)現(xiàn),計(jì)算機(jī)正是利用棧來實(shí)現(xiàn)函數(shù)的調(diào)用和返回的,棧在遞歸過程中的作用,遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過一系列調(diào)用間接調(diào)用自己的函數(shù)稱為遞歸函數(shù)。,A（ ）{ … A( ) ; …},B( ) { C( ) { …

29、 … C( ); B( ); … … } },A 直接調(diào)用自己,B間接調(diào)用自己,,棧在遞歸過程中的作用,遞歸算法的編寫1）將問題用遞歸的方式描述

30、（定義）2）根據(jù)問題的遞歸描述（定義）編寫遞歸算法遞歸定義包括兩項(xiàng)1）基本項(xiàng)（終止項(xiàng)）：描述遞歸終止時(shí)問題的求解；2）遞歸項(xiàng)：將問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題；,棧在遞歸過程中的作用,遞歸算法的編寫【例3.7】采用遞歸算法求解正整數(shù)n的階乘（n?。?。 正整數(shù)n的階乘的遞歸定義為：,棧在遞歸過程中的作用,遞歸算法的編寫/* 用遞歸方法求n的階乘的函數(shù) */ float Fact(int n)

31、{ float f = 0.0; if (n<0) printf(“輸入數(shù)據(jù)錯(cuò)誤! ”) else if (n==0) f=1; else f = n*Fact(n-1); return(f); },隊(duì)列,隊(duì)列也是一種運(yùn)算受限的線性表，在這種線性表上，插入限定在表的某一端進(jìn)行，刪除限定在表的另一端。允許插入的一端稱為隊(duì)尾

32、（Rear），允許刪除的一端稱為隊(duì)頭（Front）。在隊(duì)列中插入一個(gè)新元素的操作簡(jiǎn)稱為進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除一個(gè)元素的操作簡(jiǎn)稱為出隊(duì)或離隊(duì)，當(dāng)元素出隊(duì)后，其后繼元素就成為新的隊(duì)頭元素。若隊(duì)列中沒有元素，則稱為空隊(duì)列。,隊(duì)列,隊(duì)列又稱為先進(jìn)先出表（First In First Out），簡(jiǎn)稱FIFO表。,隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)順序隊(duì)列可利用一個(gè)一維數(shù)組和兩個(gè)指針來實(shí)現(xiàn)。一維數(shù)組用于存儲(chǔ)當(dāng)前隊(duì)列中

33、的所有元素，兩個(gè)指針front和rear分別指向當(dāng)前隊(duì)列的隊(duì)首元素和隊(duì)尾元素。（注意，它們并非指針變量，而是數(shù)組的下標(biāo)）。,e[max],front,queue,rear,隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)【例3.8】假設(shè)某個(gè)順序隊(duì)列Q為（A, B, C, D, E, F），隊(duì)列的長(zhǎng)度MAXSIZE = 6。給出順序隊(duì)列出隊(duì)和入隊(duì)時(shí)，隊(duì)首指針及隊(duì)尾指針的變化情況。,隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu),隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)與棧類似，順序隊(duì)列亦有上溢和

34、下溢現(xiàn)象。當(dāng)隊(duì)空時(shí)，再進(jìn)行出隊(duì)操作就會(huì)產(chǎn)生“下溢”。當(dāng)隊(duì)滿時(shí)，再進(jìn)行入隊(duì)操作就會(huì)產(chǎn)生“上溢”。此外，順序隊(duì)列還存在“假上溢”現(xiàn)象。當(dāng)隊(duì)尾指針指向數(shù)組的最后一個(gè)位置即: rear=MAXSIZE?1 時(shí)，就會(huì)出現(xiàn)隊(duì)滿（溢出）的情況，這時(shí)不能再進(jìn)行入隊(duì)操作；若數(shù)組前端還有空余單元，則這時(shí)隊(duì)列就不是真正隊(duì)滿，而是一種假隊(duì)滿。,隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)產(chǎn)生這種現(xiàn)象的原因在于： 進(jìn)行入隊(duì)和出隊(duì)操作時(shí)，隊(duì)頭指針和隊(duì)尾指

35、針只增大不減小，使得被刪除元素的空間在該元素被刪除后永遠(yuǎn)無法重新利用。雖然隊(duì)列中元素的實(shí)際個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于數(shù)組存儲(chǔ)空間的規(guī)模，但可能由于隊(duì)尾指針超過數(shù)組的上界而不能進(jìn)行入隊(duì)操作。,隊(duì)列,隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)解決假溢出問題的方法：1）當(dāng)元素出隊(duì)時(shí)，將整個(gè)隊(duì)列中元素依次向前移動(dòng)一個(gè)位置，并修改隊(duì)頭指針和隊(duì)尾指針，使得隊(duì)頭指針head始終保持為?1。2）當(dāng)元素出隊(duì)時(shí)，隊(duì)列不移動(dòng)，當(dāng)出現(xiàn)假溢出時(shí)，再把整個(gè)隊(duì)列中所有的元素依次向前移動(dòng)，直至隊(duì)頭指

36、針head=?1時(shí)為止。這兩種方法都是通過移動(dòng)隊(duì)列的元素使數(shù)組的空閑單元留在后面，以便隊(duì)列能夠繼續(xù)使用。其缺點(diǎn)是需要移動(dòng)大量的隊(duì)列元素，浪費(fèi)時(shí)間。,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列將整個(gè)數(shù)組空間變成一個(gè)首尾相接的圓環(huán)，即把data[0]接在data[MAXSIZE?1]之后，我們稱這種數(shù)組為循環(huán)數(shù)組。用循環(huán)數(shù)組表示的隊(duì)列稱為循環(huán)隊(duì)列。 當(dāng)循環(huán)隊(duì)列進(jìn)行出隊(duì)和入隊(duì)操作時(shí)，隊(duì)列的頭尾指針仍然要加1，向前移動(dòng)。當(dāng)隊(duì)尾指針等于數(shù)組的上界時(shí)（即re

37、ar = MAXSIZE ?1），若進(jìn)行入隊(duì)操作，可令隊(duì)尾指針等于數(shù)組的下界（即rear=0）。,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列,,入隊(duì)時(shí)，隊(duì)尾指針的操作： rear=(rear+1)% MAXSIZE,出隊(duì)時(shí)，隊(duì)頭指針的操作：head=(head+1)% MAXSIZE,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列前面規(guī)定：在順序隊(duì)列中，隊(duì)頭指針head指向隊(duì)首元素的前一個(gè)位置，而不是指向隊(duì)首元素本身；隊(duì)尾指針rear指向隊(duì)尾元素本身的位置。在這種規(guī)定

38、下，隊(duì)列初始狀態(tài)可設(shè)置為： head=rear=MAXSIZE?1當(dāng)循環(huán)隊(duì)列的某個(gè)元素出隊(duì)后，隊(duì)頭指針向前追趕隊(duì)尾指針，若head==rear，則循環(huán)隊(duì)列為空；當(dāng)循環(huán)隊(duì)列的某個(gè)元素入隊(duì)后，隊(duì)尾指針向前追趕隊(duì)頭指針，若rear==head，則循環(huán)隊(duì)列為滿。,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列無法用條件“head= =rear”判斷和區(qū)分循環(huán)隊(duì)列是“空隊(duì)”還是“滿隊(duì)”。 用一個(gè)簡(jiǎn)單的方法來解決：在循環(huán)數(shù)組中始終保留一

39、個(gè)空閑單元不用。這樣，判別循環(huán)隊(duì)列是否為滿隊(duì)時(shí)，只要確定當(dāng)前尾指針rear的下一個(gè)單元的位置是否為首指針head所指即可，即 (rear+1)%MAXSIZE==head？,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列,,,,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列,,,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列在循環(huán)隊(duì)列中隊(duì)滿和隊(duì)空的條件分別為： 隊(duì)滿的條件：(rear+1)%MAXSIZE==head隊(duì)空的條件：rear==head入隊(duì)：rear=(re

40、ar+1)% MAXSIZE出隊(duì)：head=(head+1)% MAXSIZE,隊(duì)列,順序存儲(chǔ)的循環(huán)隊(duì)列【例3.9】對(duì)于循環(huán)隊(duì)列，寫出隊(duì)列中元素個(gè)數(shù)的公式。,（Rear + QueueSize –front）％ QueueSize,隊(duì)列,隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為鏈隊(duì)列，它實(shí)際上是一個(gè)同時(shí)帶有首指針和尾指針的單鏈表。首指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)即單鏈表的最后一個(gè)結(jié)點(diǎn)。,數(shù)組,數(shù)組是由n（n≥1）個(gè)相同類

41、型的數(shù)據(jù)元素a1, a2, a3, …, an組成的有限序列，也可以稱為向量。可用數(shù)組下標(biāo)來區(qū)分各元素，一個(gè)下標(biāo)惟一地對(duì)應(yīng)一個(gè)元素，元素的下標(biāo)一般具有固定的上界和下界。,數(shù)組,一維數(shù)組A[n],由[a1, a2, …, an?1, an]這n個(gè)元素組成的，每個(gè)元素除了具有相同的類型外，還有一個(gè)確定元素位置的下標(biāo)。二維數(shù)組A[m][n],由m?n個(gè)元素組成的，元素之間有規(guī)則地排列。每個(gè)元素由值和兩個(gè)能確定元素位置的下標(biāo)組成。,數(shù)組,數(shù)

42、組的存儲(chǔ)結(jié)構(gòu)多維數(shù)組通常采用順序存儲(chǔ)方式，即把數(shù)組中各元素的值按某種次序存放在計(jì)算機(jī)的一組連續(xù)存儲(chǔ)單元中。一組連續(xù)的存儲(chǔ)單元存放多維數(shù)組就必須按照某種次序?qū)?shù)組中的元素排成一個(gè)線性序列，然后將這個(gè)線性序列順序存放到計(jì)算機(jī)中。,數(shù)組,一維數(shù)組的順序存儲(chǔ)結(jié)構(gòu)一維數(shù)組A中第i個(gè)元素ai的存儲(chǔ)位置的計(jì)算公式為： Loc(ai) = Loc(a1) + (i-1)*d (1≦i ≦ n),C++中，下

43、標(biāo)從0開始,,關(guān)鍵是計(jì)算準(zhǔn)確個(gè)數(shù),數(shù)組,二維數(shù)組的兩種順序存儲(chǔ)方式1）以行序?yàn)橹餍颍ㄐ袃?yōu)先）；2）以列序?yàn)橹餍颍袃?yōu)先）。,數(shù)組,二維數(shù)組的兩種順序存儲(chǔ)方式當(dāng)A[m][n]按“行優(yōu)先”存儲(chǔ)時(shí)的存儲(chǔ)位置計(jì)算公式：Loc(ai,j) = Loc(a0,0) + (n×i＋j )×d當(dāng)A[m][n]按“列優(yōu)先“存儲(chǔ)時(shí)的存儲(chǔ)位置計(jì)算公式： Loc(ai,j) = Loc(a0,0) + (m×

44、j＋i )×d,下標(biāo)從（0，0）到（m-1, n-1),數(shù)組,稀疏矩陣大多數(shù)元素值都是零，只有少數(shù)的非零元素，這類矩陣稱為稀疏矩陣。,數(shù)組,稀疏矩陣的壓縮存儲(chǔ)只存儲(chǔ)非零元素。三元組一個(gè)三元組（i, j, aij）來表示位于第i行j列的非零元素aij。若將每個(gè)非零元素表示為一個(gè)三元組元素，并且按行號(hào)的遞增次序（行號(hào)相同則按列號(hào)的遞增次序）順序存放到一個(gè)三元組線性表中，這就是稀疏矩陣的三元組表示方法。兩種壓縮存儲(chǔ)方式：

45、順序存儲(chǔ)方式鏈接存儲(chǔ)方式,e[max],m,trilist,n,t,i j v,,,node,數(shù)組,稀疏矩陣的壓縮存儲(chǔ)三元組,數(shù)組,稀疏矩陣的轉(zhuǎn)置運(yùn)算（三元組表示）,0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0

46、 0 00 18 0 0 0 0 015 0 0 -7 0 0 0,0 0 -3 0 0 15 0 0 0 18 0 0 0 24 0 0 0 0 0 0 0 -70 0 0 0 0 00 0

47、14 0 0 00 0 0 0 0 0,,,,,,M6x7,T7x6,數(shù)組,稀疏矩陣的轉(zhuǎn)置運(yùn)算（三元組表示）,i j v 2 121 3 93 1 -33 6 144 3 245 2 186 1 156 4 -7,,i j

48、 v1 3 -3 1 6 15 2 1 122 5 183 1 93 4 24 4 6 -7 6 3 14,,,a.data,b.data,數(shù)組,稀疏矩陣的十字鏈表表示,rhead,dhead,clist,m,n,node,t,數(shù)組,稀疏矩陣的十字鏈表表示,特殊矩陣的壓縮存儲(chǔ),特殊矩陣：

49、若值相同的元素或零元素在矩陣中的分布有一定規(guī)律，則我們稱此類矩陣為特殊矩陣。壓縮存儲(chǔ)：為了節(jié)省存儲(chǔ)空間，特別是在高階矩陣的情況下，可以利用特殊矩陣的規(guī)律，對(duì)它們進(jìn)行壓縮存儲(chǔ)，也就是說，使得多個(gè)值相同的元只分配一個(gè)存儲(chǔ)空間，對(duì)零元不分配空間。,對(duì)稱陣的壓縮存儲(chǔ),對(duì)稱陣A中元素滿足：aij = aji可以為每一對(duì)對(duì)稱元分配一個(gè)存儲(chǔ)空間，則可將n2個(gè)元壓縮存儲(chǔ)到n(n+1)/2個(gè)元的空間中。假設(shè)以一維數(shù)組B[n(n+1)/2]作為 n

50、階對(duì)稱矩陣A的存儲(chǔ)結(jié)構(gòu)，在B中只存儲(chǔ)對(duì)稱矩陣A的下三角元素aij（i>=j）。則其存儲(chǔ)分配情況如圖所示。,,對(duì)稱陣的壓縮存儲(chǔ),在這種壓縮結(jié)構(gòu)中，為了便于訪問對(duì)稱矩陣A中元素并能進(jìn)行處理，我們必須通過給定的一組下標(biāo)（i, j）找到對(duì)稱矩陣中任一元素aij在一維數(shù)組B[k]中的存儲(chǔ)位置，即在aij和B[k]之間找到一個(gè)對(duì)應(yīng)關(guān)系。,三角矩陣的壓縮存儲(chǔ),以主對(duì)角線劃分，三角矩陣分為兩種：上三角矩陣和下三角矩陣。上三角矩陣，是指下三角（不

51、包括主角線）中的元素均為常數(shù)c的n階方陣。下三角矩陣，主對(duì)角線上方均為常數(shù)c。在多數(shù)情況下，三角矩陣的常數(shù)c為0。對(duì)于任何一個(gè)n階下三角矩陣都具有下述性質(zhì)：當(dāng)i＜j時(shí)，aij=c；同理，對(duì)于任何一個(gè)n階上三角矩陣：當(dāng)i＞j時(shí)，aij=c。,三角矩陣的壓縮存儲(chǔ),三角矩陣采用壓縮存儲(chǔ)方式時(shí)，只存儲(chǔ)矩陣的下三角元素或上三角元素。如果讓矩陣中所有重復(fù)元素c共享一個(gè)存儲(chǔ)單元，那么三角矩陣中n2個(gè)元素就可以壓縮存儲(chǔ)到一維數(shù)組B[n(n+1)/2

52、]中，其中重復(fù)元素c放在數(shù)組的最后一個(gè)單元中。若按“行優(yōu)先順序”存儲(chǔ)下三角矩陣中的元素，則矩陣下三角元素的壓縮存儲(chǔ)情況如下圖所示。,三角矩陣的壓縮存儲(chǔ),三角矩陣A中任一元素aij在一維數(shù)組B[k]中的存儲(chǔ)位置。上三角關(guān)系下三角關(guān)系,樹,樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。若n=0，則樹是一棵空樹；若n＞0，則樹是一棵非空樹。一棵非空樹滿足如下兩個(gè)條件：① 有且僅有一個(gè)特定的結(jié)點(diǎn)，該結(jié)點(diǎn)稱為根結(jié)點(diǎn)；② 除根結(jié)點(diǎn)外的其他結(jié)

53、點(diǎn)可分為m（m≥0）個(gè)互不相交的有限集合T1, T2, …, Tm，其中每個(gè)集合本身又是一棵樹，這些集合稱為根結(jié)點(diǎn)的子樹。,樹的定義,T={A, B, C, D, E, F, G, H, I, J，K，L，M}A是根，其余結(jié)點(diǎn)可劃分為3個(gè)互不相交的集合： T1={B, E, F，K，L} , T2={C, G} , T3={D, H, I, J，M},樹,樹的定義,樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，其特點(diǎn)是：1）樹中每個(gè)結(jié)點(diǎn)都

54、可以有零個(gè)或多個(gè)直接后繼，若有多個(gè)后繼結(jié)點(diǎn)，則后繼結(jié)點(diǎn)是該結(jié)點(diǎn)的每個(gè)子樹的根結(jié)點(diǎn)。2）除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)，有且僅有一個(gè)直接前驅(qū)。3）數(shù)據(jù)結(jié)點(diǎn)按分支關(guān)系組織起來，清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。4）樹型結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是一對(duì)多或者多對(duì)一的關(guān)系。,樹,基本術(shù)語1．結(jié)點(diǎn)的度和樹的度結(jié)點(diǎn)具有的子樹（分支）個(gè)數(shù)稱為結(jié)點(diǎn)的度。一棵樹中所有結(jié)點(diǎn)的度的最大值稱為樹的度。2．葉子結(jié)點(diǎn)和分支結(jié)點(diǎn)樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)或

55、終端結(jié)點(diǎn)，度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)。,樹,基本術(shù)語3．雙親結(jié)點(diǎn)、孩子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)樹中每個(gè)結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子或兒子或子女；相應(yīng)地，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親或父親。具有同一個(gè)雙親的孩子們之間互稱為兄弟。每個(gè)結(jié)點(diǎn)的祖先是從樹的根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)過路徑上的所有結(jié)點(diǎn)。反之，以某結(jié)點(diǎn)為根的子樹中的所有結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。,樹,基本術(shù)語4．結(jié)點(diǎn)的層數(shù)和樹的高度結(jié)點(diǎn)的層數(shù)從樹的根結(jié)點(diǎn)開始計(jì)算。假設(shè)樹的根結(jié)點(diǎn)為

56、第一層，它的孩子結(jié)點(diǎn)為第二層，其余類推。樹中結(jié)點(diǎn)的最大層數(shù)就稱為樹的高度或深度。5．森林森林是m（m≥0）棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。6．有序樹和無序樹若樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，且相對(duì)次序是不能變換的，則該樹被稱為有序樹，否則稱為無序樹。,二叉樹,定義二叉樹是有限的結(jié)點(diǎn)集合，這個(gè)集合或者為空，或者有一個(gè)根結(jié)點(diǎn)，它由兩棵不相交的分別稱為根的左子樹和右子樹的二叉樹組成。左子樹和右子

57、樹同樣又都是一棵二叉樹。,二叉樹的5種基本形態(tài),二叉樹,定義,兩棵不同的二叉樹,一棵普通的無序樹,二叉樹,二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i 層上最多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為 h 的二叉樹最多有 2h-1 (h>=1)個(gè)結(jié)點(diǎn)。性質(zhì)3：設(shè)二叉樹葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則 n0 = n2 +1。滿二叉樹：如果深度為 k 的二叉樹，有2k-1個(gè)結(jié)點(diǎn)則稱為滿二叉樹。,二叉樹,二叉樹的性質(zhì)完全二叉樹：如果一

58、顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹。性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1,或 log2n+1,二叉樹的性質(zhì),性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)（每層從左到右），則對(duì)任一結(jié)點(diǎn)i (11，則其雙親是結(jié)點(diǎn)? i/2 ?；2）2i>n：結(jié)點(diǎn)無左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn)2i。3）2i+1>n：結(jié)點(diǎn)無右孩

59、子（結(jié)點(diǎn)I為葉子結(jié)點(diǎn)）；否則其右孩子是結(jié)點(diǎn)2i+1。,二叉樹,二叉樹的順序存儲(chǔ)結(jié)構(gòu)把二叉樹的所有結(jié)點(diǎn)，按照一定的次序順序存放到一組地址連續(xù)的存儲(chǔ)單元中。對(duì)完全二叉樹中所有結(jié)點(diǎn)進(jìn)行編號(hào)得到一個(gè)結(jié)點(diǎn)的線性序列，然后將完全二叉樹各結(jié)點(diǎn)按其編號(hào)順序存放到一個(gè)一維數(shù)組中，即將完全二叉樹上編號(hào)為 i 的結(jié)點(diǎn)存入一維數(shù)組下標(biāo)為 i 的分量中。對(duì)于編號(hào)為 i 的結(jié)點(diǎn)，若有左孩子，它的左孩子的編號(hào)為 2i；若有右孩子，它的右孩子的編號(hào)為 2i+1。

60、,二叉樹,二叉樹的順序存儲(chǔ)結(jié)構(gòu),二叉樹,二叉樹的順序存儲(chǔ)結(jié)構(gòu)普通二叉樹的順序存儲(chǔ)方法,二叉樹,二叉樹的鏈接存儲(chǔ)結(jié)構(gòu),二叉樹,二叉樹的遍歷按一定的次序“訪問”二叉樹的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)僅被“訪問”一次。實(shí)際上就是把二叉樹的所有結(jié)點(diǎn)放入一個(gè)線性序列的過程。需要尋找一種規(guī)律來系統(tǒng)地訪問二叉樹的各個(gè)結(jié)點(diǎn)。三種方式：DLR，LDR，LRD,根,,二叉樹,二叉樹的遍歷,其第一個(gè)元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。,以根結(jié)點(diǎn)的數(shù)據(jù)值為界，將

61、中序遍歷序列分為兩部分。,其最后一個(gè)元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。,算法見教材p73,二叉樹,二叉樹的遍歷例有二叉樹中序序列為：ABCEFGHD，后序序列為：ABFHGEDC，畫出此二叉樹。,二叉樹,二叉樹的遍歷【例】假設(shè)先序遍歷某二叉樹的結(jié)點(diǎn)次序?yàn)锳BCDEFGHIJ，中序遍歷該二叉樹的結(jié)點(diǎn)次序?yàn)镃BEDAGHFJI，試畫出此二叉樹。,求二叉樹的高度運(yùn)算算法,求二叉樹的高度的遞歸模型如下：

62、 0 若bt = NULL Max{ f (bt->lchild) , f ( bt->rchild ) } + 1,,f( bt ) =,求二叉樹的高度運(yùn)算算法,Int BTHeight ( bitree *bt ){ int lchilddep, rchilddep; if ( bt = =

63、NULL) return ( 0 ); else { lchilddep = BTHeight ( bt ->lchild ); rchilddep = BTHeight ( bt->rchild ); return(lchilddep>rchilddep)?(lchilddep+1):(rchilddep +1 ); }},求二叉樹結(jié)點(diǎn)個(gè)數(shù)運(yùn)算算法,對(duì)應(yīng)的遞歸模型如

64、下： 0 若bt = NULL f ( bt ->lchild ) + f ( bt->rchild ) +1,f( bt ) =,,求二叉樹結(jié)點(diǎn)個(gè)數(shù)運(yùn)算算法,Int NodeCount ( bitree *bt ){ int num1, num2; if ( bt = = NULL) r

65、eturn 0; Else { num1 = NodeCount ( bt ->lchild ); num2 = NodeCount ( bt ->rchild ); return ( num1 + num2 +1 ); }},求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)運(yùn)算算法,對(duì)應(yīng)的遞歸模型如下： 0

66、 bt = NULL 1 bt為葉子結(jié)點(diǎn) F ( bt ->lchild ) + f ( bt ->rchild ) 其他情況,F (bt) =,,求二叉樹葉子結(jié)點(diǎn)個(gè)數(shù)運(yùn)算算法,Int LeafCount ( bitree *bt ) { int

67、 num1, num2; if ( bt = = NULL ) return 0; else if ( bt ->lchild = = NULL && bt->rchild = = NULL ) return 1; else { num1 = LeafCount ( bt ->lchild ); num2 = Leaf

68、Count ( bt->rchild ); return ( num1 + num2 ); } },樹的存儲(chǔ)結(jié)構(gòu),孩子兄弟鏈表存儲(chǔ)結(jié)構(gòu),Fchild data nsibling,,,第一個(gè)孩子,,下一個(gè)兄弟,,樹的存儲(chǔ)結(jié)構(gòu),樹的遍歷兩種方式先根遍歷后根遍歷,樹、二叉樹、森林的轉(zhuǎn)換,樹、二叉樹、森林的轉(zhuǎn)換,圖,定義一個(gè)圖G是由兩個(gè)集合V(G)和E(G)組成的，圖的二元組可定義為