第三章 棧和隊(duì)列.ppt

1、2020/8/1,1,第三章棧和隊(duì)列,兩種特殊的線性表,2020/8/1,2,棧和隊(duì)列,3.1 棧 3.2 棧的應(yīng)用舉例 3.3 棧與遞歸 3.4 隊(duì)列,2020/8/1,3,3.1 棧,棧是僅限定在表的一端操作的線性表。它的插入和刪除都只能在表的一端進(jìn)行。,定義,2020/8/1,4,ADT Stack 數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。,基本操作：, ADT Stack,3.1.1 棧的類型定義,2020/8/1,5,InitStack( stack;

2、 stack S;,s,top,2020/8/1,8,棧的順序存儲,# define Maxsize 100+1 typedef struct elemtype STMaxsize int top; stack; stack S;,top,s,2020/8/1,9,棧的順序存儲,1.?？盏臈l件： S.top = 0,2020/8/1,10,2. 棧的壓入操作,Push( ,2020/8/1,11,2. 棧的壓入操作,Push( ,23,50,2020/8/1,12,3. 棧的彈出操作,pop ( ,23,50,2020/8/1,13,例題,一個棧的入棧序列是12345，則棧的不可能的出棧序列是

3、什么？ 判斷一個順序棧st(最多元素為maxsize)為?？説e棧滿的條件分別是 和 A) st-top !=0 B) st-top=0 C) st-top != maxsize -1 D) st-top = maxsize -1,B,D,2020/8/1,14,棧的鏈?zhǔn)酱鎯?進(jìn)棧 出棧 讀棧頂元素,2020/8/1,15,3.2 棧的應(yīng)用舉例,ClearStack(S) 重置S為空棧 empty (s) 判斷?？?push(s，ch) 將一個元素e推入棧s pop(s) 將棧頂元素彈出，且返回其元素 gettop(s,e) 取棧頂元素,2020/8/1,16,例1 行編輯程序問題,假設(shè)“#”

4、為退格符，表示前一個字 符無效； “”為退行符，表示當(dāng)前行無效； 設(shè)立一個棧（輸入緩沖區(qū)），用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)。,2020/8/1,17,假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,則實(shí)際有效的是下列兩行： while (*s) putchar(*s+);,2020/8/1,18,假設(shè)從終端接受了這樣兩行字符： whli#ilr#e,當(dāng) # : Pop(S,e) /彈出,當(dāng) : ClearStack(S)/清棧,否則 入棧,2020/8/1,19,假設(shè)從終端接受了這樣兩行字符： whli#ilr#

5、e,當(dāng) # : Pop(S,e) /彈出,當(dāng) : ClearStack(S)/清棧,否則 入棧,2020/8/1,20,假設(shè)從終端接受了這樣兩行字符： whli#ilr#e,當(dāng) # : Pop(S,e) /彈出,當(dāng) : ClearStack(S)/清棧,否則 入棧,while (ch != EOF / 從終端接收下一個字符 ,ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF為全文結(jié)束符,將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的 數(shù)據(jù)區(qū)；,2020/8/1,22,表達(dá)式 := (操作數(shù)1) +

6、(運(yùn)算符op) + (操作數(shù)2) 操作數(shù) := 簡單變量 | 表達(dá)式 簡單變量 : = 標(biāo)識符 | 無符號整數(shù),例2 表達(dá)式求值,-利用算符優(yōu)先級法則,2020/8/1,23,算符間的優(yōu)先級關(guān)系,2020/8/1,24,例如: Exp = a b + (c d / e) f 中綴式: #a b + c d / e f#,2020/8/1,25,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2020/8/1,26,算符間的優(yōu)先級關(guān)系,2020/8/1,27,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,+,+,2020/8/1,28,算

7、符間的優(yōu)先級關(guān)系,2020/8/1,29,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,3,2020/8/1,30,算符間的優(yōu)先級關(guān)系,2020/8/1,31,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,3,退棧,3,2,23=6,6,進(jìn)棧,10,/,2020/8/1,32,3.3 棧與遞歸的實(shí)現(xiàn),求n! Hanoi塔問題,例1 求n! (用遞歸調(diào)用),1 n=0 fac= n (n-1)! n0,int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; re

8、turn( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,求n! (用遞歸調(diào)用),1 n=0 fac= n (n-1)! n0,int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,將所有的實(shí)參、返回地址等信息傳遞給被調(diào)用函數(shù)保存； 為被調(diào)用函數(shù)的局部變量分配存儲區(qū)； 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。,求n! (用遞歸調(diào)用),1 n=0,1 fac=

9、n (n-1)! n0,int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,保存被調(diào)函數(shù)的計(jì)算結(jié)果； 釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)； 依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。,2020/8/1,36,遞歸的要點(diǎn)：,由系統(tǒng)提供一個信息棧，保留函數(shù)調(diào)用時的相關(guān)信息（調(diào)用時的信息、返回地址、局部變量）； 每執(zhí)行遞歸調(diào)用語句時，將有關(guān)信息送入棧，轉(zhuǎn)入函數(shù)入口； 每當(dāng)執(zhí)行到返回語句時，保存計(jì)算結(jié)果，釋放被調(diào)函數(shù)的

10、數(shù)據(jù)區(qū)，彈出返回地址返回。,2020/8/1,37,多個函數(shù)嵌套調(diào)用的規(guī)則是：,此時的內(nèi)存管理實(shí)行“棧式管理”,后調(diào)用先返回 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,Main的數(shù)據(jù)區(qū),函數(shù)a的數(shù)據(jù)區(qū),函數(shù)b的數(shù)據(jù)區(qū),2020/8/1,38,2020/8/1,40,例2 Hanoi 塔問題,a,b,c,2020/8/1,41,例2 Hanoi 塔問題,a,b,c,2020/8/1,42,例2 Hanoi 塔問題,a,b,c,2020/8/1,43,例2 Hanoi 塔問題,a,b,c,2020/8/1,44

11、,void hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n / 的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。 1 if (n=1) 2 move(x, 1, z); / 將編號為的圓盤從x移到z 3 else 4 hanoi(n-1, x, z, y); / 將x上編號為至n-1的 /圓盤移到y(tǒng), z作輔助塔 5 move(x, n, z); / 將編號為n的圓盤從x移到z 6 hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔 7 8 ,2020/8/1,45,v

12、oid hanoi (int n, char x, char y, char z) 1 2 if (n=1) 3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y, x, z); 8 9 ,0 3 a b c,返址 n x y z,6 2 a c b,6 1 a b c,8 1 c a b,2020/8/1,46,3.4 隊(duì)列,2020/8/1,47,3.4.1 抽象數(shù)據(jù)類型隊(duì)列的定義,隊(duì)列：是一種先進(jìn)先出的線性表，它的操作只能在表的兩端進(jìn)行。,隊(duì)尾,隊(duì)首,a1 a2 a3 an-1 an,

13、2020/8/1,48,ADT Queue 數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊(duì)列頭， an 端為隊(duì)列尾,基本操作：, ADT Queue,隊(duì)列的抽象數(shù)據(jù)類型,2020/8/1,49,隊(duì)列的基本操作：,1、InitQueue( struct QNode *next; QNode, *QPtr;,鏈隊(duì)de結(jié)點(diǎn)結(jié)構(gòu),2020/8/1,59,QPtr front; / 隊(duì)頭指針 QPtr rear; / 隊(duì)尾指針,a1,an,front,front,空隊(duì)列,rear,rear,fr

14、ont = rear,表示1,2020/8/1,60,typedef struct / 鏈隊(duì)列類型 QPtr front; / 隊(duì)頭指針 QPtr rear; / 隊(duì)尾指針 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空隊(duì)列,表示2,2020/8/1,61,Status InitQueue (LinkQueue ,2020/8/1,62,Status EnQueue (LinkQueue ,2020/8/1,63,Status DeQueue (LinkQueue ,2020/8/1,64,2020/8/1,65,3.4.3 隊(duì)列的順序存儲結(jié)構(gòu)

15、,順序隊(duì)列數(shù)組表示 隊(duì)列的順序存儲結(jié)構(gòu)稱為順序隊(duì)列。,隊(duì)首,隊(duì)尾,2020/8/1,66,1. 順序隊(duì)列數(shù)組表示,初始化建空隊(duì)列時令,front = rear = 0,2020/8/1,67,1. 順序隊(duì)列數(shù)組表示,入隊(duì)時: 加入結(jié)點(diǎn); rear+1;,J1,2020/8/1,68,1. 順序隊(duì)列數(shù)組表示,入隊(duì)：加入結(jié)點(diǎn); 頭指針rear+1;,J1,J2,J3,2020/8/1,69,1. 順序隊(duì)列數(shù)組表示,出隊(duì)： 刪除結(jié)點(diǎn); 隊(duì)頭指針front+1;,J1,J2,J3,J1,在非空隊(duì)列中，頭指針front總是指向隊(duì)頭元素，而尾指針rear總是指向隊(duì)尾元素的下一個位置,2020/8/1,70

16、,（1）入隊(duì)操作 enqueue (Q , x) if ( rear+1=MAX-1) printf (隊(duì)滿溢出) else Qrear= x; rear +; return OK; ,2順序隊(duì)列的基本運(yùn)算,2020/8/1,71,（2）出隊(duì)操作 Dequeue (Q , e) if ( front=rear) return ERROR/隊(duì)空 else e = Qfront; front +; return OK; ,2020/8/1,72,3. 循環(huán)隊(duì)列,if ( rear+1=MAX-1) 隊(duì)滿溢出 在順序隊(duì)列中，當(dāng)隊(duì)尾指針已經(jīng)指向了隊(duì)列的最后一個位置時，此時若有元素入列，就會發(fā)生“溢出”

17、。在圖中，雖然隊(duì)尾指針已經(jīng)指向最后一個位置，但事實(shí)上隊(duì)列中還有空位置。也就是說，隊(duì)列的存儲空間并沒有滿，但隊(duì)列卻發(fā)生了溢出，我們稱這種現(xiàn)象為假溢出。,2020/8/1,73,解決的方法:將隊(duì)列看成是循環(huán)表,：,2020/8/1,74,但當(dāng)隊(duì)滿時rear=front,：,2020/8/1,75,但當(dāng)隊(duì)滿時rear=front當(dāng)隊(duì)空時rear=front,：,無法判斷！,2020/8/1,76,解決的方法:少用一的單元,：,隊(duì)滿條件 (rear+1) mod max=front,2020/8/1,77,解決的方法:少用一的單元,：,隊(duì)滿條件 (rear+1) mod max=front,隊(duì)空條件

18、front=rear,2020/8/1,78,入隊(duì),Enqueue (Q, x) if (front = (rear+1) % max ) exit (over) else Qrear=x; rear= (rear+1) % max; return OK ,2020/8/1,79,出隊(duì),Delqueue (Q, e) if (front = rear) exit (over) else e=Qfront; front = (front+1) % max; return OK ,2020/8/1,80,#define MAXQSIZE 100 /最大隊(duì)列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間 int front; / 頭指針，若隊(duì)列不空， / 指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個位置 SqQueue;,循環(huán)隊(duì)