第三章棧和隊列ppt課件

1、13.1 棧棧3.2 棧的運用舉例棧的運用舉例3.4 隊列隊列2 通常稱，棧和隊列是限定插入和刪除只能通常稱，棧和隊列是限定插入和刪除只能在表的在表的“端點端點進展的線性表。進展的線性表。 線性表線性表 棧棧 隊列隊列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) Delete(L, i) Delete(S, n) Delete(Q, 1

2、) 1in 1in棧和隊列是兩種常用的數(shù)據(jù)類型棧和隊列是兩種常用的數(shù)據(jù)類型3學習提要：學習提要：1.1.掌握棧和隊列這兩種籠統(tǒng)數(shù)據(jù)類型的特點，掌握棧和隊列這兩種籠統(tǒng)數(shù)據(jù)類型的特點， 并能在相應的運用問題中正確選用它們。并能在相應的運用問題中正確選用它們。2.2.熟練掌握棧類型的兩種實現(xiàn)方法，即兩種存熟練掌握棧類型的兩種實現(xiàn)方法，即兩種存 儲構造表示時的根本操作實現(xiàn)算法，特別應儲構造表示時的根本操作實現(xiàn)算法，特別應 留意棧滿和?？盏臈l件以及它們的描畫方法。留意棧滿和棧空的條件以及它們的描畫方法。3.3.熟練掌握循環(huán)隊列和鏈隊列的根本操作實現(xiàn)熟練掌握循環(huán)隊列和鏈隊列的根本操作實現(xiàn) 算法，特別留意隊

3、滿和隊空的描畫方法。算法，特別留意隊滿和隊空的描畫方法。重難點內容：重難點內容： 順序棧的相關操作、循環(huán)隊列的判空判滿順序棧的相關操作、循環(huán)隊列的判空判滿43.1.1 棧的類型定義棧的類型定義3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)5棧的定義和特點棧的定義和特點定義：限定僅在表尾進展插入或刪除定義：限定僅在表尾進展插入或刪除操作的線性表，表尾操作的線性表，表尾棧頂，表頭棧頂，表頭棧底，不含元素的空表稱空棧。棧底，不含元素的空表稱空棧。ana1a2.棧底棧底棧棧頂頂.出棧出棧進棧進棧棧棧s=(a1,a2,an)v特點：先進后出特點：先進后出FILO或后進先出或后進先出LIFO3.1.1 棧的類型

4、定義6 ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關系：數(shù)據(jù)關系： 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)Pop(&S, &e)StackTravers(S, visit()8順序棧順序棧3.1.2 棧

5、的表示和實現(xiàn)棧的表示和實現(xiàn) 類似于線性表的順序映象實現(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ù)組實現(xiàn)：一維數(shù)組sMtop123450進棧進棧A棧滿棧滿BCDEF設數(shù)組維數(shù)為設數(shù)組維數(shù)為M Mtop=base,top=base,?？眨藭r出棧，那?？?，

6、此時出棧，那么下溢么下溢underflow)underflow)top=M,top=M,棧滿，此時入棧，那么上棧滿，此時入棧，那么上溢溢overflow)overflow)toptoptoptoptop123450空棧空棧topbasebasetop出棧出棧toptop?？諚？誦ase棧底指針棧底指針base,base,一直一直指向棧底位置；棧頂指向棧底位置；棧頂指針指針top,top,其初值指向其初值指向棧底，一直在棧頂元棧底，一直在棧頂元素的下一個位置素的下一個位置123450ABtop10 Status InitStack (SqStack &S)/ 構造一個空棧SS.base=(SEl

7、emType*)malloc(STACK_INIT_SIZE *sizeof(SElemType); if (!S.base) exit (OVERFLOW); /存儲分配失敗 S = S.base; S.stacksize = STACK_INIT_SIZE; return OK;11 Status Push (SqStack &S, SElemType e) if (S - S.base = S.stacksize) /棧滿，追加存儲空間棧滿，追加存儲空間 S.base = (SElemType *) realloc ( S.base, (S.stacksize + STACKINCREM

8、ENT) * sizeof (SElemType); if (!S.base) exit (OVERFLOW); /存儲分配失敗存儲分配失敗 S = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S+ = e; return OK; 12Status Pop (SqStack &S, SElemType &e) / 假設棧不空，那么刪除假設棧不空，那么刪除S的棧頂元素，的棧頂元素， / 用用e前往其值，并前往前往其值，并前往OK； / 否那么前往否那么前往ERROR if (S = S.base) return ERROR; e =

9、 *-S; return OK;130M-1棧棧1底底棧棧1頂頂棧棧2底底棧棧2頂頂在一個程序中同時運用兩個棧在一個程序中同時運用兩個棧14鏈棧鏈棧 棧的鏈式存儲構造。棧頂指針就棧的鏈式存儲構造。棧頂指針就是鏈表的頭指針。是鏈表的頭指針。棧頂指針a1an留意留意: 鏈棧中鏈棧中指針的方向指針的方向an-1留意留意: : 鏈棧鏈棧中指針的方向中指針的方向留意：鏈棧中的指針方向留意：鏈棧中的指針方向15v 入棧操作入棧操作v 出棧操作出棧操作 .棧底棧底toptopxptop .棧底棧底topqp-next=top ; top=p q=top ; top=top-next 163.2.1 數(shù)制轉換

10、數(shù)制轉換3.2.2 括號匹配的檢驗括號匹配的檢驗3.2.3 行編輯程序問題行編輯程序問題3.2.4 迷宮求解迷宮求解3.2.5 表達式求值表達式求值173.2.1 數(shù)制轉換數(shù)制轉換十進制十進制N和其他和其他d進制數(shù)的轉換原進制數(shù)的轉換原理理: N=( N div d )*d + N mod d 其中：其中：div為整除運算，為整除運算，mod為為求余運算求余運算18toptop4top40top405 例如：例如： (1348)10=(2504)8，其運算過程如下：，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序輸

11、出順序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 括號匹配的檢驗括號匹配的檢驗 那么那么 檢驗括號能否匹配的方法可用檢驗括號能否匹配的方法可用“等待的急迫程度等待的急迫程度這個概念來描畫。這個概念來描畫。假設在表達式中假設在表達式中或或 等為正確的格式，等為正確的格式， 或或 或或 )均均為不正確的格式。為不正確的格式。21分析能夠出現(xiàn)

12、的不匹配的情況分析能夠出現(xiàn)的不匹配的情況: :到來的右括弧并非是所到來的右括弧并非是所“等待等待的；的；例如：思索以下括號序列：例如：思索以下括號序列： ( ) 1 2 3 4 5 6 7 8直到終了，也沒有到來所直到終了，也沒有到來所“等待等待的括弧。的括弧。22算法的設計思想：算法的設計思想：1凡出現(xiàn)左括弧，那么進棧；凡出現(xiàn)左括弧，那么進棧；2凡出現(xiàn)右括弧，首先檢查棧能否空凡出現(xiàn)右括弧，首先檢查棧能否空 假設?？?，那么闡明該假設?？眨敲搓U明該“右括弧右括弧多余，多余， 否那么和棧頂元素比較，否那么和棧頂元素比較， 假設相匹配，那么假設相匹配，那么“左括弧出棧左括弧出棧 ， 否那么闡明不匹

13、配。否那么闡明不匹配。3表達式檢驗終了時，表達式檢驗終了時， 假設棧空，那么闡明表達式中匹配正確，假設棧空，那么闡明表達式中匹配正確， 否那么闡明否那么闡明“左括弧左括弧有余。有余。233.2.3 行編輯程序問題行編輯程序問題如何實現(xiàn)？如何實現(xiàn)？“每接受一個字符即存入存儲器每接受一個字符即存入存儲器 ? 不恰當不恰當!合理的作法是：合理的作法是： 設立一個輸入緩沖區(qū)，用以接受用設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設戶數(shù)據(jù)區(qū)，并假設“#為退格符，為退格符，“為退行符。為退行符。24假設從終端接受了這樣兩行字符：假設從終端接受

14、了這樣兩行字符： whli#ilr#es#*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 = getchar(); / 從終端接納下一個字符 ClearStack(S); / 重置S為空棧if (ch != EOF)

15、 ch = getchar();while (ch != EOF) /EOF為全文終了符為全文終了符將從棧底到棧頂?shù)淖址麄魉椭琳{用過程的數(shù)據(jù)區(qū)；263.2.4 迷宮求解迷宮求解通常用的是通常用的是“窮舉求解窮舉求解的方法的方法# #$# #$# $# # # # # #27求迷宮途徑算法的根本思想是：求迷宮途徑算法的根本思想是：v假設當前位置假設當前位置“可通可通，那么，那么納入途徑，納入途徑， 繼續(xù)前進繼續(xù)前進;v假設當前位置假設當前位置“不可通不可通，那么后退，換方向繼續(xù)探求那么后退，換方向繼續(xù)探求;v假設周圍假設周圍“均無通路均無通路，那，那么將當前位置從途徑中刪除么將當前位置從途徑中刪

16、除出去。出去。28 限于二元運算符的表達式定義: Exp = S1 OP S2 操作數(shù) : 變量、常量、表達式 運算符 : 算術運算符、關系運算符、 邏輯運算符 界限符：括號、終了符3.2.5 表達式求值表達式求值29例：例：3 * ( 7 2 )OPND棧棧OPTR棧棧CCC3*(C7CC2C275C*531530例：例：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 #

17、 * ( 3 7 2 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, )6 # * ( 3 7 2 ) # PHSH( OPND, 2 ) 7 # * ( 3 7 2 ) # operate( 7,-,2 )8 # * ( 3 5 ) # POP( OPTR )9 # * 3 5 # operate( 3, *, 5 )10 # 15 # return GetTop( OPND )31OperandType EvaluateExpression() / 設OPTR和OPND分別為運算符棧和運算數(shù)棧，OP為運算符集合。 InitStack (O

18、PTR); Push (OPTR, #); initStack (OPND); c = getchar(); while (c!= # | GetTop(OPTR)!= #) if (!In(c, OP) Push(OPND, c); c = getchar(); / 不是運算符那么進棧 else / while return GetTop(OPND); / EvaluateExpression 32switch ( precede(GetTop(OPTR), c) case : / 退棧并將運算結果入棧退棧并將運算結果入棧 Pop(OPTR, theta); Pop(OPND, b); Po

19、p(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch333.4 隊列隊列3.4.1 隊列的類型定義隊列的類型定義3.4.2 鏈隊列鏈隊列3.4.3 循環(huán)隊列循環(huán)隊列34隊列是限定只能在表的一端進展插入，在隊列是限定只能在表的一端進展插入，在表的另一端進展刪除的線性表。表的另一端進展刪除的線性表。a1 a2 a3.an 入隊入隊出隊出隊frontrear隊列隊列Q=(a1,a2,an)v隊列特點：先進先出隊列特點：先進先出(FIFO)(FIFO)3.4.1 隊列的類型定義隊列的類型定義v隊尾隊尾(rear)允許插入的一端允許插入

20、的一端v隊頭隊頭(front)允許刪除的一端允許刪除的一端35 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關系：數(shù)據(jù)關系： R1 | ai-1, ai D, i=2,.,n 商定其中商定其中a1 端為隊列頭，端為隊列頭， an 端為隊列尾端為隊列尾根本操作：根本操作：隊列的類型定義 ADT Queue36隊列的根本操作：隊列的根本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &

21、e)EnQueue(&Q, e)QueueTravers(Q, visit()37typedef struct QNode/ 結點類型結點類型 QElemType data ; struct QNode *next ; QNode, *QueuePtr; typedef struct /鏈隊列類型鏈隊列類型 QueuePtr front ; /隊頭指針隊頭指針 QueuePtr rear ; /隊尾指針隊尾指針 LinkQueue;3.4.2 鏈隊列隊列的鏈式表示和實現(xiàn)鏈隊列隊列的鏈式表示和實現(xiàn)38a1anQ.frontQ.rearQ.frontQ.rear空隊列空隊列39frontrearx

22、入隊入隊xfrontreary入隊入隊xyfrontrearx出隊出隊xyfrontrear空空隊隊front reary出隊出隊Q.rear - next=pQ.rear=pp= Q.front - nextQ.front - next = p - next 40 Status InitQueue (LinkQueue &Q) / 構造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; return OK;41

23、 Status EnQueue (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;42 Status DeQueue (LinkQueue &Q, QElemType &e) / 假設隊列不空，那么刪除Q的隊頭元素， /用 e 前往其值，并前往OK；否那么前往ERROR if (Q.

24、front = Q.rear) 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;433.4.3 循環(huán)隊列隊列的順序表示和實現(xiàn)循環(huán)隊列隊列的順序表示和實現(xiàn) #define MAXQSIZE 100 /最大隊列長度最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間動態(tài)分配存儲空間 int front; / 頭指針，假設隊列不空，頭指針，假設隊列不空， /指向隊

25、列頭元素指向隊列頭元素 int rear; / 尾指針，假設隊列不空，指向尾指針，假設隊列不空，指向 / 隊列尾元素隊列尾元素 的下一個位置的下一個位置 SqQueue;44實現(xiàn)：用一維數(shù)組實現(xiàn)實現(xiàn)：用一維數(shù)組實現(xiàn)sqM123450空隊列空隊列rear=0 front=0J1J2J3rearrear123450J4,J5,J6入隊J4J5J6frontrearrear123450frontJ1,J1,J3入隊rear123450J1,J2,J3出隊J1J2J3frontfrontfrontfrontv存在問題：存在問題：v當當front=0,rear=M時再有元素入隊發(fā)生溢出時再有元素入隊發(fā)生

26、溢出真溢出真溢出v當當front0,rear=M時再有元素入隊發(fā)生溢出時再有元素入隊發(fā)生溢出假溢出假溢出rear45v處理方案處理方案v隊首固定，每次出隊剩余元素向下挪動隊首固定，每次出隊剩余元素向下挪動浪費時間浪費時間v循環(huán)隊列循環(huán)隊列v 根本思想：把隊列想象成環(huán)形，讓根本思想：把隊列想象成環(huán)形，讓sq0接接在在sqM-1 之后，假設之后，假設rear+1=M,那么令那么令rear=0;u實現(xiàn)：利用實現(xiàn)：利用“模模運算運算u入隊：入隊： baserear=x; rear=(rear+1)%M; u出隊：出隊： x=basefront; front=(front+1)%M; u隊滿、隊空斷定條

27、件隊滿、隊空斷定條件46012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊出隊J7,J8,J9入隊入隊隊空：隊空：front=rearfront=rear隊滿：隊滿：front=rearfront=rear處理方案：處理方案：1.另外設一個標志位以區(qū)別隊空、隊滿另外設一個標志位以區(qū)別隊空、隊滿2.少用一個元素空間：少用一個元素空間： 隊空：隊空：front=rear 隊滿：隊滿：(rear+1)%M=front3.運用一個計數(shù)器記錄隊列中元素的總數(shù)運用一個計數(shù)器記錄隊列中元素的總數(shù)J5J6012345rearfront初始形狀J447 St

28、atus InitQueue (SqQueue &Q) / 構造一個空隊列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存儲分配失敗 Q.front = Q.rear = 0; return OK; 48Status EnQueue (SqQueue &Q, QElemType e) / 插入元素插入元素e為為Q的新的的新的隊尾元素隊尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊列滿隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK;49 Status DeQueue (SqQueue &Q, QElemType &e) / 假設隊列不空，那么刪除Q的隊頭元素， / 用e前往其值，并前往OK; 否那么前往ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;50第三章作業(yè)3.1 設將整數(shù)設將整數(shù)1、2