1、 大學(xué)計(jì)算機(jī)基礎(chǔ) 第6章 數(shù)據(jù)結(jié)構(gòu)與算法 程序是什么？ 程序=數(shù)據(jù)結(jié)構(gòu)+算法！ 算法與數(shù)據(jù)結(jié)構(gòu)一覽表 DS算法算法定義、特性算法分析時(shí)間復(fù)雜度T(n)空間復(fù)雜度D(n)邏輯結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)網(wǎng)狀結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)順序存儲(chǔ)散列存儲(chǔ)查詢(xún)DS上的運(yùn)算插入刪除更新例：某校對(duì)100個(gè)學(xué)生進(jìn)行獎(jiǎng)勵(lì)，學(xué)生信息存在磁盤(pán)文件“file.dat”中，條件是其三門(mén)成績(jī)?nèi)吭?0分以上才能進(jìn)行獎(jiǎng)勵(lì)，打印出被獎(jiǎng)勵(lì)學(xué)生的學(xué)號(hào)。以C語(yǔ)言為例，程序代碼如下：#include Void main() struct stu /*數(shù)據(jù)類(lèi)型*/ int num; float score3; a100; /* 定義變量*/

2、FILE *fp； Int I,j; fp=fopen(“file.dat”,”r”); /* 打開(kāi)文件file.dat*/ for(i=0;i100;i+) Fread(&ai,sizeof(struct stu),1,fp); /* 從文件中讀取數(shù)據(jù)*/ for(j=0;j3;j+) if(ai.scorej=3) /* 如果符合條件，輸出其學(xué)號(hào)*/ printf(“num:%d”,ai.num); Fclose(fp); 由此可見(jiàn)，程序包括：對(duì)數(shù)據(jù)的描述，在程序中要指定數(shù)據(jù)的類(lèi)型和數(shù)據(jù)的組織形式。 對(duì)操作的描述，即對(duì)數(shù)據(jù)的操作處理步驟 第6章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)（data struc

3、ture） ： 對(duì)數(shù)據(jù)的描述。即在程序中要指定數(shù)據(jù)的類(lèi)型和數(shù)據(jù)的組織形式。算法（algorithm）： 對(duì)操作的描述。即對(duì)數(shù)據(jù)的操作處理步驟。程序：就是用計(jì)算機(jī)語(yǔ)言表示的數(shù)據(jù)結(jié)構(gòu)和算法。程序設(shè)計(jì)：用計(jì)算機(jī)語(yǔ)言編寫(xiě)程序的過(guò)程。兩個(gè)基本步驟： 1、設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和算法。 2、用一種計(jì)算機(jī)語(yǔ)言表示出來(lái)。 因此，數(shù)據(jù)結(jié)構(gòu)與算法是程序設(shè)計(jì)的基礎(chǔ)。 6.1 算 法 6.1.1 算法的基本概念 算法（algorithm）： 對(duì)操作的描述。即對(duì)數(shù)據(jù)的操作處理步驟。 算法的表示方法： 自然語(yǔ)言、流程圖、N-S流程圖、偽代碼、計(jì)算機(jī)語(yǔ)言案例：計(jì)算sum=1+2+3+n的算法一、用自然語(yǔ)言描述1、輸入n，即數(shù)據(jù)個(gè)數(shù)；

4、2、設(shè)置累加器sum，初始制為0；設(shè)置計(jì)數(shù)器i，初始值為1。3、當(dāng)i小于或等于n時(shí)，做累加，即將sum與i相加，其和再放入sum中。計(jì)數(shù)器i取下一個(gè)數(shù)，即i等于i+1，直到i大于n時(shí)終止。4、輸出累加和sum。二、流程圖描述：sum=1+2+3+n的算法開(kāi)始輸入nSum0i 1i=nSum sum+Ii i+1輸出sum結(jié)束否是三、N-S圖描述： sum=1+2+3+n的算法 N-S圖是美國(guó)學(xué)者I.Nassi和B.Shneiderman在1973年提出的一種流程圖，其主要特點(diǎn)是不帶有流程線，整個(gè)算法完全寫(xiě)在一個(gè)大的矩形框中。當(dāng)i=n時(shí)，做輸入nSum=0，i=1Sum=sum+Ii=i+1輸出

5、sum的值N-S圖方式四、偽代碼描述： sum=1+2+3+n的算法 就是用文字和符號(hào)的方式來(lái)描述算法。在實(shí)際應(yīng)用中，人們往往用接近于某種程序語(yǔ)言的代碼形式作為偽代碼。這樣可以方便編程。 偽代碼方式Input n sum=0 i=1 for i=1 to n do sum=sum+i print sumend五、計(jì)算機(jī)語(yǔ)言描述：程序用C語(yǔ)言描述sum=1+2+3+n的算法main() int n; int sum=0,i=1; scanf(“%d”,&n); for(i=1;i=n;i+) sum=sum+i; printf(“sum=%dn”,sum);一、算法的5個(gè)基本特征 1、可行性 2

6、、確定性 3、有窮性 4、有零個(gè)或多個(gè)輸入 5、有一個(gè)或多個(gè)輸出二、算法的2個(gè)基本要素 1、對(duì)數(shù)據(jù)的運(yùn)算和操作 2、算法的控制結(jié)構(gòu)。 算法的基本要素之一：對(duì)數(shù)據(jù)的運(yùn)算和操作 在計(jì)算機(jī)系統(tǒng)中，基本的運(yùn)算和操作有以下四類(lèi)： 算術(shù)運(yùn)算：主要包括加、減、乘、除等運(yùn)算。 邏輯運(yùn)算：主要包括“邏輯與”、“邏輯或”、“邏輯非” 等運(yùn)算。 關(guān)系運(yùn)算：主要包括“大于”、“大于或等于”、“小于”、 “小于或等于”、“等于”、“不等于”等運(yùn)算。 數(shù)據(jù)傳輸：主要包括賦值、輸入、輸出等操作。算法流程圖例子 算法的基本要素之二：算法的控制結(jié)構(gòu) 控制結(jié)構(gòu)-算法中各種操作步驟之間的執(zhí)行順序。 順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)三種基本

7、控制結(jié)構(gòu)算法流程圖例子三、算法設(shè)計(jì)的基本方法 六種：列舉法、歸納法、遞推、 遞歸、減半遞推技術(shù)、回溯法。 1、列舉法 列舉法就是根據(jù)所要解決的問(wèn)題，把所有可 能的情況都一一列舉出來(lái)，并用問(wèn)題中給定的條 件來(lái)檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的?、歸納法 歸納法的基本思想是通過(guò)列舉少量的特殊情況，經(jīng)過(guò)分析，最后找出一般的關(guān)系。 可以看出，歸納法可以解決列舉量為無(wú)限的問(wèn)題。 3、迭代法（遞推法） 遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。4、遞歸 在解決某些復(fù)雜問(wèn)題時(shí)，為了降低問(wèn)題的復(fù)雜程度（如問(wèn)題的規(guī)模等），可以將問(wèn)題逐層分解，最后歸結(jié)為一些最簡(jiǎn)單的問(wèn)題。例8.2 有5個(gè)人坐在一起，問(wèn)第

8、5個(gè)人多少歲?他說(shuō)比第4個(gè)人大2歲。問(wèn)第4個(gè)人的歲數(shù)，他說(shuō)比第3個(gè)人大2歲。問(wèn)第3個(gè)人，又說(shuō)比第2個(gè)人大2歲。問(wèn)第2個(gè)人，說(shuō)比第1個(gè)人大2歲。最后問(wèn)第1個(gè)人，他說(shuō)是10歲。請(qǐng)問(wèn)第5個(gè)人多大？ 用遞歸方法求解，遞歸過(guò)程如下： age（5）age（4）十2 age（4）=age（3）十2 age（3）age（2）十2 age（2）age（1）十2 age（l）105、減半遞推技術(shù) “減半”是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變； “遞推”是指重復(fù)“減半”的過(guò)程。 例8.3 設(shè)方程f（x）=0在區(qū)間 a，b上有實(shí)根，且f（a）與f（b） 符號(hào)相反，即f（a）f（b）0。利用二分法求該方程在區(qū)間 a，

9、b上的一個(gè)實(shí)根。 用二分法求方程實(shí)根的減半遞推過(guò)程如下： 首先計(jì)算區(qū)間的中點(diǎn)c=（a+b）/2，然后計(jì)算函數(shù)在中點(diǎn)c的值f（c），并判斷f （c）是否為0。若f（c）=0，則說(shuō)明c就是所求的根，求解過(guò)程結(jié)束；如果f （c）0，則根據(jù)以下原則將原區(qū)間減半： 若f（a）f（c）0，則取原區(qū)間的前半部分，； 若f（b）f（c）0，則取原區(qū)間的后半部分。 最后根據(jù)計(jì)算精度 的要求，判斷減半后的區(qū)間長(zhǎng)度是否已經(jīng)很小： 若|ab|，則過(guò)程結(jié)束，?。╝+b）/2為根的近似值； 若|ab| ，則重復(fù)上述的減半過(guò)程。 6、回溯法 對(duì)于某些問(wèn)題，一種有效的方法是“試”，即通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，

10、然后沿著這個(gè)線索逐步試探，對(duì)于每一步的試探，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。這種方法稱(chēng)為回溯法?；厮莘ㄔ谔幚韽?fù)雜數(shù)據(jù)結(jié)構(gòu)方面有著廣泛的應(yīng)用。 6.1 算 法 6.1.1 算法的基本概念 一、算法的基本特征 1、可行性 2、確定性 3、有窮性 4、有零個(gè)或多個(gè)輸入 5、有一個(gè)或多個(gè)輸出 二、算法的基本要素 1、對(duì)數(shù)據(jù)的運(yùn)算和操作 2、算法的控制結(jié)構(gòu) 三、算法設(shè)計(jì)的基本方法 列舉法、歸納法、遞推、遞歸、減半遞推技術(shù)、回溯法 小結(jié)： 選用算法首先考慮正確性，還要考慮執(zhí)行算法所耗費(fèi)的時(shí)間和存儲(chǔ)空間，同時(shí)算法應(yīng)易于理解、編碼、調(diào)試等。 算法的復(fù)雜度可分為時(shí)間復(fù)雜

11、度和空間復(fù)雜度，是衡量算法優(yōu)劣的度量。8.1 算法8.1.2 算法的復(fù)雜度 一、算法的時(shí)間復(fù)雜度 算法的時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量。 算法的計(jì)算工作量：用算法所執(zhí)行的基本運(yùn)算次數(shù)來(lái)度量， 基本運(yùn)算次數(shù)：是問(wèn)題規(guī)模的函數(shù)。 則：算法的計(jì)算工作量=f（n），其中n是問(wèn)題的規(guī)模。（1） 平均性態(tài) （Average Behavior） 平均性態(tài)分析是指用各種特定輸入下的基本運(yùn)算次數(shù)的加權(quán)平均值來(lái)度量算法的工作量。假設(shè)x是所有可能輸入中的某個(gè)特定輸入，用p（x）表示x出現(xiàn)的概率（即輸入為x的概率），用t（x）表示算法在輸入為x時(shí)所執(zhí)行的基本運(yùn)算次數(shù)，則算法的平均性態(tài)定義為 在分析一個(gè)給定問(wèn)題

12、算法的時(shí)間復(fù)雜度時(shí)，可以采用下面兩種方法來(lái)分析算法的工作量。 其中Dn表示當(dāng)規(guī)模為n時(shí)，算法執(zhí)行時(shí)所有可能輸入的集合。（2）最壞情況復(fù)雜性（Worst-Case Complexity） 最壞情況分析是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。它定義為 其中，Dn和t（x）的含義同上?？梢钥闯?，最壞情況分析W（n）的計(jì)算要比平均性態(tài)分析A（n）的計(jì)算方便得多。 實(shí)際上，W（n）給出了估計(jì)算法工作量的一個(gè)上界，因此，它比A（n）更具有實(shí)用價(jià)值，是分析算法的時(shí)間復(fù)雜度常用的一個(gè)方法。 算法的執(zhí)行時(shí)間依賴(lài)于具體的軟硬件環(huán)境，所以，不能用執(zhí)行時(shí)間的長(zhǎng)短來(lái)衡量算法的時(shí)間復(fù)雜度，而要通過(guò)基本語(yǔ)句執(zhí)行次

13、數(shù)的數(shù)量級(jí)來(lái)衡量。求解算法的時(shí)間復(fù)雜度的具體步驟是： 找出算法中的基本語(yǔ)句；算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句，通常是最內(nèi)層循環(huán)的循環(huán)體。 計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)；只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。 用大記號(hào)表示算法的時(shí)間性能。將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入大記號(hào)中。時(shí)間復(fù)雜度計(jì)算步驟：如果算法中包含嵌套的循環(huán)，則基本語(yǔ)句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時(shí)間復(fù)雜度相加。例如：for (i=1

14、; i=n; i+)x+;for (i=1; i=n; i+) for (j=1; j=n; j+) x+;第一個(gè)for循環(huán)的時(shí)間復(fù)雜度為(n)，第二個(gè)for循環(huán)的時(shí)間復(fù)雜度為(n2)，則整個(gè)算法的時(shí)間復(fù)雜度為(n+n2)=(n2)。算法時(shí)間復(fù)雜度舉例：常見(jiàn)的算法時(shí)間復(fù)雜度：常見(jiàn)的算法時(shí)間復(fù)雜度由小到大依次為：(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!) (1)表示基本語(yǔ)句的執(zhí)行次數(shù)是一個(gè)常數(shù)，一般來(lái)說(shuō)，只要算法中不存在循環(huán)語(yǔ)句，其時(shí)間復(fù)雜度就是(1)。 (log2n)、(n)、(nlog2n)、(n2)和(n3)稱(chēng)為多項(xiàng)式時(shí)間，而(2n)和(n!)稱(chēng)為指數(shù)時(shí)間。

15、計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者是有效算法，把這類(lèi)問(wèn)題稱(chēng)為P類(lèi)問(wèn)題，而把后者稱(chēng)為NP問(wèn)題。“如果算法的執(zhí)行時(shí)間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)?！?Temp=i; i=j; j=temp; 總共由3條語(yǔ)言,每條的頻度均為1,每條的頻度可認(rèn)為都是O(1),那么T(n)=O(1)+O(1)+O(1)=O(1)。 下面4條語(yǔ)句: scanf(“%d”,&n); i=n; for(i=0,in;i+) i= i*1; (這也只算是一句) for(將j=0,jn*n;j+) i=i*1;(同上) 前兩條頻度均為1; 后兩條分別

16、頻度為 n和n*n 那么總頻度均為 O(1)+O(1)+O(n)+O(n*n)=O(n*n) 1. 交換i和j的內(nèi)容 sum=0；（一次） for(i=1;i=n;i+)（n次 ） for(j=1;j=n;j+) （n2次 ） sum+；（n2次 ）解：T(n)=2n2+n+1 =O(n2)2. for (i=1;in;i+) y=y+1; for (j=0;j=(2*n);j+) x+; 解：語(yǔ)句1的頻度是n-1語(yǔ)句2的頻度是(n-1)*(2n+1)=2n2-n-1 f(n)=2n2-n-1+(n-1)=2n2-2該程序的時(shí)間復(fù)雜度T(n)=O(n2). a=0; b=1; for (i=1

17、;in;i+) s=a+b; b=a; a=s; 解：語(yǔ)句1的頻度：2,語(yǔ)句2的頻度： n,語(yǔ)句3的頻度： n-1,語(yǔ)句4的頻度：n-1, 語(yǔ)句5的頻度：n-1T(n)=2+n+3(n-1)=4n-1=O(n). 2算法的空間復(fù)雜度 -執(zhí)行這個(gè)算法所需要的內(nèi)存空間。 類(lèi)似算法的時(shí)間復(fù)雜度，空間復(fù)雜度作為算法所需存儲(chǔ)空間的度量。 6.1 算法課堂練習(xí)題考題(2005_4):(11)算法具有五個(gè)特性,以下選項(xiàng)中不屬于算法特性的是 (A)有窮性 (B)簡(jiǎn)潔性 (C)可行性 (D)確定性 答案：B 考題（2005_4）5.問(wèn)題處理方案的正確而完整的描述稱(chēng)為_(kāi)答案： 算法考題（2005_9）（1）算法復(fù)

18、雜度主要包括時(shí)間復(fù)雜度和_復(fù)雜度。答案：空間6.2 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究三個(gè)問(wèn)題:1、數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；2、在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；3、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。6.2.1 什么是數(shù)據(jù)結(jié)構(gòu)？例6.5 無(wú)序表的順序查找與有序表的對(duì)分查找?，F(xiàn)實(shí)世界中存在的一切個(gè)體都可以是數(shù)據(jù)元素。例如：“春、夏、秋、冬”，可以作為季節(jié)的數(shù)據(jù)元素； “26、56、65、 73、26、”，可以作為數(shù)值的數(shù)據(jù)元素； “父親、兒子、女兒”，可以作為家庭成員的數(shù)據(jù)元素。 在數(shù)據(jù)處理領(lǐng)域中，每一個(gè)需要處理的對(duì)象都可以抽象成數(shù)據(jù)元素。數(shù)

19、據(jù)元素一般簡(jiǎn)稱(chēng)為元素。在具有相同特點(diǎn)的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在著某種關(guān)系（即聯(lián)系），這種關(guān)系反映了數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。 在數(shù)據(jù)處理中，通常把數(shù)據(jù)元素之間這種固有的關(guān)系簡(jiǎn)單地用前后件關(guān)系（或直接前驅(qū)與直接后繼關(guān)系）來(lái)描述。例如： 在“春、夏、秋、冬” 中，“春”是“夏”前件，。 一般來(lái)說(shuō)，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。1數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。這里所說(shuō)的結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。由此可見(jiàn)，一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含如下兩種信息： 表示數(shù)據(jù)元素的信息； 表示各數(shù)據(jù)元素之間的前后件關(guān)系。數(shù)據(jù)元素之間的前后件關(guān)系是指它們的邏輯關(guān)系

20、，這與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。 由前面的敘述可以看出，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)基本要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。因此，一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成 B=（D，R），其中B表示數(shù)據(jù)的邏輯結(jié)構(gòu)。例 一年四季的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示成 B=（D，R） D=春，夏，秋，冬 R=（春，夏），（夏，秋），（秋，冬）例 家庭成員的數(shù)據(jù)邏輯結(jié)構(gòu)可以表示成 B=（D， R） D=父親，兒子，女兒 R=（父親，兒子），（父親，女兒）2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放

21、形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（也稱(chēng)數(shù)據(jù)的物理結(jié)構(gòu)）。在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需 要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以表示成多種存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。對(duì)于一種數(shù)據(jù)的邏輯結(jié)構(gòu)，如果采用不同的存儲(chǔ)結(jié)構(gòu)，則數(shù)據(jù)處理的效率是不同的。因此，在進(jìn)行數(shù)據(jù)處理時(shí)，選擇合適的存儲(chǔ)結(jié)構(gòu)是非常重要的。6.2.2 數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)結(jié)構(gòu)除了可以用前面的所述的二元關(guān)系表示外，還可以用圖形來(lái)表示。例 n維向量 X = (x1,x2,xn) 也是一種數(shù)據(jù)結(jié)構(gòu)。即X = (D,R)，其中數(shù)據(jù)元素的集合為： D = x1,x2,xn 關(guān)系為： R

22、= (x1,x2),(x2,x3),(xn 1,xn)例如，mn的矩陣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ù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為： D = A1，A2，AmD上的一個(gè)關(guān)系為： R = (A1，A2)，(A2，A3)，(Ai，Ai+1)，(Am 1，Am)顯然，數(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)，(aij,ai,j

23、+ 1)，(ai,n 1，ain)一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。 例 用圖形表示數(shù)據(jù)結(jié)構(gòu)B =（D，R），其中 D = di |1i7 = d1，d2，d3，d4，d5，d6，d7 R = (d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5) 這個(gè)數(shù)據(jù)結(jié)構(gòu)的圖形表示如圖所示。6.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類(lèi)：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）有且只有一個(gè)終端結(jié)點(diǎn)；（3）除根結(jié)點(diǎn)外，其他結(jié)點(diǎn)均只有一個(gè)前件；（4）除

24、終端結(jié)點(diǎn)外，其他結(jié)點(diǎn)均只有一個(gè)后件。則稱(chēng)該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱(chēng)線性表。例如，如圖所示的數(shù)據(jù)結(jié)構(gòu)顯然是滿足上述兩個(gè)條件的，但它不屬于線性結(jié)構(gòu)這個(gè)類(lèi)型，因?yàn)槿绻谶@個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除結(jié)點(diǎn)A后，就不滿足上述的條件。一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱(chēng)之為非線性結(jié)構(gòu)。 線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來(lái)處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。課堂練習(xí)：6.2 數(shù)據(jù)結(jié)構(gòu)的基本概念考題（2005_4）:(1)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指 (A)存儲(chǔ)在外存中的數(shù)據(jù)(B)數(shù)據(jù)所占的存儲(chǔ)空間量 (C)數(shù)據(jù)在計(jì)算機(jī)中的順序存儲(chǔ)方式(D)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示

25、答案：D考題（2005_9）:(4)下列敘述正確的是( )。A)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)只能有一種存儲(chǔ)結(jié)構(gòu)B) 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)屬于非線性結(jié)構(gòu)C)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)不影響數(shù)據(jù)處理的效率D)一個(gè)邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲(chǔ)結(jié)構(gòu)，且各種存儲(chǔ)結(jié)構(gòu)影響數(shù)據(jù)處理的效率答案：D數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無(wú)向圖樹(shù)形結(jié)構(gòu)一般樹(shù)二叉樹(shù)線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列圖1-5 數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖圖1-4 邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性表樹(shù)圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)一個(gè)數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素在計(jì)算機(jī)存

26、儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系是有可能不同的。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。 常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引、散列等存儲(chǔ)結(jié)構(gòu)。 順序存儲(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)。右圖是將線性結(jié)構(gòu)(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)順序地存放在存儲(chǔ)單元中的示意圖。 （1）順序存儲(chǔ)結(jié)構(gòu)在鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)

27、存儲(chǔ)結(jié)點(diǎn)要有兩部分組成：一部分用于存放數(shù)據(jù)信息，另一部分用于存放指針。其中指針用于指向該結(jié)點(diǎn)的前件或后件。 （2）鏈接存儲(chǔ)結(jié)構(gòu)利用鏈接存儲(chǔ)方式也可以存儲(chǔ)非線性結(jié)構(gòu)。下圖（a）和（b）分別為一棵二叉樹(shù)的邏輯結(jié)構(gòu)與鏈接存儲(chǔ)結(jié)構(gòu)的示意圖。 6.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)6.3.1 線性表的基本概念 線性表（Linear List）是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。所謂線性表，是指n個(gè)數(shù)據(jù)元素的有限序列。 線性表可以表示為 （a1，a2，ai，an），其中ai是屬于數(shù)據(jù)對(duì)象的元素，通常也稱(chēng)其為線性表中的一個(gè)結(jié)點(diǎn)。 當(dāng)n=0時(shí)，稱(chēng)為空表。 6.3.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 在計(jì)算機(jī)中存放線性表，一種最簡(jiǎn)單

28、的方法是順序存儲(chǔ)。其特點(diǎn)如下：（1）線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；（2）線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。 對(duì)于線性表的順序存儲(chǔ)結(jié)構(gòu)，可以進(jìn)行各種處理。 下面主要討論線性表在順序存儲(chǔ)結(jié)構(gòu)下的插入與刪除運(yùn)算。 下面通過(guò)一個(gè)例子來(lái)說(shuō)明如何在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)新元素。 例 下圖 （a）是為一個(gè)長(zhǎng)度為5的線性表順序存儲(chǔ)在長(zhǎng)度為8的存儲(chǔ)空間中。 例 圖（a）是一個(gè)長(zhǎng)度為7的線性表順序存儲(chǔ)在長(zhǎng)度為8的存儲(chǔ)空間中?，F(xiàn)在要求刪除表中的第2個(gè)元素（即刪除元素23）。考題（2005_4）(5)下列對(duì)于線性表的描述中正確的是 A)存儲(chǔ)空間不一定是連續(xù),且各元素的存儲(chǔ)順序是任

29、意的 B)存儲(chǔ)空間不一定是連續(xù),且前件元素一定存儲(chǔ)在后件元素的前面 C)存儲(chǔ)空間必須連續(xù),且各前件元素一定存儲(chǔ)在后件元素的前面 D)存儲(chǔ)空間必須連續(xù),且各元素的存儲(chǔ)順序是任意的答案：A課堂練習(xí)：6.3 線性表及其順序存儲(chǔ)結(jié)構(gòu)6.4 棧和隊(duì)列6.4.1 棧及其基本運(yùn)算 1棧的基本概念 棧（stack）是限定僅在一端進(jìn)行插入和刪除運(yùn)算的線性表。 在棧中，允許插入與刪除的一端稱(chēng)為棧頂，而不允許插入與刪除的另一端稱(chēng)為棧底。 1棧的基本概念棧的順序存儲(chǔ)結(jié)構(gòu)如圖所示。6.4.1 棧及其基本運(yùn)算 1棧的基本概念 2棧的基本運(yùn)算棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。（1） 入棧運(yùn)算入棧運(yùn)算是指在棧頂位置

30、插入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂指針進(jìn)一，然后將新元素插入到棧頂指針指向的位置；6.4.1 棧及其基本運(yùn)算 （2） 退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給某個(gè)變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素賦給一個(gè)指定的變量，然后將棧頂指針退一。6.4.1 棧及其基本運(yùn)算 （3） 讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。在這個(gè)運(yùn)算中，棧頂指針不會(huì)改變。例 在下圖中，設(shè)top為指向棧頂元素的指針。（a） 為容量為8的棧順序存儲(chǔ)空間，棧中已有4個(gè)元素；（b）與圖（c）分別為入棧與退棧后的狀態(tài)。考題（2005_4）(2)下列關(guān)于棧的描述中錯(cuò)誤的是(A)棧是先進(jìn)后出的線性表

31、 (B)棧只能順序存儲(chǔ) (C)棧具有記憶作用 (D)對(duì)棧的插入和刪除操作中，不需要改變棧底指針答案：B分析： 棧：特殊的線性表。限定只在一端進(jìn)行插入與刪除的線性表，這一端稱(chēng)為棧頂，另一端稱(chēng)為棧底。棧是按照“先進(jìn)后出”或“后進(jìn)先出”的原則組織數(shù)據(jù)的。棧具有記憶作用。6.4.2 隊(duì)列及其基本運(yùn)算1隊(duì)列的基本概念隊(duì)列（queue）是限定僅在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除的線性表。在隊(duì)列中，允許插入的一端稱(chēng)為隊(duì)尾， 允許刪除的一端稱(chēng)為隊(duì)頭。隊(duì)列又稱(chēng)為“先進(jìn)先出”或“后進(jìn)后出”的線性表。在隊(duì)列中，通常用指針front 指向隊(duì)頭，用rear指向隊(duì)尾，如圖所示。1隊(duì)列的基本概念下圖是在隊(duì)列中進(jìn)行插

32、入與刪除的示意圖。 考題（2005_9）（3）以下關(guān)于棧的描述正確的是( )。A)在棧中只能插入元素而不能刪除元素B)在棧中只能刪除元素而不能插入C)棧是特殊的線性表，只能在一端插入或刪除元素D)棧是特殊的線性表，只能在一端插入元素，而在另一端刪除元素答案：C考題（2005_9）（5）數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，循環(huán)隊(duì)列屬于_結(jié)構(gòu)。答案：存儲(chǔ)6.6 樹(shù)與二叉樹(shù) 6.6.1 樹(shù)的基本概念樹(shù)（tree）是一種非線性結(jié)構(gòu)。在樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中，所有數(shù)據(jù)元素之間的關(guān)系具有明顯的層次特點(diǎn)。下圖表示了一棵一般的樹(shù)。圖6.22 樹(shù)的結(jié)構(gòu)圖實(shí)際上，能用樹(shù)結(jié)構(gòu)表示的例子有許多。例如，下圖中的樹(shù)表示了學(xué)校行政關(guān)

33、系結(jié)構(gòu)。 圖8.23 學(xué)校行政層次結(jié)構(gòu)樹(shù)在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱(chēng)為父結(jié)點(diǎn)，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱(chēng)為根結(jié)點(diǎn)（簡(jiǎn)稱(chēng)根）。例如，在下圖中，結(jié)點(diǎn)A是樹(shù)的根結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。例如，在下圖中，結(jié)點(diǎn)E、F、G、H、I、J均為葉子結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中，個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度。例如，在下圖中，根結(jié)點(diǎn)A的度為3；結(jié)點(diǎn)B的度為2；結(jié)點(diǎn)C的度為1；葉子結(jié)點(diǎn)的度為0。在樹(shù)結(jié)構(gòu)中，所有結(jié)點(diǎn)中的最大的度稱(chēng)為樹(shù)的度。例如，下圖所示的樹(shù)的度為3。下面介紹樹(shù)這種數(shù)據(jù)結(jié)構(gòu)中的一些基本特征和基本術(shù)語(yǔ)由于樹(shù)結(jié)構(gòu)具有明顯的層次關(guān)

34、系，即樹(shù)是一種層次結(jié)構(gòu)，所以在樹(shù)結(jié)構(gòu)中，一般按如下原則分層：根結(jié)點(diǎn)在第1層。同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)都在下一層。例如，在下圖中，根結(jié)點(diǎn)A在第1層；結(jié)點(diǎn)B、C、D在第2層；結(jié)點(diǎn)E、F、G、H、I、J在第3層。 樹(shù)的最大層數(shù)稱(chēng)為樹(shù)的深度。例如，下圖所示的樹(shù)的深度為3。 在樹(shù)結(jié)構(gòu)中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)稱(chēng)為該結(jié)點(diǎn)的一棵 子樹(shù)。例如，在下圖中：根結(jié)點(diǎn)A有3棵子樹(shù)，它們分別以B、C、D為根結(jié)點(diǎn)；結(jié)點(diǎn)B有2棵子樹(shù)，它們分別以E、F為根結(jié)點(diǎn)。在樹(shù)結(jié)構(gòu)中，葉子結(jié)點(diǎn)沒(méi)有子樹(shù)。6.6.2 二叉樹(shù)及其基本運(yùn)算1二叉樹(shù)的基本概念 二叉樹(shù)（binary tree）是一種非常用的非線性數(shù)據(jù)結(jié)構(gòu)。二叉樹(shù)與前

35、面介紹的樹(shù)結(jié)構(gòu)不同，但它與樹(shù)結(jié)構(gòu)很相似，并且，有關(guān)樹(shù)結(jié)構(gòu)的所有術(shù)語(yǔ)都可以用到二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)上。二叉樹(shù)具有以下兩個(gè)特點(diǎn)： 非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)； 每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。 右圖所示是一顆二叉樹(shù)，根結(jié)點(diǎn)為A，其左子樹(shù)包含結(jié)點(diǎn)B、D、G、H，右子樹(shù)包含結(jié)點(diǎn)C、E、F、I、J。根A的左子樹(shù)又是一顆二叉樹(shù)，其根結(jié)點(diǎn)為B，有非空的左子樹(shù)（由結(jié)點(diǎn)D、G、H組成）和空的右子樹(shù)。根A的右子樹(shù)也是一顆二叉樹(shù)，其根結(jié)點(diǎn)C，有非空的左子樹(shù)（由結(jié)點(diǎn)E、I、J組成）和右子樹(shù)（由結(jié)點(diǎn)F組成）。 在二叉樹(shù)中，一個(gè)結(jié)點(diǎn)可以只有左子樹(shù)而沒(méi)有右子樹(shù)，也可以只有右子樹(shù)而沒(méi)有左子樹(shù)。例如，下

36、圖中所示的是4顆不同的二叉樹(shù)，但如果作為樹(shù)，它們就相同了。 4顆不同的二叉樹(shù)2滿二叉樹(shù)與完全二叉樹(shù)滿二叉樹(shù)與完全二叉樹(shù)是兩種特殊的二叉樹(shù)。（1） 滿二叉樹(shù) 在一顆二叉樹(shù)中，如果所有分支結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上，這樣的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。圖（a）、（b）分別是深度為2、3的滿二叉樹(shù)。（2） 完全二叉樹(shù) 完全二叉樹(shù)是指除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值，而在最后一層上只缺少右邊的若干結(jié)點(diǎn)。顯然，滿二叉樹(shù)也是完全二叉樹(shù)，而完全二叉樹(shù)不一定是滿二叉樹(shù)。下圖是兩顆深度為3的完全二叉樹(shù)。3二叉樹(shù)的基本性質(zhì)二叉樹(shù)具有下列重要性質(zhì)：性質(zhì)1 在二叉樹(shù)中，第i層的結(jié)點(diǎn)數(shù)最多為

37、2i-1個(gè)（i1）。性質(zhì)2 在深度為k的二叉樹(shù)中，結(jié)點(diǎn)總數(shù)最多為2k-1個(gè)（k1）。20+21+22+。+2K-1=2K-1例如，在下圖所示的二叉樹(shù)中，有5個(gè)葉子結(jié)點(diǎn)，有4個(gè)度為2的結(jié)點(diǎn)，度為0的結(jié)點(diǎn)比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)3 對(duì)任意一棵二叉樹(shù)，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4 （1）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為log2n+1，其中l(wèi)og2n表示取log2n的整數(shù)部分。（2）具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1。6.6.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用于存儲(chǔ)二叉樹(shù)中各元素的存儲(chǔ)結(jié)點(diǎn)由兩部分組成：數(shù)據(jù)域與指針域。 由于在二叉樹(shù)的存儲(chǔ)

38、結(jié)構(gòu)中每個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域，因此，二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱(chēng)為二叉鏈表。下圖表示二叉鏈表的存儲(chǔ)示意圖。6.6.4 二叉樹(shù)的遍歷遍歷是二叉樹(shù)的重要運(yùn)算。二叉樹(shù)的遍歷是指按一定的次序訪問(wèn)二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且只被訪問(wèn)一次。在遍歷二叉樹(shù)的過(guò)程中，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。在先左后右的原則下，根據(jù)訪問(wèn)根結(jié)點(diǎn)的次序，二叉樹(shù)的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。下面分別介紹這三種遍歷的方法，并用D、L、R分別表示“訪問(wèn)根結(jié)點(diǎn)”、“遍歷根結(jié)點(diǎn)的左子樹(shù)”和“遍歷根結(jié)點(diǎn)的右子樹(shù)”。1前序遍歷（DLR）前序遍歷是指首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)；并且，

39、在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)例如，對(duì)如圖中的二叉樹(shù)進(jìn)行前序遍歷，則遍歷的結(jié)果為ABDGCEHIF。2中序遍歷（LDR） 中序遍歷是指首先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)；并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹(shù)。例如，對(duì)圖中的二叉樹(shù)進(jìn)行中序遍歷，則遍歷結(jié)果為DGBAHEICF。3后序遍歷（LRD）后序遍歷是指首先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)，并且，在遍歷左、右子樹(shù)時(shí)，仍然先遍歷左子樹(shù)，然后遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。例如，對(duì)圖中的二叉樹(shù)進(jìn)行后序遍歷，則遍歷結(jié)果為GDBHIEFCA。考題（2005_

40、4）1.某二叉樹(shù)中度為2的結(jié)點(diǎn)有18個(gè)，則該二叉樹(shù)中有_1_個(gè)葉子結(jié)點(diǎn)。答案：19考題（2005_4）（4）一棵二叉樹(shù)第六層（根結(jié)點(diǎn)為第一層）的結(jié)點(diǎn)數(shù)最多為_(kāi)個(gè)。答案：326.7 查找與排序技術(shù)6.7.1 順序查找順序查找又稱(chēng)為順序搜索。順序查找一般是指在線性表中查找指定的元素，基本方法如下：從線性表的第一個(gè)元素開(kāi)始，依次將線性表中的元素與被查找元素進(jìn)行比較，若相等則表示找到（即查找成功）；若線性表中所有的元素都與被查元素進(jìn)行了比較，但都不相等，則表示線性表中沒(méi)有要查找的元素（即查找失敗）。6.7.2 二分法查找二分法查找只適用于順序存儲(chǔ)的有序表，即要求線性表中的元素按元素值的大小排列（遞減排

41、列或遞增排列）。假設(shè)有序線性表是按元素值遞增排列的，并設(shè)表的長(zhǎng)度為n，被查元素為x，則二分法查找過(guò)程如下：將x與線性表的中間元素進(jìn)行比較：若中間元素的值等于x，則說(shuō)明查成功，查找結(jié)束；若x小于中間元素的值，則在線性表的前半部分以相同的方法查找；若x大于中間元素的值，則在線性表的后半部分以相同的方法查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說(shuō)明線性表中沒(méi)有這個(gè)元素）為止。可以看出，當(dāng)有序的線性表為順序存儲(chǔ)時(shí)才能采用二分查找?？梢宰C明，對(duì)于長(zhǎng)度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，順序查找需要比較n次?？梢?jiàn)，二分查找的效率要比順序查找高得多。6.7.3 交換類(lèi)排序法

42、1冒泡排序法冒泡排序法是一種最簡(jiǎn)單的交換類(lèi)排序方法，它是通過(guò)相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序的。冒泡排序法的操作過(guò)程如下：首先，從表頭開(kāi)始往后掃描線性表，在掃描過(guò)程中依次比較相鄰兩元素的大小，若前面的元素大于后面的元素，則將它們互換，稱(chēng)之為消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的大者往后移動(dòng)，最后就將線性表中的最大者換到了表的最后。然后，按相反的方向掃描剩下的線性表，在掃描過(guò)程中依次比較相鄰兩個(gè)元素的大小，若后面的元素小于前面的元素，則將它們互換，這樣就又消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的小者往前移動(dòng)，最后就將剩下的線性表中的最小者換到了表的最前

43、面。此時(shí)，線性表的第一個(gè)元素就是最小者，最后一個(gè)元素就是最大者。對(duì)剩下的元素構(gòu)成的線性表重復(fù)上述過(guò)程，直到剩下的元素為空或者在掃描過(guò)程中沒(méi)有交換任何元素，此時(shí)，線性表變?yōu)橛行颉?圖8.32是冒泡排序法的示意圖。圖中有下劃線的元素表示掃描過(guò)程中的第一個(gè)和最后一個(gè)元素的位置。 從冒泡排序法的操作過(guò)程可以看出，對(duì)長(zhǎng)度為n的線性表，在最壞的情況下需要進(jìn)行（n-1）+（n-2）+2+1=n（n-1）/2次比較。原序列628131957第1遍（從前往后）261318579（從后往前）126135879第2遍（從前往后）121356789（從后往前）112356789第3遍（從前往后）112356789最后

44、結(jié)果1123567898.32冒泡排序示意圖2快速排序法 快速排序法是對(duì)冒泡排序法的改進(jìn)，又叫作分區(qū)交換排序法?？焖倥判蚍ǖ幕舅枷肴缦拢?從線性表中任意選取一個(gè)元素（通常選第一個(gè)元素），設(shè)為T(mén)，將線性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，結(jié)果就將線性表分成了兩部分（稱(chēng)為兩個(gè)子表），T處于分界線的位置處，這個(gè)過(guò)程稱(chēng)為線性表的分割。通過(guò)對(duì)線性表的一次分割，就以T為分界線，將線性表分成了前后兩個(gè)子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。 如果對(duì)分割后的各子表再按上述原則進(jìn)行分割，并且，這種分割過(guò)程可以一直做下去，直到所有子表為空為止，此時(shí)的線性表

45、就變成了有序表。設(shè)當(dāng)前要排序的線性表的下界為low，上界為high，則分割操作的步驟如下：（1）設(shè)兩個(gè)指針i和j分別指向線性表的第一個(gè)元素和最后一個(gè)元素，即P（i）=low；P（j）=high，并將第一個(gè)元素保存在T中。（2）用T與j指向的元素比較，若TP（j），則讓j指向前一個(gè)元素，再比較；否則將P（j）和P（i）互換位置。（3）用T與i指向的元素比較，若TP（i），則讓i指向后一個(gè)元素，再比較；否則將P（j）和P（i）互換位置。（4）反復(fù)進(jìn)行（2）和（3）兩步操作，直到i和j指向同一個(gè)元素，即i=j時(shí)，分割結(jié)束。i所指向的元素就是T應(yīng)該放置的位置。下面舉例說(shuō)明快速排序法。設(shè)線性表為（33

46、18 22 88 38 14 55 13 47），若選第一個(gè)元素33為T(mén)，則第一次排序過(guò)程如圖8.33（a）所示。對(duì)線性表進(jìn)行完一次快速排序后，用同樣的方法對(duì)分割后的子表進(jìn)行快速排序，直到各個(gè)子表的長(zhǎng)度為1為止。排序過(guò)程如圖8.33（b）所示。6.7.3 插入類(lèi)排序法1簡(jiǎn)單插入排序法 簡(jiǎn)單插入排序法也叫直接插入排序法。插入排序是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。 圖8.34給出了插入排序的示意圖。圖中方括號(hào) 中為已排好序的元素。 在簡(jiǎn)單插入排序法中，每一次比較后最多移掉一個(gè)逆序，因此，這種排序方法的效率與冒泡排序法相同。在最壞情況下，簡(jiǎn)單插入排序需要n（n-1）/2次比較。2希爾排序法 希爾排序法（Shell Sort）又稱(chēng)縮小增量排序法，它對(duì)簡(jiǎn)單插入排序做了較大的改進(jìn)。 其方法如下： 將整個(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行簡(jiǎn)單插入排序。 子序列的分割方法如下： 使相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后