第三章棧與隊(duì)列和

1、13.1 棧（棧（Stack） 第三章第三章 棧和隊(duì)列棧和隊(duì)列 1. 1. 定義定義2. 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 3. 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)4. 4. 運(yùn)算規(guī)則運(yùn)算規(guī)則 5. 5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式23.2 隊(duì)列（隊(duì)列（Queue） 第三章第三章 棧和隊(duì)列棧和隊(duì)列1. 1. 定義定義2. 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 3. 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)4. 4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容4（1 1）定義）定義3.1 3.1 棧棧與線性表相同，仍為一對(duì)一與線性表相同，仍為一對(duì)一( 1:1)( 1:1)關(guān)系。關(guān)系。用用或或存儲(chǔ)均可，但以順序棧更常見存儲(chǔ)均

2、可，但以順序棧更常見（3 3）存儲(chǔ)結(jié)構(gòu)）存儲(chǔ)結(jié)構(gòu)（2 2）邏輯結(jié)構(gòu)）邏輯結(jié)構(gòu)限定只能在表的限定只能在表的進(jìn)行插入和刪除運(yùn)算的進(jìn)行插入和刪除運(yùn)算的線性表。線性表。即棧頂即棧頂53.1 3.1 棧棧只能在只能在運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照（LIFOLIFO）或）或（FILOFILO）的原則。）的原則。關(guān)鍵是編寫關(guān)鍵是編寫和和函數(shù)，具體實(shí)現(xiàn)依順函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。（4 4）運(yùn)算規(guī)則）運(yùn)算規(guī)則（5 5）實(shí)現(xiàn)方式）實(shí)現(xiàn)方式 （6 6）基本操作有：）基本操作有：建棧、判斷棧滿或棧空、入棧、建棧、判斷棧滿或棧空、入棧、 出棧、讀棧

3、頂元素值，等等。出棧、讀棧頂元素值，等等。6 是僅在是僅在表尾表尾進(jìn)行插入、刪除操作的線性表。進(jìn)行插入、刪除操作的線性表。表尾表尾(即即 an 端端)稱為稱為棧頂棧頂 /top ; 表頭表頭(即即 a1 端端)稱為稱為棧底棧底/base例如：例如： 棧棧 = (a1 , a2 , a3 , .,an-1 , an )插入元素到棧頂?shù)牟迦朐氐綏ｍ數(shù)牟僮?，稱為操作，稱為入棧入棧。從棧頂刪除最后一從棧頂刪除最后一個(gè)元素的操作，稱個(gè)元素的操作，稱為為出棧出棧。a an n稱為棧頂元素稱為棧頂元素a a1 1稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能在表的一端（棧頂）進(jìn)行！的一端（棧

4、頂）進(jìn)行！1 1、棧是一種特殊的線性表、棧是一種特殊的線性表7Q1Q1：堆棧是什么？它與一般線性表有什么不同？：堆棧是什么？它與一般線性表有什么不同？ 堆棧是堆棧是一種特殊的線性表一種特殊的線性表，它只能在表的一端，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。（即棧頂）進(jìn)行插入和刪除運(yùn)算。 與一般線性表的區(qū)別：僅在于與一般線性表的區(qū)別：僅在于不同。不同。3.1 3.1 棧棧8Q1Q1：堆棧是什么？它與一般線性表有什么不同？：堆棧是什么？它與一般線性表有什么不同？邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：1:1 1:1 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 1:1 1:1 存儲(chǔ)結(jié)構(gòu)：順序表、鏈表存儲(chǔ)結(jié)構(gòu)：順序表、鏈表 存儲(chǔ)結(jié)構(gòu)：順

5、序棧、鏈棧存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：運(yùn)算規(guī)則： 運(yùn)算規(guī)則：運(yùn)算規(guī)則：(LIFO)(LIFO)“進(jìn)進(jìn)”插入插入= =壓入壓入=PUSH=PUSH（a an+1n+1) )“出出”刪除刪除= =彈出彈出=POP(a=POP(an n) )3.1 3.1 棧棧9 a1 a2 an順序棧順序棧S S a ai iQ2Q2：順序表和順序棧的操作有何區(qū)別？：順序表和順序棧的操作有何區(qū)別？表頭表頭表尾表尾低地址低地址高地址高地址寫入：寫入：Si= ai讀出：讀出： e= Si壓入壓入(S+=an+1彈出彈出( -低地址低地址高地址高地址Si a1 a2 ai an 順序表順序表S an+1以線性表以線

6、性表 S= (a1 , a2 , . , an-1 , an )為例為例棧底棧底棧頂棧頂前提：一定要前提：一定要棧頂指針棧頂指針棧頂棧頂10棧不存在的條件：棧不存在的條件： base=NULL;base=NULL;棧為空棧為空 的條件的條件 ： base=top; base=top;棧滿的條件棧滿的條件 ： top-base=top-base=stacksizestacksize; ; a1 a2 an順序棧順序棧S S ai低地址低地址高地址高地址棧底棧底棧頂棧頂Q2Q2：順序表和順序棧的操作有何區(qū)別？：順序表和順序棧的操作有何區(qū)別？3.1 3.1 棧棧11若入棧動(dòng)作使地址向高端增長(zhǎng)，稱為若

7、入棧動(dòng)作使地址向高端增長(zhǎng)，稱為“向上生成向上生成”的棧；的棧；若入棧動(dòng)作使地址向低端增長(zhǎng)，稱為若入棧動(dòng)作使地址向低端增長(zhǎng)，稱為“向下生成向下生成”的棧；的棧； 對(duì)于向上生成的堆棧對(duì)于向上生成的堆棧: :入?？谠E：堆棧指針入?？谠E：堆棧指針top “top “先壓后加先壓后加” ” : Stop+=a: Stop+=an+1n+1出棧口訣：堆棧指針出?？谠E：堆棧指針top “top “先減后彈先減后彈” ” : e=S-top: e=S-topQ3Q3：什么叫：什么叫“向上生成向上生成”的棧？的棧？ “ “向下生成向下生成”又是何意？又是何意？3.1 3.1 棧棧12Q4Q4：為什么要設(shè)計(jì)堆棧？

8、它有什么獨(dú)特用途？：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？1. 1.調(diào)用函數(shù)或子程序非它莫屬；調(diào)用函數(shù)或子程序非它莫屬；2. 2.遞歸遞歸運(yùn)算的有力工具；運(yùn)算的有力工具；3. 3.用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；4. 4.簡(jiǎn)化了程序設(shè)計(jì)的問題。簡(jiǎn)化了程序設(shè)計(jì)的問題。3.1 3.1 棧棧13void test(int &sum) int x; scanf(x);if(x=0) sum=0;else; sum+=x; printf(sum); 斷點(diǎn)斷點(diǎn)地址地址入棧入棧例例1 1 閱讀下列遞歸過程，說明其功能。閱讀下列遞歸過程，說明其功能。輸入輸入x10輸入輸入x50輸入輸入x

9、2輸入輸入x3輸入輸入x4輸出輸出sum0輸出輸出sum0+x4輸出輸出sumx4+x3輸出輸出sum x4+x3 +x2輸出輸出sum x4+x3 +x2+x1注意：最先輸入的注意：最先輸入的數(shù)據(jù)數(shù)據(jù) x x1 1 最后才被累最后才被累加加程序功能：對(duì)鍵盤輸入數(shù)據(jù)求和，直到輸入程序功能：對(duì)鍵盤輸入數(shù)據(jù)求和，直到輸入0 0結(jié)束結(jié)束堆棧舉例堆棧舉例14答：答：可以通過窮舉所有可能性來求解：可以通過窮舉所有可能性來求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132

10、132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合計(jì)有合計(jì)有5 5種可能性。種可能性。例例2 2 一個(gè)棧的輸入序列為一個(gè)棧的輸入序列為1,2,31,2,3，若在入棧的過程中，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？允許出棧，則可能得到的出棧序列是什么？15例例3 3：一個(gè)棧的輸入序列是一個(gè)棧的輸入序列是1234512345，若在入棧的過程中允許，若在入棧的過程中允許出

11、棧出棧，則棧的輸出序列則棧的輸出序列4351243512可能實(shí)現(xiàn)嗎？可能實(shí)現(xiàn)嗎？1234512345的輸出呢？的輸出呢？答：答：4351243512不可能實(shí)現(xiàn)，主要是其中的不可能實(shí)現(xiàn)，主要是其中的1212順序不能實(shí)現(xiàn)；順序不能實(shí)現(xiàn)；1234512345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。 思考：有無通用的判別原則？思考：有無通用的判別原則？3.1 3.1 棧棧16例例4：設(shè)依次進(jìn)入一個(gè)棧的元素序列為：設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可則可得到出棧的元素序列是：得到出棧的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，

12、a ）a，c，d，bA A）、）、D D）可以，）可以， B B）、）、C C）不行。）不行。討論：有無通用的判別原則？討論：有無通用的判別原則？有！若輸入序列是有！若輸入序列是 ,P,Pi iPPj jPPk k(ijk,(ijdata=e; p-link=st; st=p; Status Pop( ) if(st=NULL)下溢下溢elsee=st-data;p=st;st=st-link; free(p); return(e); 插入插入表頭表頭從表頭從表頭刪除刪除(2) (2) 入、出棧操作入、出棧操作由此可以看出：一個(gè)鏈棧由其由此可以看出：一個(gè)鏈棧由其棧頂指針唯一指定棧頂指針唯一指定

13、 設(shè)設(shè) 指向棧頂元素，則指向棧頂元素，則 = NULL = NULL 表示?？毡硎緱？?41) 1) 鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；鏈棧不必設(shè)頭結(jié)點(diǎn)，因?yàn)闂ｍ敚ū眍^）操作頻繁；2) 2) 鏈棧一般不會(huì)出現(xiàn)棧滿情況，除非沒有空間導(dǎo)致鏈棧一般不會(huì)出現(xiàn)棧滿情況，除非沒有空間導(dǎo)致mallocmalloc分配失敗。分配失敗。3) 3) 鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。改指針即可完成。4) 4) 采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共享空間；當(dāng)采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，

14、且存在多個(gè)棧的情況下，鏈棧棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧是棧的首選存儲(chǔ)方式。是棧的首選存儲(chǔ)方式。幾點(diǎn)說明幾點(diǎn)說明: :25例例1 1： 數(shù)制轉(zhuǎn)換（十轉(zhuǎn)數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N N） 見教材見教材 設(shè)計(jì)思路：用棧暫存低位值設(shè)計(jì)思路：用棧暫存低位值例例2 2：括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)見教材見教材 設(shè)計(jì)思路：用棧暫存左括號(hào)設(shè)計(jì)思路：用棧暫存左括號(hào)例例3 3 ：表達(dá)式求值表達(dá)式求值 -見教材見教材 設(shè)計(jì)思路：用棧暫存運(yùn)算符設(shè)計(jì)思路：用棧暫存運(yùn)算符例例4 4：漢諾（漢諾（HanoiHanoi）塔）塔-見教材見教材 設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用4 4、棧的應(yīng)用舉例、棧

15、的應(yīng)用舉例26例例3 3 表達(dá)式求值表達(dá)式求值 ( ( 這是棧應(yīng)用的典型例子這是棧應(yīng)用的典型例子) ) 這里，表達(dá)式求值的算法是這里，表達(dá)式求值的算法是 “ “算符優(yōu)先法算符優(yōu)先法”。例如：編寫算法，用棧實(shí)現(xiàn)表達(dá)式例如：編寫算法，用棧實(shí)現(xiàn)表達(dá)式3 3* *（7 2 7 2 ）求值。求值。一個(gè)算術(shù)表達(dá)式是由一個(gè)算術(shù)表達(dá)式是由操作數(shù)（操作數(shù)（x x，y y，zz）和）和 算符（算符（* * ，/ /， + + ，- -，（，），（，），# # ）組成）組成. .表達(dá)式的表達(dá)式的起止符號(hào)起止符號(hào)棧的應(yīng)用舉例棧的應(yīng)用舉例27例例3 3 表達(dá)式求值表達(dá)式求值 ( ( 這是棧應(yīng)用的典型例子這是棧應(yīng)用的典型

16、例子) )(1)(1) 表達(dá)式求值必須滿足算術(shù)四則運(yùn)算規(guī)則表達(dá)式求值必須滿足算術(shù)四則運(yùn)算規(guī)則： a. a. 從左算到右從左算到右 b. b. 先乘除，后加減先乘除，后加減 c. c. 先括號(hào)內(nèi)，后括號(hào)外先括號(hào)內(nèi)，后括號(hào)外棧的應(yīng)用舉例棧的應(yīng)用舉例28例例3 3 表達(dá)式求值表達(dá)式求值 ( ( 這是棧應(yīng)用的典型例子這是棧應(yīng)用的典型例子) )教材表教材表3.13.1給出了算符之間的優(yōu)先級(jí)給出了算符之間的優(yōu)先級(jí)專為計(jì)算機(jī)處理而設(shè)計(jì)的表專為計(jì)算機(jī)處理而設(shè)計(jì)的表! !棧的應(yīng)用舉例棧的應(yīng)用舉例為了實(shí)現(xiàn)算符優(yōu)先算法，可以設(shè)定兩個(gè)工作棧，為了實(shí)現(xiàn)算符優(yōu)先算法，可以設(shè)定兩個(gè)工作棧，存放操作數(shù)或運(yùn)算結(jié)果，存放操作數(shù)或

17、運(yùn)算結(jié)果， 存放運(yùn)算存放運(yùn)算符號(hào)。符號(hào)。29(2) (2) 算法思想算法思想1 1）首先置操作數(shù)棧）首先置操作數(shù)棧OPNDOPND為空棧，表達(dá)式的起始符為空棧，表達(dá)式的起始符# #為為運(yùn)算符棧運(yùn)算符棧OPTROPTR的棧底元素的棧底元素2 2）依次讀入表達(dá)式中的每個(gè)字符，）依次讀入表達(dá)式中的每個(gè)字符，若運(yùn)算符是若運(yùn)算符是#或棧頂是或棧頂是#，結(jié)束計(jì)算，返回，結(jié)束計(jì)算，返回OPNDOPND棧頂值。棧頂值。 if if（是操作數(shù)）（是操作數(shù)） 則則PUSHPUSH（ OPNDOPND，操作數(shù)），操作數(shù)）；棧的應(yīng)用舉例棧的應(yīng)用舉例30(2) (2) 算法思想算法思想if if（是運(yùn)算符）（是運(yùn)算符）

18、 則與則與OPTROPTR棧頂元素進(jìn)行比較，按優(yōu)先級(jí)棧頂元素進(jìn)行比較，按優(yōu)先級(jí)( (規(guī)定規(guī)定詳見表詳見表3.13.1）進(jìn)行操作；）進(jìn)行操作； if if 棧頂元素棧頂元素 運(yùn)算符運(yùn)算符，則退棧、按棧頂計(jì)算，將結(jié)果壓入，則退棧、按棧頂計(jì)算，將結(jié)果壓入OPNDOPND棧。棧。且該未入棧的運(yùn)算符要保留，繼續(xù)與下一個(gè)棧頂元素比較！且該未入棧的運(yùn)算符要保留，繼續(xù)與下一個(gè)棧頂元素比較！棧的應(yīng)用舉例棧的應(yīng)用舉例313 3）直到整個(gè)表達(dá)式求值完畢（當(dāng)前讀入的運(yùn)算）直到整個(gè)表達(dá)式求值完畢（當(dāng)前讀入的運(yùn)算符和符和棧的棧頂元素均為棧的棧頂元素均為 ） 棧的應(yīng)用舉例棧的應(yīng)用舉例32問：?jiǎn)枺航滩谋斫滩谋?.13.1中，

19、中， 1 1和和 2 2哪個(gè)對(duì)應(yīng)棧頂元素，哪個(gè)哪個(gè)對(duì)應(yīng)棧頂元素，哪個(gè)對(duì)應(yīng)鍵盤輸入值？對(duì)應(yīng)鍵盤輸入值？答：答：根據(jù)根據(jù)Precede()Precede()函數(shù)可知，函數(shù)可知， 1 1對(duì)應(yīng)棧頂元素對(duì)應(yīng)棧頂元素棧的應(yīng)用舉例棧的應(yīng)用舉例33v 由表由表3.13.1可看出，右括號(hào)可看出，右括號(hào) ) ) 和井號(hào)和井號(hào) # # 作為作為 2 2時(shí)時(shí)級(jí)別最低；級(jí)別最低；v 由由c c 規(guī)則規(guī)則得出：得出： * * ，/ /， + + ，- -為為 1 1時(shí)的優(yōu)先權(quán)低于時(shí)的優(yōu)先權(quán)低于，高于，高于v 由由a a規(guī)則規(guī)則得出：得出：= 表明括號(hào)內(nèi)的運(yùn)算已表明括號(hào)內(nèi)的運(yùn)算已完成；完成； = = 表明表達(dá)式求值完畢。表

20、明表達(dá)式求值完畢。附：附：棧的應(yīng)用舉例棧的應(yīng)用舉例34表達(dá)式求值過程的描述：表達(dá)式求值過程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#,*3(7-2)#Push(optr,()#,*,(37-2)#Push(opnd,7)#,*,(3,7-2)#Push(optr,-)#,*,(,3,72)#Push(opnd,2)#,*,(,3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3*（7 2 ）35Status

21、 EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#); =getchar(); while(c!=#)&(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c); c=getchar(); else switch(precede(GetTop(OPTR) , c) case : Pop(OPTR ,theta); Pop(OPND,b);a=Pop();thetabreak; /switch /while result=Ge

22、tTop(OPND);/EvaluateExpression C是操作是操作符嗎？符嗎？運(yùn)算符與棧頂比運(yùn)算符與棧頂比較并查較并查3.13.1表表程序清單程序清單遞歸算法的設(shè)計(jì)步驟遞歸算法的設(shè)計(jì)步驟第一步驟（遞歸步驟）：第一步驟（遞歸步驟）：將規(guī)模較大的原問題分解為一個(gè)或多將規(guī)模較大的原問題分解為一個(gè)或多個(gè)規(guī)模更小、但具有類似于原問題特性的子問題。即較大個(gè)規(guī)模更小、但具有類似于原問題特性的子問題。即較大的問題遞歸地用較小的子問題來描述，解原問題的方法同的問題遞歸地用較小的子問題來描述，解原問題的方法同樣可用來解這些子問題。樣可用來解這些子問題。第二步驟：第二步驟：確定一個(gè)或多個(gè)無須分解、可直接求

23、解的最小子問確定一個(gè)或多個(gè)無須分解、可直接求解的最小子問題（稱為題（稱為遞歸的終止條件遞歸的終止條件）。）?！纠糠秦?fù)整數(shù)【例】非負(fù)整數(shù)n的階乘可遞歸定義為：的階乘可遞歸定義為：36 37傳說在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫傳說在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫BrahmaBrahma的寺廟里，有三個(gè)柱子，其中的寺廟里，有三個(gè)柱子，其中一柱上有一柱上有6464個(gè)盤子從小到大依次疊放，僧侶的工作是將這個(gè)盤子從小到大依次疊放，僧侶的工作是將這6464個(gè)盤個(gè)盤子從一根柱子移到另一個(gè)柱子上。子從一根柱子移到另一個(gè)柱子上。x y zx y znn 1移動(dòng)時(shí)的規(guī)則：移動(dòng)時(shí)的規(guī)則： v 每次只能移動(dòng)一個(gè)盤子；每次只能移動(dòng)一個(gè)盤子；v

24、 只能小盤子在大盤子上面；只能小盤子在大盤子上面；v 可以使用任一柱子。可以使用任一柱子。當(dāng)工作做完之后，就標(biāo)志著世界末日到來。當(dāng)工作做完之后，就標(biāo)志著世界末日到來。例例4 4 漢諾（漢諾（ HanoiHanoi）塔）塔38分析：分析： 設(shè)三根柱子分別為設(shè)三根柱子分別為 x, y, z , x, y, z , 盤子在盤子在 x x 柱上，要移到柱上，要移到 z z 柱上。柱上。1 1、當(dāng)、當(dāng) n=1 n=1 時(shí)，盤子直接從時(shí)，盤子直接從 x x 柱移到柱移到 z z 柱上；柱上；2 2、當(dāng)、當(dāng) n1n1 時(shí)時(shí), , 則則: : 設(shè)法將前設(shè)法將前 n 1 n 1 個(gè)盤子個(gè)盤子 從從 x x 移到

25、移到 y y 柱上柱上（借助（借助z z），），則則 盤子盤子 n n 就能從就能從 x x 移到移到 z z 柱上；柱上； 再設(shè)法把再設(shè)法把n 1 n 1 個(gè)盤子個(gè)盤子 從從 y y 移到移到 z z 柱上柱上( (這又是一個(gè)與原來這又是一個(gè)與原來相同的問題，只是規(guī)模少了）相同的問題，只是規(guī)模少了） 。 x y z x y znn 1例例4 4 漢諾（漢諾（ HanoiHanoi）塔）塔39Void Hanoi ( int n, char x, char y, char z ) /將將n個(gè)編號(hào)從上到下為個(gè)編號(hào)從上到下為1n的盤子從的盤子從x柱，借助柱，借助y柱移到柱移到z柱柱 if ( n

26、= = 1 ) move ( x , 1 , z ) ; /將編號(hào)為將編號(hào)為1的盤子從的盤子從x柱移到柱移到z柱柱 else /將將n-1個(gè)編號(hào)從上到下為個(gè)編號(hào)從上到下為1n-1的盤子從的盤子從x柱，借助柱，借助y柱柱移到移到z柱柱 Hanoi ( n-1 , x , z , y ) ; move ( x , n, z) ; /將編號(hào)為將編號(hào)為n的盤子從的盤子從x柱移到柱移到z柱柱 /將將n-1個(gè)編號(hào)從上到下為個(gè)編號(hào)從上到下為1n-1的盤子從的盤子從y柱，借助柱，借助x柱移到柱移到z柱柱 /Hanoi程序設(shè)計(jì)如下程序設(shè)計(jì)如下誰能畫出誰能畫出HanoiHanoi塔的塔的遞歸函數(shù)運(yùn)行示意圖？遞歸函

27、數(shù)運(yùn)行示意圖？棧在遞歸算法的內(nèi)部實(shí)現(xiàn)中所起的作用棧在遞歸算法的內(nèi)部實(shí)現(xiàn)中所起的作用調(diào)用函數(shù)時(shí)：系統(tǒng)將會(huì)為調(diào)用者構(gòu)造一個(gè)由調(diào)用函數(shù)時(shí)：系統(tǒng)將會(huì)為調(diào)用者構(gòu)造一個(gè)由返回地返回地址、參數(shù)表（實(shí)參）址、參數(shù)表（實(shí)參）和和中間變量中間變量組成的活動(dòng)記錄，并組成的活動(dòng)記錄，并將其壓入到由系統(tǒng)提供的運(yùn)行時(shí)刻棧的棧頂，然后將將其壓入到由系統(tǒng)提供的運(yùn)行時(shí)刻棧的棧頂，然后將程序的控制權(quán)轉(zhuǎn)移到被調(diào)函數(shù)。若被調(diào)函數(shù)有局部變程序的控制權(quán)轉(zhuǎn)移到被調(diào)函數(shù)。若被調(diào)函數(shù)有局部變量，則在運(yùn)行時(shí)刻棧的棧頂也要為其分配相應(yīng)的空間量，則在運(yùn)行時(shí)刻棧的棧頂也要為其分配相應(yīng)的空間。因此，活動(dòng)記錄和這些局部變量形成了一個(gè)可供被。因此，活動(dòng)記錄

28、和這些局部變量形成了一個(gè)可供被調(diào)函數(shù)使用的活動(dòng)結(jié)構(gòu)。調(diào)函數(shù)使用的活動(dòng)結(jié)構(gòu)。403.1 3.1 棧棧棧在遞歸算法的內(nèi)部實(shí)現(xiàn)中所起的作用棧在遞歸算法的內(nèi)部實(shí)現(xiàn)中所起的作用注意：注意： 參數(shù)表的內(nèi)容為實(shí)參；返回地址是函數(shù)調(diào)用語句參數(shù)表的內(nèi)容為實(shí)參；返回地址是函數(shù)調(diào)用語句的下一指令的位置。的下一指令的位置。被調(diào)函數(shù)執(zhí)行完畢時(shí)：系統(tǒng)將運(yùn)行時(shí)刻棧棧頂?shù)幕畋徽{(diào)函數(shù)執(zhí)行完畢時(shí)：系統(tǒng)將運(yùn)行時(shí)刻棧棧頂?shù)幕顒?dòng)結(jié)構(gòu)退棧，并根據(jù)退棧的活動(dòng)結(jié)構(gòu)中所保存的返動(dòng)結(jié)構(gòu)退棧，并根據(jù)退棧的活動(dòng)結(jié)構(gòu)中所保存的返回地址將程序的控制權(quán)轉(zhuǎn)移給調(diào)用者繼續(xù)執(zhí)行?；氐刂穼⒊绦虻目刂茩?quán)轉(zhuǎn)移給調(diào)用者繼續(xù)執(zhí)行。413.1 3.1 棧棧遞歸算法的執(zhí)行過

29、程是遞歸算法的執(zhí)行過程是不斷地自調(diào)用不斷地自調(diào)用，直到到達(dá)遞歸，直到到達(dá)遞歸出口才結(jié)束自調(diào)用過程；到達(dá)遞歸出口后，遞歸算法出口才結(jié)束自調(diào)用過程；到達(dá)遞歸出口后，遞歸算法開始按開始按最后調(diào)用的過程最先返回最后調(diào)用的過程最先返回的次序返回；返回到的次序返回；返回到最外層的調(diào)用語句時(shí)遞歸算法執(zhí)行過程結(jié)束。最外層的調(diào)用語句時(shí)遞歸算法執(zhí)行過程結(jié)束。42 堆棧遞歸調(diào)用總結(jié)堆棧遞歸調(diào)用總結(jié)3.1 3.1 棧棧433.2 3.2 隊(duì)列隊(duì)列與線性表相同，仍為一對(duì)一關(guān)系。與線性表相同，仍為一對(duì)一關(guān)系。順序隊(duì)順序隊(duì)或或鏈隊(duì)鏈隊(duì)，以，以循環(huán)順序隊(duì)循環(huán)順序隊(duì)更常見。更常見。存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)只能在表的只能

30、在表的一端一端進(jìn)行插入運(yùn)算，在表進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。的另一端進(jìn)行刪除運(yùn)算的線性表。尾部插入尾部插入首部刪除首部刪除隊(duì)列定義隊(duì)列定義443.2 3.2 隊(duì)列隊(duì)列只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照依照先進(jìn)先出（先進(jìn)先出（FIFOFIFO）的原則。的原則。關(guān)鍵是掌握關(guān)鍵是掌握入隊(duì)入隊(duì)和和出隊(duì)出隊(duì)操作，具體實(shí)操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同?，F(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同?；静僮鳎夯静僮鳎?入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空 或隊(duì)滿等操作。或隊(duì)滿等操作。45隊(duì)列隊(duì)列 （Queue）是僅在是僅在表尾表尾進(jìn)行

31、插入操作，在進(jìn)行插入操作，在表頭表頭進(jìn)行進(jìn)行刪除操作的線性表。它是一種先進(jìn)先出刪除操作的線性表。它是一種先進(jìn)先出（FIFO）的線的線性表。性表。例如：隊(duì)列例如：隊(duì)列 Q= (Q= (a a1 1 , a , a2 , 2 , a a3 , .,3 , .,a an-1 , n-1 , a an n ) )在隊(duì)尾插入元素稱為在隊(duì)尾插入元素稱為；在隊(duì)首刪除元素稱為；在隊(duì)首刪除元素稱為。隊(duì)首隊(duì)首隊(duì)尾隊(duì)尾1 1、隊(duì)列、隊(duì)列 是是一種特殊線性表一種特殊線性表3.2 3.2 隊(duì)列隊(duì)列46問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？問：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？1. 1. 離散事件的模擬離散事件的模擬

32、（模擬事件發(fā)生的先后順序模擬事件發(fā)生的先后順序, ,例如例如 CPUCPU芯片中的指令譯碼隊(duì)列）；芯片中的指令譯碼隊(duì)列）；2. 2. 操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPUCPU執(zhí)行多個(gè)業(yè)）；執(zhí)行多個(gè)業(yè)）；3. 3. 簡(jiǎn)化程序設(shè)計(jì)。簡(jiǎn)化程序設(shè)計(jì)。答：答：3.2 3.2 隊(duì)列隊(duì)列47隊(duì)的隊(duì)的實(shí)現(xiàn)方式實(shí)現(xiàn)方式是本節(jié)重點(diǎn)，關(guān)鍵是掌握是本節(jié)重點(diǎn)，關(guān)鍵是掌握入隊(duì)和出隊(duì)入隊(duì)和出隊(duì)操作。操作。具體實(shí)現(xiàn)依存儲(chǔ)結(jié)構(gòu)（具體實(shí)現(xiàn)依存儲(chǔ)結(jié)構(gòu)（鏈隊(duì)鏈隊(duì)或或順序隊(duì)順序隊(duì)）的不同而不同。）的不同而不同。隊(duì)的抽象數(shù)據(jù)類型定義隊(duì)的抽象數(shù)據(jù)類型定義：ADT Queue數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D=數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系

33、：R=基本操作：基本操作： ADT Queue建隊(duì)、入隊(duì)或出隊(duì)、判隊(duì)空建隊(duì)、入隊(duì)或出隊(duì)、判隊(duì)空或隊(duì)滿等，教材或隊(duì)滿等，教材P59-60P59-60羅列羅列了了9 9種基本操作。種基本操作。2、隊(duì)列實(shí)現(xiàn)方式、隊(duì)列實(shí)現(xiàn)方式3.2.1 3.2.1 隊(duì)列物理存儲(chǔ)方式隊(duì)列物理存儲(chǔ)方式481、鏈隊(duì)列2、順序隊(duì)49鏈隊(duì)列類型定義： typedef struct QueuePtr front ; /隊(duì)首指針 QueuePtr rear ; /隊(duì)尾指針 LinkQueue;結(jié)點(diǎn)類型定義： typedef Struct QNode QElemType data; /元素 Struct QNode *next; /

34、指向下一結(jié)點(diǎn)的指針 Qnode , * QueuePtr ;關(guān)于整個(gè)鏈隊(duì)的關(guān)于整個(gè)鏈隊(duì)的總體描述總體描述鏈隊(duì)中任一鏈隊(duì)中任一結(jié)點(diǎn)的結(jié)構(gòu)結(jié)點(diǎn)的結(jié)構(gòu)1. 1.鏈隊(duì)列鏈隊(duì)列3.2.1 3.2.1 隊(duì)列物理存儲(chǔ)方式隊(duì)列物理存儲(chǔ)方式50討論：討論： 空鏈隊(duì)的特征？空鏈隊(duì)的特征？Q(隊(duì)尾隊(duì)尾)(隊(duì)首隊(duì)首)fronta1a2a3rearpfrontrear 怎樣實(shí)現(xiàn)鏈隊(duì)的怎樣實(shí)現(xiàn)鏈隊(duì)的入隊(duì)和出隊(duì)入隊(duì)和出隊(duì)操作？操作？ 鏈隊(duì)會(huì)滿嗎？鏈隊(duì)會(huì)滿嗎？front=rear一般不會(huì)，因?yàn)閯h除時(shí)有一般不會(huì)，因?yàn)閯h除時(shí)有freefree動(dòng)作。除非內(nèi)存不足！動(dòng)作。除非內(nèi)存不足！入隊(duì)（尾部插入）：入隊(duì)（尾部插入）：rear-n

35、ext=s; rear=s;出隊(duì)（頭部刪除）：出隊(duì)（頭部刪除）：front-next=front-next-next;SD鏈隊(duì)示意圖：鏈隊(duì)示意圖：完整操作函數(shù)完整操作函數(shù)見教材見教材51采用動(dòng)態(tài)分配空間的形式順序隊(duì)類型定義：順序隊(duì)類型定義：建隊(duì)建隊(duì)核心語句核心語句：q . base=(QElemType *)malloc(sizeof (QElemType ）* QUEUE_MAXSIZE); /分配空間分配空間關(guān)于整個(gè)順序關(guān)于整個(gè)順序隊(duì)的總體描述隊(duì)的總體描述#define QUEUE-MAXSIZE 100 /最大隊(duì)列長(zhǎng)度最大隊(duì)列長(zhǎng)度 typedef struct QElemType *ba

36、se; /隊(duì)列的基址隊(duì)列的基址 int front; /隊(duì)首指針隊(duì)首指針 int rear; /隊(duì)尾指針隊(duì)尾指針 SqQueue2. 2.順序隊(duì)順序隊(duì)3.2.1 3.2.1 隊(duì)列物理存儲(chǔ)方式隊(duì)列物理存儲(chǔ)方式52Q(隊(duì)尾隊(duì)尾)(隊(duì)首隊(duì)首)front a1 a2 a3data a40.99rear 隊(duì)列會(huì)滿嗎？隊(duì)列會(huì)滿嗎？極易裝滿！極易裝滿！因?yàn)閿?shù)組因?yàn)閿?shù)組通常有長(zhǎng)度限制，而通常有長(zhǎng)度限制，而其前端空間無法釋放。其前端空間無法釋放。 空隊(duì)列的特征？空隊(duì)列的特征？ 約定：約定：front=rearfront=rear隊(duì)尾后地址隊(duì)尾后地址入隊(duì)入隊(duì)( (尾部插入尾部插入) )： Q.baseQ.base

37、rear=e; rear=e; Q.rearQ.rear+ ; ; 出隊(duì)出隊(duì)( (頭部刪除頭部刪除) )： e=e=Q.baseQ.basefront; front; Q.frontQ.front+;+; 討論：討論：有有缺缺陷陷 怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？操作？核心語句如下：核心語句如下：用用base做數(shù)組名做數(shù)組名e順序隊(duì)示意圖：順序隊(duì)示意圖：53解決假溢出的途徑解決假溢出的途徑采用循環(huán)隊(duì)列采用循環(huán)隊(duì)列答：答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還有空位置，這就叫有空位

38、置，這就叫“假溢出假溢出”。問：什么叫問：什么叫“假溢出假溢出” ” ？如何解決？如何解決？54a3a2a10123N-1rearfronta3a2a1frontrear 0 1 2 3 . .N-1順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列55新問題：新問題：在循環(huán)隊(duì)列中，空隊(duì)特征是在循環(huán)隊(duì)列中，空隊(duì)特征是front=rearfront=rear；隊(duì)滿時(shí)也會(huì)隊(duì)滿時(shí)也會(huì)有有front=rearfront=rear；判決條件將出現(xiàn)二義性！判決條件將出現(xiàn)二義性！解決方案有三：解決方案有三：使用一個(gè)使用一個(gè)計(jì)數(shù)器計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；加加設(shè)標(biāo)志位

39、設(shè)標(biāo)志位，刪除時(shí)置，刪除時(shí)置1, 1,插入時(shí)置插入時(shí)置0, 0,則可識(shí)別當(dāng)前則可識(shí)別當(dāng)前front=rearfront=rear屬于何種情況屬于何種情況 人為人為浪費(fèi)一個(gè)單元浪費(fèi)一個(gè)單元，則隊(duì)滿特征可改為，則隊(duì)滿特征可改為front=(rear+1)%Nfront=(rear+1)%N；順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列56隊(duì)空條件隊(duì)空條件 : : front = rearfront = rear ( (初始化時(shí)：初始化時(shí)：front = rear )front = rear )隊(duì)滿條件隊(duì)滿條件： front = (rearfront = (rear) % N) % N (N= (N

40、=maxsizemaxsize) )隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：L=L=（N Nrearrearfrontfront）% N % N J2 J3J1 J4 J5frontrear 實(shí)際中常選用方案實(shí)際中常選用方案3 3（人為人為浪費(fèi)一個(gè)單元）浪費(fèi)一個(gè)單元）：即即frontfront和和rearrear二者之一指向?qū)嵲?，另一個(gè)指向空閑元素。二者之一指向?qū)嵲?，另一個(gè)指向空閑元素。 問問3 3： 在具有在具有n n個(gè)單元的循環(huán)隊(duì)列個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？中，隊(duì)滿時(shí)共有多少個(gè)元素？ N-1個(gè)個(gè)6 問問1 1：左圖中隊(duì)列左圖中隊(duì)列maxsize N=ma

41、xsize N=？問問2 2：左圖中隊(duì)列左圖中隊(duì)列長(zhǎng)度長(zhǎng)度L=L=？5順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列順序隊(duì)列轉(zhuǎn)化為循環(huán)隊(duì)列57（）（） rf （）（）（nfr）% n （）（）nrf （）（） （nrf）% n要分析要分析4 4種公式哪種最合理？種公式哪種最合理？當(dāng)當(dāng) r f r f 時(shí)（時(shí)（A A）合理；）合理；當(dāng)當(dāng) r f r f 時(shí)（時(shí)（C C）合理；）合理；答：答：綜合綜合2種情況，以（種情況，以（D）的表達(dá)最為合理的表達(dá)最為合理例例1 1：數(shù)組：數(shù)組nn用來表示一個(gè)循環(huán)隊(duì)列，用來表示一個(gè)循環(huán)隊(duì)列，f f 為當(dāng)前隊(duì)列頭元素為當(dāng)前隊(duì)列頭元素的的前一前一位置，位置，r r 為隊(duì)尾元素的位置。假定隊(duì)

42、列中元素的個(gè)數(shù)小為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于于n n，計(jì)算隊(duì)列中元素的公式為，計(jì)算隊(duì)列中元素的公式為: :示例示例58例例2 2：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的首元素的前一個(gè)前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是先一個(gè)元素時(shí)，其操作是先 移動(dòng)隊(duì)首指針移動(dòng)隊(duì)首指針取出元素取出元素，后，后。示例示例59例例3 3： 一循環(huán)隊(duì)列如下圖所示，若先刪除一循環(huán)隊(duì)列如下圖所示，若先刪除4 4個(gè)元素，個(gè)元素，接著再插入接著再插入4 4個(gè)元素，請(qǐng)問隊(duì)頭和隊(duì)尾指針分別指?jìng)€(gè)元素，請(qǐng)問隊(duì)頭和隊(duì)尾指針分別指

43、向哪個(gè)位置向哪個(gè)位置? ? 示例示例60J2 J3J1 J4 J5front=1rear=0解：解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=1和和rear=0。刪除刪除4個(gè)元素后個(gè)元素后 f=5；再插入再插入4個(gè)元素后，個(gè)元素后，r=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4rear=0front=5示例示例61討論：循環(huán)隊(duì)列的基本操作如何實(shí)現(xiàn)？討論：循環(huán)隊(duì)列的基本操作如何實(shí)現(xiàn)？以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例以建隊(duì)、入隊(duì)和出隊(duì)三種基本操作為例1 1、初始化一個(gè)空隊(duì)列、初始化一個(gè)空隊(duì)列算法要求：生成一空隊(duì)列算法要求：生成

44、一空隊(duì)列算法操作：算法操作：為隊(duì)列分配基本容量空間為隊(duì)列分配基本容量空間 設(shè)置隊(duì)列為空隊(duì)列，其特征即：設(shè)置隊(duì)列為空隊(duì)列，其特征即： front=rear=0front=rear=0（也可為任意單元，如（也可為任意單元，如1 1，2 2，甚至甚至-1 -1 ）3.2.2 3.2.2 循環(huán)隊(duì)列操作循環(huán)隊(duì)列操作621 1、建隊(duì)的完整算法、建隊(duì)的完整算法Status InitQueue ( SqQueue &q ) /初始化空循環(huán)隊(duì)列 q q . base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE); /分配空間 if (!q.b

45、ase) exit(OVERFLOW);/內(nèi)存分配失敗，退出程序 q.front =q.rear=0; /置空隊(duì)列 return OK; /InitQueue;3.2.2 3.2.2 循環(huán)隊(duì)列操作循環(huán)隊(duì)列操作63算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素分分 析析：(1) (1) 插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？ if ( q . rear + 1 ) % QUEUE_MAXSIZE )=if ( q . rear + 1 ) % QUEUE_MAXSIZE )=q.frontq.front) ) return ERROR; return ERROR;(2 (2）插入動(dòng)作）插入動(dòng)作 q.baseq.base q.rear