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

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

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

3、復(fù)雜度。,算法分析,算法復(fù)雜度例：下面算法為求n個自然數(shù)的和S=1+2+3+…+n。請給出該算法的語句頻度。 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ù)值、字符? 圖形、圖像?聲音、視頻數(shù)據(jù)元素（Data Element） ：數(shù)據(jù)的基本單位，亦稱為結(jié)點(diǎn)、元素、頂點(diǎn)和記錄等。在計算機(jī)程序中通常作為一個整體考慮和處理。（例如：一個學(xué)生記錄）數(shù)據(jù)項（Data Item）：數(shù)據(jù)結(jié)

5、構(gòu)中討論的最小單位，數(shù)據(jù)元素是數(shù)據(jù)項的集合。亦稱為域、字段等。（例如：學(xué)生記錄中的學(xué)號。）,數(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)系。存儲結(jié)構(gòu),指數(shù)據(jù)及其關(guān)系在計算機(jī)中的存儲方式，或數(shù)據(jù)的物理結(jié)構(gòu)。運(yùn)算,指對數(shù)據(jù)進(jìn)行檢索、插入、刪除、合并、排序、統(tǒng)計、簡單計算、轉(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),存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計算機(jī)存儲器中的表示（映像），又稱物理結(jié)構(gòu)。

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

8、結(jié)構(gòu)順序存儲結(jié)構(gòu)例：用順序存儲方式表示一周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),存儲結(jié)構(gòu)鏈接存儲結(jié)構(gòu)在存儲每個結(jié)點(diǎn)信息的同時，需要增加一個指針來表示結(jié)點(diǎn)間的邏輯關(guān)系。該方法不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。鏈接存儲結(jié)構(gòu)中的每個結(jié)點(diǎn)由兩部分組成：一

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

10、y直接計算出該結(jié)點(diǎn)的存儲地址。即以線性表中的每個結(jié)點(diǎn)的關(guān)鍵字Key為自變量，通過一個確定的函數(shù)關(guān)系f，計算出對應(yīng)的函數(shù)值f(key)，然后把這個值解釋為一塊連續(xù)存儲空間的存儲地址，將結(jié)點(diǎn)存儲到f(key)所指的存儲單元中，使每個關(guān)鍵字和結(jié)構(gòu)中一個的存儲地址相對應(yīng)。,數(shù)據(jù)結(jié)構(gòu),存儲結(jié)構(gòu)散列方式例：已知一組待存儲的關(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）個具有相同特性的數(shù)據(jù)元素（結(jié)點(diǎn)）a1, a2, a3, …, an組成的有限序列。通常記作： L =（a1, a2, a3, …, an）n=0 時稱為空表；表中 ai-1 是ai 的直接前驅(qū)，ai+1 是ai 的直接后繼；線性表中，除第一個元素和最后一個元素之外，其他元素都有且僅有一個直接前驅(qū)和直接后繼；ai是線性表

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

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

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

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

16、ad,（帶表頭結(jié)點(diǎn)）,線性表,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)雙向鏈表雙向鏈表中結(jié)點(diǎn)：,,∧,∧,線性表,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)循環(huán)鏈表,,線性表,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)循環(huán)鏈表,,線性表,線性表的鏈?zhǔn)酱鎯Y(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）個（或符合要求的）位置上，插入一個新的結(jié)點(diǎn)x，

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

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

19、返回值為0。見教材p.45算法2-1,線性表的基本運(yùn)算,單鏈表的插入假設(shè)指針p指向單鏈表中某個結(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個（或符合要求）的數(shù)據(jù)元素刪除，使長度為n的線性表： ( a1, …, ai?1 , ai , ai+1 ,…, an ) 變成為長度為n-1的線性表：( a1, …, ai?1, ai+1,…, an ),線性表的基本運(yùn)算,順序表的刪除過程：① 檢查給定結(jié)點(diǎn)的刪除位置是否正確，若刪除位置有錯，則顯示出錯信息，退出程序運(yùn)行；②

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

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

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

24、較,空間性能的比較存儲密度：存儲結(jié)點(diǎn)中數(shù)據(jù)域占用的存儲量與存儲結(jié)點(diǎn)所占用的存儲量之比稱為存儲密度。存儲密度越大，則存儲空間的利用率就越高。順序表的存儲密度是高于鏈表的存儲密度。但是，順序表要求事先估計容量，這是比較困難的。,順序表和鏈表的比較,時間性能的比較當(dāng)線性表的主要操作是查找運(yùn)算時，最好采用順序存儲結(jié)構(gòu)。對于需要頻繁地進(jìn)行插入和刪除操作的線性表，最好采用鏈接存儲結(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)算的另一端則稱為棧底；向棧中插入一個新元素稱為入?；驂簵?，從棧中刪除一個元素稱為出?；蛲藯?；記錄棧頂元素位置的變量稱為棧頂指針，處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素；不含

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

27、的基本運(yùn)算,見教材p48 算法2-3，算法2-4,棧,鏈棧的基本運(yùn)算,棧,共享棧,棧在遞歸過程中的作用,所謂遞歸，是指一個函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)，若在其定義的內(nèi)部又直接或者間接出現(xiàn)有定義自身的應(yīng)用，則稱其是遞歸的或者是遞歸定義的。在調(diào)用一個函數(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ī)制可通過棧來實現(xiàn),計算機(jī)正是利用棧來實現(xiàn)函數(shù)的調(diào)用和返回的,棧在遞歸過程中的作用,遞歸函數(shù)：一個直接調(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ù)問題的遞歸描述（定義）編寫遞歸算法遞歸定義包括兩項1）基本項（終止項）：描述遞歸終止時問題的求解；2）遞歸項：將問題分解為與原問題性質(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ù)錯誤! ”) else if (n==0) f=1; else f = n*Fact(n-1); return(f); },隊列,隊列也是一種運(yùn)算受限的線性表，在這種線性表上，插入限定在表的某一端進(jìn)行，刪除限定在表的另一端。允許插入的一端稱為隊尾

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

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

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

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

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

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

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

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

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

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

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

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

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

45、順序存儲方式鏈接存儲方式,e[max],m,trilist,n,t,i j v,,,node,數(shù)組,稀疏矩陣的壓縮存儲三元組,數(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ù)組,稀疏矩陣的十字鏈表表示,特殊矩陣的壓縮存儲,特殊矩陣：

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

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

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

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

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

54、可以有零個或多個直接后繼，若有多個后繼結(jié)點(diǎn)，則后繼結(jié)點(diǎn)是該結(jié)點(diǎn)的每個子樹的根結(jié)點(diǎn)。2）除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)，有且僅有一個直接前驅(qū)。3）數(shù)據(jù)結(jié)點(diǎn)按分支關(guān)系組織起來，清晰地反映了數(shù)據(jù)元素之間的層次關(guān)系。4）樹型結(jié)構(gòu)中數(shù)據(jù)元素之間的關(guān)系是一對多或者多對一的關(guān)系。,樹,基本術(shù)語1．結(jié)點(diǎn)的度和樹的度結(jié)點(diǎn)具有的子樹（分支）個數(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)樹中每個結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子或兒子或子女；相應(yīng)地，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親或父親。具有同一個雙親的孩子們之間互稱為兄弟。每個結(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)開始計算。假設(shè)樹的根結(jié)點(diǎn)為

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

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

58、顆二叉樹只有最下一層結(jié)點(diǎn)數(shù)可能未達(dá)到最大，并且最下層結(jié)點(diǎn)都集中在該層的最左端，則稱為完全二叉樹。性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2n+1,或 log2n+1,二叉樹的性質(zhì),性質(zhì)5：如果對一棵有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號（每層從左到右），則對任一結(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。,二叉樹,二叉樹的順序存儲結(jié)構(gòu)把二叉樹的所有結(jié)點(diǎn)，按照一定的次序順序存放到一組地址連續(xù)的存儲單元中。對完全二叉樹中所有結(jié)點(diǎn)進(jìn)行編號得到一個結(jié)點(diǎn)的線性序列，然后將完全二叉樹各結(jié)點(diǎn)按其編號順序存放到一個一維數(shù)組中，即將完全二叉樹上編號為 i 的結(jié)點(diǎn)存入一維數(shù)組下標(biāo)為 i 的分量中。對于編號為 i 的結(jié)點(diǎn)，若有左孩子，它的左孩子的編號為 2i；若有右孩子，它的右孩子的編號為 2i+1。

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

61、中序遍歷序列分為兩部分。,其最后一個元素值為二叉樹中根結(jié)點(diǎn)的數(shù)據(jù)值。,算法見教材p73,二叉樹,二叉樹的遍歷例有二叉樹中序序列為：ABCEFGHD，后序序列為：ABFHGEDC，畫出此二叉樹。,二叉樹,二叉樹的遍歷【例】假設(shè)先序遍歷某二叉樹的結(jié)點(diǎn)次序為ABCDEFGHIJ，中序遍歷該二叉樹的結(jié)點(diǎn)次序為CBEDAGHFJI，試畫出此二叉樹。,求二叉樹的高度運(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)個數(shù)運(yùn)算算法,對應(yīng)的遞歸模型如

64、下： 0 若bt = NULL f ( bt ->lchild ) + f ( bt->rchild ) +1,f( bt ) =,,求二叉樹結(jié)點(diǎn)個數(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)個數(shù)運(yùn)算算法,對應(yīng)的遞歸模型如下： 0

66、 bt = NULL 1 bt為葉子結(jié)點(diǎn) F ( bt ->lchild ) + f ( bt ->rchild ) 其他情況,F (bt) =,,求二叉樹葉子結(jié)點(diǎn)個數(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 ); } },樹的存儲結(jié)構(gòu),孩子兄弟鏈表存儲結(jié)構(gòu),Fchild data nsibling,,,第一個孩子,,下一個兄弟,,樹的存儲結(jié)構(gòu),樹的遍歷兩種方式先根遍歷后根遍歷,樹、二叉樹、森林的轉(zhuǎn)換,樹、二叉樹、森林的轉(zhuǎn)換,圖,定義一個圖G是由兩個集合V(G)和E(G)組成的，圖的二元組可定義為