莊朝暉-數據結構第三章棧和隊列_第1頁
莊朝暉-數據結構第三章棧和隊列_第2頁
莊朝暉-數據結構第三章棧和隊列_第3頁
莊朝暉-數據結構第三章棧和隊列_第4頁
莊朝暉-數據結構第三章棧和隊列_第5頁
已閱讀5頁,還剩38頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、 第三章 棧和隊列3.1 棧 3.1.1 抽象數據類型棧的定義 3.1.2 棧的表示和實現(xiàn)3.2 棧的應用舉例 3.2.1 數制轉換 3.2.2 括號匹配的檢驗 3.2.3 行編輯程序 3.2.4 迷宮求解 3.2.5 表達式求值3.3 棧與遞歸的實現(xiàn)3.4 隊列 3.4.1 抽象數據類型隊列的定義 3.4.2 鏈隊列隊列的鏈式表示和實現(xiàn) 3.4.3 循環(huán)隊列隊列的順序表示和實現(xiàn)3.5 離散事件模擬 3.1.1 棧3.1.1 棧的定義及基本運算 棧(Stack)是限制在表的一端進行插入和刪除運算的線性表,通常稱插入、刪除的這一端為棧頂(Top),另一端為棧底(Bottom)。當表中沒有元素時稱

2、為空棧。 假設棧S=(a1,a2,a3,an),則a1稱為棧底元素,an為棧頂元素。棧中元素按a1,a2,a3,an的次序進棧,退棧的第一個元素應為棧頂元素。換句話說,棧的修改是按后進先出的原則進行的。因此,棧稱為后進先出表(LIFO)。例、一疊書或一疊盤子。 棧的抽象數據類型的定義如下:P45 a n a n-1 a2 a1棧頂 棧底3.1.2 順序棧 由于棧是運算受限的線性表,因此線性表的存儲結構對棧也適應。 棧的順序存儲結構簡稱為順序棧,它是運算受限的線性表。因此,可用數組來實現(xiàn)順序棧。因為棧底位置是固定不變的,所以可以將棧底位置設置在數組的兩端的任何一個端點;棧頂位置是隨著進棧和退棧操

3、作而變化的,故需用一個整型變量top來表示 top用來指示當前棧頂的位置,通常稱top為棧頂指針。順序棧的類型定義如下: #define STACK_INIT_SIZE #define STACKINCREMENT typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; 設S是SqStack類型的指針變量。若棧底位置在向量的低端,即sbase是棧底元素,那么棧頂指針stop是正向增加的,即進棧時需將stop加1,退棧時需將stop 減1。stop=s-base表示空棧,當??諘r再做退棧運算也將產生溢出,簡稱

4、“下溢”。stop-s-base =stacksize表示棧滿。當棧滿時再做進棧運算必定產生空間溢出,簡稱“上溢”。1、初始化棧算法:1.構建棧 1.1 分配空間并檢查空間是否分配失敗,若失敗則返回錯誤 1.2 設置棧底和棧頂指針 1.3 設置棧大小2.算法結束2、取棧頂元素算法:1.取元素 1.1 判斷棧是否是空棧,若是空棧則返回錯誤 1.2 通過棧頂指針獲取棧頂元素2.算法結束3、入棧算法:1.初值 獲取入棧元素e2.入棧 2.1 判斷??臻g是否存在,若無空間則重新分配更大的空間,并調整棧底,棧頂指針以及棧大小。 2.2 元素e壓入棧中的棧頂位置 2.3 棧頂指針增加13.算法結束4、退棧

5、算法:1.退棧 1.1 判斷棧是否為空,為空則返回錯誤。 1.2 獲取棧頂元素e 1.3 棧頂指針減12.算法結束3.1.3 鏈棧 棧的鏈式存儲結構稱為鏈棧,它是運算受限的單鏈表,插入和刪除操作僅限制在表頭位置上進行。由于只能在鏈表頭部進行操作,故鏈表沒有必要像單鏈表那樣附加頭結點。棧頂指針就是鏈表的頭指針。 鏈棧的類型說明如下: typedef struct stacknode datatype data; struct stacknode *next; stacknode; typedef struct struct stacknode *top; linkstack; void init

6、stack(linkstack *p) ptop=null; int stackempty(linkstack *p) return ptop=null; void push(linkstack *p,datatype x) stacknode *q; q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=q;datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=q

7、data; ptop=qnext; free(q); return x; datatype stacktop(linkstack *p) if(stackempty(p) return ERROR; return ptopdata; 3.2 棧的應用舉例 由于棧結構具有的后進先出的固有特性,致使棧成為程序設計中常用的工具。以下是幾個棧應用的例子。 3.2.1 數制轉換 十進制n和其它d進制數的轉換是計算機實現(xiàn)計算的基本問題,其解決方法很多,其中一個簡單算法基于下列原理: n=(n div d)*d+n mod d ( 其中:div為整除運算,mod為求余運算) 例如 (1348)10=(250

8、4)8,其運算過程如下: n n div 8 n mod 8 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); 3.2.2 括號匹配的檢驗 假設表達式中充許括號嵌套,則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。例: ()() ()3.2.3 行編輯程序 在編輯程序中,設立一個輸入緩沖區(qū),用于接受用戶輸入的一行字符,然后逐行存入用戶數據區(qū)。允許

9、用戶輸入錯誤,并在發(fā)現(xiàn)有誤時可以及時更正。 行編輯程序算法如下: 3.2.4 迷宮求解 入口出口設定當前位置的初值為入口位置;do 若當前位置可通,則將當前位置插入棧頂;若該位置是出口位置,則結束;否則切換當前位置的東鄰方塊為新的當前位置;否則,若棧不空且棧頂位置尚有其他方向未經探索,則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊;若棧不空但棧頂位置的四周均不可通,則刪去棧頂位置;/從路徑中刪去該通道塊若棧不空,則重新測試新的棧頂位置,直至找到一個可通的相鄰塊出棧至???;while (棧不空);3.2.5 表達式求值例如:42*310/5算法3.4OperandType Eva

10、luateExpression()InitStack(OPTR); push(OPTR, #);InitStack(OPND); c=getchar();while (c!=# |GetTop(OPTR)!=#)if (! In(c, OP)Push(OPND, c);c=getchar();elseswitch(Precede(GetTop(OPTR), c) case : Pop(OPTR, theta); Pop(OPND, b);Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; return GetTop(OPND); *棧與遞

11、歸的實現(xiàn)主程序在調用子程序的時候,符合“后進先出”的特點,可以使用棧進行模擬。當父函數將控制轉交給子函數的時候,需要做以下三件事:1、將所有的實參傳遞給子函數的形參,還要傳遞返回地址。2、為子函數的局部變量分配空間3、將控制轉移到子函數的入口。當子函數返回父函數的時候,依次完成如下工作:保存計算結果、釋放空間、根據返回地址將控制轉交給父函數。例如P56圖3.6遞歸程序是一種特別的子函數調用,自己調用自己,但參數會越來越小,直到接近出口。因此,遞歸程序,可以實現(xiàn)非遞歸化:1、尾遞歸可以使用循環(huán)實現(xiàn)非遞歸化,如n!=n*(n-1)!2、其他遞歸可以使用棧來實現(xiàn)非遞歸化3.4 隊列3.4.1 抽象數

12、據類型隊列的定義 隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入,而在另一端進行刪除。允許刪除的一端稱為隊頭(front),允許插入的一端稱為隊尾(rear)。例如:排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(First In First Out)的線性表,簡稱FIFO表。當隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,an之后,a1是隊頭元素,an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,an ,也就是說隊列的修改是依先進先出的原則進行的。下圖是隊列的示意圖: a1a2an出隊入隊隊頭隊尾隊列的抽象數

13、據定義見書59雙端隊列3.4.2 循環(huán)隊列隊列的順序表示和實現(xiàn)隊列的順序存儲結構稱為順序隊列,順序隊列實際上是運算受限的順序表,和順序表一樣,順序隊列也是必須用一個向量空間來存放當前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的,因而要設兩個指針和分別指示隊頭和隊尾元素在隊列中的位置,它們的初始值地隊列初始化時均應置為。入隊時將新元素插入隊尾,然后將尾指針加。出隊時,刪去所指的元素,然后將頭指針加并返回被刪元素。由此可見,當頭尾指針相等時隊列為空。在非空隊列里,頭指針始終指向隊頭元素,而尾指針始終指向隊尾元素的下一位置。 0 1 2 3frontrearabcdfront rear (a)隊

14、列初始為空(b)a,b,c, d入隊 b cd front rear front rear (c) a出隊 (d) b,c,d出隊隊為空和棧類似,隊列中亦有上溢和下溢現(xiàn)象。此外,順序隊列中還存在“假上溢”現(xiàn)象。因為在入隊和出隊的操作中,頭尾指針只增加不減小,致使被刪除元素的空間永遠無法重新利用。因此,盡管隊列中實際的元素個數遠遠小于向量空間的規(guī)模,但也可能由于尾指針巳超出向量空間的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。為充分利用向量空間??朔鲜黾偕弦绗F(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán),并稱這種向量為循環(huán)向量,存儲在其中的隊列稱為循環(huán)隊列(Circular Queue)。在循環(huán)隊

15、列中進行出隊、入隊操作時,頭尾指針仍要加1,朝前移動。只不過當頭尾指針指向向量上界(QueueSize-1)時,其加1操作的結果是指向向量的下界0。這種循環(huán)意義下的加1操作可以描述為: if(i+1=QueueSize) i=0; else i+; 利用模運算可簡化為: i=(i+1)%QueueSize 顯然,因為循環(huán)隊列元素的空間可以被利用,除非向量空間真的被隊列元素全部占用,否則不會上溢。因此,除一些簡單的應用外,真正實用的順序隊列是循環(huán)隊列。 如圖所示:由于入隊時尾指針向前追趕頭指針,出隊時頭指針向前追趕尾指針,故隊空和隊滿時頭尾指針均相等。因此,我們無法通過front=rear來判斷

16、隊列“空”還是“滿”。 解決此問題的方法至少有三種: 其一是另設一個布爾變量以匹別隊列的空和滿;其二是少用一個元素的空間,約定入隊前,測試尾指針在循環(huán)意義下加1后是否等于頭指針,若相等則認為隊滿(注意:rear所指的單元始終為空);其三是使用一個計數器記錄隊列中元素的總數(實際上是隊列長度)。循環(huán)隊列的類型定義:#define MAXQSIZE 100typedef struct QElemType *base; int front; int rear;SqQueue;實現(xiàn)算法見P64-P653.4.3 鏈隊列 隊列的鏈式存儲結構簡稱為鏈隊列,它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作,為此再增加一個尾指針,指向鏈表的最后一個結點。于是,一個鏈隊列由一個頭指針唯一確定。

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論