《數(shù)據(jù)結(jié)構(gòu)與算法》第三章棧和隊(duì)列解析課件

1、第三章棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列第1頁，共60頁。邏輯結(jié)構(gòu)存儲結(jié)構(gòu)操作建立。線性表廣義表串樹二叉樹圖數(shù)組堆棧和隊(duì)列順序存儲鏈?zhǔn)酱鎯λ饕⒘星宄２迦霐?shù)據(jù)元素刪除數(shù)據(jù)元素修改數(shù)據(jù)元素排序查找(檢索)第2頁，共60頁。3.1 棧stack窗口函數(shù)調(diào)用撤消undo第3頁，共60頁。一、 棧的定義棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表 不含元素的空表稱為空棧 若有棧S=(a1，a2，.，an), 則a1為棧底元素、an為棧頂元素操作原則：LI FOana1a2.棧底棧頂表尾稱為棧頂（top）表頭稱為棧底（bottom）第4頁，共60頁?；疖囌救胝境稣镜?頁

2、，共60頁。棧的抽象數(shù)據(jù)類型ADT Stack數(shù)據(jù)對象:D =a ia i ElemSet, i= 1,2,n, n0 數(shù)據(jù)關(guān)系: R = a i-1 , a i D, i = 2,n 約定a n端為棧頂, a 1端為棧底. 基本操作: DestroyStack(&S)；操作結(jié)果:棧S被銷毀ClearStack(&S)；操作結(jié)果:棧S清為空棧.InitStack(&S)；操作結(jié)果:構(gòu)造一個(gè)空棧S.第6頁，共60頁。StackLength(S)；操作結(jié)果:返回S的元素個(gè)數(shù)GetTop(S, &e)；初始條件:棧S已存在且非空.操作結(jié)果:用e返回S的棧頂元素.StackEmpty(S)；操作結(jié)果:

3、若棧S為空棧,則返回TRUE, 否則FALSE第7頁，共60頁。Push(&S, e)；操作結(jié)果:插入元素e為新的棧頂元素. Pop(&S, &e)；初始條件:棧S已存在且非空.操作結(jié)果:刪除S的棧頂元素,并用e返回其值 StackTraverse(S, visit( )；初始條件:棧S已存在且非空.操作結(jié)果:從棧底到棧頂依次對S的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit(). 一旦visit()失敗, 則操作失效.ADT Stack第8頁，共60頁。DestroyStack(&S)；ClearStack(&S)；InitStack(&S)；StackLength(S)；GetTop(S, &e)；St

4、ackEmpty(S)；Push(&S, e)； Pop(&S, &e)； StackTraverse(S, visit( )；第9頁，共60頁。二、棧的表示和實(shí)現(xiàn)1順序棧 利用一組地址連續(xù)的空間存放棧底到棧頂?shù)脑?用指針top指出棧頂元素的位置2順序棧定義typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;第10頁，共60頁。3 順序棧的實(shí)現(xiàn)/ 棧的順序存儲表示 #define STACK_INIT_SIZE 100 /存儲空間初始分配#define STACKINCREMENT 10 /存儲空間分配增

5、量/ 基本操作的函數(shù)原型說明 Status InitStack(SqStack &S); /構(gòu)造一個(gè)空棧SStatus DestroyStack(SqStack &S); /銷毀棧S,S不在存在Status ClearStack(SqStack &S); /把S置為空棧第11頁，共60頁。Status StackEmpty(SqStack S); /若棧S為空棧,則返回TRUE,否則返回FALSEint StackLength(SqStack S); /返回S的元素個(gè)數(shù),即棧的長度Status GetTop(SqStack S, SElemType &e); /若棧不空,則用e返回S的棧頂元素

6、,并返回OK; 否則返回ERRORStatus Push(SqStack &S, SElemType e); /插入元素e為新的棧頂元素Status Pop(SqStack &S, SElemType &e); /若棧不空,則刪除S的棧頂元素,用e返回其值,并返回OK; / 否則返回ERRORStatus StackTraverse(SqStack S, Status(*visit)(); /從棧底到棧頂依次對棧中每個(gè)元素調(diào)用函數(shù)visit(). /一旦visit()失敗,則操作失敗.第12頁，共60頁。/ 基本操作的算法描述(部分)Status InitStack(SqStack &S) /

7、構(gòu)造一個(gè)空棧S S.base=(SElemType*) malloc(STACK_INIT_SIZE *sizeof(SElemType); if (!S.base) exit(OVERFLOW); /存儲分配失敗 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;/InitStack100basetop第13頁，共60頁。Status GetTop(SqStack S, SElemType &e)/若棧不空,則用e返回S的棧頂元素,并返回OK; /否則返回ERRORif (S.top =S.base) return ERROR;

8、e = *(S.top-1);return OK;/GetTopbasetope第14頁，共60頁。Status Push (SqStack &S,SElemType e) /插入元素e為新的棧頂元素 if(S.top-S.base=S.stacksize) /棧滿(上溢),追加存儲空間 S.base = (SElemType*)realloc(S.base, (S.stacksize+ STACKINCREMENT)*sizeof(SElemType); if(!S.base)exit(OVERFLOW); /存儲分配失敗 S.top = S.base + S.stacksize; S.st

9、acksize +=STACKINCREMENT; *S.top+ = e;return OK;/Pushbasetopeetop第15頁，共60頁。Status Pop(SqStack &S,SElemType &e) /若棧不空,則刪除S的棧頂元素,用e返回其值,并返回OK;否則返回ERROR;if(S.top=S.base) return ERROR; /下溢e = * -S.top;return OK;/Popbasetopeetop第16頁，共60頁。4棧式鏈 *top為首元結(jié)點(diǎn)，做棧頂 鏈?zhǔn)綏Ｊ窃诒眍^進(jìn)行插入刪除操作的鏈表a5a4a3a2a1top頭結(jié)點(diǎn)?第17頁，共60頁。bas

10、e1 top1 top2 base22多個(gè)棧共享空間三、 多個(gè)棧共享空間1兩個(gè)棧共享空間第18頁，共60頁。32棧的應(yīng)用一、數(shù)制轉(zhuǎn)換二、 括號匹配三、 行編輯四、迷宮求解五、 表達(dá)式求值第19頁，共60頁。一、數(shù)制轉(zhuǎn)換對于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)打印輸出與其等值的八進(jìn)制數(shù)41073513164080110余數(shù)產(chǎn)生順序八進(jìn)制輸出順序第20頁，共60頁。void conversion ( ) InitStack(S); /建空棧 scanf(&N); while(N) Push(S, N%8); N = N/8; while(!StatckEmpty(S) Pop(S,e); printf(%

11、d,e)； /conversion第21頁，共60頁。二、 括號匹配輸入一個(gè)符號串，判斷其中圓括號和方括號是否匹配( a b h j ( f h ( j ) k g h ) )算法思想：(1)凡出現(xiàn)左括號，則進(jìn)棧(2)凡出現(xiàn)右括號，首先檢查棧是否空 如果棧空，表明右括號多了 否則與棧頂元素比較，若相匹配，左括號出棧 否則不匹配(3)表達(dá)式檢查結(jié)束時(shí)，若棧空，則匹配正確第22頁，共60頁。Status match( )InitStack(S); scanf(ch); while (ch!= n) if (ch= ( | ch= ) Push(S,ch); else if (ch= ) if(St

12、ackEmpty(S) return ERROR; Pop(S, t); if (t!= ( ) return ERROR; else if (ch= ) if(StackEmpty(S) return ERROR; Pop(S, t); if (t!= ) return ERROR; scanf(ch); if(StackEmpty(S) return OK; else return ERROR;/match第23頁，共60頁。第24頁，共60頁。三、迷宮求解墻通道入口出口第25頁，共60頁。墻通道入口出口第26頁，共60頁。算法思想: 若當(dāng)前位置可通,則加入路徑 若當(dāng)前位置不可通,則后退,

13、換一個(gè)方向搜索 若四周都不可通,則從路徑中刪除路徑中最先被刪除的位置是最近搜索過的利用棧存放路徑第27頁，共60頁。設(shè)定當(dāng)前位置的初值為入口位置;do 若當(dāng)前位置可通, 將當(dāng)前位置入棧; 切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置; while(棧不空) 若當(dāng)前位置不可通, 出棧 找到下一個(gè)可能通的位置 第28頁，共60頁。設(shè)定當(dāng)前位置的初值為入口位置;do 若當(dāng)前位置可通, 則 將當(dāng)前位置入棧; /納入路徑 若該位置是出口位置,則結(jié)束; /求得路徑存放在棧中 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置; while(棧不空)否則 若棧不空 出棧e 若e的四周均不可通(或探索過)則繼續(xù)出棧 若e尚有其

14、他方向未經(jīng)探索 沿順時(shí)針方向找到新的當(dāng)前位置第29頁，共60頁。typedef struct int ord; /通道塊在路徑上的序號 PosType seat; /通道塊在迷宮中的坐標(biāo)位置 int di; /從此通道塊走向下一通道塊的方向 SElemType; /棧的元素類型FootPrint(curpos); /記錄位置curpos已經(jīng)搜索過Pass(curpos) /返回位置curpos是否可通(搜索過)NextPos(curpos,i); /返回從位置curpos按方向i到達(dá)的新位置MarkPrint(curpos); /記錄位置curpos4個(gè)方向都搜索過不可通typedef str

15、uct int x,y; PosType; /坐標(biāo)第30頁，共60頁。Status MazePath (MazeType maze, PosType start, PosType end) /若迷宮maze中存在從入口start到出口end的通道,則求得一條存放在棧中 /(從棧底到棧頂),并返回TRUE;否則返回FALSE InitStack(S); curpos = start; /設(shè)定當(dāng)前位置為入口位置 curstep = 1; /探索第一步 do if(Pass(curpos) /當(dāng)前位置可以通過,即是未曾走到過的通道塊 FootPrint(curpos); /留下足跡 e = (cur

16、step,curpos,1); Push(S,e); /加入路徑 if(curpos=end) return(TRUE); /到達(dá)終點(diǎn)(出口) curpos = NextPos(curpos,1); /下一位置是當(dāng)前位置的東鄰 curstep +; /探索下一步第31頁，共60頁。else /if(!Pass(curpos) /當(dāng)前位置不能通過 if(!StackEmpty(S) Pop(S,e); while (e.di=4&!StackEmpty(S) MarkPrint(e.seat); Pop(S,e);/留下不能通過的標(biāo)記,并退回一步 if(e.di4) e.di+; Push (S

17、,e); /換下一個(gè)方向探索 curpos = NextPos(e.seat, e.di); curstep=e.ord+1; /設(shè)定當(dāng)前位置是該新方向上的相鄰塊 /if /if /if(else)while(!StackEmpty(S); return(FALSE); /MazePath第32頁，共60頁。四、表達(dá)式求值a+b*(c+d)+(c-d)/f棧內(nèi)第33頁，共60頁。(1) 初始化，置OPND為空棧， 將#壓入OPTR棧底(2) 依次讀入表達(dá)式中的每個(gè)成員： (a)若是操作數(shù)，壓入OPND棧 (b)若是界限符或運(yùn)算符， 則與OPTR棧內(nèi)運(yùn)算符比較優(yōu)先級， 若棧內(nèi)高， 則從OPTR彈

18、出運(yùn)算符， 并OPND從彈出相應(yīng)個(gè)數(shù)的操作數(shù)進(jìn)行運(yùn)算， 將運(yùn)算結(jié)果壓入OPND棧 若棧內(nèi)棧外相同，則退棧 否則，將讀入的運(yùn)算符壓入OPTR棧(3) 重復(fù)(2)，直到讀入#且棧頂為#為止操作數(shù)運(yùn)算符第34頁，共60頁。OperandType EvaluateExpression( ) /算術(shù)表達(dá)式求值的算符優(yōu)先算法, OP為運(yùn)算符集合 /設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar( ); while(c!=#GetTop(OPTR)!=#) if (!In(c,OP) Pus

19、h(OPND,c);c = getchar( ); else /while return GetTop(OPND);/EvaluataeExpression第35頁，共60頁。switch(Precede(GetTop(OPTR),c) case: Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch第36頁，共60頁。后綴表達(dá)式（逆波蘭表達(dá)式）一種不需要括號的后綴表達(dá)式如： ab+d* abd+*如何利用堆棧計(jì)算后綴表達(dá)式的值？中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式第37頁，共6

20、0頁。3.3 棧與遞歸的實(shí)現(xiàn)保存B的計(jì)算結(jié)果 （return.）釋放B的數(shù)據(jù)區(qū)按返回地址返回A繼續(xù)執(zhí)行B(int x)int a, b; . return (.)A( )int m,n;.B(m);.當(dāng)函數(shù)A調(diào)用B，在執(zhí)行B之前保存實(shí)參信息、返回地址為B的局部變量分配存儲區(qū)將控制轉(zhuǎn)移到B入口從B返回A之前：第38頁，共60頁。int first(int s, int t);int second(int d);int main( ) int m, n; . first(m, n);1: .int first(int s, int t) int i; . second(i); 2: . int s

21、econd(int d)int x,y; .返回地址s,t(m,n)im,n返回地址d(i)x,y調(diào)用second時(shí)棧內(nèi)的數(shù)據(jù)第39頁，共60頁。調(diào)用函數(shù)前： 返回地址入棧 實(shí)參入棧 (形參)調(diào)用函數(shù)時(shí)先： 局部變量入棧返回調(diào)用函數(shù)前： 局部變量出棧 形參出棧 返回地址出棧第40頁，共60頁。float fac(int n)float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;float fac(int n)float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;float fac(i

22、nt n)float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;3n2n1n6f2f1fn3fn3fn2n3fn2fn3fn2fn1n3fn2fn1f第41頁，共60頁。 數(shù)制問題void f1(int num) if(num=8) f1(num/8); printf(%d,num%8);int main() int x=4107; f1(x); return 0;x(4107)返回地址num(4107)返回地址num(513)返回地址num(64)返回地址num(8)返回地址num(1)第42頁，共60頁。34隊(duì)列Queue1隊(duì)列的定義

23、 隊(duì)列是一種先進(jìn)先出的線性表（FIFO） 限定：只能在表的一端插入，而在另一端刪除 允許插入的一端稱為隊(duì)尾(rear) 允許刪除的一端稱為隊(duì)頭(front) 若線性表q=（ a1，a2，.，an ）是一個(gè)隊(duì)列，則a1是隊(duì)頭，an是隊(duì)尾一、 隊(duì)列a1 a2 a3 . an第43頁，共60頁。2隊(duì)列的ADTADT Queue 數(shù)據(jù)對象:D = ai | ai ElemSet, i = 1,2,n; n0 數(shù)據(jù)關(guān)系:R1 = ai-1, ai D, i = 1,2,n 基本操作: InitQueue(&Q) 操作結(jié)果:構(gòu)造一個(gè)空隊(duì)列 DestroyQueue(&Q) 操作結(jié)果:隊(duì)列Q被銷毀,不再存在

24、. ClearQueue(&Q) 操作結(jié)果:將Q清為空隊(duì)列. QueueEmpty(Q) 操作結(jié)果:若Q為空隊(duì)列,則返回TRUE,否則返回FALSE.第44頁，共60頁。 QueueLength(Q) 操作結(jié)果:返回Q的元素個(gè)數(shù),即隊(duì)列的長度. GetHead(Q,&e) 初始條件:Q為非空隊(duì)列. 操作結(jié)果:用e返回Q的隊(duì)頭元素. EnQueue(&Q,e) 操作結(jié)果:插入元素e為Q的新的隊(duì)尾元素. DeQueue(&Q,&e) 初始條件:Q為非空隊(duì)列. 操作結(jié)果:刪除Q的隊(duì)頭元素,并用e返回其值. QueueTraverse(Q,visit() 初始條件:Q已存在且非空. 操作結(jié)果:從對頭到

25、隊(duì)尾,依次對Q的每個(gè)數(shù)據(jù)元素 調(diào)用函數(shù)visit().一旦visit()失敗,則操作失敗,/ADT Queue第45頁，共60頁。二、 順序隊(duì)列 用一組地址連續(xù)的存儲單元依次存放隊(duì)列中的元素方式一：用一維數(shù)組表示隊(duì)列typedef structQElemType *q; int rear; SqQueue1;Q.q0表示隊(duì)頭，Q.qQ.rear-1表示隊(duì)尾隊(duì)空：Q.rear=0隊(duì)滿：Q.rear=100（空間大?。┏鲫?duì)：e=Q.q0; Q.q1至Q.qQ.rear-1往前挪入隊(duì)：Q.qQ.rear=e; Q.rear+;第46頁，共60頁。方式二： #define Queue_SIZE 100

26、 typedef struct QElemType *Q; int front; int rear; SqQueue2;frontrear第47頁，共60頁。三、 循環(huán)隊(duì)列a1a2a3a4a5Q.frontQ.rear第48頁，共60頁。Q.frontQ.reara1a2a3a4a5Q.frontQ.reara6a7a8隊(duì)空隊(duì)滿第49頁，共60頁。/循環(huán)隊(duì)列隊(duì)列的順序存儲結(jié)構(gòu)#define MAXQSIZE 100 /最大隊(duì)列長度typedef struct QElemType *base; /初始化的動態(tài)分配存儲空間 int front; /頭指針,若隊(duì)列不空,指向隊(duì)列頭元素 int rea

27、r; /尾指針,若隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置SqQueue;解決方法：（1）專設(shè)一個(gè)表示隊(duì)滿隊(duì)空的標(biāo)記full 一開始，full=0 當(dāng)入隊(duì)時(shí)出現(xiàn)Q.rear=Q.front，隊(duì)滿full=1 當(dāng)出隊(duì)時(shí)出現(xiàn)Q.rear=Q.front，隊(duì)空full=0（2）專門空出一個(gè)位置不用第50頁，共60頁。Q.rearQ.front隊(duì)空a1a2a3a4a5Q.frontQ.reara6a7隊(duì)滿第51頁，共60頁。/循環(huán)隊(duì)列的基本操作的算法描述Status InitQueue(SqQueue &Q)/ 構(gòu)造一個(gè)空隊(duì)列Q Q.base = (QElemType *)malloc(MAXQSIZE

28、* sizeof(QElemType); if (!Q.base) exit(OVERFLOW); /存儲分配失敗 Q.front = Q.rear = 0; return OK;int QueueLength(SqQueue Q)/返回Q的元素個(gè)數(shù),即隊(duì)列的長度 return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;第52頁，共60頁。Status EnQueue(SqQueue &Q,QElemType e)/ 插入元素e為Q的新的隊(duì)尾元素 if(Q.rear+1)%MAXQSIZE = Q.front) return ERROR; /隊(duì)列滿 Q.baseQ.

29、rear = e; Q.rear = (Q.rear+1)% MAXQSIZE; return OK;第53頁，共60頁。Status DeQueue(SqQueue &Q, QElemType &e)/ 刪除隊(duì)頭元素，送給變量e if( Q.front=Q.rear ) return ERROR; /隊(duì)列空 e=Q.baseQ.front; Q.front = (Q.front+1)% MAXQSIZE; return OK;第54頁，共60頁。/隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedef struct QNodeQElemType data; Struct QNode *next; QNode, *

30、QueuePtr;四、鏈?zhǔn)疥?duì)列 Q.frontQ.reartypedef struct QueuePtr front; /隊(duì)頭指針 QueuePtr rear; /隊(duì)尾指針LinkQueue第55頁，共60頁。Status InitQueue(LinkQueue &Q)/ 構(gòu)造一個(gè)空隊(duì)列QStatus DestroyQueue(LinkQueue &Q)/ 銷毀空隊(duì)列Q,隊(duì)列Q不再存在Status ClearQueue(LinkQueue &Q)/ 將Q清為空隊(duì)列Status QueueEmpty(LinkQueue Q)/ 若隊(duì)列Q為空隊(duì)列,則返回TRUE,否則返回FALSE .int QueueLength(LinkQueue Q)/ 返回Q的元素個(gè)數(shù),即為隊(duì)列的長度Status GetHead(LinkQueue Q,QElemType &e)/ 若隊(duì)列不為空,則用e返回Q的隊(duì)頭元