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

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

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

3、列為ABCDEF,能否得到 DCEFAB和ACEDBF出棧序列. ? 以0和1分別表示進棧和出棧,棧的 初態(tài)和終態(tài)均為?？?進出棧操作 序列0101和0110是否合法.6 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 棧的類型定義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 棧的表示和實現(xiàn) 類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。/- 棧的順序存儲表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;9實現(xiàn)：一維數(shù)組sqstack s 表示棧s.top123450進棧A棧滿BCDEF?？諚l件，s.top=s.base, 此時出棧，則下溢（under

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

6、f (!S.base) exit (OVERFLOW); /存儲分配失敗 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) /棧滿，追加存儲空間 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (SElemType); if (!S.base) exit (OVERFLO

7、W); /存儲分配失敗 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頂在一個連續(xù)存儲單元空間中同時使用兩個棧14鏈棧 棧的鏈式存儲結(jié)構(gòu)。棧頂指針就是鏈表的

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

9、10=(2504)8，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸出順序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 括號匹配的檢驗 則 檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。假設在表達式中（）或（ ）等為正確的格式，（ ）或（

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

11、合理的作法是： 設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設“#”為退格符，“”為退行符。24假設從終端接受了這樣兩行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);則實際有效的是下列兩行： 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(); / 從終端接收下一個字符 ClearStack(S); / 重置S為空棧if (ch != EOF) ch = getchar();while (ch != EOF) /EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；263.2.4 迷宮求解通常用的是“窮舉求解”的方法27求迷宮路徑算法的基本思想是：若當前位置“可通”，則納入路徑， 繼續(xù)前進;若當前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當前位置從路徑中刪除出去。28 限于二元運算符的表達式定義: Exp = S1 OP S2 操作數(shù) : 變量、常量、表達式 運算符 : 算術(shù)運算符、關(guān)系運

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

14、2 運算,結(jié)果進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() / 設OPTR和OPND分別為運算符棧和運算數(shù)棧，OP為運算符集合。 InitStack (OPTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if

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

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

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

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

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

21、ont)允許刪除的一端41 ADT Queue 數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊列頭， an 端為隊列尾基本操作：隊列的類型定義 ADT Queue42隊列的基本操作： 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é)點類型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /鏈隊列類型 QueuePtr front ; /隊頭指針 QueuePtr rear ; /隊尾指針 LinkQueue;3.4.2 鏈隊列隊列的鏈式表示和實現(xiàn)44a1anQ.frontQ.rearQ.frontQ.rear空隊列45Q.frontQ.rearx入隊xQ.frontQ.reary入隊xyQ.frontQ.rearx出隊xyQ.frontQ.rear空隊frontreary出隊Q.rear - next=pQ.re

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

24、ueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;48 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 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)隊列隊列的順序表示和實現(xiàn) #define MAXQSIZE 100 /最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空， /指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向 / 隊列尾元素 的下一個位置 SqQueue;?

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

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

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