第三章棧和隊列(無答案).ppt

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

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

3、(SqStack /復雜度O(1),Status Push(SqStack /Push ,復雜度O(1),Status Pop(SqStack /復雜度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 /除遍歷操作外時間復雜度均O(1),引用型操作,/可據(jù)需要適當增加新操作 Status SetTopE

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

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

6、在兩種結構下的實現(xiàn) 棧的應用- Last In First Out后進先出/總是訪問最近插入的一個/按插入順序倒著訪問,#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、括號匹配檢驗,正確：() 錯誤：() ( ) (),Status match( ) initstack(S);hasErr=0; while(c=getchar()!=n ,編譯過程中尚需報告出錯行數(shù)、忽略注釋/字符串和字符常量等,思路:依次掃描各符號,每遇一結束符都找最近的開始符來匹配,不匹配或未找到則報錯.最后應左右括號完全匹配畢 初始化一個空棧 逐個掃描符號 如果當前符號是開始符則入棧 如果是結束符號則分三種情況 如果?？談t報告出錯 /右多 否則,出棧,若彈出元素與當前元素不匹配則報告出錯/不匹配 否則無動作

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

9、ck(S); ch=getchar(); while(ch!=EOF)/全文未結束 while(ch!=n /行尾非EOF ,4、迷宮求解,令curPos指向入口,curStep為1,重復while(TRUE) 若當前位置通,則將其納入路徑(棧).是出口停,非出口重置curPos為右鄰，開始下次循環(huán) 若當前位置不通,看上一步，若其四周均已訪問過，則將其從路徑中刪除，如此重復直至找到一個曾經(jīng)訪問之位置，其四個方向至少有一個未曾訪問過；此時重置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,重復while(TRUE) 若當前位置通,則將其納入路徑(棧).是出口停,非出口重置curPos為右鄰，開始下次循環(huán) 若當前位置不通,看上一步，若

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

12、棧頂運算符出棧,兩操作數(shù)出棧,進行運算,所得結果入數(shù)棧, 開始下次循環(huán)(不掃描新符號，重新比較剛才掃描到的運算符與新棧頂運算符) 。如此重復直到棧頂運算符與當前符號均為(#),5、表達式求值算符優(yōu)先法,-,*,#,#,#,設操作符棧和操作數(shù)棧,運算符棧最初壓入#,逐個掃描符號:遇操作數(shù)則直接入棧,繼續(xù)讀下一字符；遇運算符則與棧頂運算符比較優(yōu)先級,當前運算符優(yōu)先級高(前面的運算還不應執(zhí)行)則當前運算符入棧,讀下一符號;否則棧頂運算符出棧,兩操作數(shù)出棧,進行運算,所得結果入數(shù)棧,不掃描新符號開始下次循環(huán)。(重新比較剛才掃描到的運算符與新棧頂運算符)如此重復直到棧頂運算符與當前符號均為(#),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)/比較棧頂運算符與c優(yōu)先級 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）所示鐵道進行車廂調度（注意：兩側鐵道均為單向行駛道,棧）,則請回答：,（1）如果進站的車廂序列為123，則可能得到的出站車廂序列是什么？,（2）如果進站車廂序列為123456，能否得到435612和135426的出站序列，并請說明為什么不能得到或者如何得到（既寫出以S表示進棧和已X表示出棧的棧操作序列 ）。,3.19表達式已存入字符串中，檢查括號匹配,3.3 棧與遞歸,專題課件,專題課件,1、 相關概念和類型定義 概念: 隊列類似線性表和棧,也是定義在線性結構上的ADT,與線性表和棧的區(qū)別在于，元素的插入和刪除

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

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

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

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

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

20、) /從隊頭元素到隊尾元素依次執(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),用隊列結構表示日常生活中的排隊，用入隊和出隊表示排到隊尾和服務完畢撤對，如銀行業(yè)務模擬.注意課程設計選題。 可根據(jù)實際情況對隊列的結構加以修改,如定義雙端隊列(兩頭均可插入/刪除)、輸入受限的雙端隊列(一側只允許刪除、另一側插入刪除均可)、輸出受限的雙端隊列等,3.5 離散事件模擬,3.15假設以靜態(tài)分配的順序存儲結構實現(xiàn)一個雙向棧，既在一維數(shù)組的存儲空間存在著兩個棧，它們的棧底分別設在數(shù)組的兩個端點。試編寫實現(xiàn)這個雙向棧的三個操作：初始化IniStack(tws)、入棧Push(tws,i,x)、和出棧Pop(tws,i)的算法，其中i 為0或1，用以分別指示設在數(shù)組兩端的兩個棧，并討論按過程（正/誤狀態(tài)變量可設為變參）或函數(shù)設計這些操作算法各有什么優(yōu)缺點