棧棧的應(yīng)用舉例隊(duì)列ppt課件

1、1 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 隊(duì)列隊(duì)列 2 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 重點(diǎn)重點(diǎn): (1)棧、隊(duì)列的定義、特點(diǎn)、性質(zhì)和應(yīng)用；棧、隊(duì)列的定義、特點(diǎn)、性質(zhì)和應(yīng)用；(2)ADT棧、棧、ADT隊(duì)列的設(shè)計(jì)和實(shí)現(xiàn)以及基本操作及隊(duì)列的設(shè)計(jì)和實(shí)現(xiàn)以及基本操作及相關(guān)算法。相關(guān)算法。 難點(diǎn)難點(diǎn): (1)循環(huán)隊(duì)列中對(duì)邊界條件的處理；循環(huán)隊(duì)列中對(duì)邊界條件的處理；(2)分析棧分析棧和隊(duì)列在表達(dá)式求值、括號(hào)匹配、數(shù)制轉(zhuǎn)換、迷宮和隊(duì)列在表達(dá)式求值、括號(hào)匹配、數(shù)制轉(zhuǎn)換、迷宮求解中的應(yīng)用實(shí)例，提高利用棧和隊(duì)列解決實(shí)際問求解中的應(yīng)用實(shí)例，提高利用棧和隊(duì)列解決實(shí)際問題的應(yīng)用水平。題的應(yīng)用水平。

2、本章重點(diǎn)難點(diǎn) 3 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 隊(duì)列隊(duì)列 4 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧 3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 5 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義p棧的定義棧的定義棧棧(Stack)是一種特殊的線性表，其插入和刪除操是一種特殊的線性表，其插入和刪除操作均在表的一端進(jìn)行，是一種運(yùn)算受限的線性表。作均在表的一端進(jìn)行，是一種運(yùn)算受限的線性表。棧頂棧頂(top)是棧中允許插入和刪除的一端。是棧中允

3、許插入和刪除的一端。棧底棧底(bottom)是棧頂?shù)牧硪欢?。是棧頂?shù)牧硪欢恕棧的術(shù)語棧的術(shù)語 6 第第3 3章章 棧和隊(duì)列棧和隊(duì)列p棧的特點(diǎn)棧的特點(diǎn)p棧的示意圖棧的示意圖后進(jìn)先出后進(jìn)先出(Last In First Out，簡稱，簡稱LIFO)。又稱棧為后進(jìn)先出表又稱棧為后進(jìn)先出表(簡稱簡稱LIFO結(jié)構(gòu)結(jié)構(gòu))。 ana2a1棧底棧底棧頂棧頂入棧入棧出棧出棧3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 7 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 ADT Stack 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： p抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型?；静僮鳎夯静僮鳎?ADT StackR1 | ai

4、-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 D ai | ai ElemSet, i=1,2,.,n, n0 見下頁見下頁3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 8 第第3 3章章 棧和隊(duì)列棧和隊(duì)列InitStack(&S) /初始化棧初始化棧DestroyStack(&S) /銷毀棧銷毀棧ClearStack(&S) /清空棧清空棧StackEmpty(S) /判?？张袟？誗tackLength(S) /求棧長度求棧長度GetTop(S, &e) /取棧頂元素取棧頂元素Push(&S,

5、e) /入棧入棧Pop(&S, &e) /出棧出棧StackTravers(S, visit() /遍歷棧遍歷棧p棧的基本操作棧的基本操作3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 9 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧 3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 10 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) /- 棧的順序存儲(chǔ)表示棧的順序存儲(chǔ)表示 - #define STACK_INIT_SIZE 100; /存儲(chǔ)空間初始分配存儲(chǔ)空間初始分配量量 #define STA

6、CKINCREMENT 10; /存儲(chǔ)空間分配增存儲(chǔ)空間分配增量量 typedef struct SElemType *base; /棧底指針棧底指針 SElemType *top; /棧頂指針棧頂指針 int stacksize; /當(dāng)前可使用最大容量當(dāng)前可使用最大容量 SqStack;SqStack S;p順序棧的順序棧的C語言實(shí)現(xiàn)語言實(shí)現(xiàn) 11 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)p棧初始化過程演示棧初始化過程演示(1) 給棧給棧S申請(qǐng)?？臻g申請(qǐng)?？臻g(2) 設(shè)置基地址設(shè)置基地址S.base和棧頂?shù)刂泛蜅ｍ數(shù)刂稴SS.base(3) 設(shè)置棧容量設(shè)置棧容

7、量S.stacksize=STACK_INIT_SIZE 12 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Status InitStack (SqStack &S) / 構(gòu)造一個(gè)空棧構(gòu)造一個(gè)空棧S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S = S.base; S.stacksize = STACK_INIT_SIZE; return OK;3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)p棧初始化算法棧初始化算法 13 第第3 3章章

8、 棧和隊(duì)列棧和隊(duì)列3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)p入棧操作演示入棧操作演示(1) 如果棧滿，給棧增加容量如果棧滿，給棧增加容量abcdef(2) 將數(shù)據(jù)存入棧頂位置，棧頂后移一位將數(shù)據(jù)存入棧頂位置，棧頂后移一位SS.baseeS 14 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Status Push (SqStack &S, SElemType e) if (S - S.base = S.stacksize) S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemTyp

9、e); if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 S = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S+ = e; return OK;3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)p入棧操作演示入棧操作演示 15 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)DestroyStack(&S) /銷毀棧銷毀棧ClearStack(&S) /清空棧清空棧StackEmpty(S) /判棧空判?？誗tackLength(S) /求棧長度求棧長度GetT

10、op(S, &e) /取棧頂元素取棧頂元素Pop(&S, &e) /出棧出棧StackTravers(S, visit() /遍歷棧遍歷棧p其它棧操作討論其它棧操作討論 16 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Typedef struct SNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct Snode *next; /鏈域鏈域 SNode, *LinkStack; 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn)p鏈棧的鏈棧的C語言類型定義語言類型定義 鏈棧的實(shí)現(xiàn)與鏈表的實(shí)現(xiàn)基本相同，頭結(jié)鏈棧的實(shí)現(xiàn)與鏈表的實(shí)現(xiàn)基本相同，頭結(jié)點(diǎn)作為棧頂位置。點(diǎn)作為棧頂位置。L

11、inkStack *top; /棧頂指針棧頂指針 17 第第3 3章章 棧和隊(duì)列棧和隊(duì)列InitStack(&S) /初始化棧初始化棧DestroyStack(&S) /銷毀棧銷毀棧ClearStack(&S) /清空棧清空棧StackEmpty(S) /判?？张袟？誗tackLength(S) /求棧長度求棧長度GetTop(S, &e) /取棧頂元素取棧頂元素Push(&S, e) /入棧入棧Pop(&S, &e) /出棧出棧StackTravers(S, visit() /遍歷棧遍歷棧p討論鏈?；静僮鞯膶?shí)現(xiàn)討論鏈?；静僮鞯膶?shí)現(xiàn)3

12、.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 18 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換3.2.2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)3.2.3 行編輯程序問題行編輯程序問題3.2.4 迷宮求解迷宮求解3.2.5 表達(dá)式求值表達(dá)式求值 19 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換00122.YaYaYaYaNnnX 任何任何X進(jìn)制數(shù)進(jìn)制數(shù)N轉(zhuǎn)換成轉(zhuǎn)換成Y進(jìn)制數(shù)其結(jié)果都是要化進(jìn)制數(shù)其結(jié)果都是要化成如下形式。成如下形式。p進(jìn)制轉(zhuǎn)換原理：進(jìn)制轉(zhuǎn)換原理： 轉(zhuǎn)換的過程就是通過取余運(yùn)算求出轉(zhuǎn)換的過程就是通過取余運(yùn)算求出a0,a1,an，而先

13、求出的是個(gè)位，十位而先求出的是個(gè)位，十位，與我們寫數(shù)的習(xí)慣先，與我們寫數(shù)的習(xí)慣先從高位寫正好相反，通過棧先進(jìn)后出的特點(diǎn)，很容從高位寫正好相反，通過棧先進(jìn)后出的特點(diǎn)，很容易實(shí)現(xiàn)倒過來的過程。易實(shí)現(xiàn)倒過來的過程。 20 第第3 3章章 棧和隊(duì)列棧和隊(duì)列過程如下：過程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2輸出順序輸出順序計(jì)算順序計(jì)算順序3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例例將將10進(jìn)制進(jìn)制1346轉(zhuǎn)換成轉(zhuǎn)換成8進(jìn)制進(jìn)制 21 第第3 3章章 棧和隊(duì)列棧和隊(duì)列void conversion () InitStack(S); scanf (%d,N)

14、; while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換p10進(jìn)制數(shù)進(jìn)制數(shù)N轉(zhuǎn)換成轉(zhuǎn)換成8進(jìn)制的算法進(jìn)制的算法 22 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 一個(gè)表達(dá)式中，包含三種括號(hào)一個(gè)表達(dá)式中，包含三種括號(hào)“(”和和“)”，“”和和“”和和“”和和“”，這三種括號(hào)可以按任意的合，這三種括號(hào)可以按任意的合法次序使用。法次序使用。 設(shè)計(jì)算法檢驗(yàn)表達(dá)式中所使用括號(hào)的合法性。設(shè)計(jì)算法檢驗(yàn)表達(dá)式中所使用括號(hào)的合法性。3.2.2 括號(hào)匹配的

15、檢驗(yàn)括號(hào)匹配的檢驗(yàn)p問題描述問題描述 討論：如果第一次遇到的右括號(hào)是討論：如果第一次遇到的右括號(hào)是“”，那么前，那么前面出現(xiàn)的左括號(hào)有什么特點(diǎn)。面出現(xiàn)的左括號(hào)有什么特點(diǎn)。 p問題討論問題討論 結(jié)論：如果第一次遇到的右括號(hào)是結(jié)論：如果第一次遇到的右括號(hào)是“”，那么前，那么前面出現(xiàn)的左括號(hào)最后一個(gè)必然是面出現(xiàn)的左括號(hào)最后一個(gè)必然是“”，否則不合法。，否則不合法。 23 第第3 3章章 棧和隊(duì)列棧和隊(duì)列p算法過程算法過程3.2.2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)當(dāng)遇到左括號(hào)時(shí)，進(jìn)棧，遇到右括號(hào)時(shí)出棧；當(dāng)遇到左括號(hào)時(shí)，進(jìn)棧，遇到右括號(hào)時(shí)出棧；(2) 當(dāng)遇到某一個(gè)右括號(hào)時(shí)，棧已空，說明到當(dāng)遇到某一個(gè)右括號(hào)

16、時(shí)，棧已空，說明到目前為止，右括號(hào)多于左括號(hào)；目前為止，右括號(hào)多于左括號(hào)；(3) 從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)從棧中彈出的左括號(hào)與當(dāng)前檢驗(yàn)的右括號(hào)類型不同，說明出現(xiàn)了括號(hào)交叉情況；類型不同，說明出現(xiàn)了括號(hào)交叉情況；(4) 算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號(hào)，說明左括號(hào)多于右括號(hào)。配的左括號(hào)，說明左括號(hào)多于右括號(hào)。 24 第第3 3章章 棧和隊(duì)列棧和隊(duì)列Status check( ) char ch; InitStack(S); while (ch=getchar()!=#) switch (ch) case (ch=(|ch=|ch=):

17、Push(S,ch);break; case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= () return FALSE; break;p括號(hào)匹配檢驗(yàn)算法括號(hào)匹配檢驗(yàn)算法3.2.2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn) 25 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= ) return FALSE; break; default:break; if (StackEmpty(S) return TRUE

18、;else return FALSE;p括號(hào)匹配檢驗(yàn)算法括號(hào)匹配檢驗(yàn)算法3.2.2 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn) 26 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.2.3 行編輯程序問題行編輯程序問題 設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符，為退格符，“”“”為退行符。為退行符。 在用戶輸入一行的過程中，允許用戶輸入出差在用戶輸入一行的過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。p解決辦法解決辦法p問題描述問題描述 27 第第3

19、 3章章 棧和隊(duì)列棧和隊(duì)列假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#es#*s) outchaputchar(*s=#+);則實(shí)際有效的是下列兩行：則實(shí)際有效的是下列兩行： while (*s) putchar(*s+);例例3.2.3 行編輯程序問題行編輯程序問題 28 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 DestroyStack(S);void LineEdit() /利用字符棧利用字符棧S，從終端接收一行并傳送至調(diào)，從終端接收一行并傳送至調(diào) /用過程的數(shù)據(jù)區(qū)用過程的數(shù)據(jù)區(qū) InitStack(S); ch=getchar(); . 3.2.3 行編輯程

20、序問題行編輯程序問題p行編輯問題算法行編輯問題算法while (ch != EOF) /EOF為全文結(jié)束符為全文結(jié)束符 while (ch != EOF & ch != n) 29 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); / 從終端接收下一個(gè)字符從終端接收下一個(gè)字符 ClearStack(S); / 重置重置S為空棧為空棧if (ch !=

21、EOF) ch = getchar(); 棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；3.2.3 行編輯程序問題行編輯程序問題p行編輯問題算法行編輯問題算法 30 第第3 3章章 棧和隊(duì)列棧和隊(duì)列入口入口出口出口3.2.4 迷宮求解迷宮求解如圖表示一個(gè)迷宮，有一個(gè)入口，一個(gè)出口，從一個(gè)如圖表示一個(gè)迷宮，有一個(gè)入口，一個(gè)出口，從一個(gè)位置可以向位置可以向4個(gè)方向個(gè)方向(東、南、西、北東、南、西、北)走，白方塊表示走，白方塊表示通道，藍(lán)方塊表示墻，求從入口到出口的路徑。通道，藍(lán)方塊表示墻，求從入口到出口的路徑。p問題描述問題描述1234567812345678 31 第第3 3章

22、章 棧和隊(duì)列棧和隊(duì)列3.2.4 迷宮求解迷宮求解p求解方法求解方法“窮舉求解方法：從入口出發(fā)，順某一方向向前探窮舉求解方法：從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到一個(gè)方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為止。為了保證在任何位置上都能沿原路退回，需要一個(gè)后為了保證在任何位置上都能沿原路退回，需要一個(gè)后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，求解迷宮通路算法需要應(yīng)用求解迷宮通路算法需要應(yīng)用“棧來保存當(dāng)前路

23、徑。棧來保存當(dāng)前路徑。 32 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.2.4 迷宮求解迷宮求解p 四周墻壁解決辦法如圖四周墻壁解決辦法如圖012345678901234567891234567812345678 33 第第3 3章章 棧和隊(duì)列棧和隊(duì)列p當(dāng)前位置：在搜索過程中某一時(shí)刻所在圖中某個(gè)方當(dāng)前位置：在搜索過程中某一時(shí)刻所在圖中某個(gè)方塊位置。塊位置。p當(dāng)前位置可通：未承走到過的通道塊，該方塊既不當(dāng)前位置可通：未承走到過的通道塊，該方塊既不在當(dāng)前路徑上，也不是曾經(jīng)納入過路徑的通道塊。在當(dāng)前路徑上，也不是曾經(jīng)納入過路徑的通道塊。3.2.4 迷宮求解迷宮求解01234567890123456789p

24、下一位置：當(dāng)前位下一位置：當(dāng)前位置四周置四周4個(gè)方向個(gè)方向(東、東、南、西、北南、西、北)上相鄰上相鄰的方塊。的方塊。當(dāng)前當(dāng)前位置位置(3,3)(3,2)(2,2)(1,2)當(dāng)前路徑當(dāng)前路徑 34 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.2.4 迷宮求解迷宮求解p 算法思想算法思想(1)若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入，則納入“當(dāng)前路徑當(dāng)前路徑”，并繼續(xù)朝，并繼續(xù)朝“下一位置探求，即切換下一位置探求，即切換“下一位置為下一位置為“當(dāng)前位置當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；如此重復(fù)直至到達(dá)出口；(2)若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則應(yīng)順著，則應(yīng)順著“來向退回到來向退回到“前前一通道塊

25、一通道塊”，然后朝著除了，然后朝著除了“來向之外的其他方向繼來向之外的其他方向繼續(xù)探索；續(xù)探索；(3)若該通道塊的四周若該通道塊的四周4個(gè)方塊均個(gè)方塊均“不可通不可通”，則應(yīng)從，則應(yīng)從“當(dāng)當(dāng)前路徑上刪除該通道塊。前路徑上刪除該通道塊。 35 第第3 3章章 棧和隊(duì)列棧和隊(duì)列設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通，若當(dāng)前位置可通， 那么將當(dāng)前位置插入棧頂；那么將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束；若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置；新的當(dāng)前位置； 否則否則 .whil

26、e (棧不空）；棧不空）；p迷宮路徑求解算法迷宮路徑求解算法3.2.4 迷宮求解迷宮求解 36 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為則設(shè)定新的當(dāng)前位置為: 沿順時(shí)針方向旋轉(zhuǎn)找沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通，那么若棧不空但棧頂位置的四周均不可通，那么 刪去棧頂位置；刪去棧頂位置； 若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置， 直至找到一個(gè)可通的相鄰塊或出棧至?？?；直至找到一個(gè)可通的相鄰塊或出棧至?？?；

27、若?？?，則表明迷宮沒有通路。若?？?，則表明迷宮沒有通路。p迷宮路徑求解算法迷宮路徑求解算法3.2.4 迷宮求解迷宮求解 37 第第3 3章章 棧和隊(duì)列棧和隊(duì)列012345678901234567893.2.4 迷宮求解迷宮求解p求解過程示例求解過程示例 38 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.2.5 表達(dá)式求值表達(dá)式求值 一個(gè)表達(dá)式由操作數(shù)一個(gè)表達(dá)式由操作數(shù)(operand)、運(yùn)算符、運(yùn)算符(operator)、界限符、界限符(delimiter)組成。寫出組成。寫出“算符算符優(yōu)先法求值的算法。優(yōu)先法求值的算法。p問題描述問題描述例例求求3*(2+3*5)+6的值的值 39 第第3 3章章

28、棧和隊(duì)列棧和隊(duì)列 設(shè)置兩個(gè)棧，一個(gè)存操作數(shù)，棧名為設(shè)置兩個(gè)棧，一個(gè)存操作數(shù)，棧名為OPND，一個(gè)存操作符，棧名為一個(gè)存操作符，棧名為OPTR棧。棧。 (1) 首先置操作數(shù)棧為空，表達(dá)式起始符首先置操作數(shù)棧為空，表達(dá)式起始符#為運(yùn)為運(yùn)算符棧的棧底元素；算符棧的棧底元素； (2)依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則依次讀入表達(dá)式中每個(gè)字符，若是操作數(shù)則進(jìn)進(jìn)OPND棧，若是運(yùn)算符則和棧，若是運(yùn)算符則和OPTR棧的棧頂運(yùn)算棧的棧頂運(yùn)算符比較優(yōu)先權(quán)后作相應(yīng)操作，直到整個(gè)表達(dá)式操作符比較優(yōu)先權(quán)后作相應(yīng)操作，直到整個(gè)表達(dá)式操作完畢。完畢。3.2.5 表達(dá)式求值表達(dá)式求值p算法求解過程算法求解過程 40 第

29、第3 3章章 棧和隊(duì)列棧和隊(duì)列 (1)若棧頂運(yùn)算符小于輸入運(yùn)算符，輸入運(yùn)算符若棧頂運(yùn)算符小于輸入運(yùn)算符，輸入運(yùn)算符進(jìn)棧進(jìn)棧OPTR； (2)若棧頂運(yùn)算符等于輸入運(yùn)算符只有棧頂是若棧頂運(yùn)算符等于輸入運(yùn)算符只有棧頂是“（”，輸入是，輸入是“）”，或者棧頂是，或者棧頂是“#”，輸入是，輸入是“#）”兩種情況，分別去除一對(duì)括號(hào)，或結(jié)束。兩種情況，分別去除一對(duì)括號(hào)，或結(jié)束。 (3)若棧頂運(yùn)算符大于輸入運(yùn)算符，彈出棧頂運(yùn)若棧頂運(yùn)算符大于輸入運(yùn)算符，彈出棧頂運(yùn)算符，從算符，從OPND中彈出兩個(gè)操作數(shù)與彈出運(yùn)算符計(jì)算中彈出兩個(gè)操作數(shù)與彈出運(yùn)算符計(jì)算后再存入后再存入OPND棧，繼續(xù)。棧，繼續(xù)。3.2.5 表達(dá)式

30、求值表達(dá)式求值p算法求解過程算法求解過程 41 第第3 3章章 棧和隊(duì)列棧和隊(duì)列OperandType EvaluateExpression() initStack(OPTR);Push(OPTR,#); initStack(OPND);c=getchar(); while(c!=#)|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c);c=getchar(); else switch(Precede(GetTop(OPTR),c)3.2.5 表達(dá)式求值表達(dá)式求值p表達(dá)式求值算法表達(dá)式求值算法 42 第第3 3章章 棧和隊(duì)列棧和隊(duì)列case : Pop(OPT

31、R,theta); Pop(OPND,a); Pop(OPND,b); Push(OPND,Operate(a,theta,b);break; /switch語句結(jié)束語句結(jié)束 /while 語句結(jié)束語句結(jié)束 return(GetTop(OPND); /算法結(jié)束算法結(jié)束p表達(dá)式求值算法表達(dá)式求值算法 43 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 隊(duì)列隊(duì)列 44 第第3 3章章 棧和隊(duì)列棧和隊(duì)列p隊(duì)列的定義隊(duì)列的定義3.4.1 抽象數(shù)據(jù)類型隊(duì)列的定義抽象數(shù)據(jù)類型隊(duì)列的定義 隊(duì)列隊(duì)列(Queue)是一種運(yùn)算受限的特殊的線性是一種運(yùn)算受限的特殊的線性表

32、，它只允許在表的一端進(jìn)行插入，而在表的另一表，它只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。端進(jìn)行刪除。 隊(duì)尾隊(duì)尾(rear)是隊(duì)列中允許插入的一端。是隊(duì)列中允許插入的一端。 隊(duì)頭隊(duì)頭(front)是隊(duì)列中允許刪除的一端。是隊(duì)列中允許刪除的一端。p隊(duì)列的術(shù)語隊(duì)列的術(shù)語 45 第第3 3章章 棧和隊(duì)列棧和隊(duì)列p隊(duì)列的特點(diǎn)隊(duì)列的特點(diǎn)p隊(duì)列示意圖隊(duì)列示意圖3.4.1 抽象數(shù)據(jù)類型隊(duì)列的定義抽象數(shù)據(jù)類型隊(duì)列的定義a1a2a3 an隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾出隊(duì)出隊(duì)出隊(duì)出隊(duì) 先進(jìn)先出先進(jìn)先出(First In First Out ，簡稱，簡稱FIFO)。 又稱隊(duì)列為先進(jìn)先出表。又稱隊(duì)列為先進(jìn)先出表。 46

33、第第3 3章章 棧和隊(duì)列棧和隊(duì)列 ADT Queue 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： p抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型?；静僮鳎夯静僮鳎?ADT Queue見下頁見下頁3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義Dai | aiElemSet, i=1,2,.,n, n0R1 | ai-1, ai D, i=2,.,n約定其中約定其中a1 端為隊(duì)列頭，端為隊(duì)列頭， an 端為隊(duì)列尾端為隊(duì)列尾 47 第第3 3章章 棧和隊(duì)列棧和隊(duì)列InitQueue(&Q) /初始化隊(duì)列初始化隊(duì)列DestroyQueue(&Q) /銷毀隊(duì)列銷毀隊(duì)列QueueEmpty(Q)

34、/判隊(duì)列是否空判隊(duì)列是否空QueueLength(Q) /求隊(duì)列長度求隊(duì)列長度GetHead(Q, &e) /取隊(duì)頭元素取隊(duì)頭元素ClearQueue(&Q) /清空隊(duì)列清空隊(duì)列EnQueue(&Q, e) /入隊(duì)列入隊(duì)列DeQueue(&Q, &e) /出隊(duì)列出隊(duì)列QueueTravers(Q, visit() /遍歷隊(duì)列遍歷隊(duì)列p隊(duì)列的基本操作隊(duì)列的基本操作3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 48 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.4.2 鏈隊(duì)列鏈隊(duì)列 typedef struct QNode / 結(jié)點(diǎn)類型結(jié)點(diǎn)類型 QElemTy

35、pe data; struct QNode *next; QNode, *QueuePtr;p鏈隊(duì)列結(jié)點(diǎn)實(shí)現(xiàn)鏈隊(duì)列結(jié)點(diǎn)實(shí)現(xiàn)typedef struct / 鏈隊(duì)列類型鏈隊(duì)列類型 QueuePtr front; / 隊(duì)頭指針隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針隊(duì)尾指針 LinkQueue;p鏈隊(duì)列數(shù)據(jù)類型實(shí)現(xiàn)鏈隊(duì)列數(shù)據(jù)類型實(shí)現(xiàn) 49 第第3 3章章 棧和隊(duì)列棧和隊(duì)列Q.frontQ.rearp帶頭結(jié)點(diǎn)的鏈隊(duì)列示意圖帶頭結(jié)點(diǎn)的鏈隊(duì)列示意圖3.4.2 鏈隊(duì)列鏈隊(duì)列頭結(jié)點(diǎn)頭結(jié)點(diǎn)空隊(duì)列空隊(duì)列a1a2anQ.frontQ.rear 50 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Status In

36、itQueue (LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列構(gòu)造一個(gè)空隊(duì)列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 Q.front-next = NULL; return OK;3.4.2 鏈隊(duì)列鏈隊(duì)列p帶頭結(jié)點(diǎn)的鏈隊(duì)列初始化帶頭結(jié)點(diǎn)的鏈隊(duì)列初始化 51 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素插入元素e為為Q的新的隊(duì)尾元素的新的隊(duì)

37、尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗存儲(chǔ)分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;3.4.2 鏈隊(duì)列鏈隊(duì)列p帶頭結(jié)點(diǎn)的鏈隊(duì)列入隊(duì)算法帶頭結(jié)點(diǎn)的鏈隊(duì)列入隊(duì)算法 52 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除若隊(duì)列不空，則刪除Q的隊(duì)頭元素，的隊(duì)頭元素， /用用 e 返回

38、其值，并返回返回其值，并返回OK；否則返回；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;3.4.2 鏈隊(duì)列鏈隊(duì)列p帶頭結(jié)點(diǎn)的鏈隊(duì)列出隊(duì)算法帶頭結(jié)點(diǎn)的鏈隊(duì)列出隊(duì)算法 53 第第3 3章章 棧和隊(duì)列棧和隊(duì)列DestroyQueue(&Q) /銷毀隊(duì)列銷毀隊(duì)列QueueEmpty(Q) /判隊(duì)列是否空判隊(duì)列是否空QueueLength

39、(Q) /求隊(duì)列長度求隊(duì)列長度GetHead(Q, &e) /取隊(duì)頭元素取隊(duì)頭元素ClearQueue(&Q) /清空隊(duì)列清空隊(duì)列QueueTravers(Q, visit() /遍歷隊(duì)列遍歷隊(duì)列3.4.2 鏈隊(duì)列鏈隊(duì)列p帶頭結(jié)點(diǎn)的鏈隊(duì)列其它操作討論帶頭結(jié)點(diǎn)的鏈隊(duì)列其它操作討論 54 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列 循環(huán)隊(duì)列屬于順序隊(duì)列的一種，討論在采用一般循環(huán)隊(duì)列屬于順序隊(duì)列的一種，討論在采用一般順序隊(duì)列時(shí)出現(xiàn)的問題。順序隊(duì)列時(shí)出現(xiàn)的問題。 p順序隊(duì)列討論順序隊(duì)列討論43210空隊(duì)列空隊(duì)列AA入隊(duì)入隊(duì)BAB入隊(duì)入隊(duì)EDCBAC,D,E相繼相繼入隊(duì)

40、入隊(duì)Sq.rearSq.frontSq.rearSq.frontSq.rearSq.frontSq.rearSq.front 55 第第3 3章章 棧和隊(duì)列棧和隊(duì)列EDCBA隊(duì)列滿隊(duì)列滿EDCBA被刪除被刪除(出隊(duì)出隊(duì))EDCB被刪除被刪除討論結(jié)論：在采用一般順序隊(duì)列時(shí)出現(xiàn)假上溢現(xiàn)象？討論結(jié)論：在采用一般順序隊(duì)列時(shí)出現(xiàn)假上溢現(xiàn)象？C,D,E相繼相繼被刪除被刪除p順序隊(duì)列討論順序隊(duì)列討論3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列43210Sq.rearSq.frontSq.frontSq.rearSq.rearSq.frontSq.frontSq.rear 56 第第3 3章章 棧和隊(duì)列棧和隊(duì)列p循環(huán)隊(duì)列示意

41、圖循環(huán)隊(duì)列示意圖3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列01234CDESq.frontSq.rear01234CDESq.frontSq.rearFF入隊(duì)入隊(duì)01234CDESq.frontSq.rearFGG入隊(duì)入隊(duì) 57 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列#define MAXQSIZE 100 /最大隊(duì)列長度最大隊(duì)列長度 typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空，頭指針，若隊(duì)列不空， / 指向隊(duì)列頭元素指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向尾

42、指針，若隊(duì)列不空，指向 隊(duì)列尾元素隊(duì)列尾元素 的下一個(gè)位置的下一個(gè)位置 SqQueue;SqQueue Sq;p鏈隊(duì)列數(shù)據(jù)類型實(shí)現(xiàn)鏈隊(duì)列數(shù)據(jù)類型實(shí)現(xiàn) 58 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 循環(huán)隊(duì)列是順序隊(duì)列的一種特例，它是把順序隊(duì)循環(huán)隊(duì)列是順序隊(duì)列的一種特例，它是把順序隊(duì)列構(gòu)造成一個(gè)首尾相連的循環(huán)表。指針和隊(duì)列元素之列構(gòu)造成一個(gè)首尾相連的循環(huán)表。指針和隊(duì)列元素之間關(guān)系不變。間關(guān)系不變。3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列p循環(huán)隊(duì)列的定義循環(huán)隊(duì)列的定義01maxsize-1Sq.frontSq.rear 59 第第3 3章章 棧和隊(duì)列棧和隊(duì)列3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列p循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)的討論循

43、環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)的討論討論結(jié)論：討論結(jié)論：循環(huán)隊(duì)列空狀循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)都態(tài)和滿狀態(tài)都滿足滿足Q.front=Q.rear01234CDESq.frontSq.rearFG滿隊(duì)列滿隊(duì)列01234Sq.frontSq.rear空隊(duì)列空隊(duì)列 60 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 (1) 另設(shè)一個(gè)標(biāo)志區(qū)別隊(duì)列是空還是滿；另設(shè)一個(gè)標(biāo)志區(qū)別隊(duì)列是空還是滿；3.4.3 循環(huán)隊(duì)列循環(huán)隊(duì)列p循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)的判別循環(huán)隊(duì)列空狀態(tài)和滿狀態(tài)的判別 例如：設(shè)一個(gè)變量例如：設(shè)一個(gè)變量count用來記錄隊(duì)列中元素個(gè)用來記錄隊(duì)列中元素個(gè)數(shù)，當(dāng)數(shù)，當(dāng)count=0時(shí)隊(duì)列為空，當(dāng)時(shí)隊(duì)列為空，當(dāng)count= MAXQSIZE時(shí)隊(duì)列為滿。時(shí)隊(duì)列為滿。 61 第第3 3章章 棧和隊(duì)列棧和隊(duì)列 (2)隊(duì)滿條件：以隊(duì)頭指針在隊(duì)列尾指針的下隊(duì)滿條件：以隊(duì)頭指針在隊(duì)列尾指針的下一位置作為隊(duì)列呈滿狀態(tài)的標(biāo)志，犧牲一個(gè)存儲(chǔ)一位置作為隊(duì)列