數(shù)據(jù)結(jié)構(gòu)與算法1

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

2、FILE *fp； Int I,j; fp=fopen(“file.dat”,”r”); /* 打開文件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) /* 如果符合條件，輸出其學號*/ printf(“num:%d”,ai.num); Fclose(fp); 由此可見，程序包括：對數(shù)據(jù)的描述，在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式。 對操作的描述，即對數(shù)據(jù)的操作處理步驟 第6章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)（data struc

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

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

5、sum的值N-S圖方式四、偽代碼描述： sum=1+2+3+n的算法 就是用文字和符號的方式來描述算法。在實際應用中，人們往往用接近于某種程序語言的代碼形式作為偽代碼。這樣可以方便編程。 偽代碼方式Input n sum=0 i=1 for i=1 to n do sum=sum+i print sumend五、計算機語言描述：程序用C語言描述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個基本特征 1、可行性 2

6、、確定性 3、有窮性 4、有零個或多個輸入 5、有一個或多個輸出二、算法的2個基本要素 1、對數(shù)據(jù)的運算和操作 2、算法的控制結(jié)構(gòu)。 算法的基本要素之一：對數(shù)據(jù)的運算和操作 在計算機系統(tǒng)中，基本的運算和操作有以下四類： 算術(shù)運算：主要包括加、減、乘、除等運算。 邏輯運算：主要包括“邏輯與”、“邏輯或”、“邏輯非” 等運算。 關系運算：主要包括“大于”、“大于或等于”、“小于”、 “小于或等于”、“等于”、“不等于”等運算。 數(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ù)、回溯法。 1、列舉法 列舉法就是根據(jù)所要解決的問題，把所有可 能的情況都一一列舉出來，并用問題中給定的條 件來檢驗哪些是需要的，哪些是不需要的。2、歸納法 歸納法的基本思想是通過列舉少量的特殊情況，經(jīng)過分析，最后找出一般的關系。 可以看出，歸納法可以解決列舉量為無限的問題。 3、迭代法（遞推法） 遞推是指從已知的初始條件出發(fā)，逐步推出所要求的結(jié)果。4、遞歸 在解決某些復雜問題時，為了降低問題的復雜程度（如問題的規(guī)模等），可以將問題逐層分解，最后歸結(jié)為一些最簡單的問題。例8.2 有5個人坐在一起，問第

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

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

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

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

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

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

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

15、計算機科學家普遍認為前者是有效算法，把這類問題稱為P類問題，而把后者稱為NP問題?！叭绻惴ǖ膱?zhí)行時間不隨著問題規(guī)模n的增加而增長，即使算法中有上千條語句，其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復雜度是O(1)?！?Temp=i; i=j; j=temp; 總共由3條語言,每條的頻度均為1,每條的頻度可認為都是O(1),那么T(n)=O(1)+O(1)+O(1)=O(1)。 下面4條語句: 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+; 解：語句1的頻度是n-1語句2的頻度是(n-1)*(2n+1)=2n2-n-1 f(n)=2n2-n-1+(n-1)=2n2-2該程序的時間復雜度T(n)=O(n2). a=0; b=1; for (i=1

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

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

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

20、，這與它們在計算機中的存儲位置無關。數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關系的數(shù)據(jù)結(jié)構(gòu)。 由前面的敘述可以看出，數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個基本要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關系，它反映了D中各數(shù)據(jù)元素之間的前后件關系，通常記為R。因此，一個數(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ù)的存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放

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

22、= (x1,x2),(x2,x3),(xn 1,xn)例如，mn的矩陣mn的矩陣是一個數(shù)據(jù)結(jié)構(gòu)。在這個數(shù)據(jù)結(jié)構(gòu)中，矩陣的每一行 Ai = (ai1，ai2，ain)，i = 1,2,m可以看成是它的一個數(shù)據(jù)元素。即這個數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為： D = A1，A2，AmD上的一個關系為： R = (A1，A2)，(A2，A3)，(Ai，Ai+1)，(Am 1，Am)顯然，數(shù)據(jù)結(jié)構(gòu)A中的每一個數(shù)據(jù)元素Ai（i = 1,2,m）又是另一個數(shù)據(jù)結(jié)構(gòu)，即數(shù)據(jù)元素的集合為： Di = ai1，ai2, ，ainDi上的一個關系為： Ri = (ai1，ai2)，(ai2，ai3)，(aij,ai,j

23、+ 1)，(ai,n 1，ain)一個數(shù)據(jù)結(jié)構(gòu)除了用二元關系表示外，還可以直觀地用圖形表示。 例 用圖形表示數(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) 這個數(shù)據(jù)結(jié)構(gòu)的圖形表示如圖所示。6.2.3 線性結(jié)構(gòu)與非線性結(jié)構(gòu)根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間前后件關系的復雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分為兩大類：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列條件：（1）有且只有一個根結(jié)點；（2）有且只有一個終端結(jié)點；（3）除根結(jié)點外，其他結(jié)點均只有一個前件；（4）除

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

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

26、儲空間中的位置關系與邏輯關系是有可能不同的。數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式稱為數(shù)據(jù)的存儲結(jié)構(gòu) 。數(shù)據(jù)的存儲結(jié)構(gòu)在數(shù)據(jù)的存儲結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關系的信息。 常用的存儲結(jié)構(gòu)有順序、鏈接、索引、散列等存儲結(jié)構(gòu)。 順序存儲結(jié)構(gòu)主要用于線性結(jié)構(gòu)。在這種存儲方式中，把邏輯上相鄰的數(shù)據(jù)元素結(jié)點存儲在物理上相鄰的存儲單元中，各結(jié)點之間的關系由存儲單元的鄰接關系來體現(xiàn)。右圖是將線性結(jié)構(gòu)(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)順序地存放在存儲單元中的示意圖。 （1）順序存儲結(jié)構(gòu)在鏈接存儲結(jié)構(gòu)中，每個

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

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

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

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

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

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

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

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

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

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

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

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

39、在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹例如，對如圖中的二叉樹進行前序遍歷，則遍歷的結(jié)果為ABDGCEHIF。2中序遍歷（LDR） 中序遍歷是指首先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹；并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點，最后遍歷右子樹。例如，對圖中的二叉樹進行中序遍歷，則遍歷結(jié)果為DGBAHEICF。3后序遍歷（LRD）后序遍歷是指首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點，并且，在遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點。例如，對圖中的二叉樹進行后序遍歷，則遍歷結(jié)果為GDBHIEFCA?？碱}（2005_

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

41、列或遞增排列）。假設有序線性表是按元素值遞增排列的，并設表的長度為n，被查元素為x，則二分法查找過程如下：將x與線性表的中間元素進行比較：若中間元素的值等于x，則說明查成功，查找結(jié)束；若x小于中間元素的值，則在線性表的前半部分以相同的方法查找；若x大于中間元素的值，則在線性表的后半部分以相同的方法查找。這個過程一直進行到查找成功或子表長度為0（說明線性表中沒有這個元素）為止。可以看出，當有序的線性表為順序存儲時才能采用二分查找?？梢宰C明，對于長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次，順序查找需要比較n次?？梢姡植檎业男室软樞虿檎腋叩枚?。6.7.3 交換類排序法

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

43、面。此時，線性表的第一個元素就是最小者，最后一個元素就是最大者。對剩下的元素構(gòu)成的線性表重復上述過程，直到剩下的元素為空或者在掃描過程中沒有交換任何元素，此時，線性表變?yōu)橛行颉?圖8.32是冒泡排序法的示意圖。圖中有下劃線的元素表示掃描過程中的第一個和最后一個元素的位置。 從冒泡排序法的操作過程可以看出，對長度為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快速排序法 快速排序法是對冒泡排序法的改進，又叫作分區(qū)交換排序法?？焖倥判蚍ǖ幕舅枷肴缦拢?從線性表中任意選取一個元素（通常選第一個元素），設為T，將線性表中小于T的元素移到T的前面，而大于T的元素移到T的后面，結(jié)果就將線性表分成了兩部分（稱為兩個子表），T處于分界線的位置處，這個過程稱為線性表的分割。通過對線性表的一次分割，就以T為分界線，將線性表分成了前后兩個子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。 如果對分割后的各子表再按上述原則進行分割，并且，這種分割過程可以一直做下去，直到所有子表為空為止，此時的線性表

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

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