第3章-棧和隊(duì)列

1、3.1 棧3.2 棧應(yīng)用舉例3.3 棧與遞歸函數(shù)3.4 隊(duì)列3.5 隊(duì)列應(yīng)用舉例3.6 小結(jié) 第第3 3章章 棧和隊(duì)列棧和隊(duì)列1.棧的定義及其基本操作3.1 棧定義：定義：棧（stack）在邏輯上是一種線性表，記為 S =（a0，a1，an-1 ）。 對棧S的操作（插入、刪除等）限定在表的一端進(jìn)行an-1 a1 a0 棧頂top棧底bottomXX 進(jìn)棧進(jìn)棧X出棧出棧 C語言函數(shù)調(diào)用和返回語言函數(shù)調(diào)用和返回是如何正確實(shí)現(xiàn)的？是如何正確實(shí)現(xiàn)的？棧的特點(diǎn)：棧的特點(diǎn)：后進(jìn)先出（Last In First Out，LIFO） 若元素進(jìn)棧順序?yàn)閍0，a1，an-1，則出棧順序是an-1，an-2，a0，

2、即后進(jìn)棧的元素先出棧，故?？煞Q作“后進(jìn)先出” 的線性表。棧頂是唯一的出入口棧頂是唯一的出入口 當(dāng)棧中沒有元素時(shí)，稱“?？铡?。若棧的存儲空間已滿，再作進(jìn)棧操作時(shí)稱“棧滿溢出”。棧頂?shù)奈恢秒S著進(jìn)棧棧頂?shù)奈恢秒S著進(jìn)棧/出棧操作而發(fā)生變化出棧操作而發(fā)生變化棧的定義及其基本操作棧的抽象數(shù)據(jù)類型：棧的抽象數(shù)據(jù)類型：棧的定義及其基本操作ADT Stack 數(shù)據(jù)元素集：數(shù)據(jù)元素集：D=ai |aidatatype, i=0,1,2, , n-1, n0 數(shù)據(jù)關(guān)系集：數(shù)據(jù)關(guān)系集：R=|ai, ai+1D, 0in-2 約定an-1為棧頂元素 基本操作集：基本操作集：PStackInit(&S) 操作結(jié)果

3、：創(chuàng)建一個(gè)空棧S。ClearStack(&S) 初始條件：棧S存在。 操作結(jié)果：將S清為空棧。EmptyStack(S) 初始條件：棧S存在。 操作結(jié)果：若S為空棧，則返回TRUE(或返回1)，否則返回FLASE(或返回0)。棧的定義及其基本操作Push(&S, e) 初始條件：棧S存在且未滿。 操作結(jié)果：插入數(shù)據(jù)元素e，使之成為新棧頂元素。Pop(&S) 初始條件：棧S存在且非空。 操作結(jié)果：刪除S的棧頂元素并返回其值。GetTop(S) 初始條件：棧S存在且非空。 操作結(jié)果：返回棧頂元素的值。 ADT Stack;2.棧的順序存儲結(jié)構(gòu)3.1 棧（1）順序棧的描述#d

4、efine MAXSIZE 64 /棧最大容量typedef struct datatype dataMAXSIZE; /棧的存儲空間 int top; /棧頂指針（或游標(biāo)） sqstack,*sqslink; /順序棧說明符若說明 sqslink S; S = (sqlink)malloc(sizeof(sqstack)；則S指向一個(gè)順序棧，如右圖所示。 棧頂元素an-1寫作：S-data S-top ?？諘r(shí)S-top = -1 棧滿時(shí)S-top = MAXSIZE - 1an-1 a1 a0 MAXSIZE-1 S-top 1 0 （2）順序?；静僮鞯膶?shí)現(xiàn)棧的順序存儲結(jié)構(gòu)1）void C

5、learStack (sqslink s) /置?？?s-top = -1; 2）int EmptyStack (sqslink s) /判斷?？?if（s-top top = MAXSIZE - 1) return -1; /棧滿溢出 s-top+; s-datas-top = x; /x進(jìn)棧 return 0; /成功 4）int Pop(sqslink s, datatype *px) /出棧 if (EmptyStack(s) return -1; /?？眨祷?1 *px = s-datas-top; s-top-; return 0; /成功 / 為簡單起見，出棧操作常寫成為簡單起

6、見，出棧操作常寫成 x = Pop(s)5）int GetTop(sqslink s, datatype *px) if (EmptyStack(s) return -1; /?？?，返回-1 *px = s-datas-top; return 0; /成功 棧的順序存儲結(jié)構(gòu)棧的共享：棧的順序存儲結(jié)構(gòu)a0an-1空閑空間空閑空間 bm-1b0 S1 S2S1底 S-top1 S-top2 S2底多個(gè)棧共用一個(gè)數(shù)組可以將棧S1及棧S2的棧底分別設(shè)置在頭尾兩端（a0, an-1）為棧S1中當(dāng)前元素，S-top1為棧S1的棧頂指針（b0 , bm-1）為棧S2中當(dāng)前元素，S-top2為棧S2的棧頂指針

7、2.棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)3.1 棧（1）鏈?zhǔn)綏５拿枋鰐ypedef struct node datatype data ; /存儲一個(gè)棧元素 struct node *next ; /后繼指針 snode,*slink; a0 a1top an-1top為棧頂指針，表示棧（a0，a1，an-1 ）。鏈?zhǔn)綏５幕静僮魅绾螌?shí)現(xiàn)？鏈?zhǔn)綏５幕静僮魅绾螌?shí)現(xiàn)？ClearStack, Push, Pop, EmptyStack棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)（2）鏈?zhǔn)綏；静僮鞯膶?shí)現(xiàn)1) Lclearstack(slink *ptop) /置?？? 略去了棧非空時(shí)釋放空間的操作 *ptop = NULL; /調(diào)用方式：調(diào)用方

8、式：Lclearstack(&top);2) int Lemptystack(slink top) /判斷?？辗?if (top = NULL) return 1; else return 0; 3) Lpush(slink *ptop, datatype x ) /進(jìn)棧 slink p = (slink)malloc(sizeof(snode) ; /生成進(jìn)棧p節(jié)點(diǎn) p-data = x; p-next = *ptop; *ptop = p; /p節(jié)點(diǎn)作為新的棧頂鏈入 /調(diào)用方式：調(diào)用方式：Lpush(&top, x);棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)4) int Lpop(slink *p

9、top, datatype *px) /出棧 if (Lemptystack(*ptop) return -1; /?？辗祷?*px = (*ptop)-data; /取棧頂元素 slink p = *ptop; *ptop = (*ptop)-next; /重置棧頂指針 free(p); return 0; /成功 / 調(diào)用方式：調(diào)用方式：Lpop(&top, &x);5) int Lgettop(slink top, datatype *px) if (Lemptystack(top) return -1; /棧空返回 *px = top-data; /取棧頂元素 retu

10、rn 0; /成功 3.順序棧與鏈?zhǔn)綏５谋容^3.1 棧 時(shí)間復(fù)雜度：均為O(1) 順序棧長度固定，浪費(fèi)空間 鏈?zhǔn)綏Ｓ薪Y(jié)構(gòu)性開銷 可以用數(shù)組實(shí)現(xiàn)2個(gè)棧，每個(gè)棧從各自的端點(diǎn)向中間延伸1.數(shù)制轉(zhuǎn)換3.2 棧應(yīng)用舉例10進(jìn)制正整數(shù)N與d進(jìn)制數(shù)的基數(shù)d之間滿足關(guān)系： N10= ( N/d )*d + N % d 整除 取模（取余數(shù)）10進(jìn)制正整數(shù)進(jìn)制正整數(shù)N如何轉(zhuǎn)換為二進(jìn)制數(shù)？如何轉(zhuǎn)換為二進(jìn)制數(shù)？10進(jìn)制正整數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)的方法： 除以除以d取余數(shù)（直到商為取余數(shù)（直到商為0 ），逆序排列），逆序排列。數(shù)制轉(zhuǎn)換算法描述：算法描述： int x = N; ClearStack(S); /置?？?whi

11、le (x 0) push(S, x % d ); /當(dāng)前x%d進(jìn)棧 x = x/d; while (!EmptyStack(S) x = Pop(S); printf(%d, x); 2.表達(dá)式求值3.2 棧應(yīng)用舉例(1) 表達(dá)式的形式表達(dá)式的形式1）中綴表達(dá)式中綴表達(dá)式： 如A + B2）后綴表達(dá)式后綴表達(dá)式： ，或稱逆波蘭式 如A B +3）前綴表達(dá)式前綴表達(dá)式： ，或稱波蘭式 如+ A B例 中綴表達(dá)式：A + (B C / D) * F 后綴表達(dá)式：A B C D / F * + 前綴表達(dá)式：+ A * B / C D F（2）后綴表達(dá)式求值）后綴表達(dá)式求值表達(dá)式求值后綴表達(dá)式計(jì)算不

12、存在優(yōu)先級問題。例如 A B C D / F * +如何計(jì)算？如何計(jì)算？方法：方法： 從左到右掃描，當(dāng)遇到操作符時(shí)，對其左邊的2個(gè)操作數(shù)進(jìn)行計(jì)算，以結(jié)果取代之，繼續(xù)。算法思路：算法思路：設(shè)置一個(gè)棧S;從左到右依次掃描表達(dá)式中的各分量x： 若x是操作數(shù)：Push(S, x) ; 若x是操作符：a = Pop(S); b = Pop(S); Push(b x a的計(jì)算結(jié)果);繼續(xù)，直到表達(dá)式掃描完畢;最后，棧頂就是表達(dá)式的值。表達(dá)式求值（3）中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換）中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換表達(dá)式求值如何轉(zhuǎn)換？如何轉(zhuǎn)換？A + B當(dāng)掃描到+時(shí)記錄下來，得AB+A + B - C當(dāng)掃描到+時(shí)

13、記錄下來;當(dāng)掃描到-時(shí)，-的優(yōu)先級不大于+，說明+應(yīng)先計(jì)算，則得AB+，最后得AB+C-A + B * C當(dāng)掃描到+時(shí)記錄下來;當(dāng)掃描到*時(shí)，仍然只能先記錄下來，因?yàn)椴恢篮竺嬗袩o優(yōu)先級更高的，最后得ABC*+采用什么數(shù)據(jù)結(jié)構(gòu)記錄操作符？采用什么數(shù)據(jù)結(jié)構(gòu)記錄操作符？棧！棧！中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換再如：A + B C * DA + (B C / D) * F轉(zhuǎn)換方法要點(diǎn)：轉(zhuǎn)換方法要點(diǎn)： 中綴表達(dá)式與后綴表達(dá)式操作數(shù)出現(xiàn)的次序是相同的 需要考慮操作符的優(yōu)先級，優(yōu)先級高的先轉(zhuǎn)換 從左到右掃描表達(dá)式，將遇到的操作數(shù)輸出 設(shè)置一個(gè)棧存放操作符 遇到的第1個(gè)操作符進(jìn)棧 在掃描過程中，將遇到的操作符與

14、棧頂進(jìn)行優(yōu)先級比較 棧中的操作符滿足條件：后進(jìn)棧的優(yōu)先級高于先進(jìn)棧的棧中的操作符滿足條件：后進(jìn)棧的優(yōu)先級高于先進(jìn)棧的 當(dāng)掃描完畢時(shí)，若棧非空，則將棧中操作符依次出棧輸出中綴表達(dá)式到后綴表達(dá)式的轉(zhuǎn)換方法：方法：從左到右掃描表達(dá)式，設(shè)置一個(gè)棧s存放操作符;對于遇到的每個(gè)分量x，分以下幾種情況處理：1) x = 操作數(shù)：輸出x;2) x = (：x進(jìn)棧；3) x = 操作符（非括號）： while (1) if (EmptyStack(s) break; y = GetTop(s); if (y = () break; if (y 優(yōu)先級棧頂） 輸出的后綴表達(dá)式未掃描的中綴表達(dá)式1AA+ (B C

15、/ D) * F2+A(B C / D) * F3(+(AB C / D) * F4B+(AB C / D) * F5-+(-ABC / D) * F6C+(-ABC / D) * F7/+(-/ABC D) * F8D+(-/ABCD ) * F9)+ABCD/-* F10*+*ABCD/-F11F+*ABCD/-F12結(jié)束標(biāo)志ABCD/-F*+1.遞歸的定義和遞歸函數(shù) 3.3 棧與遞歸函數(shù)(1) 遞歸定義遞歸定義 對于定義： = (左部) (右部)若定義的右部又出現(xiàn)定義的左部形式定義的右部又出現(xiàn)定義的左部形式，則稱為遞歸定義例例 n的階乘定義： 1 當(dāng)n = 0時(shí) n! = n*( n -

16、1)! 當(dāng)n 0時(shí)例例 Fibonacci數(shù)列定義： 0 當(dāng)n = 0時(shí) Fibonacci(n) 1 當(dāng)n = 1時(shí) Fibonacci(n-1)+Fibonacci(n-2) 其他例例 Ackermam 函數(shù)定義： n +1 當(dāng)m = 0時(shí) Ack(m,n) = Ack (m-1, 1) 當(dāng)n = 0時(shí) Ack (m-1, Ack (m, n-1) 其他 遞歸的定義和遞歸函數(shù) （2）遞歸函數(shù)（或過程）遞歸函數(shù)（或過程） 直接或間接調(diào)用自己直接或間接調(diào)用自己 直接遞歸 間接遞歸遞歸的定義和遞歸函數(shù) （3）遞歸的基本思想）遞歸的基本思想 一個(gè)大問題分解為幾個(gè)子問題，其中的某些子問題與原問題相同

17、，只是規(guī)模比原問題小； 隨著問題的不斷分解，一定存在一個(gè)最小問題，可以直接解決，這便是遞歸出口（即終止條件）。說明：說明： 對于本身就是遞歸定義的問題，用遞歸最容易實(shí)現(xiàn)。用非遞歸反而較難。 任何循環(huán)均可以遞歸的方式來實(shí)現(xiàn)。當(dāng)然，與循環(huán)一樣，遞歸函數(shù)也必須存在一個(gè)終止條件。 遞歸過程（函數(shù)）設(shè)計(jì)的關(guān)鍵：保證除了出口參數(shù)外，每次調(diào)用都不破遞歸過程（函數(shù)）設(shè)計(jì)的關(guān)鍵：保證除了出口參數(shù)外，每次調(diào)用都不破壞以前調(diào)用時(shí)所用到的參數(shù)和中間結(jié)果。壞以前調(diào)用時(shí)所用到的參數(shù)和中間結(jié)果。遞歸的定義和遞歸函數(shù) 例：例：int Fact (int n) /求n!（只能用于小規(guī)模的n，這里只是為了說明遞歸） if (n

18、= 0) return 1; return n*Fact(n-1) ；int Ack (int m, int n) /求Ackermam函數(shù) if (m = 0) return n+1; else if (n = 0) return Ack (m-1,1) ; else return ACK (m-1, Ack (m, n-1); 遞歸的定義和遞歸函數(shù) 例例 3.10 hanoi塔問題：設(shè)有A、B、C三塔（或柱子），n(n 1)個(gè)直徑不同的盤子依次從小到大編號為1，2，n存放于A塔中。要求將A塔上的1到n號盤移到C塔，B 塔作為輔助塔。移動規(guī)則：每次只能移動一個(gè)盤從一塔到另一塔，且任何時(shí)候編號

19、大的盤不能在編號小的盤之上。1-C, 2-B, 1-B, 3-C, 1-A, 2-C, 1-C遞歸的定義和遞歸函數(shù) (A) (B) (C) n=3時(shí)的情況時(shí)的情況2131 21 3 1 2 1如何分析設(shè)計(jì)這類遞歸問題的算法？如何分析設(shè)計(jì)這類遞歸問題的算法？1）最小問題：最小問題：n=1?？芍苯咏鉀Q（從A移到C即可）hanoi塔問題2）否則（否則（n 1）：）： 將A上的1到（n-1）號盤移到B，C為輔助塔； 將A上第 n號盤移至C； 將B上1到( n -1)號盤移到C，A為輔助塔。void hanoi ( int n, char A, char B , char C) /hanoi塔算法 if

20、 (n = 1) move (A, 1, C ); /移A上的一個(gè)盤到C else hanoi(n-1, A, C, B); /解決子問題 move (A, n, C); /移A上的n 號盤到C hanoi (n-1, B, A, C); /解決子問題 和與原問題相同，和與原問題相同，只是規(guī)模小。只是規(guī)模小。許多問題都可以很容易用遞歸函數(shù)來設(shè)計(jì)。例如：求1 + 2 + 3 + +N。求N個(gè)數(shù)的最大值。將N個(gè)數(shù)倒序。遞歸的定義和遞歸函數(shù) 例例 計(jì)算n!。以n = 4為例，分析其計(jì)算過程。Fact(4) = 4 * Fact(3) 3 * Fact(2) 2 * Fact(1) 1 * Fact(

21、0) 12種求解思路：種求解思路：（1）從整個(gè)問題開始，當(dāng)不能解決時(shí)先記下，不斷分解，直到最小問題直接解決后，再逐層返回。（2）直接從求最小問題開始。int Fact (int n) /求n! if (n = 0) return 1; else return n * Fact(n-1) ；返回地址返回地址2.遞歸到非遞歸的轉(zhuǎn)換遞歸的定義和遞歸函數(shù) 非遞歸：非遞歸：（1）不用棧，直接從最小問題（）不用棧，直接從最小問題（0!）開始求。）開始求。int Fact(int n) int f, i; f = 1; i = 0; while (i 0時(shí)，n進(jìn)棧，然后n-，繼續(xù)，直到n = 0，得f =

22、1； 然后，依次出棧n，f = f * n，直到棧空為止。遞歸到非遞歸的轉(zhuǎn)換int Fact(int n) int f; ClearStack(S); while (n 0) Push(S, n); n-; f = 1; while (!EmptyStack(S) f = f * Pop(S); return f;說明：說明： 對于某些遞歸問題，非遞歸函數(shù)必須使用棧來實(shí)現(xiàn)； 理解函數(shù)調(diào)用與返回； 遞歸過程（函數(shù)）與非遞歸過程（函數(shù)）沒有本質(zhì)區(qū)別。遞歸到非遞歸的轉(zhuǎn)換例例 求Ackerman函數(shù)。以Ack(2, 1)為例，m=2, n=1。Ack(2, 1) = 5int Ack (int m,

23、int n) /求Ackermam函數(shù) if (m = 0) return n+1; else if (n = 0) return Ack (m-1,1) ; else return ACK (m-1, Ack (m, n-1);返回地址返回地址Ack(2, 1)Ack(1, Ack(2, 0) Ack(1, 1) Ack(0, Ack(1, 0) Ack(0, 1) 2 3Ack(1, 3)Ack(0, Ack(1, 2) Ack(0, Ack(1, 1) Ack(0, Ack(1, 0) Ack(0, 1) 2 3 4 5 遞歸到非遞歸的轉(zhuǎn)換非遞歸：非遞歸：int Ack (int m,

24、int n) /求Ackermam函數(shù) int f; ClearStack(S); while (1) if (m = 0) f = n + 1; if (EmptyStack(S) break; m = Pop(S); n = f; else if (n = 0) m-; n = 1; else Push(S, m - 1); n-; return f;遞歸到非遞歸的轉(zhuǎn)換1.隊(duì)列的定義及其基本操作 3.4 隊(duì)列定義：定義：隊(duì)列（Queue）邏輯上也是一種線性表，記為 Q = (a0, a1 , , an-1)對隊(duì)Q的操作（插入，刪除）限定在表的兩端進(jìn)行。 a0a1an-2an-1 隊(duì)頭隊(duì)頭

25、隊(duì)尾隊(duì)尾X 進(jìn)隊(duì)進(jìn)隊(duì) a0 出隊(duì)出隊(duì)隊(duì)頭：僅能刪除（出隊(duì)出隊(duì)） 隊(duì)尾：僅能插入（進(jìn)隊(duì)進(jìn)隊(duì)）隊(duì)列的特點(diǎn)：隊(duì)列的特點(diǎn)：先進(jìn)先出（First In First Out，F(xiàn)IFO） 設(shè)元素進(jìn)隊(duì)順序?yàn)閍0，a1，an-1，則出隊(duì)順序也是a0，a1，an-1，即先進(jìn)隊(duì)的元素先出隊(duì)，故隊(duì)列可稱為“先進(jìn)先出先進(jìn)先出” 的線性表，隊(duì)頭是唯一的出口，隊(duì)尾是唯一的入口。隊(duì)頭是唯一的出口，隊(duì)尾是唯一的入口。 當(dāng)隊(duì)列中沒有元素時(shí)，稱“隊(duì)空隊(duì)空”。若隊(duì)列存儲空間已滿，再作進(jìn)隊(duì)操作時(shí)，稱“隊(duì)滿溢出隊(duì)滿溢出”。 隊(duì)列的定義及其基本操作隊(duì)列的抽象數(shù)據(jù)類型：隊(duì)列的抽象數(shù)據(jù)類型：隊(duì)列的定義及其基本操作ADT Queue 數(shù)據(jù)元素集

26、：數(shù)據(jù)元素集：D=ai |aidatatype, i=0,1,2, , n-1, n0 數(shù)據(jù)關(guān)系集：數(shù)據(jù)關(guān)系集：R=|ai, ai+1D, 0in-2 約定a0為隊(duì)頭元素， an-1為隊(duì)尾元素 基本操作集基本操作集：PQueueInit(&Q) 操作結(jié)果：創(chuàng)建一個(gè)空隊(duì)列Q。ClearQueue(&Q) 初始條件：隊(duì)列Q已經(jīng)存在。 操作結(jié)果：清空隊(duì)列。QueueLength(Q) 初始條件：隊(duì)列Q已經(jīng)存在。 操作結(jié)果：返回隊(duì)列Q的元素個(gè)數(shù)。隊(duì)列的定義及其基本操作EmptyQueue(Q) 初始條件：隊(duì)列Q已經(jīng)存在。 操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FLASE。Qu

27、eueFull(Q) 初始條件：隊(duì)列Q已經(jīng)存在。 操作結(jié)果：若Q為已滿，則返回TRUE，否則返回FLASE。EnQueue(&Q, e) 初始條件：隊(duì)列Q已經(jīng)存在且未滿。 操作結(jié)果：插入數(shù)據(jù)元素e，使之成為新隊(duì)尾元素。DeQueue(&Q) 初始條件：隊(duì)列Q已經(jīng)存在且非空。 操作結(jié)果：刪除Q的隊(duì)頭元素，并返回其值。GetHead(Q) 初始條件：隊(duì)列Q已經(jīng)存在且非空。 操作結(jié)果：返回隊(duì)頭元素的值。ADT Queue； 2.隊(duì)列的順序存儲結(jié)構(gòu)（1）順序隊(duì)列的描述）順序隊(duì)列的描述 #define MAXSIZE 64 /隊(duì)列最大容量 typedef struct datatype

28、dataMAXSIZE; /隊(duì)列的存儲空間 int front, rear; /隊(duì)頭、隊(duì)尾指針 squeue, *squlink;3.4 隊(duì)列隊(duì)頭、隊(duì)尾的位置以及如何變化？隊(duì)頭、隊(duì)尾的位置以及如何變化？隊(duì)列的順序存儲結(jié)構(gòu)a0an-1 MAXSIZE - 1 Q- rear j Q- front i Q - data0Q-fronta0 MAXSIZE-1 0Q rearan-1 頭循環(huán)隊(duì)列循環(huán)隊(duì)列設(shè)Q-front指向隊(duì)頭的前驅(qū) Q-rear指向隊(duì)尾隊(duì)列的順序存儲結(jié)構(gòu)Q-fronta0 MAXSIZE-1 0Q rearan-1 頭初始化：初始化：Q-front = Q-rear = 0進(jìn)隊(duì)：進(jìn)

29、隊(duì)： Q-rear = (Q-rear + 1)% MAXSIZE; Q-dataQ-rear = e;出隊(duì)：出隊(duì)： Q-front = (Q-front + 1)%MAXSIZE; e = Q-dataQ-front;如何判斷隊(duì)空如何判斷隊(duì)空/隊(duì)滿？隊(duì)滿？Q-front = Q-rear ? 無法區(qū)分隊(duì)空無法區(qū)分隊(duì)空/隊(duì)滿！隊(duì)滿！解決辦法：解決辦法：隊(duì)列的順序存儲結(jié)構(gòu)Q-fronta0 MAXSIZE-1 0Q rearan-1 頭1）設(shè)置）設(shè)置1個(gè)布爾變量表示隊(duì)空個(gè)布爾變量表示隊(duì)空/隊(duì)滿。隊(duì)滿。 當(dāng)出隊(duì)使得隊(duì)頭追上隊(duì)尾，則隊(duì)空 當(dāng)進(jìn)隊(duì)使得隊(duì)尾追上隊(duì)頭，則隊(duì)滿2）犧牲）犧牲1個(gè)單元，使個(gè)單元

30、，使隊(duì)尾不會追上隊(duì)頭。隊(duì)尾不會追上隊(duì)頭。即n個(gè)單元最多放n-1個(gè)元素 隊(duì)空：隊(duì)空： Q-front = Q-rear 隊(duì)滿：隊(duì)滿： (Q-rear + 1) % MAXSIZE = Q-front （2）循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)）循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)隊(duì)列的順序存儲結(jié)構(gòu)1) void ClearQueue(squlink Q) /置隊(duì)空 Q-front = Q-rear = 0; 2) int EmptyQueue(squlink Q) /判斷隊(duì)空 return (Q-front = Q-rear); 3) int QueueLength(squlink Q) /求隊(duì)Q中當(dāng)前元素個(gè)數(shù) int i

31、 = (Q-rear - Q-front + MAXSIZE) % MAXSIZE; return i; 隊(duì)列的順序存儲結(jié)構(gòu)4) int EnQueue(squlink Q, datatype e) /元素e進(jìn)隊(duì) if (Q-rear + 1) % MAXSIZE = Q-front) return -1; /隊(duì)滿 Q-rear = (Q-rear + 1) % MAXSIZE; Q-dataQ-rear = e; return 0; /成功 5) int DeQueue (squlink Q, datatype *pe) /出隊(duì) if ( EmptyQueue(Q) return -1; /

32、隊(duì)空 Q-front = (Q-front + 1 ) % MAXSIZE; *pe = Q-dataQ-front); return 0; /為了簡便起見，調(diào)用時(shí)常簡單地寫作e = DeQueue(q);2.隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)3.4 隊(duì)列（1）鏈?zhǔn)疥?duì)列的描述）鏈?zhǔn)疥?duì)列的描述typedef struct node /節(jié)點(diǎn)類型 typedef struct /q節(jié)點(diǎn)類型 datatype data; Qnode *front, *rear; struct node *next; linkqueue;Qnode, *Qlinkfrontrearqa0an-1頭節(jié)點(diǎn)（2 2）鏈?zhǔn)疥?duì)列基本操作的實(shí)現(xiàn)）

33、鏈?zhǔn)疥?duì)列基本操作的實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)1) viod Lcreatqueue (linkqueue *q ) /創(chuàng)建空隊(duì)列 q-front = q-rear = (Qlink) malloc(sizeof(Qnode); /申請頭節(jié)點(diǎn) q-front-next = NULL; 2) int Lemptyqueue (linkqueue *q) /判斷隊(duì)空 return ( q-front = q-rear); 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)3) void Lenqueue ( linkqueue *q, datatype e ) /元素e進(jìn)隊(duì) Qlink p = (Qlink) malloc ( (si

34、zeof (Qnode) ); /申請進(jìn)隊(duì)節(jié)點(diǎn) p-data = e; p-next = NULL; q-rear-next = p; q-rear = p; 進(jìn)隊(duì)示意：frontrearq頭頭a0an-1ep隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)4) int Ldequeue(linkqueue *q, datatype *pe) /出隊(duì) Qlink p; if ( Lemptyqueue (q) return -1; /隊(duì)空處理 p = q-front ; q-front = p-next ; free(p); *pe = q-front-data; return 0; 出隊(duì)示意：frontrearq頭頭a0

35、an-1pa0頭頭隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)如果鏈?zhǔn)疥?duì)列采用不帶頭節(jié)點(diǎn)的單鏈表，如何實(shí)現(xiàn)？如果鏈?zhǔn)疥?duì)列采用不帶頭節(jié)點(diǎn)的單鏈表，如何實(shí)現(xiàn)？pfrontrearqa0a1an-11) viod Lcreatqueue (linkqueue *q ) /創(chuàng)建空隊(duì)列 q-front = q-rear = NULL; 2) int Lemptyqueue (linkqueue *q) /判斷隊(duì)空 return ( q-front = NULL); 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)p3) int Lenqueue( linkqueue *q, datatype e ) /元素e進(jìn)隊(duì) Qlink p = (Qlink) mall

36、oc( (sizeof (Qnode) ); /申請進(jìn)隊(duì)節(jié)點(diǎn) if (p = NULL ) return -1;/為簡化處理，許多算法略去了對p的檢查 p-data = e; p-next = NULL; if (q-rear) != NULL ) q-rear-next = p; q-rear = p; else q-front = q-rear = p; return 0; 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)p4) int Ldequeue(linkqueue *q, datatype *pe) /出隊(duì) Qlink p; if ( Lemptyqueue (q) return -1; /隊(duì)空處理 *pe

37、= q-front-data; p = q-front ; q-front = q-front-next ; free(p); if (q-front = NULL ) q-rear = NULL; return 0; 1.迷宮問題：設(shè)二維數(shù)組mazem+2n+2 表示一迷宮，如m=5、n=6 時(shí)的迷宮如下圖所示。求從迷宮入口到出口的一條最短路徑。3.5 隊(duì)列應(yīng)用舉例11111111100111111010111110100011111101011111110111111111 0 1 2 3 4 5 6 7 (列下標(biāo))0123456 (行下標(biāo))x , y(x-1,y+1)(x,y+1)(x,

38、y-1)(x+1,y+1)(x-1,y-1)(x+1,y-1)(x+1,y)(x-1,y)（搜索方向）（搜索方向）約定：約定：maze11=0為迷宮入口，mazemn=0為迷宮出口；mazexy取值為0時(shí)表示路通，取1時(shí)表示路不通。迷宮外所圍的一層為處理問題方便所加，其相應(yīng)點(diǎn)全為1。每一步怎么走？每一步怎么走？迷宮問題11111111100111111010111110100011111101011111110111111111 0 1 2 3 4 5 6 7 (列下標(biāo))0123456 (行下標(biāo))x , y(x-1,y+1)(x,y+1)(x,y-1)(x+1,y+1)(x-1,y-1)(x+

39、1,y-1)(x+1,y)(x-1,y)（搜索方向）（搜索方向）采用什么數(shù)據(jù)結(jié)構(gòu)？如何處理？采用什么數(shù)據(jù)結(jié)構(gòu)？如何處理？1）8個(gè)搜索方向的表示：個(gè)搜索方向的表示：2）搜索過程如何記錄？）搜索過程如何記錄？ 坐標(biāo)增量表坐標(biāo)增量表隊(duì)列，要避免重復(fù)搜索隊(duì)列，要避免重復(fù)搜索算法描述：算法描述：建立空隊(duì)列Q；將迷宮入口點(diǎn)進(jìn)隊(duì)；置入口點(diǎn)在迷宮的值為-1; /表示已處理CurrentPoint = Q隊(duì)頭元素; /入口點(diǎn)while (CurrentPoint存在) for (k = 0; k 8; k+) /依次處理8個(gè)搜索方向 NextPoint =相對CurrentPoint第k個(gè)方向的點(diǎn); if (NextPoint可達(dá)) 將NextPoint進(jìn)隊(duì)；