數(shù)據(jù)結(jié)構(gòu)第3章-棧和隊(duì)列課件

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

2、，an為棧頂元素。棧中元素按a1，a2，a3，an的次序進(jìn)棧，退棧的第一個(gè)元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱為后進(jìn)先出（LIFO）的線性表。a1a2an入棧出棧棧頂棧底入棧出?；疖囌{(diào)度4棧的定義續(xù)假設(shè)棧S=(a1，a2，a3，an)，則a1稱棧的定義續(xù)棧的抽象數(shù)據(jù)類型定義 ADT Stack 數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,n,n0, 數(shù)據(jù)關(guān)系：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)：返回元素個(gè)數(shù)，即棧的長度。 GetTop(S,&e)：用e返回S的棧頂元素。 Push(&S,e)：插入元素e為新的棧頂元素。 Pop(&S,&e)：刪除S的棧頂元素，值給e。 StackTraverse(S,visit( )：遍歷棧。 ADT Stack5棧的定義續(xù)棧的抽象數(shù)據(jù)類型定義5棧的順序存儲(chǔ)順序棧的定義順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。棧的順序存儲(chǔ)結(jié)構(gòu)定義 #define STACK_INIT

4、_SIZE 100 / 存儲(chǔ)空間初始分配量 #define STACKINCREMENT 10 / 存儲(chǔ)空間分配增量 typedef struct SElemType *base; / 棧底指針 SElemType *top / 棧頂指針 int stacksize; / 當(dāng)前已分配的存儲(chǔ)容量 SqStack;6棧的順序存儲(chǔ)6稱base為棧底指針，在順序棧中，它始終指向棧底的位置，若base的值為NULL，則表明棧結(jié)構(gòu)不存在。稱top為棧頂指針，其初始值指向棧底，即top=base可作為棧空的標(biāo)記，每當(dāng)插入新的棧頂元素時(shí)，指針top增1；刪除棧頂元素時(shí)，指針top減1。因此，非空棧中的棧頂指針

5、始終在棧頂元素的下一個(gè)位置上。basetopbasetopAbasetopABCDbasetopABC7稱base為棧底指針，在順序棧中，它始終指向棧底的位置，若b棧的鏈?zhǔn)酱鎯?chǔ)若是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。將用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的棧稱作“鏈?！?。鏈棧通常用一個(gè)無頭結(jié)點(diǎn)的單鏈表表示。由于棧的插入刪除操作只能在一端進(jìn)行，而對(duì)于單鏈表來說，在首端插入刪除結(jié)點(diǎn)要比尾端相對(duì)地容易一些，所以，我們將單鏈表的首端作為棧頂端，即將單鏈表的頭指針作為棧頂指針。topdatanext8棧的鏈?zhǔn)酱鎯?chǔ)topdatanext83.2 棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換【例】十進(jìn)制數(shù)

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

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

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

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

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

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

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

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

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

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

16、指針指向頭結(jié)點(diǎn)。由此，空的鏈隊(duì)列的判別條件為頭指針和尾指針均指向頭結(jié)點(diǎn)。24鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)一個(gè)鏈隊(duì)列需要兩個(gè)指針才能唯一確鏈隊(duì)列續(xù)鏈隊(duì)列的操作即為單鏈表的插入和刪除操作的特殊情況，只是需要修改尾指針或頭指針。Q.frontQ.rear(a)空隊(duì)列AQ.frontQ.rear(b)元素A入隊(duì)Q.frontABQ.rear(c)元素B入隊(duì)ABABQ.frontQ.rear(d)元素A出隊(duì)25鏈隊(duì)列續(xù)鏈隊(duì)列的操作即為單鏈表的插入和刪除操作的特殊情況，鏈隊(duì)列續(xù)鏈隊(duì)列存儲(chǔ)結(jié)構(gòu)定義typedef struct QNode /鏈隊(duì)列結(jié)點(diǎn)的類型 QElemType data; struct QNo

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

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