數(shù)據(jù)結(jié)構(gòu)課件：第三章 棧和隊(duì)列

1、第三章 棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用舉例3.4 隊(duì)列3.3 棧與遞歸的實(shí)現(xiàn)1提要：1.掌握棧和隊(duì)列的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn) 題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，即兩種存 儲(chǔ)結(jié)構(gòu)表示時(shí)的基本操作實(shí)現(xiàn)算法，特別應(yīng) 注意棧滿和?？盏臈l件以及它們的描述方法。3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn) 算法，特別注意隊(duì)滿和隊(duì)空的描述方法。4.熟練掌握遞歸算法的實(shí)現(xiàn)(棧的應(yīng)用)重難點(diǎn)內(nèi)容： 順序棧的相關(guān)操作、循環(huán)隊(duì)列的判空判滿(假溢出)和遞歸算法2 棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。其基本操作是線性表操作的子集. 線性表 棧 隊(duì)列Insert(L, i, x)

2、 Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 入棧 入隊(duì) Delete(L, i) Delete(S, n) Delete(Q, 1) 1in 出棧 出隊(duì)棧和隊(duì)列是兩種常用和應(yīng)用最廣泛的數(shù)據(jù)結(jié)構(gòu)33.1 棧（stack）3.1.1 棧的類型定義3.1.2 棧的表示和實(shí)現(xiàn)4棧的定義和特點(diǎn)定義：限定僅在表尾進(jìn)行插入(進(jìn)棧)或刪除( 出棧)操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧。ana1a2.棧底棧頂.出棧進(jìn)棧棧s=(a1,a2,an)特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）3.1.1 棧的類型定義5基于特點(diǎn)給出以下問(wèn)題: ? 若進(jìn)棧序

3、列為ABCDEF,能否得到 DCEFAB和ACEDBF出棧序列. ? 以0和1分別表示進(jìn)棧和出棧,棧的 初態(tài)和終態(tài)均為棧空,進(jìn)出棧操作 序列0101和0110是否合法.6 ADT Stack 數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作： ADT Stack 棧的類型定義7InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S, &e)Push(&S, e

4、)Pop(&S, &e)StackTravers(S, visit()8 順序棧3.1.2 棧的表示和實(shí)現(xiàn) 類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。/- 棧的順序存儲(chǔ)表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;9實(shí)現(xiàn)：一維數(shù)組sqstack s 表示棧s.top123450進(jìn)棧A棧滿BCDEF?？諚l件，s.top=s.base, 此時(shí)出棧，則下溢（under

5、flow)棧滿條件 S.top - S.base = S.stacksize 此時(shí)入棧，則上溢（overflow)s.tops.tops.tops.tops.top123450空棧s.tops.bases.bases.top出棧s.tops.top棧空s.base棧底指針s.base,始終指向棧底位置；棧頂指針s.top,其初值指向棧底，始終在棧頂元素的下一個(gè)位置123450ABs.top10 Status InitStack (SqStack &S)/ 構(gòu)造一個(gè)空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType); i

6、f (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;11 Status Push (SqStack &S, SElemType e) if (S.top - S.base = S.stacksize) /棧滿，追加存儲(chǔ)空間 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLO

7、W); /存儲(chǔ)分配失敗 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top+ = e; return OK; 12Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用e返回其值，并返回OK； / 否則返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;130M-1棧1底棧1頂棧2底棧2頂在一個(gè)連續(xù)存儲(chǔ)單元空間中同時(shí)使用兩個(gè)棧14鏈棧 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。棧頂指針就是鏈表的

8、頭指針。棧頂指針a1an注意: 鏈棧中指針的方向an-1注意: 鏈棧中指針的方向注意：鏈棧中的指針?lè)较?5 入棧操作 出棧操作 .棧底toptopxptop .棧底topqp-next=top ; top=p q=top ; top=top-next 163.2 棧的應(yīng)用3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號(hào)匹配的檢驗(yàn)3.2.3 行編輯程序問(wèn)題3.2.4 迷宮求解3.2.5 表達(dá)式求值173.2.1 數(shù)制轉(zhuǎn)換十進(jìn)制N和其他d進(jìn)制數(shù)的轉(zhuǎn)換原理: N=( N div d )*d + N mod d 其中：div為整除運(yùn)算，mod為求余運(yùn)算18toptop4top40top405 例如： (1348)

9、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計(jì)算順序輸出順序top405219 void conversion( ) initstack(S); scanf (“%d”,N); while(N) push(S，N%8); N=N/8; while(! Stackempty(s) pop(S,e); printf(“%d”,e); /conversion203.3.2 括號(hào)匹配的檢驗(yàn) 則 檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。假設(shè)在表達(dá)式中（）或（ ）等為正確的格式，（ ）或（

10、）或 （）)均為不正確的格式。21分析可能出現(xiàn)的不匹配的情況:到來(lái)的右括弧并非是所“期待”的；例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8直到結(jié)束，也沒(méi)有到來(lái)所“期待”的括弧。22算法的設(shè)計(jì)思想：1）對(duì)表達(dá)式從左至右掃描凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？眨瑒t表明該“右括弧”多余，(失敗) 否則和棧頂元素比較， 若相匹配，則“左括弧出棧” ， 否則表明不匹配，(失敗) 。3）表達(dá)式檢驗(yàn)結(jié)束時(shí)， 若?？眨瑒t表明表達(dá)式中匹配正確， 否則表明“左括弧”有余，(失敗) 。233.2.3 行編輯程序問(wèn)題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器” ? 不恰當(dāng)!

11、合理的作法是： 設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符，“”為退行符。24假設(shè)從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實(shí)際有效的是下列兩行： while (*s) putchar(*s+);25 while (ch != EOF & ch != n) switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S為空棧 default : Push(S, ch); break; ch = get

12、char(); / 從終端接收下一個(gè)字符 ClearStack(S); / 重置S為空棧if (ch != EOF) ch = getchar();while (ch != EOF) /EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；263.2.4 迷宮求解通常用的是“窮舉求解”的方法27求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑， 繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。28 限于二元運(yùn)算符的表達(dá)式定義: Exp = S1 OP S2 操作數(shù) : 變量、常量、表達(dá)式 運(yùn)算符 : 算術(shù)運(yùn)算符、關(guān)系運(yùn)

13、算符、 邏輯運(yùn)算符 界限符：括號(hào)、結(jié)束符3.2.5 表達(dá)式求值29一種表達(dá)式求值的算法思想(算符優(yōu)先法): 將運(yùn)算符和界限符統(tǒng)稱為算符,用OPTR棧存儲(chǔ)算符,用OPND棧存儲(chǔ)運(yùn)算結(jié)果和操作數(shù).設(shè)OPTR棧頂元素為1,算法實(shí)現(xiàn)步驟為: 1.OPND棧置空,OPTR棧底元素置為#”.表達(dá)式尾 置為#”. 2.依此讀入表達(dá)式字符,若是操作數(shù)一律進(jìn)OPND棧, 若是算符則設(shè)為2,參照P53表3.1進(jìn)行以下比較: 若2 1,則2 進(jìn)OPTR棧,繼續(xù)2 若2 1則OPTR棧頂出棧(括弧配對(duì)),繼續(xù)2若2 1則OPTR棧頂出棧作為運(yùn)算符(OP),同時(shí)OPND棧連續(xù)出二個(gè)元素作為S2和S1進(jìn)行 S1 OP S

14、2 運(yùn)算,結(jié)果進(jìn)OPND棧,繼續(xù)2.結(jié)束條件是 2 =130例：3 * ( 7 2 )OPND棧OPTR棧CCC3*(C7CC2C275C*531531例：3 * ( 7 2 ) OPTR棧 OPND棧 輸入 操作1 # 3 * ( 7 2 ) # PUSH( OPND, 3 )2 # 3 * ( 7 2 ) # PUSH( OPTR, * )3 # * 3 ( 7 2 ) # PUSH( OPTR, ( )4 # * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPND,

15、 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND )32OperandType EvaluateExpression() / 設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if

16、(!In(c, OP) Push(OPND, c); c = getchar(); / 不是運(yùn)算符則進(jìn)棧 else / while return GetTop(OPND); / EvaluateExpression 33switch ( precede(GetTop(OPTR), c) case : / 退棧并將運(yùn)算結(jié)果入棧 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch34 3.3 棧與遞歸的實(shí)現(xiàn)遞歸的概念: 一個(gè)直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句調(diào)用

17、自己 的函數(shù),稱為遞歸函數(shù).具有遞歸特征的問(wèn)題可分為以下幾類: 1. 數(shù)學(xué)函數(shù)本身是遞歸定義的,如階乘函數(shù)、 Fibonacci 數(shù)列和Ackerman 函數(shù)等. 2. 有些數(shù)據(jù)結(jié)構(gòu)本身具有遞歸特征,如二叉樹(shù),廣義表 等.對(duì)它們的操作可遞歸的描述(后面可見(jiàn)). 3. 問(wèn)題本身遞歸結(jié)構(gòu)不明顯,但用遞歸求解比迭代更 簡(jiǎn)單.如八皇后,Hanoi塔問(wèn)題,關(guān)鍵是如何抽象出 遞歸特征.35棧在遞歸函數(shù)實(shí)現(xiàn)中的應(yīng)用: 如下圖,函數(shù)調(diào)用的過(guò)程是先調(diào)用后返回,而棧的特 征是先進(jìn)后出.因此,函數(shù)調(diào)用過(guò)程可用棧來(lái)實(shí)現(xiàn).MAINSUB1SUB2SUB3斷點(diǎn)1斷點(diǎn)2斷點(diǎn)3調(diào)用調(diào)用調(diào)用返回返回返回結(jié)束36函數(shù)調(diào)用和返回過(guò)

18、程中棧存儲(chǔ)內(nèi)容:調(diào)用函數(shù)和被調(diào)用函數(shù)之間的連接和形參與實(shí)參 之間的內(nèi)容傳遞是通過(guò)棧來(lái)完成. 當(dāng)一個(gè)函數(shù)運(yùn)行期間調(diào)用另一函數(shù)時(shí),在運(yùn)行 被調(diào)用函數(shù)之前完成以下三件事: (1) 將所有的實(shí)參和返回地址(斷點(diǎn))入棧,供 實(shí)參到形參信息傳遞和被調(diào)用函數(shù)運(yùn)行 完后返回調(diào)用函數(shù)繼續(xù)運(yùn)行. (2) 為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū) (3) 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口地址當(dāng)從被調(diào)用函數(shù)返回之前也完成以下二件事: (1) 保存被調(diào)用函數(shù)的計(jì)算結(jié)果,釋放數(shù)據(jù)區(qū). (2) 返回地址(斷點(diǎn))出棧,將控制轉(zhuǎn)移到調(diào)用函數(shù)注意 : 當(dāng)前運(yùn)行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂.37例子 漢諾塔算法的實(shí)現(xiàn)及遞歸工作棧的變化 從漢諾塔問(wèn)題

19、中抽象出遞歸規(guī)律(問(wèn)題需求和 規(guī)則見(jiàn)P55)12nnn-11XYZXYZ(問(wèn)題的規(guī)模為 n)(問(wèn)題的規(guī)模為 n-1,僅供移動(dòng)的輔助塔發(fā)生變化)38求解n階漢諾塔問(wèn)題的C函數(shù) void hanoi(int n , char x, char y, char z) 將塔 X 上 1 至 n 個(gè)圓盤(pán)按規(guī)則搬到Z塔上 , Y為輔助塔1 2 if ( n =1 )3 move ( x , 1 , z) ; 將編號(hào)為 1 的圓盤(pán)從 x 移到 z4 else 5 hanoi ( n-1 , x , z , y) ;將 X 上 1 至 n-1 個(gè)圓盤(pán) 按規(guī)則搬到 Y 塔上 , Z為輔助塔6 move ( x ,

20、 n , z); 將編號(hào)為 n的圓盤(pán)從 x 移到 z7 hanoi ( n-1 , y , x , z) ;將 y 上 1 至 n-1 個(gè)圓盤(pán) 按規(guī)則搬到 z 塔上 , x 為輔助塔8 9 設(shè)n=3,則調(diào)用該遞歸函數(shù)為 hanoi(3, a , b, c) . 棧的變化見(jiàn)P57393.4 隊(duì)列3.4.1 隊(duì)列的類型定義3.4.2 鏈隊(duì)列3.4.3 循環(huán)隊(duì)列40隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。a1 a2 a3.an 入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,an)隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)3.4.1 隊(duì)列的類型定義隊(duì)尾(rear)允許插入的一端隊(duì)頭(fr

21、ont)允許刪除的一端41 ADT Queue 數(shù)據(jù)對(duì)象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊(duì)列頭， an 端為隊(duì)列尾基本操作：隊(duì)列的類型定義 ADT Queue42隊(duì)列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()43typedef struct

22、QNode/ 結(jié)點(diǎn)類型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /鏈隊(duì)列類型 QueuePtr front ; /隊(duì)頭指針 QueuePtr rear ; /隊(duì)尾指針 LinkQueue;3.4.2 鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)44a1anQ.frontQ.rearQ.frontQ.rear空隊(duì)列45Q.frontQ.rearx入隊(duì)xQ.frontQ.reary入隊(duì)xyQ.frontQ.rearx出隊(duì)xyQ.frontQ.rear空隊(duì)frontreary出隊(duì)Q.rear - next=pQ.re

23、ar=pp= Q.front - nextQ.front - next = p - next P 指向待入隊(duì)或出隊(duì)的結(jié)點(diǎn)注意:若出隊(duì)的為最后一個(gè)結(jié)點(diǎn)需做以下操作,避免rear指針丟失:If (Q.rear=p) Q.rear=Q.frant46 Status InitQueue (LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲(chǔ)分配失敗 Q.front-next = NULL; return OK;47 Status EnQ

24、ueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊(duì)尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;48 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear

25、) 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;493.4.3 循環(huán)隊(duì)列隊(duì)列的順序表示和實(shí)現(xiàn) #define MAXQSIZE 100 /最大隊(duì)列長(zhǎng)度 typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空， /指向隊(duì)列頭元素 int rear; / 尾指針，若隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個(gè)位置 SqQueue;?

26、為什么沒(méi)有說(shuō)明增量50用一維數(shù)組SqQueue Q順序表示隊(duì)列123450空隊(duì)列Q.rear=0 Q.front=0J1J2J3Q.rearQ.rear123450J4,J5,J6入隊(duì)J4J5J6Q.frontrearQ.rear123450Q.frontJ1,J1,J3入隊(duì)Q.rear123450J1,J2,J3出隊(duì)J1J2J3Q.frontQ.frontQ.frontQ.front存在問(wèn)題：當(dāng)front=0,rear=Maxqsize時(shí)再有元素入隊(duì)發(fā)生溢出為真溢出當(dāng)front0,rear=Maxqsize時(shí)再有元素入隊(duì)發(fā)生溢出為假溢出Q.rear應(yīng)采用定長(zhǎng)分配(為什么)51假溢出的解決方案

27、(循環(huán)隊(duì)列)隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)浪費(fèi)時(shí)間循環(huán)隊(duì)列(設(shè)M=MaxQSIZE) 基本思想：把隊(duì)列設(shè)想成環(huán)形，讓Q.base0接在Q.baseM-1之后,若Q.rear+1=M,則令Q.rear=0;實(shí)現(xiàn)：利用“?！边\(yùn)算入隊(duì)： Q.baserear=x; Q.rear=(Q.rear+1)%M; 出隊(duì)： x=Q.basefront; Q.front=(Q.front+1)%M; 52012345Q.rearQ.frontJ5J6J7012345Q.rearQ.frontJ4J9J8J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：Q.front=Q.rear隊(duì)滿：Q.front=Q.rea

28、r解決方案：1.另外設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間：(以下算法采用) 隊(duì)空: Q.front=Q.rear 隊(duì)滿: (Q.rear+1)%M=front3.使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)J5J6012345Q.rearQ.front初始狀態(tài)J4隊(duì)滿、隊(duì)空判定條件53 Status InitQueue (SqQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存儲(chǔ)分配失敗 Q.front = Q.rear = 0