1、第三章 棧和隊(duì)列,3.1 棧的抽象數(shù)據(jù)類型定義與實(shí)現(xiàn) 3.2 棧的應(yīng)用舉例 3.3 棧的應(yīng)用-棧與遞歸 3.4 隊(duì)列的抽象數(shù)據(jù)類型定義和實(shí)現(xiàn) 3.5 隊(duì)列應(yīng)用-離散事件模擬,1、 棧的相關(guān)概念 概念: 棧(Stack)是定義在線性結(jié)構(gòu)上的抽象數(shù)據(jù)類型，其操作類似線性表操作，但元素的插入、刪除和訪問都必須在表的一端進(jìn)行,為形象起見,稱允許操作端為棧頂(Top),另一端為棧底(base),注意Top指向待插入位置 特性:Last In First Out后進(jìn)先出/總是訪問最近插入的一個(gè)/按插入順序倒著訪問,3.1 棧(Stack),棧頂 元素,2、棧的ADT定義,ADT Stack 數(shù)據(jù)對(duì)象：D=

2、ai|aiElemSet,i=1,2,n,n=0 數(shù)據(jù)關(guān)系：R=|ai-1,aiD，約定an為棧頂元素 基本操作： InitStack (/棧元素類型 typedef struct SElemType *base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; /棧容量 SqStack /如何判?？?、求棧長、判棧滿？,順序?；静僮鞯膶?shí)現(xiàn)初始化/銷毀/置空,Status InitStack(SqStack /InitStack 復(fù)雜度”O(jiān)(1)”,Status DestroyStack(SqStack /復(fù)雜度O(1),Status ClearStack

3、(SqStack /復(fù)雜度O(1),Status Push(SqStack /Push ,復(fù)雜度O(1),Status Pop(SqStack /復(fù)雜度O(1),入棧與出棧,Status StackEmpty(SqStack S) if(S.top=S.base)return TRUE;else return FALSE; int StackLength (SqStack S) return (S.top-S.base); Status GetTop(SqStack S, SElemType /除遍歷操作外時(shí)間復(fù)雜度均O(1),引用型操作,/可據(jù)需要適當(dāng)增加新操作 Status SetTopE

4、lem(SqStack S,ElemType e) /將棧頂元素的值修改為e if(S.top=S.base)return ERROR; *(S.top-1)=e; return OK; /可用pop和push合作實(shí)現(xiàn),4、鏈棧的定義與實(shí)現(xiàn)【補(bǔ)充】,若棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，可考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱作“鏈棧”。 鏈棧常用一個(gè)無頭結(jié)點(diǎn)的單鏈表表示，棧名指針指向棧頂元素，相當(dāng)于順序棧棧頂指針，但有不同,順序棧棧頂指針指向第一個(gè)空位置 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義:,typedef struct SNode SElemType data; struct SNo

5、de *next; SNode, *LinkStack; LinkStack S; /鏈棧棧名S指向棧頂元素，順序棧top指向首個(gè)空位置,注意最先插入在最底端 鏈棧鏈指針向下,基本操作實(shí)現(xiàn),Status InitStack(LinkStack /其余操作自行實(shí)現(xiàn), 遍歷/銷毀/清空/求表長均O(n)，其余O(1),3.2 棧的應(yīng)用,1、十進(jìn)制整數(shù)轉(zhuǎn)換為八進(jìn)制,0,5,2,4,void conversion( ) scanf (“%d”, ,充分利用棧后進(jìn)先出的特性,比用數(shù)組更易讀易寫抽象層次更高,回顧:,棧的概念:棧 棧底指針 棧頂指針 棧頂元素 棧的兩種存儲(chǔ)結(jié)構(gòu)定義及各自適用場(chǎng)合，及棧的操作

6、在兩種結(jié)構(gòu)下的實(shí)現(xiàn) 棧的應(yīng)用- Last In First Out后進(jìn)先出/總是訪問最近插入的一個(gè)/按插入順序倒著訪問,#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef ? SElemType; typedef struct SElemType *base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; /棧容量 SqStack; SqStack S1,S2; typedef struct SNode datatype data; struct SNode *next; SNode

7、,*LinkStack; LinkStack S3;/棧名S為棧頂元素指針,2、括號(hào)匹配檢驗(yàn),正確：() 錯(cuò)誤：() ( ) (),Status match( ) initstack(S);hasErr=0; while(c=getchar()!=n ,編譯過程中尚需報(bào)告出錯(cuò)行數(shù)、忽略注釋/字符串和字符常量等,思路:依次掃描各符號(hào),每遇一結(jié)束符都找最近的開始符來匹配,不匹配或未找到則報(bào)錯(cuò).最后應(yīng)左右括號(hào)完全匹配畢 初始化一個(gè)空棧 逐個(gè)掃描符號(hào) 如果當(dāng)前符號(hào)是開始符則入棧 如果是結(jié)束符號(hào)則分三種情況 如果?？談t報(bào)告出錯(cuò) /右多 否則,出棧,若彈出元素與當(dāng)前元素不匹配則報(bào)告出錯(cuò)/不匹配 否則無動(dòng)作

8、，掃描下一符號(hào) 掃描結(jié)束,若棧不空則出錯(cuò) /左多,3、行編輯程序,whli#ilr#e(s#*s) /while(*s) outchaputchar(*s=#+) /putchar(*s+);,思路:為提高數(shù)據(jù)輸入效率設(shè)置輸入緩沖區(qū).對(duì)于輸入的一行數(shù)據(jù),行結(jié)束時(shí)方將緩沖區(qū)的數(shù)據(jù)存入用戶數(shù)據(jù)區(qū),中間過程允許編輯;若最近的一個(gè)字符出錯(cuò)則用退格符#表示刪去,若當(dāng)前行不要?jiǎng)t用退行符則將當(dāng)前行清空. 遇到行結(jié)束符前，每遇一個(gè)符號(hào)，若它不是#或則入棧,若是#則出棧,若是則清空棧，一旦遇到行結(jié)束符或全文結(jié)束符則將緩沖區(qū)中數(shù)據(jù)保存到用戶數(shù)據(jù)區(qū)如此重復(fù)直到全文結(jié)束,void LineEdit() InitSta

9、ck(S); ch=getchar(); while(ch!=EOF)/全文未結(jié)束 while(ch!=n /行尾非EOF ,4、迷宮求解,令curPos指向入口,curStep為1,重復(fù)while(TRUE) 若當(dāng)前位置通,則將其納入路徑(棧).是出口停,非出口重置curPos為右鄰，開始下次循環(huán) 若當(dāng)前位置不通,看上一步，若其四周均已訪問過，則將其從路徑中刪除，如此重復(fù)直至找到一個(gè)曾經(jīng)訪問之位置，其四個(gè)方向至少有一個(gè)未曾訪問過；此時(shí)重置curPos為此未訪問鄰塊，開始下次循環(huán)。若?？杖稳晃凑业絼t退出。,typedef int Maze1010;Maze maze;/或int maze101

10、0; typedef struct int x;int y;PosType;/迷宮中的位置類型 typedef structint ord;PosType seat;int di;SElemType;/棧元素類型 typedef structSElemType *base;SElemType *top; int stacksize; Stack;/棧類型,Status PassMaze(MazeType ,令curPos指向入口,curStep為1,重復(fù)while(TRUE) 若當(dāng)前位置通,則將其納入路徑(棧).是出口停,非出口重置curPos為右鄰，開始下次循環(huán) 若當(dāng)前位置不通,看上一步，若

11、?？諢o路徑；若其四周均已訪問過，則將其從路徑中刪除，如此重復(fù)直至找到一個(gè)曾經(jīng)訪問之位置，其四個(gè)方向至少有一個(gè)未曾訪問過；此時(shí)重置curPos為此未訪問鄰塊，開始下次循環(huán)。若?？杖匀晃凑业絼t退出。,例:計(jì)算 4+2*3-10/5# 2+4-3*6# (假設(shè)只有二元運(yùn)算符) 注：拿當(dāng)前掃描的符號(hào)與上一個(gè)比較優(yōu)先級(jí)，當(dāng)前掃描符號(hào)低或相等則進(jìn)行上一個(gè)運(yùn)算(需取最近的兩個(gè)數(shù)據(jù))；否則掃描下個(gè) 注:設(shè)操作符棧和操作數(shù)棧,運(yùn)算符棧最初壓入起始符#,逐個(gè)掃描符號(hào): 遇操作數(shù)則直接入棧,繼續(xù)讀下一字符；遇運(yùn)算符則與棧頂運(yùn)算符比較優(yōu)先級(jí),當(dāng)前運(yùn)算符優(yōu)先級(jí)高(前面的運(yùn)算還不應(yīng)執(zhí)行)則當(dāng)前運(yùn)算符入棧,讀下一符號(hào);否則

12、棧頂運(yùn)算符出棧,兩操作數(shù)出棧,進(jìn)行運(yùn)算,所得結(jié)果入數(shù)棧, 開始下次循環(huán)(不掃描新符號(hào)，重新比較剛才掃描到的運(yùn)算符與新棧頂運(yùn)算符) 。如此重復(fù)直到棧頂運(yùn)算符與當(dāng)前符號(hào)均為(#),5、表達(dá)式求值算符優(yōu)先法,-,*,#,#,#,設(shè)操作符棧和操作數(shù)棧,運(yùn)算符棧最初壓入#,逐個(gè)掃描符號(hào):遇操作數(shù)則直接入棧,繼續(xù)讀下一字符；遇運(yùn)算符則與棧頂運(yùn)算符比較優(yōu)先級(jí),當(dāng)前運(yùn)算符優(yōu)先級(jí)高(前面的運(yùn)算還不應(yīng)執(zhí)行)則當(dāng)前運(yùn)算符入棧,讀下一符號(hào);否則棧頂運(yùn)算符出棧,兩操作數(shù)出棧,進(jìn)行運(yùn)算,所得結(jié)果入數(shù)棧,不掃描新符號(hào)開始下次循環(huán)。(重新比較剛才掃描到的運(yùn)算符與新棧頂運(yùn)算符)如此重復(fù)直到棧頂運(yùn)算符與當(dāng)前符號(hào)均為(#),Ini

13、tStack(OPTR);InitStack(OPND);Push(OPTR,#); c=getchar( ); while( c!=# | GetTop(OPTR)!=#) if( !In(c,OP) ) Push(OPND,c);c=getchar(); /操作數(shù)直接入棧 else switch(Precede(GetTop(OPTR),c)/比較棧頂運(yùn)算符與c優(yōu)先級(jí) case : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch /else /while; Ret

14、urn(GetTop(OPND)）；,作業(yè):,3.1若按教科書P44中圖3.1（b）所示鐵道進(jìn)行車廂調(diào)度（注意：兩側(cè)鐵道均為單向行駛道,棧）,則請(qǐng)回答：,（1）如果進(jìn)站的車廂序列為123，則可能得到的出站車廂序列是什么？,（2）如果進(jìn)站車廂序列為123456，能否得到435612和135426的出站序列，并請(qǐng)說明為什么不能得到或者如何得到（既寫出以S表示進(jìn)棧和已X表示出棧的棧操作序列 ）。,3.19表達(dá)式已存入字符串中，檢查括號(hào)匹配,3.3 棧與遞歸,專題課件,專題課件,1、 相關(guān)概念和類型定義 概念: 隊(duì)列類似線性表和棧,也是定義在線性結(jié)構(gòu)上的ADT,與線性表和棧的區(qū)別在于，元素的插入和刪除

15、分別在表的兩端進(jìn)行。類似日常生活中排隊(duì),允許插入的一端為隊(duì)尾(rear),允許刪除端稱隊(duì)頭(front) 特性:First In First Out先進(jìn)先出，如操作系統(tǒng)中的作業(yè)隊(duì)列和打印任務(wù)隊(duì)列、日常生活中各類排隊(duì)業(yè)務(wù)等均可用隊(duì)列模擬,3.4 隊(duì) 列(Queue),a2,an,e, ,a1,隊(duì)頭,隊(duì)尾,入隊(duì)列,出隊(duì)列,隊(duì)列的ADT定義,ADT Queue 數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,n,n=0 數(shù)據(jù)關(guān)系：R=|ai-1,aiD，約定a1為隊(duì)頭，an為對(duì)尾部 基本操作： InitQueue ( struct QNode *next; QNode, *QueuePtr;,t

16、ypedef struct QueuePtr front;/隊(duì)頭指針 QueuePtr rear; /隊(duì)尾指針 LinkQueue;/ 鏈隊(duì)列,隊(duì)頭元素,隊(duì)尾元素,設(shè)立尾指針有什么好處?,基本操作實(shí)現(xiàn)初始化,a1,an,Q.front Q.rear,Status InitQueue (LinkQueue /時(shí)間復(fù)雜度O(1),Q.front Q.rear,基本操作實(shí)現(xiàn)銷毀與清空,a1,an,Q.front Q.rear,Status DestroyQueue (LinkQueue /去掉下劃線部分為置空操作, 復(fù)雜度O(n),基本操作實(shí)現(xiàn)入隊(duì),a1,an,Q.front Q.rear,Stat

17、us EnQueue (LinkQueue /復(fù)雜度O(1),基本操作實(shí)現(xiàn)出隊(duì),a1,an,Q.front Q.rear,Status DeQueue (LinkQueue /復(fù)雜度O(1),3、順序隊(duì)列的定義和操作實(shí)現(xiàn),front與rear是int,刪除隊(duì)頭不移動(dòng)數(shù)據(jù),直接front+,f,g,h,插入rear=(rear+1)%M 循環(huán)隊(duì)列(臆造),如何判隊(duì)列空？ 如何判隊(duì)列“真”滿？ 為區(qū)分隊(duì)空和對(duì)真滿,約定只剩一個(gè)元素空間時(shí)為隊(duì)滿（假滿， (rear+1)%M=front),base,循環(huán)隊(duì)列類型定義：,#define MAXQSIZE 100 /最大隊(duì)列長度 typedef stru

18、ct QElemType *base;/ 動(dòng)態(tài)分配存儲(chǔ)空間 int front; / 頭指針,隊(duì)列不空則指向隊(duì)列頭元素 int rear;/尾指針,隊(duì)列不空則指向隊(duì)列尾元素下一位置 SqQueue;,記：注意隊(duì)滿和隊(duì)空的判定條件，僅當(dāng)“非空”時(shí)訪問元素方能成功 可類似順序表設(shè)初始大小與增量, 無統(tǒng)一標(biāo)準(zhǔn),Status InitQueue (SqQueue /復(fù)雜度O(1),基本操作實(shí)現(xiàn)初始化,Status DestroyQueue(SqQueue /復(fù)雜度O(1)比鏈隊(duì)列快,基本操作實(shí)現(xiàn)銷毀和清空,Status EnQueue (SqQueue /時(shí)間復(fù)雜度O(1),基本操作實(shí)現(xiàn)：插入和刪除,

19、Status DeQueue (SqQueue /時(shí)間復(fù)雜度O(1),int QueueLength(SqQueue Q) return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;/減可能為負(fù) /時(shí)間復(fù)雜度O(1)，比鏈隊(duì)列快，可修改鏈隊(duì)列定義,基本操作實(shí)現(xiàn)：隊(duì)長、隊(duì)空、求首元、遍歷,Status GetHead(SqQueue Q,QElemType / O(1)若要修改對(duì)頭元素的值可新設(shè)SetHead( else return FALSE; /O(1),Status QueueTraverse(SqQueue Q, Status (*visit)(ElemType

20、) /從隊(duì)頭元素到隊(duì)尾元素依次執(zhí)行函數(shù)(*visit) for(int i=Q.front; i!=Q.rear; i=(i+1)%MAXQSIZE ) (*visit)(Q.basei); return OK; /O(n),常用于輸出，如語句QueueTraverse(Q,PrintElem),用隊(duì)列結(jié)構(gòu)表示日常生活中的排隊(duì)，用入隊(duì)和出隊(duì)表示排到隊(duì)尾和服務(wù)完畢撤對(duì)，如銀行業(yè)務(wù)模擬.注意課程設(shè)計(jì)選題。 可根據(jù)實(shí)際情況對(duì)隊(duì)列的結(jié)構(gòu)加以修改,如定義雙端隊(duì)列(兩頭均可插入/刪除)、輸入受限的雙端隊(duì)列(一側(cè)只允許刪除、另一側(cè)插入刪除均可)、輸出受限的雙端隊(duì)列等,3.5 離散事件模擬,3.15假設(shè)以靜態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧，既在一維數(shù)組的存儲(chǔ)空間存在著兩個(gè)棧，它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn)。試編寫實(shí)現(xiàn)這個(gè)雙向棧的三個(gè)操作：初始化IniStack(tws)、入棧Push(tws,i,x)、和出棧Pop(tws,i)的算法，其中i 為0或1，用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧，并討論按過程（正/誤狀態(tài)變量可設(shè)為變參）或函數(shù)設(shè)計(jì)這些操作算法各有什么優(yōu)缺點(diǎn)