數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料- chap3棧與隊列ppt課件

1、第三章棧和隊列通常稱，棧和隊列是限定插入和刪除只能在表的“端點進(jìn)展的線性表。 線性表線性表 棧棧 隊列隊列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) 1in 1in棧和隊列是兩種常用的數(shù)據(jù)類型棧和隊列是兩種常用的數(shù)據(jù)類型3.1 棧的類型定義棧的類型定義3.2

2、 棧的運用舉例棧的運用舉例3.3 棧類型的實現(xiàn)棧類型的實現(xiàn)3.4 隊列的類型定義隊列的類型定義3.5 隊列類型的實現(xiàn)隊列類型的實現(xiàn)3.1 棧的類型定義棧的類型定義 ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 商定商定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 根本操作：根本操作： ADT StackInitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLengt

3、h(S)GetTop(S, &e)/前往棧頂元素Push(&S, e)/插入新的棧頂Pop(&S, &e)/刪除棧頂，并用e前往它的值StackTravers(S, visit() InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧 S。 DestroyStack(&S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷毀。StackEmpty(S)初始條件：棧 S 已存在。 操作結(jié)果：假設(shè)棧 S 為空棧，那么前往 TRUE，否那么 FALE。StackLength(S)初始條件：棧 S 已存在。 操作結(jié)果：前往 S 的元素個數(shù)，即棧的長度。

4、GetTop(S, &e) 初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 前往 S 的棧頂元素。a1 a2an ClearStack(&S)初始條件：棧 S 已存在。 操作結(jié)果：將 S 清為空棧。Push(&S, e) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 e 為新的棧頂元素。a1 a2an e Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除 S 的棧頂元素，并用 e 前往其值。a1 a2anan-1 3.2 棧的運用舉例棧的運用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號匹配的檢驗括號匹配的檢驗例三、例三

5、、 行編輯程序問題行編輯程序問題例四、例四、 迷宮求解迷宮求解例五、例五、 表達(dá)式求值表達(dá)式求值例六、例六、 實現(xiàn)遞歸實現(xiàn)遞歸 例一、 數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 例如：1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmp

6、ty(S) Pop(S,e); printf ( %d, e ); / conversion例二、例二、 括號匹配的檢驗括號匹配的檢驗假設(shè)在表達(dá)式中假設(shè)在表達(dá)式中或或 等為正確的格式，等為正確的格式， 或或 或或 )均為不正確的格式。均為不正確的格式。那么 檢驗括號能否匹配的方法可用“等待的急迫程度這個概念來描畫。分析能夠出現(xiàn)的不匹配的情況: 到來的右括弧并非是所等待的；例如：思索以下括號序列： ( ) 1 2 3 4 5 6 7 8 到來的是“不速之客； 直到終了，也沒有到來所“等待的括弧。算法的設(shè)計思想：算法的設(shè)計思想：1凡出現(xiàn)左括弧，那么進(jìn)棧；凡出現(xiàn)左括弧，那么進(jìn)棧；2凡出現(xiàn)右括弧，首先

7、檢查棧能否空凡出現(xiàn)右括弧，首先檢查棧能否空 假設(shè)?？?，那么闡明該假設(shè)?？?，那么闡明該“右括弧多余，右括弧多余， 否那么和棧頂元素比較，否那么和棧頂元素比較， 假設(shè)相匹配，那么假設(shè)相匹配，那么“左括弧出棧左括弧出棧 ， 否那么闡明不匹配。否那么闡明不匹配。3表達(dá)式檢驗終了時，表達(dá)式檢驗終了時， 假設(shè)?？眨敲搓U明表達(dá)式中匹配正確，假設(shè)?？?，那么闡明表達(dá)式中匹配正確， 否那么闡明否那么闡明“左括弧有余。左括弧有余。Status matching(string& exp) int state = 1; while (i= S.stacksize) /棧滿，追加存儲空間棧滿，追加存儲空間 S.

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

9、值，并前往前往其值，并前往OK； / 否那么前往否那么前往ERROR if (S = S.base) return ERROR; e = *-S; return OK;棧頂指針鏈棧鏈棧a1an留意留意: 鏈棧中鏈棧中指針的方向指針的方向an-1 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 商定其中商定其中a1 端為隊列頭，端為隊列頭， an 端為隊列尾端為隊列尾根本操作：根本操作：3.4 隊列的類型定義隊列的類型定義 ADT Queue隊列的根本操作：隊列的根本操

10、作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作結(jié)果：構(gòu)造一個空隊列操作結(jié)果：構(gòu)造一個空隊列Q。DestroyQueue(&Q)初始條件：隊列初始條件：隊列Q已存在。已存在。 操作結(jié)果：隊列操作結(jié)果：隊列Q被銷毀，被銷毀， 不再存在。不再存在。 QueueEmpty

11、(Q)初始條件：隊列Q已存在。 操作結(jié)果：假設(shè)Q為空隊列，那么前往TRUE，否那么前往FALSE。 QueueLength(Q) 初始條件：隊列Q已存在。 操作結(jié)果：前往Q的元素個數(shù)，即隊列的長度。 GetHead(Q, &e) 初始條件：Q為非空隊列。 操作結(jié)果：用e前往Q的隊頭元素。a1 a2an ClearQueue(&Q)初始條件：隊列Q已存在。 操作結(jié)果：將Q清為空隊列。 EnQueue(&Q, e) 初始條件：隊列Q已存在。 操作結(jié)果：插入元素e為Q的新的隊尾元素。a1 a2an e DeQueue(&Q, &e) 初始條件：Q為非空隊列。

12、操作結(jié)果：刪除Q的隊頭元素，并用e前往其值。a1 a2an 3.5 隊列類型的實現(xiàn)隊列類型的實現(xiàn)鏈隊列鏈隊列鏈?zhǔn)接诚箧準(zhǔn)接诚笱h(huán)隊列循環(huán)隊列順序映象順序映象 typedef struct QNode / 結(jié)點類型 QElemType data; struct QNode *next; QNode, *QueuePtr;鏈隊列鏈隊列鏈?zhǔn)接诚箧準(zhǔn)接诚髏ypedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空隊列空隊

13、列 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; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素 p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /

14、存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElemType &e) / 假設(shè)隊列不空，那么刪除Q的隊頭元素， /用 e 前往其值，并前往OK；否那么前往ERROR if (Q.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; fre

15、e (p); return OK;#define MAXQSIZE 100 /最大隊列長度最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間動態(tài)分配存儲空間 int front; / 頭指針，假設(shè)隊列不空，頭指針，假設(shè)隊列不空， / 指向隊列頭元素指向隊列頭元素 int rear; / 尾指針，假設(shè)隊列不空，指向尾指針，假設(shè)隊列不空，指向 / 隊列尾元素隊列尾元素 的下一個位置的下一個位置 SqQueue;循環(huán)隊列循環(huán)隊列順序映象順序映象 Status InitQueue (SqQueue &Q) / 構(gòu)造一個空隊列Q Q.base =

16、(ElemType *) malloc (MAXQSIZE *sizeof (ElemType); if (!Q.base) exit (OVERFLOW); / 存儲分配失敗 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemType e) / 插入元素插入元素e為為Q的新的隊尾元素的新的隊尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊列滿隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZ

17、E; return OK; Status DeQueue (SqQueue &Q, ElemType &e) / 假設(shè)隊列不空，那么刪除Q的隊頭元素， / 用e前往其值，并前往OK; 否那么前往ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % MAXQSIZE; return OK;第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二項式系數(shù)值楊輝三角 (非考試內(nèi)容)設(shè)第 i-1行的值：(a0=0) a1.ai

18、(ai+1=0)那么第 i 行的值：bj = aj-1+aj, j=1,2,i+1利用循環(huán)隊列計算二項式的過程：假設(shè)只計算四行，那么隊列的最大容量為 5。1 1 00q.frontq.rear1 1 001q.frontq.rear1 1 021q.frontq.rear1 1 021q.frontq.rear1 0 021q.frontq.rear1 0 121q.frontq.rear1 0 121q.frontq.rear1 0 123q.frontq.rear1 0 133q.frontq.rear1 0 131q.frontq.reardo DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d, e); EnQueue(Q, s+e); wh