數據結構第3章-棧和隊列課件

1、 第三章 棧和隊列1 第三章 棧和隊列1主要內容棧的概念、存儲結構及其基本操作棧的應用隊列的概念、存儲結構及其基本操作 2主要內容棧的概念、存儲結構及其基本操作23.1 棧棧的定義棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表的一端進行。通常將表中允許進行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂的當前位置是動態(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端被稱為棧底(Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔＃瑒h除操作稱為出?；蛲藯！?33.1 棧棧的定義3棧的定義續(xù)假設棧S=(a1，a2，a3，an)，則a1稱為棧底元素

2、，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進棧，退棧的第一個元素應為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為后進先出（LIFO）的線性表。a1a2an入棧出棧棧頂棧底入棧出?；疖囌{度4棧的定義續(xù)假設棧S=(a1，a2，a3，an)，則a1稱棧的定義續(xù)棧的抽象數據類型定義 ADT Stack 數據對象：D=ai|aiElemSet,i=1,2,n,n0, 數據關系：R1=ai-1,ai|ai-1,aiD,i=2,n， 約定an端為棧頂，a1端為棧底。 基本操作： InitStack(&S)：將S初始化為空棧。 DestroyStack(&S)：棧S被銷毀。

3、 ClearStack(&S)：將棧S置成空棧。 StackEmpty(S)：若空棧，則返回真，否則假。 StackLength(S)：返回元素個數，即棧的長度。 GetTop(S,&e)：用e返回S的棧頂元素。 Push(&S,e)：插入元素e為新的棧頂元素。 Pop(&S,&e)：刪除S的棧頂元素，值給e。 StackTraverse(S,visit( )：遍歷棧。 ADT Stack5棧的定義續(xù)棧的抽象數據類型定義5棧的順序存儲順序棧的定義順序棧是用順序存儲結構實現的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂的數據元素。棧的順序存儲結構定義 #define STACK_INIT

4、_SIZE 100 / 存儲空間初始分配量 #define STACKINCREMENT 10 / 存儲空間分配增量 typedef struct SElemType *base; / 棧底指針 SElemType *top / 棧頂指針 int stacksize; / 當前已分配的存儲容量 SqStack;6棧的順序存儲6稱base為棧底指針，在順序棧中，它始終指向棧底的位置，若base的值為NULL，則表明棧結構不存在。稱top為棧頂指針，其初始值指向棧底，即top=base可作為?？盏臉擞洠慨敳迦胄碌臈ｍ斣貢r，指針top增1；刪除棧頂元素時，指針top減1。因此，非空棧中的棧頂指針

5、始終在棧頂元素的下一個位置上。basetopbasetopAbasetopABCDbasetopABC7稱base為棧底指針，在順序棧中，它始終指向棧底的位置，若b棧的鏈式存儲若是棧中元素的數目變化范圍較大或不清楚棧元素的數目，就應該考慮使用鏈式存儲結構。將用鏈式存儲結構表示的棧稱作“鏈棧”。鏈棧通常用一個無頭結點的單鏈表表示。由于棧的插入刪除操作只能在一端進行，而對于單鏈表來說，在首端插入刪除結點要比尾端相對地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。topdatanext8棧的鏈式存儲topdatanext83.2 棧的應用舉例1.數制轉換【例】十進制數

6、轉換成二進制數 使用展轉相除法將一個十進制數值轉換成二進制數值。即用該十進制數值除以2，并保留其余數；重復此操作，直到該十進制數值為0為止。最后將所有的余數反向輸出就是所對應的二進制數值。例如：(692)10 = (1010110100)2 先把余數一味地入棧，完成后進行一邊出棧一邊輸出即可。93.2 棧的應用舉例1.數制轉換【例】十進制數轉換成二進制2 括號匹配檢查程序中經常用到括號：圓括號( )，中括號 和花括號 。正確地使用括號是要配對，其嵌套任意。正確格式如：( )、( )。不正確格式如：( )、( )?？梢允褂美ㄌ枟硗瓿衫ㄌ柶ヅ錂z查。102 括號匹配檢查103 行編輯程序一個簡單的

7、行編輯程序的功能是：接受用戶從終端輸入的程序或數據，并存入用戶的數據區(qū)。由于用戶在終端上進行輸入時，不能保證不出差錯，因此，若在編輯程序中，“每接受一個字符即存入用戶數據區(qū)”的做法顯然不是最恰當的。例如：當用戶發(fā)現剛剛鍵入的一個字符是錯的時，可以補進一個退格符“#”，以表示前一個字符無效；如果發(fā)現當前輸入的行內差錯較多或難以補救，則可以鍵入一個退行符“”，以表示當前行中的字符均無效。113 行編輯程序11行編輯程序續(xù)例如：假設從終端接收了如下兩行字符： whli#ilr#e(s#*s) outchaputchar(*s=#+); 則實際有效的是下列兩行： while(*s) putchar(*

8、s+);可設一個存放一行的棧，每當從終端接受了一個字符之后作如下判別：如果它既不是退格符也不是退行符，則將該字符壓入棧；如果是一個退格符，則從棧頂刪去一個字符；如果它是一個退行符，則將字符棧清空。一行結束，表示行編輯完成。12行編輯程序續(xù)例如：假設從終端接收了如下兩行字符：則實際有效4 迷宮求解迷宮求解通常用“窮舉求解”的方法。 從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為了保證在任何位置上都能沿原路退回，顯然需要一個后進先出棧來保存沿路的位置信息。 入口出口134 迷宮求解入口出口135 表達式求值表達式求值

9、是高級語言編譯中的一個基本問題，即“算符優(yōu)先法”，是棧的典型應用實例。 任何一個表達式都是由操作數(operand)、 運算符(operator)和界限符(delimiter)組成的。操作數既可以是常數， 也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符、關系運算符和邏輯運算符三類；基本界限符有左右括號和表達式結束符等。 145 表達式求值14表達式求值續(xù)假設操作數是整型常數，運算符只含加、減、乘、除等四種運算符，界限符有左右括號和表達式起始、結束符“”，引入表達式起始、結束符是為了方便。要對一個簡單的算術表達式求值，首先要了解算術四則運算的規(guī)則。 先乘除，后加減；從左算到右； 先

10、括號內，后括號外。1與2的優(yōu)先關系表/()#/(#=15表達式求值續(xù)假設操作數是整型常數，運算符只含加、減、乘、除步驟操作數棧操作符棧輸入串動作1#(7+15)*(23-28/4)#(,7,+,15分別進棧2#7 15#(+)*(23-28/4)#運算，7+15=223#22#()*(23-28/4)#(出棧，*進棧4#22#*(23-28/4)#(,23,-,28分別進棧5#22 23 28#*(-/4)#/和4分別進棧6#22 23 28 4#*(-/)#運算，28/4=77#22 23 7#*(-)#運算，23-7=168#22 16#*()#(出棧9#22 16#*#出棧，22*16=

11、35210#352#彈出結果352如求表達式值：（7+15）*（23-28/4）。16步驟操作數棧操作符棧輸入串動作1#(7+15)*(23-23.3 棧與遞歸的實現棧在程序設計中實現遞歸調用，即直接調用自己的函數，稱為遞歸函數。如階乘函數： 2階Fibonacci數列：Ackerman函數：173.3 棧與遞歸的實現棧在程序設計中實現遞歸調用，即直接調用例，n階漢諾塔問題。假設有3個分別命名為X、Y和Z的塔座，在X塔座上插有n個直徑各不相同、依小到大編號的圓盤。現要求將X塔座上的n個圓盤移到這塔座上并仍按同樣的順序排，圓盤移動時必須遵循以下規(guī)則： 1）每次只能移動一個圓盤； 2）圓盤可以插在

12、任一XYZ塔座上； 3）任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。3階漢諾塔18例，n階漢諾塔問題。假設有3個分別命名為X、Y和Z的塔座，在abcdefgh19abcdefgh19例，n階漢諾塔問題的C函數實現。 void hanoi(int n,char x,char y,char z) / 將x上編號為1n的圓盤借助y移到z if (n=1) move(x,1,z) / 將編號為1的圓盤從x到z else hanoi(n-1,x,z,y); / 將x上編號為1n-1的圓盤借助z移到y(tǒng) move(x,n,z); / 將編號為n的圓盤從x到z hanio(n-1,y,x,z); / 將

13、y上編號為1n-1的圓盤借助x移到z 20例，n階漢諾塔問題的C函數實現。203.4 隊列隊列的定義隊列 (Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進先出(Fist In Fist Out， 縮寫為FIFO)的特性。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端則稱為隊頭(front)。當隊列中沒有元素時稱為空隊列。 213.4 隊列隊列的定義21隊列的定義續(xù)假設隊列為q=(a1,a2,an)，那么a1就是隊頭元素，an則是隊尾元素。隊列中的元素是按照a1,a2,an的順序進入的， 退出隊列也必須按照同樣的次序依次出隊，也

14、就是說，只有在a1,a2,an-1都離開隊列之后，an才能退出隊列。入隊列出隊列a1 a2 an隊尾隊頭22隊列的定義續(xù)假設隊列為q=(a1,a2,an)，那么a隊列的定義續(xù)隊列的抽象數據類型定義 ADT Queue 數據對象：D=ai|aiElemSet,i=1,2,n,n0, 數據關系：R1=ai-1,ai|ai-1,aiD,i=2,n， 約定其中a1端為隊頭，an端為隊尾。 基本操作： InitQueue(&Q)：將Q初始化為空隊列。 DestroyQueue(&Q)：隊列Q被銷毀。 ClearQueue(&Q)：將Q清為空隊列。 QueueEmpty(Q)：若Q為空隊列，則返回真，否則

15、返回假。 QueueLength(Q)：返回Q的元素個數，即隊列的長度。 GetHead(Q,&e)：用e返回Q的隊頭元素。 EnQueue(&Q,e)：插入元素e為Q的新的隊尾元素。 DeQueue(&Q,&e)：刪除Q的隊頭元素，并用e返回其值。 QueueTraverse(Q,visit( ):遍歷隊列。 ADT Queue23隊列的定義續(xù)隊列的抽象數據類型定義23鏈隊列隊列的鏈式表示和實現鏈隊列的定義用鏈表表示的隊列簡稱為鏈隊列。一個鏈隊列需要兩個指針才能唯一確定，它們分別指示隊頭和隊尾（分別稱為頭指針和尾指針）。與線性表的單鏈表一樣，為了操作方便起見， 給鏈隊列添加一個頭結點，并令頭

16、指針指向頭結點。由此，空的鏈隊列的判別條件為頭指針和尾指針均指向頭結點。24鏈隊列隊列的鏈式表示和實現一個鏈隊列需要兩個指針才能唯一確鏈隊列續(xù)鏈隊列的操作即為單鏈表的插入和刪除操作的特殊情況，只是需要修改尾指針或頭指針。Q.frontQ.rear(a)空隊列AQ.frontQ.rear(b)元素A入隊Q.frontABQ.rear(c)元素B入隊ABABQ.frontQ.rear(d)元素A出隊25鏈隊列續(xù)鏈隊列的操作即為單鏈表的插入和刪除操作的特殊情況，鏈隊列續(xù)鏈隊列存儲結構定義typedef struct QNode /鏈隊列結點的類型 QElemType data; struct QNo

17、de *next;QNode; *QueuePtr;typedef struct / 鏈隊列指針類型 QueuePtr front; / 隊頭指針 QueuePtr rear; / 隊尾指針 LinkQueue;26鏈隊列續(xù)鏈隊列存儲結構定義typedef struct Q循環(huán)隊列隊列的順序表示和實現隊列的順序存儲結構隊列的順序存儲結構和順序棧類似，在隊列的順序存儲結構中，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，還需要設置頭尾兩個指針front和rear，分別指示隊列頭元素及隊尾元素的位置。約定：初始化建立空隊列時，令front=rear=0，每當插入新的隊尾元素時，“

18、尾指針增1”；每當刪除隊頭元素時，“頭指針增1”。在非空隊列中，頭指針始終指向隊列頭元素，尾指針始終指向隊列尾元素的下一個位置。27循環(huán)隊列隊列的順序表示和實現27 Q.front 540123Q.rear(b)J1、J2、J3相繼入隊J1J2J3 Q.front 540123Q.rear(a)空隊列 Q.front 540123Q.rear(c)J1、J2相繼出隊J3 Q.front 540123Q.rear(d)J4、J5、J6相繼入隊后，J3、J4相繼出隊J5J628 Q.front 540123Q.rear(b)J1、J2循環(huán)隊列續(xù)因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際的元素個數遠遠小于向量空間的規(guī)模，但也可能由于尾指針巳超出向量空間的上界而不能做入隊操作。該現象稱為假溢出。解決辦法：將順序隊列臆造為一個環(huán)狀的空間，稱之為循環(huán)隊列。在C語言中，不能用動態(tài)分配