數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第3章

1、第三章 棧和隊(duì)列,【課前思考】,簡單地說，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的序列。,必然是依從上往下的次序，即n,2,1。它們遵循的是后進(jìn)先出的規(guī)律，這正是本章要討論的棧的結(jié)構(gòu)特點(diǎn)。,是排隊(duì)。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。,【學(xué)習(xí)目標(biāo)】,1. 掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 2. 熟練掌握棧類型的兩種實(shí)現(xiàn)方法。 3. 熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。 4. 理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。,棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用。,【知識(shí)點(diǎn)】,順

2、序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列,【重點(diǎn)和難點(diǎn)】,【學(xué)習(xí)指南】,在這一章中，主要是學(xué)習(xí)如何在求解應(yīng)用問題中適當(dāng)?shù)貞?yīng)用棧和隊(duì)列，棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)都不難，但應(yīng)該對(duì)它們了如指掌，特別要注意它們的基本操作實(shí)現(xiàn)時(shí)的一些特殊情況，如棧滿和?？?、隊(duì)滿和隊(duì)空的條件以及它們的描述方法。本章要求必須完成的算法設(shè)計(jì)題為：3.15，3.17，3.19，3.22， 3.27 ,3.28，3.30，3.31，3.32。其中前4個(gè)主要是練習(xí)棧的應(yīng)用，后4個(gè)主要是有關(guān)隊(duì)列的實(shí)現(xiàn)方法的練習(xí)。,通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。,線性表 棧 隊(duì)列 insert(l, i, x) inser

3、t(s, n+1, x) insert(q, n+1, x) 1in+1 delete(l, i) delete(s, n) delete(q, 1) 1in,棧和隊(duì)列是兩種常用的數(shù)據(jù)類型,3.1 棧,3.2 棧的應(yīng)用舉例,3.4 隊(duì)列,目 錄,3.3 棧與遞歸的實(shí)現(xiàn),3.1 棧,一、棧的定義,棧(stack)作為一種限定性線性表，是將線性表的插入和刪除運(yùn)算限制為僅在表的一端進(jìn)行。 通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(top)，因此棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針的位置指示器指示。同時(shí)表的另一端為固定的一端，被稱為棧底(bottom)。當(dāng)棧中沒有元素時(shí)稱為空棧。棧的

4、插入操作被形象地稱為進(jìn)?；蛉霔＃瑒h除操作稱為出?；蛲藯?。 插入：最先放入棧中元素在棧底，最后放入的元素在棧頂； 刪除：最后放入的元素最先刪除，最先放入的元素最后刪除。 棧是一種后進(jìn)先出(last in first out)的線性表，簡稱為lifo表。,圖3.1 棧,例：設(shè)一個(gè)棧的輸入序列為a,b,c,d,則借助一個(gè)棧所得到的輸出序列不可能是 。 (a) a,b,c,d(b) d,c,b,a (c) a,c,d,b(d) d,a,b,c 答:可以簡單地推算,得容易得出d,a,b,c是不可能的,因?yàn)閐先出來,說明a,b,c,d均在棧中,按照入棧順序,在棧中順序應(yīng)為d,c,b,a,出棧的順序只能是d

5、,c,b,a。所以本題答案為d。,二、棧的主要操作,1.初始化棧：initstack( /在棧構(gòu)造前和銷毀后base值為null selemtype *top; /棧頂指針 int stacksize; sqstack; /當(dāng)前已分配存儲(chǔ)空間 或簡單定義如下： #define m 100 int sm; int top;,圖3.2 順序棧中的進(jìn)棧和出棧,top指向棧頂元素 初態(tài)：top=-1; 空棧，棧中無元素， 進(jìn)棧：top=top+1; stop=x; 退棧：取stop; top=top-1; 棧滿：top=m-1;棧溢出（上溢），不能再進(jìn)棧（錯(cuò)誤狀態(tài)） top=-1時(shí)不能退棧，下溢（正常

6、狀態(tài)，常作控制條件）,（1）構(gòu)造空順序棧算法:初始化棧 status initstack ( sqstack / initstack,2.順序?；静僮鞯膶?shí)現(xiàn)如下:,程序描述： /this program is to initialize a stack # include # include # include # define stack_init_size 100 # define stackincrement 10 # define ok 1 # define error 0 typedef int selemtype; typedef struct /define structure

7、 sqstack() selemtype *base; selemtype *top; int stacksize; sqstack;,int initstack(sqstack ,（2） 取順序棧的棧頂元素 status gettop ( sqstack s, selemtype / gettop,（3）將元素壓入順序棧算法（進(jìn)棧） status push ( sqstack / push,（4）將元素彈出順序棧算法（退棧） status pop ( sqstack / pop,（5） 判?？辗?int empty ( sqstack s) / 如果棧 s 空，返回 1 ；如果棧 s 不空，

8、返回 0 。 if ( s.top = = s.base ) return 1; / 如果棧 s 為空，則返回 1 else return 0; / 如果棧 s 為空，則返回 0 / empty end,3棧的共享 有時(shí)，一個(gè)程序設(shè)計(jì)中，需要使用多個(gè)同一類型的棧,這時(shí)候，可能會(huì)產(chǎn)生一個(gè)?？臻g過小，容量發(fā)生溢出，而另一個(gè)棧空間過大，造成大量存儲(chǔ)單元浪費(fèi)的現(xiàn)象。 為了充分利用各個(gè)棧的存儲(chǔ)空間，這時(shí)可以采用多個(gè)棧共享存儲(chǔ)單元，即給多個(gè)棧分配一個(gè)足夠大的存儲(chǔ)空間，讓多個(gè)棧實(shí)現(xiàn)存儲(chǔ)空間優(yōu)勢互補(bǔ)。,?？眨簍op1=0,top2=m-1; 棧滿：top1+1=top2,兩個(gè)棧共享存儲(chǔ)單元可用如下c語句描述：

9、 #define maxsize 100 #define dustacksize maxsize typedef struct dusqstack selemtype datamaxsize; int top1; /top1 is the pointer of dusqstack s1 int top2; /top2 is the pointer of dusqstack s2 int flag;dusqstack; / 或： #define maxsize 100 struct duseqstack elemtype datamaxsize; int top2 ; /兩個(gè)棧的棧頂指針 int

10、 flag; ,（1）兩個(gè)棧共享存儲(chǔ)單元的進(jìn)棧算法 status dusqstackpush ( dusqstack / 如果 flag 不為 1,2，則返回 error else / 如果 flag 為 1 或 2，則入棧 switch ( s.flag ) case 1 : / 標(biāo)志位 flag 為 1,s.datas.top1 = x; / 元素 x 入棧 s1 s.top1+; / 修改棧 s1 的棧頂指針 break; case 2 : / 標(biāo)志位 flag 為 2 s.datas.top2 = x; / 元素 x 入棧 s2 s.top2- -; / 修改棧 s2 的棧頂指針 br

11、eak; / switch 結(jié)束 return ok; / else 結(jié)束 / else 結(jié)束 / dusqstackpush,（2）兩個(gè)棧共享存儲(chǔ)單元的退棧算法 status dusqstackpop ( dusqstack / 元素 x 出棧 / if 結(jié)束,else return error; / 如果棧 s1 為空，則返回 error break; case 2 : / 標(biāo)志位 flag 為 1 if ( s.top2maxsize-1 ) /若棧 s2 不空，對(duì) s2 進(jìn)行操作 s.top2+; / 修改棧 s2 的棧頂指針 x = s.datas.top2; / 元素 x 出棧 /

12、 if 結(jié)束 else return error; / 如果棧 s2 為空，則返回 error break; / switch結(jié)束 return ok; / else結(jié)束 / dusqstackpop,4.鏈棧 （1）鏈棧結(jié)構(gòu)及數(shù)據(jù)類型 棧的鏈?zhǔn)酱尜A結(jié)構(gòu),也稱為鏈棧，它是一種限制運(yùn)算的鏈表，即規(guī)定鏈表中的插入和刪除運(yùn)算只能在鏈表開頭進(jìn)行。鏈棧結(jié)構(gòu)見圖3-4。,typedef struct snode /define structure linkstack selemtype data; struct snode *next; snode,*linkstack,（2）鏈棧的五種棧運(yùn)算,（a）棧初

13、始化 void inistack(linkstack top) top = ( linkstack ) malloc ( sizeof ( snode ) ); top-next=null; （b）進(jìn)棧運(yùn)算 status push_l ( linkstack / push_l,（c）退棧運(yùn)算 status pop_l ( linkstack / pop_l,（d）取棧頂元素 status gettop_l ( linkstack top, selemtype / else 結(jié)束 / gettop_l,（5）判?？?int empty(linkstack *top) if(top-next=nu

14、ll) return(1); else return(0); ,課 前 復(fù) 習(xí),設(shè)n 個(gè)元素的進(jìn)棧序列是p1，p2，p3， pn，其輸出序列是1,2，3，n，若p1=3，則p2的值 ()。 a、可能是2b、一定是2 c、不可能是1d、一定是1,一、 數(shù)制轉(zhuǎn)換 假設(shè)要將十進(jìn)制數(shù)n轉(zhuǎn)換為d進(jìn)制數(shù)，一個(gè)簡單的轉(zhuǎn)換算法是重復(fù)下述兩步， 直到n等于零： x = n mod d (其中mod為求余運(yùn)算) n = n div d (其中div為整除運(yùn)算) 計(jì)算過程從低位到高位，打印輸出從高位到低位,3.2 棧的應(yīng)用舉例 棧在日常生活中和計(jì)算機(jī)程序設(shè)計(jì)中有著許多應(yīng)用，下面僅介紹棧在計(jì)算機(jī)中的應(yīng)用。,void

15、conversion(int n) /*對(duì)于任意的一個(gè)非負(fù)十進(jìn)制數(shù)n， 打印出與其等值的8進(jìn)制數(shù)*/ stack s; int x; /* s為順序棧或鏈棧 */ initstack( 算法3.1,二、括號(hào)匹配問題 假設(shè)表達(dá)式中允許包含三種括號(hào):圓括號(hào)、方括號(hào)和大括號(hào)。編寫一個(gè)算法判斷表達(dá)式中的括號(hào)是否正確配對(duì)。 解:設(shè)置一個(gè)括號(hào)棧,掃描表達(dá)式：遇到左括號(hào)(包括(、和)時(shí)進(jìn)棧,遇到右括號(hào)時(shí),若棧是相匹配的左括號(hào),則出棧,否則,返回0。 若表達(dá)式掃描結(jié)束,棧為空,返回1表示括號(hào)正確匹配,否則返回0。,int correct(char exp,int n) char stmaxsize; int

16、top=-1,i=0,tag=1; while (in ,if (expi=) /*遇到,若棧頂是, 則繼續(xù)處 理,否則以不配對(duì)返回*/ if (sttop=) top-; else tag=0; if (expi=) /*遇到,若棧頂是 ,則繼續(xù)處 理,否則以不配對(duì)返回*/ if (sttop=) top-; else tag=0; i+; /*表達(dá)式掃描完畢*/ if (top-1) tag=0; /*若棧不空,則不配對(duì)*/ return(tag); ,三、行編輯程序 功能：接收用戶從終端輸入的數(shù)據(jù)或程序，并存入用戶的數(shù)據(jù)區(qū)。 算法思想：設(shè)輸入緩沖區(qū)為一個(gè)棧結(jié)構(gòu)，每當(dāng)從終端接收一個(gè)字符后先

17、作如下判別：若它既不是退格符（#）也不是退行符（）,則將該字符入棧；若是退格符（#），則從棧頂刪去一個(gè)字符；若是退行符（），則將棧清空。 算法描述如下：,void lineedit() initstack(s); ch=getchar(); while(ch!=eof) /eof為全文結(jié)束符 while(ch!=eof,五、 表達(dá)式求值,表達(dá)式求值是高級(jí)語言編譯中的一個(gè)基本問題， 是棧的典型應(yīng)用實(shí)例。 任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、 運(yùn)算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)， 也可以是被說明為變量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符

18、、 關(guān)系運(yùn)算符和邏輯運(yùn)算符三類；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。,1.無括號(hào)算術(shù)表達(dá)式求值,表達(dá)式計(jì)算 程序設(shè)計(jì)語言中都有計(jì)算表達(dá)式的問題， 這是語言編譯中的典型問題。 (1) 表達(dá)式形式： 由運(yùn)算對(duì)象、 運(yùn)算符及必要的表達(dá)式括號(hào)組成； (2) 表達(dá)式運(yùn)算： 運(yùn)算時(shí)要有一個(gè)正確的運(yùn)算形式順序。 由于某些運(yùn)算符可能具有比別的運(yùn)算符更高的優(yōu)先級(jí)，因此表達(dá)式不可能嚴(yán)格的從左到右， 見圖3.5。,圖3.5 表達(dá)式運(yùn)算及運(yùn)算符優(yōu)先級(jí),圖3.6 無括號(hào)算術(shù)表達(dá)式的處理過程,2. 算術(shù)表達(dá)式處理規(guī)則 (1) 規(guī)定優(yōu)先級(jí)表。 (2) 設(shè)置兩個(gè)棧： ovs(運(yùn)算數(shù)棧)和optr(運(yùn)算符棧)。 (3) 自左

19、向右掃描，遇操作數(shù)進(jìn)ovs，遇操作符則與optr棧頂優(yōu)先數(shù)比較：當(dāng)前操作符optr棧頂, 當(dāng)前操作符進(jìn)optr棧；當(dāng)前操作符optr棧頂，ovs棧頂、次頂和optr棧頂，退棧形成運(yùn)算t(i)，t(i)進(jìn)ovs棧。 例： 實(shí)現(xiàn)a/bc+d*e的運(yùn)算過程時(shí)棧區(qū)變化情況如圖3.7所示。,圖3.7 a/bc+d*e運(yùn)算過程的棧區(qū)變化情況示意圖,+,*,3. 帶括號(hào)算術(shù)表達(dá)式 假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符， 界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“”，如： （7+15）*（23-28/4）。 引入表達(dá)式起始、 結(jié)束符是為了方便。 要對(duì)一個(gè)簡單的算術(shù)表達(dá)式求值， 首先要了解算術(shù)

20、四則運(yùn)算的規(guī)則， 即： (1) 從左算到右；(2) 先乘除， 后加減；(3) 先括號(hào)內(nèi)， 后括號(hào)外。,運(yùn)算符和界限符可統(tǒng)稱為算符，它們構(gòu)成的集合命名為optr。根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算過程中，任意兩個(gè)前后相繼出現(xiàn)的算符1和2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一： 12， 1的優(yōu)先權(quán)高于2。,表 3-1 算符之間的優(yōu)先關(guān)系,實(shí)現(xiàn)算符優(yōu)先算法時(shí)需要使用兩個(gè)工作棧： 一個(gè)稱作optr， 用以存放運(yùn)算符；另一個(gè)稱作opnd，用以存放操作數(shù)或運(yùn)算的中間結(jié)果。 算法的基本過程如下： 首先初始化操作數(shù)棧opnd和運(yùn)算符棧optr， 并將表達(dá)式起始符“”壓入運(yùn)算符棧； 依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)

21、則直接進(jìn)入操作數(shù)棧opnd， 若是運(yùn)算符，則與運(yùn)算符棧optr的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)比較，并做如下處理： ,(1) 若棧頂運(yùn)算符的優(yōu)先級(jí)低于剛讀入的運(yùn)算符， 則讓剛讀入的運(yùn)算符進(jìn)optr棧； (2) 若棧頂運(yùn)算符的優(yōu)先級(jí)高于剛讀入的運(yùn)算符，則將棧頂運(yùn)算符退棧，送入，同時(shí)將操作數(shù)棧opnd退棧兩次，得到兩個(gè)操作數(shù)a、b，對(duì)a、 b進(jìn)行運(yùn)算后， 將運(yùn)算結(jié)果作為中間結(jié)果推入opnd棧； (3) 若棧頂運(yùn)算符的優(yōu)先級(jí)與剛讀入的運(yùn)算符的優(yōu)先級(jí)相同，說明左右括號(hào)相遇，只需將棧頂運(yùn)算符（左括號(hào)）退棧即可。,算法具體描述如下：,int expevaluation() /*讀入一個(gè)簡單算術(shù)表達(dá)式并計(jì)算其值。 o

22、perator和operand分別為運(yùn)算符棧和運(yùn)算數(shù)棧， ops為運(yùn)算符集合*/ initstack( while(c!=|gettop(optr)! =) /* gettop()通過函數(shù)值返回棧頂元素*/, if(!in(c,op) push(,pop( ,例求表達(dá)式1+2*3-4/2的值，棧的變化如下。,步驟 操作數(shù)棧 運(yùn)算符棧 說明,開始,兩棧均為空,1,1,1進(jìn)入操作數(shù)棧,+進(jìn)入運(yùn)算符棧,2進(jìn)入操作數(shù)棧,*進(jìn)入運(yùn)算符棧,3進(jìn)入操作數(shù)棧,退棧,2*3進(jìn)入操作數(shù)棧,退棧,1+6進(jìn)入操作數(shù)棧,2,3,4,5,6,7,8,9,1,+,1,2,+,1,2,+,1,1,1,7,+,*,2,3,6,

23、+,*,+,步驟 操作數(shù)棧 運(yùn)算符棧 說明,10,7,-進(jìn)入運(yùn)算符棧,4進(jìn)入操作數(shù)棧,/進(jìn)入運(yùn)算符棧,2進(jìn)入操作數(shù)棧,退棧,4/2進(jìn)入操作數(shù)棧,退棧,7-2進(jìn)入操作數(shù)棧,11,12,13,14,15,16,17,7 4,-,7 4,- /,7 4 2,- /,7,7 2,-,-,-,5,當(dāng)然，算術(shù)表達(dá)式除了簡單求值外，還會(huì)涉及到算術(shù)表達(dá)式的兩種表示方法，即中綴表示法和后綴表示法。中綴表達(dá)式求值較麻煩（須考慮運(yùn)算符的優(yōu)先級(jí)，甚至還要考慮圓括號(hào)），而后綴表達(dá)式求值較方便（無須考慮運(yùn)算符的優(yōu)先級(jí)及圓括號(hào)）。下面將介紹算術(shù)表達(dá)式的中綴表示和后綴表示及它們的求值規(guī)律，,例如，對(duì)于下列各中綴表達(dá)式：（1）

24、 3/5+8 （2） 18-9*(4+3) （3） (25+x)*(a*(a+b)+b) 對(duì)應(yīng)的后綴表達(dá)式為： (1)3 5 / 8 + (2)18 9 4 3 + * - (3)25 x + a a b + * b + *,4.中綴表達(dá)式變成等價(jià)的后綴表達(dá)式 將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式，表達(dá)式中操作數(shù)次序不變，運(yùn)算符次序發(fā)生變化，同時(shí)去掉了圓括號(hào)。轉(zhuǎn)換規(guī)則是：設(shè)立一個(gè)棧，存放運(yùn)算符，首先棧為空，編譯程序從左到右掃描中綴表達(dá)式，若遇到操作數(shù)，直接輸出，并輸出一個(gè)空格作為兩個(gè)操作數(shù)的分隔符；若遇到運(yùn)算符，則必須與棧頂比較，運(yùn)算符級(jí)別比棧頂級(jí)別高則進(jìn)棧，否則退出棧頂元素并輸出，然后輸出一個(gè)空

25、格作分隔符；若遇到左括號(hào)，進(jìn)棧；若遇到右括號(hào)，則一直退棧輸出，直到退到左括號(hào)止。當(dāng)棧變成空時(shí)，輸出的結(jié)果即為后綴表達(dá)式。 將中綴表達(dá)式(1+2)*(8-2)/(7-4)變成等價(jià)的后綴表達(dá)式。 現(xiàn)在用棧來實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下,步驟 棧中元素 輸出結(jié)果 說明,5.后綴表達(dá)式的求值 將中綴表達(dá)式轉(zhuǎn)換成等價(jià)的后綴表達(dá)式后，求值時(shí)，不需要再考慮運(yùn)算符的優(yōu)先級(jí)，只需從左到右掃描一遍后綴表達(dá)式即可。具體求值步驟為：設(shè)置一個(gè)棧，開始時(shí)，棧為空，然后從左到右掃描后綴表達(dá)式，若遇操作數(shù)，則進(jìn)棧；若遇運(yùn)算符，則從棧中退出兩個(gè)元素，先退出的放到運(yùn)算符的右邊，后退出的放到運(yùn)算符左邊，運(yùn)算后的結(jié)果再進(jìn)棧，直

26、到后綴表達(dá)式掃描完畢。此時(shí)，棧中僅有一個(gè)元素，即為運(yùn)算的結(jié)果。例，求后綴表達(dá)式：1 2 + 8 2 - 7 4 - / *的值， 棧的變化情如下：,從上可知，最后求得的后綴表達(dá)式之值為6，與用中綴表達(dá)式求得的結(jié)果一致，但后綴式求值要簡單得多。,五、 求解迷宮問題 求迷宮問題就是求出從入口到出口的路徑。在求解時(shí),通常用的是“窮舉求解”的方法,即從入口出發(fā),順某一方向向前試探,若能走通,則繼續(xù)往前走；否則沿原路退回,換一個(gè)方向再繼續(xù)試探,直至所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回(稱為回溯),需要用一個(gè)后進(jìn)先出的棧來保存從入口到當(dāng)前位置的路徑。 首先用如圖3.3所示的方塊圖

27、表示迷宮。對(duì)于圖中的每個(gè)方塊,用空白表示通道,用陰影表示墻。所求路徑必須是簡單路徑,即在求得的路徑上不能重復(fù)出現(xiàn)同一通道塊。,為了表示迷宮,設(shè)置一個(gè)數(shù)組mg,其中每個(gè)元素表示一個(gè)方塊的狀態(tài),為0時(shí)表示對(duì)應(yīng)方塊是通道,為1時(shí)表示對(duì)應(yīng)方塊為墻,如圖3.3所示的迷宮,對(duì)應(yīng)的迷宮數(shù)組mg如下: int mgm+1n+1= /*m=10,n=10*/ 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,0,0,1,1,0,0,1, 1,0,1,1,1,0,0,0,0,1, 1,0,0,0,1,0,0,0,0,1, 1,

28、0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1;,while (棧不空) 若當(dāng)前位置可通， 則將當(dāng)前位置插入棧頂； / 納入路徑 若該位置是出口位置，則算法結(jié)束； / 此時(shí)棧中存放的是一條從入口位置到出口位置的路徑否則切換當(dāng)前位置的北鄰方塊為新的當(dāng)前位置； 否則若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置；/ 從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置， 直至

29、找到一個(gè)可通的相鄰塊或出棧至棧空； ,算法描述：,void mgpath()/*路徑為:(1,1)-(m-2,n-2)*/ int i,j,di,find,k; top+; /*初始方塊進(jìn)棧*/ stacktop.i=1;stacktop.j=1;stacktop.di=-1;mg11=-1; while (top-1) /*棧不空時(shí)循環(huán)*/ i=stacktop.i;j=stacktop.j;di=stacktop.di; if (i=m-2 ,find=0; while (di4 ,if (find=1) /*找到了下一個(gè)可走方塊*/ stacktop.di=di; /*修改原棧頂元素的d

30、i值*/ top+; /*下一個(gè)可走方塊進(jìn)棧*/ stacktop.i=i;stacktop.j=j;stacktop.di=-1; mgij=-1;/*避免重復(fù)走到該方塊*/ else /*沒有路徑可走,則退棧*/ mgstacktop.istacktop.j=0; /*讓該位置變?yōu)槠渌窂娇勺叻綁K*/ top-; printf(沒有可走路徑!n); ,3.3 棧與遞歸的實(shí)現(xiàn),1、什么是遞歸 在定義一個(gè)過程或函數(shù)時(shí)出現(xiàn)調(diào)用本過程或本函數(shù)的成分,稱之為遞歸。若調(diào)用自身,稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q,而q又調(diào)用p,稱之為間接遞歸。 如果一個(gè)遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后

31、一條執(zhí)行語句,則稱這種遞歸調(diào)用為尾遞歸。,例 以下是求n!(n為正整數(shù))的遞歸函數(shù)。 int fun(int n) int x; if (n=1) /*語句1*/ x=1;/*語句2*/ else /*語句3*/ x=fun(n-1)*n;/*語句4*/ return(x);/*語句5*/ 在該函數(shù)fun(n)求解過程中,直接調(diào)用fun(n-1)(語句4)自身,所以它是一個(gè)直接遞歸函數(shù)。又由于遞歸調(diào)用是最后一條語句,所以它又屬于尾遞歸。,2 、何時(shí)使用遞歸 在以下三種情況下,常常要用到遞歸的方法。 1) 定義是遞歸的 有許多數(shù)學(xué)公式、數(shù)列等的定義是遞歸的。例如,求n!和fibonacci數(shù)列等

32、。這些問題的求解過程可以將其遞歸定義直接轉(zhuǎn)化為對(duì)應(yīng)的遞歸算法。,2) 數(shù)據(jù)結(jié)構(gòu)是遞歸的 有些數(shù)據(jù)結(jié)構(gòu)是遞歸的。例如,第2章中介紹過的單鏈表就是一種遞歸數(shù)據(jù)結(jié)構(gòu),其結(jié)點(diǎn)類型定義如下： typedef struct lnode elemtype data; struct lnode *next; linklist; 該定義中,結(jié)構(gòu)體lnode的定義中用到了它自身,即指針域next是一種指向自身類型的指針,所以它是一種遞歸數(shù)據(jù)結(jié)構(gòu)。,對(duì)于遞歸數(shù)據(jù)結(jié)構(gòu),采用遞歸的方法編寫算法既方便又有效。例如,求一個(gè)不帶頭結(jié)點(diǎn)的單鏈表head的所有data域(假設(shè)為int型)之和的遞歸算法如下： int sum(li

33、nklist *head) if (head=null) return 0; else return(head-data+sum(head-next); ,3)問題的求解方法是遞歸的 有些問題的解法是遞歸的,典型的有hanoi問題求解,該問題描述是：設(shè)有3個(gè)分別命名為x,y和z的塔座,在塔座x上有n個(gè)直徑各不相同,從小到大依次編號(hào)為1,2,n的盤片,現(xiàn)要求將x塔座上的n個(gè)盤片移到塔座z上并仍按同樣順序疊放,盤片移動(dòng)時(shí)必須遵守以下規(guī)則：每次只能移動(dòng)一個(gè)盤片；盤片可以插在x,y和z中任一塔座；任何時(shí)候都不能將一個(gè)較大的盤片放在較小的盤片上。設(shè)計(jì)遞歸求解算法,并將其轉(zhuǎn)換為非遞歸算法。 設(shè)hanoi(

34、n,x,y,z)表示將n個(gè)盤片從x通過y移動(dòng)到z上,遞歸分解的過程是：,hanoi(n,a,b,c),hanoi(n-1,a,c,b)； move(n,a,c):將第n個(gè)圓盤從a移到c； hanoi(n-1,b,a,c),圖 hanoi塔的遞歸函數(shù)運(yùn)行示意圖,3、 遞歸模型 遞歸模型是遞歸算法的抽象,它反映一個(gè)遞歸問題的遞歸結(jié)構(gòu),例如,前面的遞歸算法對(duì)應(yīng)的遞歸模型如下： fun(1)=1 (1) fun(n)=n*fun(n-1) n1 (2) 其中,第一個(gè)式子給出了遞歸的終止條件,第二個(gè)式子給出了fun(n)的值與fun(n-1)的值之間的關(guān)系,我們把第一個(gè)式子稱為遞歸出口,把第二個(gè)式子稱為

35、遞歸體。,實(shí)際上,遞歸思路是把一個(gè)不能或不好直接求解的“大問題”轉(zhuǎn)化成一個(gè)或幾個(gè)“小問題”來解決,再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決,如此分解,直至每個(gè)“小問題”都可以直接解決(此時(shí)分解到遞歸出口)。但遞歸分解不是隨意的分解,遞歸分解要保證“大問題”與“小問題”相似,即求解過程與環(huán)境都相似。,求解fun(5)的過程如下：5!,4 遞歸問題的優(yōu)點(diǎn) 通過上面的例子可看出，遞歸既是強(qiáng)有力的數(shù)學(xué)方法， 也是程序設(shè)計(jì)中一個(gè)很有用的工具。其特點(diǎn)是對(duì)遞歸問題描述簡捷，結(jié)構(gòu)清晰，程序的正確性容易證明。 5、消除遞歸的原因 其一：有利于提高算法時(shí)空性能，因?yàn)檫f歸執(zhí)行時(shí)需要系統(tǒng)提供隱式棧實(shí)現(xiàn)遞歸

36、，效率低且費(fèi)時(shí)。 其二： 無應(yīng)用遞歸語句的語言設(shè)施環(huán)境條件，有些計(jì)算機(jī)語言不支持遞歸功能，如fortran語言中無遞歸機(jī)制 。 其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時(shí)不合適， 也存在一個(gè)把遞歸算法轉(zhuǎn)化為非遞歸算法的需求。 ,3.4 隊(duì)列,隊(duì)列簡稱隊(duì),它也是一種運(yùn)算受限的線性表,其限制僅允許在表的一端進(jìn)行插入,而在表的另一端進(jìn)行刪除。 我們把進(jìn)行插入的一端稱做隊(duì)尾(rear),進(jìn)行刪除的一端稱做隊(duì)首(front)。 向隊(duì)列中插入新元素稱為進(jìn)隊(duì)或入隊(duì),新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為出隊(duì)或離隊(duì),元素出隊(duì)后,其后繼元素就成為隊(duì)首元素。,二、隊(duì)列的基本運(yùn)算 1. 初始化操作

37、：initqueue( /*數(shù)據(jù)域*/ struct qnode *next; /*指針域*/ qnode,*queueptr; typedef struct queueptr front; queueptr rear; linkqueue;,鏈隊(duì)列的基本操作 （1） 初始化操作。 int initqueue(linkqueue ,（2） 入隊(duì)操作。 status enqueue(linkqueue ,（3） 出隊(duì)操作。 int dequeue(linkqueue ,2. 循環(huán)隊(duì)列:隊(duì)列的順序表示和實(shí)現(xiàn),圖3.15 隊(duì)列的基本操作,用一組連續(xù)的存儲(chǔ)單元依次存放隊(duì)列的元素，并設(shè)兩個(gè)指針front

38、、rear分別指示隊(duì)頭和隊(duì)尾元素的位置。 front：指向?qū)嶋H的隊(duì)頭；rear：指向?qū)嶋H隊(duì)尾的下一位置。 初態(tài)： frontrear0；隊(duì)空： frontrear;隊(duì)滿： rearm; 入隊(duì)： qrear=x; rear rear+1; 出隊(duì)：x=qfront;front=front+1;,圖3.16 循環(huán)隊(duì)列,假溢出的解決方法： （1）將隊(duì)中元素向隊(duì)頭移動(dòng)；（2）采用循環(huán)隊(duì)列：q0接在qm-1之后 初態(tài)： frontrear0或m-1；隊(duì)空： frontrear; 入隊(duì)： qrear=x； rear( rear+1)%m; 出隊(duì)： x=qfront; front=(front+1)%m; 隊(duì)

39、滿： 留一個(gè)空間不用(rear+1)%m=front; 或另設(shè)一個(gè)標(biāo)志以區(qū)分隊(duì)空和隊(duì)滿。,循環(huán)隊(duì)列的類型定義： define maxsize 100 /*隊(duì)列的最大長度*/ typedef struct qelemtype elementmaxsize; /* 隊(duì)列的元素空間*/ int front; /*頭指針指示器*/ int rear ; /*尾指針指示器*/ seqqueue;,循環(huán)隊(duì)列的基本操作： （1） 初始化操作。 void initqueue（seqqueue ,（2） 入隊(duì)操作。 int enterqueue(seqqueue *q, queueelementtype x) /*將元素x入隊(duì)*/ if(q-rear+1)%maxsize=q-front) /*隊(duì)列已經(jīng)滿了*/ return error; q-elementq-rear=x; q-rear=(q-rear+1)%maxsize; /* 重新設(shè)置隊(duì)尾指針 */ return ok; /*操作成功*/ ,（3） 出隊(duì)操作。 int dequeue(seqqueue /*操作成功*/ ,鍵盤輸入循環(huán)緩沖區(qū)問題,有兩個(gè)進(jìn)程同時(shí)存在于一個(gè)程序中。 其中第一個(gè)進(jìn)程在屏幕上連續(xù)顯示字符“a”，與此同時(shí)，程序不斷檢測鍵盤是否有輸入，如果有的話，就讀入用戶鍵入