嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)課件第三章

1、通常稱(chēng)，棧和隊(duì)列是限定插入和刪除插入和刪除只能只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。 線性表線性表 棧棧 隊(duì)列隊(duì)列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊(duì)列是兩種常用的數(shù)據(jù)類(lèi)型棧和隊(duì)列是兩種常用的數(shù)據(jù)類(lèi)型3.1 棧的類(lèi)型定義棧的類(lèi)型定義3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 棧類(lèi)型的實(shí)現(xiàn)棧類(lèi)型的實(shí)現(xiàn)3.4 隊(duì)列的類(lèi)型定義隊(duì)列的類(lèi)型定義3.5 隊(duì)列類(lèi)型的實(shí)現(xiàn)隊(duì)列類(lèi)型的實(shí)現(xiàn)3.1 棧的類(lèi)型定義棧的類(lèi)型定義 ADT Stack 數(shù)據(jù)對(duì)象數(shù)

2、據(jù)對(duì)象： 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)StackLength(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e)StackTravers(S, visit() InitStack(&S) 操作結(jié)果：構(gòu)造一個(gè)空棧 S。

3、 DestroyStack(&S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷(xiāo)毀。StackEmpty(S)初始條件：棧 S 已存在。 操作結(jié)果：若棧 S 為空棧，則返回 TRUE，否則 FALE。StackLength(S)初始條件：棧 S 已存在。 操作結(jié)果：返回 S 的元素個(gè)數(shù)，即棧的長(zhǎng)度。 GetTop(S, &e) 初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S 的棧頂元素。a1a2an ClearStack(&S)初始條件：棧 S 已存在。 操作結(jié)果：將 S 清為空棧。Push(&S, e) 初始條件：棧 S 已存在。 操作結(jié)果：

4、插入元素 e 為新的棧頂元素。a1a2ane Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。a1a2anan-1 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)例三、例三、 行編輯程序問(wèn)題行編輯程序問(wèn)題例四、例四、 迷宮求解迷宮求解例五、例五、 表達(dá)式求值表達(dá)式求值例六、例六、 實(shí)現(xiàn)遞歸實(shí)現(xiàn)遞歸 例一、例一、 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ，其運(yùn)算過(guò)程如下

5、： N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2計(jì)算順序計(jì)算順序輸出順序輸出順序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 ); / conversion例二、例二、 括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中 （）或（ ）等為正確的格式， （ ）或（ ）或 ( )均為不正確的格式。則 檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”

6、這個(gè)概念來(lái)描述。分析可能出現(xiàn)的不匹配不匹配的情況: 到來(lái)的右括弧非是所“期待”的;例如：考慮下列括號(hào)序列： ( ) 1 2 3 4 5 6 7 8 到來(lái)的是“不速之客”; 直到結(jié)束，也沒(méi)有到來(lái)所“期待”的括弧;算法的設(shè)計(jì)思想：算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧左括弧，則進(jìn)棧進(jìn)棧；2）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若?？諚？?，則表明該“右括弧右括弧”多余多余 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出棧” 否則表明不匹配不匹配3）表達(dá)式表達(dá)式檢驗(yàn)結(jié)束時(shí)結(jié)束時(shí)， 若?？諚？?，則表明表達(dá)式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余Status matchi

7、ng(string& exp) int state = 1; while (i= S.stacksize) /棧滿(mǎn) return OVERFLOW; *S.top+ = e; return OK;Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用 e 返回其值，并返回OK； / 否則返回ERROR if (S.top = S.base) return ERROR; e = *-S.top; return OK;棧頂指針鏈棧鏈棧a1an注意注意: 鏈棧中鏈棧中指針的方向指針的方向an-1棧底元素棧底元素

8、ADT Queue 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊(duì)列頭隊(duì)列頭， an 端為隊(duì)列尾隊(duì)列尾基本操作：基本操作：3.4 隊(duì)列的類(lèi)型定義隊(duì)列的類(lèi)型定義 ADT Queue隊(duì)列的基本操作：隊(duì)列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueu

9、e(&Q, e)QueueTravers(Q, visit()InitQueue(&Q) 操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。DestroyQueue(&Q)初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：隊(duì)列Q被銷(xiāo)毀， 不再存在。 QueueEmpty(Q)初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。 QueueLength(Q) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列的長(zhǎng)度。 GetHead(Q, &e) 初始條件：初始條件：Q為非空隊(duì)列。 操作

10、結(jié)果：操作結(jié)果：用e返回Q的隊(duì)頭元素。a1a2an ClearQueue(&Q)初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：將Q清為空隊(duì)列。 EnQueue(&Q, e) 初始條件：初始條件：隊(duì)列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。a1a2ane DeQueue(&Q, &e) 初始條件：初始條件：Q為非空隊(duì)列。 操作結(jié)果：操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。a1a2an 3.5 隊(duì)列類(lèi)型的實(shí)現(xiàn)隊(duì)列類(lèi)型的實(shí)現(xiàn)鏈隊(duì)列鏈隊(duì)列鏈?zhǔn)接诚笱h(huán)隊(duì)列循環(huán)隊(duì)列順序映象 typedef struct QNode / 結(jié)點(diǎn)類(lèi)型結(jié)點(diǎn)類(lèi)型

11、QElemType data; struct QNode *next; QNode, *QueuePtr;鏈隊(duì)列鏈隊(duì)列鏈?zhǔn)接诚髏ypedef struct / 鏈隊(duì)列類(lèi)型鏈隊(duì)列類(lèi)型 QueuePtr front; / 隊(duì)頭指針隊(duì)頭指針 QueuePtr rear; / 隊(duì)尾指針隊(duì)尾指針 LinkQueue;a1anQ.frontQ.frontQ.rear空隊(duì)列空隊(duì)列Q.rear Status InitQueue (LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q Q.front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW); /

12、存儲(chǔ)分配失敗 Q.front-next = NULL; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊(duì)尾元素 p = new QNode; if (!p) exit (OVERFLOW); /存儲(chǔ)分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;a1anQ.frontQ.rearep Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除

13、Q的隊(duì)頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; delete (p); return OK;if (Q.rear = p) Q.rear = Q.front;#define MAXQSIZE 100 /最大隊(duì)列長(zhǎng)度typedef struct QElemType *base; / 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針，若隊(duì)列不空， / 指向隊(duì)列頭元素 int rear; / 尾指針，若

14、隊(duì)列不空，指向 / 隊(duì)列尾元素 的下一個(gè)位置 int queuesize; SqQueue;循環(huán)隊(duì)列循環(huán)隊(duì)列順序映象 Status InitQueue (SqQueue &Q, int maxsize) / 構(gòu)造一個(gè)最大存儲(chǔ)空間為 maxsize 的 / 空循環(huán)隊(duì)列 Q Q.base = new ElemTypemaxsize; if (!Q.base) exit (OVERFLOW); Q.queuesize = maxsize; Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemType e)

15、/ 插入元素e為Q的新的隊(duì)尾元素 if (Q.rear+1) % Q.queuesize = Q.front) return ERROR; /隊(duì)列滿(mǎn) Q.baseQ.rear = e; Q.rear = (Q.rear+1) % Q.queuesize; return OK; Status DeQueue (SqQueue &Q, ElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q

16、.front+1) % Q.queuesize; return OK;隊(duì)列應(yīng)用示例隊(duì)列應(yīng)用示例一、計(jì)算一、計(jì)算 n 行楊輝三角的值行楊輝三角的值二、二、“劃分無(wú)沖突子集問(wèn)題劃分無(wú)沖突子集問(wèn)題” 求解求解第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二項(xiàng)式系數(shù)值（楊輝三角）設(shè)第 i-1行的值：(a0=0) a1.ai (ai+1=0)則第 i 行的值：bj = aj-1+aj, j=1,2,i+1利用循環(huán)隊(duì)列計(jì)算二項(xiàng)式的過(guò)程：假設(shè)只計(jì)算三行，則隊(duì)列的最大容量為 5。1 1 00q.frontq.rear1 1 001q.frontq.rear1

17、 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 133q.frontq.reardo DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); while (e!=0); 某運(yùn)動(dòng)會(huì)設(shè)立 N 個(gè)比賽項(xiàng)目，每個(gè)運(yùn)動(dòng)員可以參加一至三個(gè)項(xiàng)目。試問(wèn)如何安排比賽日程既可以使同一運(yùn)動(dòng)

18、員參加的項(xiàng)目不安排在同一單位時(shí)間進(jìn)行，又使總的競(jìng)賽日程最短。 若將此問(wèn)題抽象成數(shù)學(xué)模型，則歸屬于“劃分子集”問(wèn)題。N 個(gè)比賽項(xiàng)目構(gòu)成一個(gè)大小為 n 的集合，有同一運(yùn)動(dòng)員參加的項(xiàng)目則抽象為“沖突”關(guān)系。 例如：某運(yùn)動(dòng)會(huì)設(shè)有 9 個(gè)項(xiàng)目: A = 0，1，2，3，4，5，6，7，8 ，七名運(yùn)動(dòng)員報(bào)名參加的項(xiàng)目分別為：（1，4，8）、（1，7）、（8，3）、（1，0，5）、（3，4）、（5，6，2）、（6，4） 它們之間的沖突關(guān)系為: R = （1，4）,（4，8）,（1，8）,（1，7）,（8，3）,（1，0）,（0，5）,（1，5）,（3，4）,（5，6）,（5，2）,（6，2）,（6，4） 將

19、集合A劃分成k個(gè)互不相交的子集 A1，A2，Ak（kn），使同一子集中的元素均無(wú)沖突關(guān)系，并要求劃分的子集數(shù)目盡可能地少?！皠澐肿蛹瘎澐肿蛹眴?wèn)題即為問(wèn)題即為: : 對(duì)前述例子而言，問(wèn)題即為:同一子集的項(xiàng)目為可以同時(shí)進(jìn)行的項(xiàng)目，顯然希望運(yùn)動(dòng)會(huì)的日程盡可能短。 可利用“過(guò)篩過(guò)篩”的方法來(lái)解決劃分子集問(wèn)題。從第一個(gè)元素考慮起，凡不和第一個(gè)元素發(fā)生沖突的元素都凡不和第一個(gè)元素發(fā)生沖突的元素都可以和它分在同一子集中可以和它分在同一子集中，然后再“過(guò)篩”出一批互不沖突的元素為第二個(gè)子集，依次類(lèi)推，直至所有元素都進(jìn)入某個(gè)子集為止。 012345678001000100011000110112000001100300001000140101001015111000100600101100070100000008010110000012345678145684588 0 1 0 0 0 1 0 0 0 0 1 0 0 0 2 1 0 0 0 1 0 0 1 2 1 0 1 0 2