1、第三章 棧和隊列,棧和隊列都屬于線性結(jié)構(gòu)，是兩種在運算上受到某些限制的特殊線性表，他們比一般線性表更簡單，被廣泛應(yīng)用于程序設(shè)計中。 學習重點 1、掌握棧和隊列的定義、特性，并能正確應(yīng)用它們解決實際問題；2、熟練掌握棧的順序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)。特別注意棧空和棧滿的條件；3、熟練掌握隊列的順序表示、鏈表表示以及相應(yīng)操作的實現(xiàn)。特別是循環(huán)隊列中隊頭與隊尾指針的變化情況。,3.1 棧,3.2 棧的應(yīng)用舉例,3.3 棧類型的實現(xiàn),3.4 隊列,3.5 隊列類型的實現(xiàn),棧 ( Stack ),定義:是限定僅在表尾進行插入或刪除操作的線性表。 允許插入和刪除的一端 稱為棧頂(top)，另一端

2、稱為棧底(base) 特點：后進先出 (LIFO),a1,top,base,an . . . .,進棧,出棧,InitStack(/存儲空間初始分配量 #define STACKINCREMENT 10;/存儲空間分配增量 typedef struct SElemType *base; /在棧構(gòu)造之前和銷毀之后， / base 的值為NULL SElemType *top; /棧頂指針 int stacksize; /當前已分配的存儲空間，以元素為單位 SqStack;,類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。,Status InitStack (SqStack ,Stat

3、us Push (SqStack ,Status Pop (SqStack ,例：一個棧入棧序列是a,b,c,d,e,則不可能輸出的序列是 。,A、edcba B、decba,C、dceab,D、abcde,答案：C,鏈式棧:棧的鏈接表示,鏈式棧無棧滿問題，空間可擴充 插入與刪除僅在棧頂處執(zhí)行 鏈式棧的棧頂在鏈頭,top,3.1.3 棧的鏈式存儲實現(xiàn),鏈棧的操作易于實現(xiàn)，在此不作詳細討論。,3.2 棧的應(yīng)用舉例,例一、 數(shù)制轉(zhuǎn)換,例二、 括號匹配的檢驗,例三、 行編輯程序問題,例四、 迷宮求解,例五、 表達式求值,例六、 實現(xiàn)遞歸,數(shù)制轉(zhuǎn)換例如：（1348)10 = (2504)8 ，其運算過

4、程如下： N N div 8 N mod 8 1348 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 (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion,例二、 括號匹配的檢驗 假設(shè)在表達式中 （）或（ ） 等為正確的格式， （ ）或（ ）或 ( ) 均為不正確的格式。,則 檢驗括號是否匹配的方法可用 “期待的急迫程度”這個概念來

5、描述。,分析可能出現(xiàn)的不匹配的情況:,到來的右括弧非是所“期待”的;,例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8,到來的是“不速之客”;,直到結(jié)束，也沒有到來所“期待”的括弧;,算法的設(shè)計思想：,1）凡出現(xiàn)左括弧，則進棧；,2）凡出現(xiàn)右括弧，首先檢查棧是否空 若?？?，則表明該“右括弧”多余 否則和棧頂元素比較，若相匹配， 則“左括弧出棧”;否則表明不匹配,3）表達式檢驗結(jié)束時， 若?？?，則表明表達式中匹配正確 否則表明“左括弧”有余,3.19 假設(shè)一個算術(shù)表達式中可以包含三種括號：圓括號“(” 和“)”，方括號“”和“”和花括號“”和“”，且這三種括號可按任意的.次序嵌套

6、使用（如：()）。編寫判別給定表達式中所含括號是否正確配對出現(xiàn)的算法(已知表達式已存入數(shù)據(jù)元素為字符的順序表中)。,實現(xiàn)下列函數(shù)： Status MatchCheck(SqList exp); /* 順序表exp表示表達式； */ /* 若exp中的括號配對，則返回TRUE，否則返回FALSE */ 順序表類型定義如下： typedef struct ElemType *elem; int length; int listsize; SqList; / 順序表,Status MatchCheck(SqList exp) /* 順序表exp表示表達式； */ /* 若exp中的括號配對，則返回T

7、RUE，否則返回FALSE */ ElemType *p; Stack s; char c; InitStack(s); for(p= else if (*p=)|*p=|*p=), if (StackEmpty(s) return FALSE; Pop(s,c); if(*p=) ,例三、行編輯程序問題,如何實現(xiàn)？,“每接受一個字符即存入存儲器” ?,并不恰當！,在用戶輸入一行的過程中，允許 用戶輸入出差錯，并在發(fā)現(xiàn)有誤時 可以及時更正。,設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū); 并假設(shè)“#”為退格符，“”為退行符。,合理的作法是：,假設(shè)從終端接受了這樣兩行字

8、符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,則實際有效的是下列兩行： while (*s) putchar(*s+);,Void LineEdit() InitStack(s); ch=getchar(); while (ch != EOF) /EOF為全文結(jié)束符 while (ch != EOF / 從終端接收下一個字符 /while,將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的 數(shù)據(jù)區(qū)； ClearStack(S); / 重置S為空棧 if (ch != EOF) ch = getchar(); /while DestroyStack(s); ,temp=S

9、.base while(temp!=S.top) printf(%c,*temp); +temp; ,求迷宮路徑算法的基本思想是：,若當前位置“可通”，則納入路徑，即當前位置插入棧頂，繼續(xù)前進;,若當前位置“不可通”，則換方向繼續(xù)探索;沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊,若四周“均無通路”，則將當前位置從路徑中刪除出去。,例四 迷宮求解,迷宮求解,常用“窮舉求解”的方法,設(shè)定當前位置的初值為入口位置； do 若當前位置可通， 則將當前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束； 否則切換當前位置的東鄰方塊為新的 當前位置； .,否則 若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定

10、新的當前位置為: 沿順時針方向旋轉(zhuǎn) 找到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置；/ 從路徑中刪去該通道塊 若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？? while (棧不空）；,限于二元運算符的表達式定義: 表達式 := (操作數(shù)) + (運算符) + (操作數(shù)) 操作數(shù) := 簡單變量 | 表達式 簡單變量 : = 標識符 | 無符號整數(shù),例五、 表達式求值,表達式的三種標識方法：,設(shè) Exp = S1 + OP + S2,則稱 OP S1 S2 為前綴表示法,S1 OP S2 為中綴表示法,S1 S2 OP 為后綴表示法

11、,例如: Exp = a b + (c d / e) f 后綴式: a b c d e / f +,結(jié)論:,1）操作數(shù)之間的相對次序不變;,2）運算符的相對次序不同;,3）中綴式丟失了括弧信息， 致使運算的次序不確定;,4) 后綴式的運算規(guī)則為: 運算符在式中出現(xiàn)的順序恰為表達式的運算順序;每個運算符和在它之前出現(xiàn) 且緊靠它的兩個操作數(shù)構(gòu)成一個最小表達式;,如何從后綴式求值？,先找運算符， 再找操作數(shù),例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,如何從原表達式求得后綴式？,分析 “原表達式” 和 “后綴式”的運算符: 原表達式: a + b c d /

12、e f 后綴式: a b c + d e / f ,從中綴表達式求得后綴式的規(guī)律為：,1) 設(shè)立運算符棧;,2) 設(shè)表達式的結(jié)束符為“#”, 予設(shè)運算符棧的棧底為“#”,3) 若當前字符是操作數(shù)， 則直接發(fā)送給后綴式;,4) 若當前運算符的優(yōu)先級高于棧頂 運算符，則進棧;,5) 若當前運算符的優(yōu)先級低于棧頂運算符，退出棧頂運算符發(fā)送給后綴式;,可以使用兩個工作棧，一個為運算符棧OPTR,用以寄存運算符符，一個為操作數(shù)棧OPND用以寄存操作數(shù)或運算結(jié)果。,中綴表達式求值,在算符集中，在每一個運算步，相鄰的算符c1 和c2之間的關(guān)系是如下三種情況（c1出現(xiàn)在c2之前）： c1c2,c1的優(yōu)先級大于

13、c2,為實現(xiàn)中綴表達式計算，在這里用了兩個工作棧。一個存放算符OPTR，另一個存放數(shù)據(jù)OPND。算法思想是： （1）首先置數(shù)據(jù)棧為空棧，表達式起始符“”為算符棧的棧底元素 （2）自左向右掃描表達式，讀到操作數(shù)進OPND棧，讀到運算符，則和OPTR棧頂元素比較（棧頂元素為c1，讀到的算符為c2); 若c1c2,則將c1出棧，并在操作數(shù)棧取出兩個元素a和b按c1做運算，運算結(jié)果進OPND. 重復(fù)直到表達式求值完畢。,中綴表達式：操作數(shù)棧和運算符棧,例 計算 2+4+3*6,OperandType EvaluateExpression( ) /算術(shù)表達式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別是

14、運算符棧和運算數(shù)棧，OP為運算符集合。 Initstack(OPTR) ; Push(OPTR,）； Initstack(OPND) ; c=getchar( ) ; While(c!=# | GetTop (OPTR)!=#) if ( ! In(c,OP) )Push(OPDN,c) ; c=getchar( );/不是運算符則進棧 else switch(Precede(GetTop(OPTR), c) /比較棧頂和當前運算符的優(yōu)先級別 case : /棧頂元素優(yōu)先權(quán)低 Push（OPTR，c); c=getchar( ) ; break; case =: /脫括號并接受下一字符 Pop

15、(OPTR , x) ; c=getchar( ); break;,Case : /退棧并將運算結(jié)果入棧 Pop(OPTR, theta) ; Pop(OPND ,b) ; Pop(OPND, a) ; Push(OPND, Operate( a, theta, b); break ; /switch /while return GetTop(OPND); /EvaluateExpression,后綴表達式求值步驟： 1、讀入表達式一個字符 2、若是操作數(shù)，壓入棧 3、若是運算符，從棧中彈出2個數(shù)，將運算結(jié)果再壓入棧 4、若表達式輸入完畢，棧頂即表達式值； 若表達式未輸入完，轉(zhuǎn)1,例 計算 4

16、+3*5,后綴表達式：435*+,例六 實現(xiàn)遞歸,多個函數(shù)嵌套調(diào)用的規(guī)則是:,此時的內(nèi)存管理實行“棧式管理”,后調(diào)用先返回 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,Main的數(shù)據(jù)區(qū),函數(shù)a的數(shù)據(jù)區(qū),函數(shù)b的數(shù)據(jù)區(qū),void hanoi (int n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n / 的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。 1 if (n=1) 2 move(x, 1, z); / 將編號為的圓盤從x移到z 3 else 4

17、hanoi(n-1, x, z, y); / 將x上編號為至n-1的 /圓盤移到y(tǒng), z作輔助塔 5 move(x, n, z); / 將編號為n的圓盤從x移到z 6 hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔 7 8 ,隊列 隊列的定義及特點 定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表 隊尾(rear)允許插入的一端 隊頭(front)允許刪除的一端 隊列特點：先進先出(FIFO),ADT Queue 數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系： R1 | ai-1, ai

18、 D, i=2,.,n 約定其中a1 端為隊列頭， an 端為隊列尾,基本操作：,隊列的類型定義, ADT Queue,隊列的基本操作：,InitQueue( / 動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空， / 指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向 / 隊列尾元素 的下一個位置 SqQueue;,循環(huán)隊列順序映象,SqOueue *sq ;,Status InitQueue (SqQueue ,Status EnQueue (SqQueue ,Status DeQueue (SqQueue ,typedef struct QNode / 結(jié)點類

19、型 QElemType data; struct QNode *next; QNode, *QueuePtr;,鏈隊列鏈式映象,為了操作方便，給鏈隊列添加一個頭結(jié)點。,typedef struct / 鏈隊列類型 QueuePtr front; / 隊頭指針 QueuePtr rear; / 隊尾指針 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空隊列,Q.front-next = Q.rear-next =NULL,Y出對,Status InitQueue (LinkQueue ,Status EnQueue (LinkQueue if (!p) exit (OVERFLOW); /存儲分配失敗,p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;,Status DeQueue (LinkQueue ,p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free