1、第三章 棧 和 隊(duì)列,3.1 棧 3.2 棧的應(yīng)用舉例 *3.3 棧與遞歸的實(shí)現(xiàn) 3.4 隊(duì)列 *3.5 離散事件模擬,從數(shù)據(jù)結(jié)構(gòu)的角度看: 棧、隊(duì)列和線性表相同 從數(shù)據(jù)類型的角度看: 棧、隊(duì)列和線性表不同 ListInsert(L, i, e) (1in+1) ListInsert(S, n+1, e) ListDelete(L, i，e)(1in) ListDelete(S, n),棧底,棧頂,只允許在一端插入和刪除操作的線性表. 允許插入和刪除的一端 稱為棧頂 (top)，另一端 稱為棧底(base) 特點(diǎn): 后進(jìn)先出 (LIFO),3.1 棧 ( Stack ),退棧,進(jìn)棧,a1,an

2、,an-1,top,base,ADT Stack 數(shù)據(jù)對(duì)象：D ai |aiElemSet,i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1|ai-1,aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作： InitStack(/存儲(chǔ)空間初始分配量 #define STACKINCREMENT 10;/存儲(chǔ)空間分配增量 typedef struct SElemType *base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; /當(dāng)前已分配的存儲(chǔ)空間,以元素為單位 SqStack;,空棧:S.base=S.top (初始化狀態(tài)),a,b,c

3、,d,e,棧滿:S.top-S.base=S.stacksize,若棧結(jié)構(gòu)不存在，base為NULL,棧頂指針始終是指在棧頂元素的后面一個(gè)位置,順序棧的初始化操作 Status InitStack(SqStack / InitStack,獲取棧頂元素操作,Status GetTop(SqStack S, SElemType /GetTop,進(jìn)棧操作,Status Push(SqStack /Push,出棧操作,Status Pop(SqStack /Pop,- - S.top;,e=*(S.top-1);,棧的鏈接存儲(chǔ)表示 鏈棧,插入與刪除僅在棧頂處執(zhí)行,非常簡(jiǎn)單,不作討論。,鏈棧: 利用鏈表

4、實(shí)現(xiàn)棧 注意鏈表中指針的方向是從棧頂?shù)綏５住?3.2 棧的應(yīng)用舉例,問(wèn)題有后進(jìn)先出的特點(diǎn) 例一 數(shù)制轉(zhuǎn)換 例二 括號(hào)匹配的檢驗(yàn) 例三 行編輯程序問(wèn)題 例四 迷宮求解 例五 表達(dá)式求值 例六 實(shí)現(xiàn)遞歸（3.3）,例一 數(shù)制轉(zhuǎn)換 十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題,其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理： N = (N div d)d + N mod d (其中:div為整除運(yùn)算，mod為求余運(yùn)算） 例如：（1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,輸出順

5、序,void conversion( ) /對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù),打印輸出與其等值的八進(jìn)制數(shù) InitStack(S); / 構(gòu)造空棧 scanf(%d,N); while(N) Push(S, N % 8); N = N/8; while(!StackEmpty(S) Pop(S,e); printf ( %d, e ); /conversion,例二 括號(hào)匹配的檢驗(yàn),假設(shè)表達(dá)式中允許包含兩種括號(hào): 即（）或（ ）等為正確的格式 （ ）或 ( )或（ ）均為不正確的格式。 檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。 例如考慮下列括號(hào)序列： ( ) 1 2 3 4

6、 5 6 7 8 分析可能出現(xiàn)的不匹配的情況: 到來(lái)的右括弧非是所“期待”的; 到來(lái)的是“不速之客”; 直到結(jié)束，也沒(méi)有到來(lái)所“期待”的。,算法設(shè)計(jì)思想： 1)凡出現(xiàn)左括號(hào)，則進(jìn)棧； 2)凡出現(xiàn)右括號(hào)，首先檢查棧是否空 若?？眨瑒t表明右括號(hào)多了； 否則和棧頂元素比較,若匹配,則左括號(hào)出棧； 否則不匹配； 3)表達(dá)式檢驗(yàn)結(jié)束時(shí) 若?？?，則匹配正確； 否則表明左括號(hào)多了，不匹配；,status matching(SqList exp) /順序表exp中存有數(shù)據(jù)元素為字符的表達(dá)式,檢驗(yàn)表達(dá)式中所含括弧是否正確嵌套,若是,則返回OK,否則返回ERROR state= 1; i =0; InitStac

7、k(S); while (i exp.length /matching,作業(yè),1、從鍵盤輸入一個(gè)整數(shù)序列：a1,a2,a3，an,編寫算法PushPops實(shí)現(xiàn);用棧存儲(chǔ)輸入的整數(shù)序列,當(dāng)ai-1時(shí),將ai進(jìn)棧;當(dāng)ai=-1時(shí),輸出棧頂元素并出棧.算法應(yīng)對(duì)異常情況(棧滿,棧空)等給出相應(yīng)信息。,void PushPops (SqStack ,1、從鍵盤輸入一個(gè)整數(shù)序列：a1,a2,a3，an,編寫算法PushPops實(shí)現(xiàn);用棧存儲(chǔ)輸入的整數(shù)序列,當(dāng)ai-1時(shí),將ai進(jìn)棧;當(dāng)ai=-1時(shí),輸出棧頂元素并出棧.算法應(yīng)對(duì)異常情況(棧滿,棧空)等給出相應(yīng)信息。,例三 行編輯程序問(wèn)題,一個(gè)簡(jiǎn)單的行編輯程序

8、的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。 “每接收一個(gè)字符即存入用戶數(shù)據(jù)區(qū)”不恰當(dāng)。 較好的做法是：設(shè)立一個(gè)輸入緩沖區(qū)，用以接收用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。,退格符： # 退行符： 例如，假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+); 則實(shí)際有效的是下列兩行： while (*s) putchar(*s+);,保留已經(jīng)輸入的字符的緩沖區(qū)結(jié)構(gòu)應(yīng)該是一個(gè)棧,void LineEdit( ) / 利用字符棧S,從終端接收一行并傳送至調(diào)用過(guò)程的數(shù)據(jù)區(qū)。 I

9、nitStack(S); ch = getchar(); /從終端接收第一個(gè)字符 while (ch != EOF) /EOF為全文結(jié)束符 while (ch != EOF / LineEdit,例五 表達(dá)式求值,限于二元運(yùn)算符的表達(dá)式定義: 表達(dá)式 : (操作數(shù))+(運(yùn)算符)+(操作數(shù)) 操作數(shù) : 簡(jiǎn)單變量 | 表達(dá)式 簡(jiǎn)單變量 : 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù),設(shè) Exp = S1 + OP + S2 在計(jì)算機(jī)中,表達(dá)式可以有三種不同的表示方法 稱 OP + S1 + S2 為表達(dá)式的前綴表示法 稱 S1 + OP + S2 為表達(dá)式的中綴表示法 稱 S1 + S2 + OP 為表達(dá)式的后綴表

10、示法 可見(jiàn)，它以運(yùn)算符所在不同位置命名的。,例如： Exp= a b +(c-d/e) f 前綴式： + a b (c-d/e) f + a b (c-d/e) f + a b - c d/e f + a b -c /d e f 中綴式： a b + c-d/e f 后綴式： a b (c-d/e) f+ a b (c-d/e) f+ a b cd/e- f+ a b cde/- f+,寫出 23 +(12*3-2)/4 +34*5/7)+108/9 的后綴表達(dá)式： 23 12 3*2-4/34 5*7/+108 9/+,結(jié)論 1)操作數(shù)之間的相對(duì)次序不變; 2)運(yùn)算符的相對(duì)次序不同; 3)中

11、綴式丟失了括弧信息，致使運(yùn)算的次序不確定; 4)前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們 之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式; 5)后綴式的運(yùn)算規(guī)則為: 運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序; 每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式; 如何從后綴式求值？先找運(yùn)算符，后找操作數(shù),后綴式計(jì)算機(jī)處理起來(lái)比較方便，所以很多編譯程序，每碰到一個(gè)表達(dá)式先求出后綴形式，然后再求值。,如何從原表達(dá)式求得后綴式？ 分析 “原表達(dá)式” 和 “后綴式”中的運(yùn)算符 每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定,在后綴式中優(yōu)先級(jí)高的運(yùn)算符領(lǐng)先于優(yōu)先級(jí)低的運(yùn)算符，若當(dāng)前運(yùn)算符

12、的優(yōu)先數(shù)小,則暫不進(jìn)行;否則立即進(jìn)行。,從原表達(dá)式求得后綴式的規(guī)律為： 1)設(shè)立運(yùn)算符棧; 2)設(shè)表達(dá)式的結(jié)束符為“#”,設(shè)運(yùn)算符棧的棧底為“#” 3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式; 4)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧; 5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式; 6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符。,void transform(char suffix, char exp ) / 從合法的表達(dá)式字符串exp求得其相應(yīng)的后綴式 InitStack(S); Push(S, #); p = exp; ch = *p; while

13、(!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); / 直接發(fā)送給后綴式 elseswitch (ch) case ( : Push(S, ch); break; case ) : Pop(S,c); while(c!=() Pass(Suffix,c);Pop(S,c) break; defult: while(!Gettop(S,c) / while / CrtExptree,OperandType EvaluateExpression() /算術(shù)表達(dá)式求值的算符優(yōu)先算法.設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧,OP為運(yùn)算符集合 In

14、itStack(OPTR); Push (OPTR,#); IinitStack(OPND); c=getchar(); while (c!=#|GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c);c=getchar();/不是運(yùn)算符則進(jìn)棧 else switch (precede(GetTop(OPTR), c) case # /退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b);break; / switch / while return GetT

15、op(OPND); / EvaluateExpression,3.3 實(shí)現(xiàn)遞歸,遞歸( recursion)做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用.是指函數(shù)在運(yùn)行過(guò)程序中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)像.用遞歸思想寫出的程序往往十分簡(jiǎn)潔易懂。 設(shè)a是含n個(gè)分量的整數(shù)數(shù)組,寫出求n個(gè)整數(shù)之和 f(n)的遞歸定義：,void hanoi (int n, char x, char y, char z) /漢諾塔問(wèn)題：將塔座x上按直徑由小到大且至上而下編號(hào) /為1至n的n個(gè)圓盤按規(guī)則搬到塔座z上,y可用作輔助塔座 if(n=1) move(x,1,z);/將編號(hào)為的圓盤從x移到z else hanoi

16、(n-1,x,z,y);/將x上編號(hào)為至n-1的圓盤 移到y(tǒng),z作輔助塔 move(x,n,z); hanoi(n-1,y,x,z); ,3,2,1,hanoi (3,a,b,c),1,2,1,3,1,2,1,3.4 隊(duì)列 ( Queue ),定義 隊(duì)列是只允許在一端插入,在另一端刪除的順序表。 允許插入的一端叫做隊(duì)尾(rear) ,允許刪除的一端叫做隊(duì)頭(front)。 特性 先進(jìn)先出(FIFO, First In First Out),抽象數(shù)據(jù)類型隊(duì)列的定義 ADT Queue 數(shù)據(jù)對(duì)象：Dai | aiElemSet,i=1,2,.,n, n0 數(shù)據(jù)關(guān)系:R1 |ai-1, aiD, i

17、=2,.,n 約定其中a1 端為隊(duì)列頭，an 端為隊(duì)列尾。 基本操作： InitQueue( struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; / 隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針 LinkQueue;,Q.rear,Q.front,Q.front,Q.front,/- 基本操作的函數(shù)原型說(shuō)明 - Status InitQueue (LinkQueue InitQueue(Q); ch=getchar( ); while(ch!=) Push(S, ch); EnQueue(Q, ch)

18、; ch=getchar( ); state=TRUE; while(!StackEmpty(S) ,判斷abcba是否是回文,a,b,c,b,a,a,b,a,b,c,鏈隊(duì)列鏈?zhǔn)接诚?typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; / 隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針 LinkQueue;,Q.rear,Q.front,3.4.3 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn) #define MAXQSIZE 10 /最大隊(duì)列長(zhǎng)

19、度 typedef struct QElemType *base; / 初始化的動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空，指向隊(duì)列頭元素 int rear;/尾指針,若隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置 SqQueue;,普通的順序存儲(chǔ)隊(duì)滿時(shí)再進(jìn)隊(duì)將溢出出錯(cuò)； 解決辦法之一：將隊(duì)列元素存放數(shù)組首尾相接， 形成循環(huán)(環(huán)形)隊(duì)列。,0,1,2,3,4,5,6,7,Q.front:0,Q.rear:0,空隊(duì)列,Q.base,隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則,進(jìn)隊(duì)時(shí)隊(duì)尾指針先進(jìn)一 rear = rear + 1， 再將新元素按 rear 指示位置加入。 出隊(duì)時(shí)隊(duì)頭指針先進(jìn)一 front =

20、 front + 1， 再將下標(biāo)為 front 的元素取出。,隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。 隊(duì)頭、隊(duì)尾指針加1時(shí)從MAXQSIZE -1直接進(jìn)到0，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。 隊(duì)頭指針進(jìn)1: Q.front = (Q.front+1) % MAXQSIZE; 隊(duì)尾指針進(jìn)1: Q.rear = (Q.rear+1) % MAXQSIZE; 隊(duì)列初始化：Q.front = Q.rear = 0; 隊(duì)空條件：Q.front = Q.rear; 隊(duì)滿條件：(Q.rear+1) % MAXQSIZE = Q.front,循環(huán)隊(duì)列 (Circular Queue),P64,0,1,2,3,4

21、,5,6,7,front,0,1,2,3,6,7,front,A,A,B,C,rear,rear,A進(jìn)隊(duì),B, C進(jìn)隊(duì),0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A退隊(duì),B退隊(duì),0,1,2,3,4,5,6,7,D,E,F,G,H,I進(jìn)隊(duì),front,B,C,rear,A,front,B,C,rear,front,C,rear,D,E,F,G,H,I,0,1,2,3,4,5,6,7,front,rear,空隊(duì)列,練習(xí)：假設(shè)循環(huán)隊(duì)列定義為：以域變量rear和length分別指示循環(huán)隊(duì)列中隊(duì)尾元素的下一個(gè)位置和內(nèi)含元素的個(gè)數(shù)。給出此循環(huán)隊(duì)列的隊(duì)滿條件，并寫出相應(yīng)的入隊(duì)列和出隊(duì)列

22、的算法。 隊(duì)滿條件 Q.length= MAXQSIZE; 1）入隊(duì)列操作 Status EnQueue(SqQueue / EnQueue,2）出隊(duì)列操作 Status DeQueue(SqQueue / DeQueue,將隊(duì)列Q中元素逆置。（使用順序棧進(jìn)行過(guò)渡，要求使用基本操作實(shí)現(xiàn)） Status ReverseQueue(SqQueue / ReverseQueue,練習(xí),1、設(shè)棧的輸入序列是1，2，3，4，5，則（ ）不可能是其出棧序列。 A. 54321 B. 45321 C. 43512 D. 12345 2、若已知一個(gè)棧的入棧序列是1，2，3，,n,其輸出序列為p1,p2,p3,pn，若p1=n,則pi為（ ）。 A. i B.n=i C.n-i+1 D.不確定,C,C,4、一個(gè)遞歸算法必須包括（ ） A.遞歸部分 B.終止條件和遞歸部分 C.迭代部分 D.終止條件和迭代部分 5、用鏈表方式存儲(chǔ)的隊(duì)列，在進(jìn)