算法與數(shù)據(jù)結(jié)構(gòu)第3章 棧和隊(duì)列

1、第 3 章 限定性線性表?xiàng)：完?duì)列 第第3章章 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧 3.2 隊(duì)列隊(duì)列 第 3 章 限定性線性表?xiàng)：完?duì)列 3.1 棧棧 3.1.1 棧的定義棧的定義 棧作為一種限定性線性表，是將線性表的插入和刪除運(yùn)算限制為僅在表的一端進(jìn)行，通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱為棧頂指針的位置指示器指示。同時(shí)表的另一端被稱為棧底(Bottom)。當(dāng)棧中沒有元素時(shí)稱為空棧。棧的插入操作被形象地稱為進(jìn)?；蛉霔?，刪除操作稱為出棧或退棧。 第 3 章 限定性線性表?xiàng)：完?duì)列 圖圖3.1 棧棧 ana2a1進(jìn)棧出棧棧頂棧底進(jìn)棧出棧(a)

2、 棧的示意圖(b) 鐵路調(diào)序棧的表示第 3 章 限定性線性表?xiàng)：完?duì)列 ADT Stack 數(shù)據(jù)元素?cái)?shù)據(jù)元素： 可以是任意類型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對象。 關(guān)系關(guān)系： 棧中數(shù)據(jù)元素之間是線性關(guān)系。 基本操作：基本操作： （1） InitStack(S) 操作前提： S為未初始化的棧。 操作結(jié)果： 將S初始化為空棧。 （2） ClearStack(S) 操作前提： 棧S已經(jīng)存在。 操作結(jié)果： 將棧S置成空棧。 第 3 章 限定性線性表?xiàng)：完?duì)列 （3） IsEmpty(S) 操作前提：棧S已經(jīng)存在。 操作結(jié)果：判棧空函數(shù)，若S為空棧，則函數(shù)值為TRUE，否則為FALSE。 （4） IsFull

3、(S) 操作前提： 棧S已經(jīng)存在。 操作結(jié)果： 判棧滿函數(shù)，若S棧已滿，則函數(shù)值為TRUE， 否則為FALSE。 第 3 章 限定性線性表?xiàng)：完?duì)列 （5） Push(S,x) 操作前提：棧S已經(jīng)存在。 操作結(jié)果：在S的頂部插入(亦稱壓入)元素x；若S棧未滿，將x插入棧頂位置，若棧已滿，則返回FALSE，表示操作失敗，否則返回TRUE。 （6） Pop(S, x) 操作前提：棧S已經(jīng)存在。 操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，并用x帶回該值；若棧為空，返回值為FALSE，表示操作失敗，否則返回TRUE。 （7） GetTop(S, x) 操作前提： 棧S已經(jīng)存在。 操作結(jié)果：取棧S的頂部元

4、素。與Pop(S, x)不同之處在于GetTop(S,x)不改變棧頂?shù)奈恢谩?第 3 章 限定性線性表?xiàng)：完?duì)列 3.1.2 棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 1. 順序棧順序棧 順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性， 還必須附設(shè)一個(gè)位置指針top（棧頂指針）來動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧。順序棧的存儲(chǔ)結(jié)構(gòu)可以用C語言中的一維數(shù)組來表示。 棧的順序存儲(chǔ)結(jié)構(gòu)定義如下： 第 3 章 限定性線性表?xiàng)：完?duì)列 define TRUE 1define FALSE 0define Stack-Size

5、 50typedef struct StackElementType elemStack-Size; /*用來存放棧中元素的一維數(shù)組*/ int top; /*用來存放棧頂元素的下標(biāo)*/SeqStack; 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.2 順序棧中的進(jìn)棧和出棧 第 3 章 限定性線性表?xiàng)：完?duì)列 順序?；静僮鞯膶?shí)現(xiàn)如下:(1) 初始化。 void InitStack(SeqStack *S)/*構(gòu)造一個(gè)空棧S*/ S-top= -1; (2) 判?？铡?int IsEmpty(SeqStack *S) /*判棧S為空棧時(shí)返回值為真， 反之為假*/ return(S-top=-1?TR

6、UE:FALSE); 第 3 章 限定性線性表?xiàng)：完?duì)列 (3) 判棧滿。 int IsFull(SeqStack *S) return(S-top = Stack-Size?TRUE:FALSE); (4) 進(jìn)棧。 int Push(SeqStack *S, StackElementType x) if(S-top= Stack-Size) return(FALSE); /*棧已滿*/ S-top+; S-elemS-top=x; return(TRUE); 第 3 章 限定性線性表?xiàng)：完?duì)列 (5) 出棧。 int Pop(SeqStack * S, StackElementType *x)

7、/* 將棧S的棧頂元素彈出， 放到x所指的存儲(chǔ)空間中 */ if(S-top=-1) /*棧為空*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改棧頂指針 */ return(TRUE); 第 3 章 限定性線性表?xiàng)：完?duì)列 (6) 取棧頂元素。 int GetTop（SeqStack S, StackElementType *x） /* 將棧S的棧頂元素彈出， 放到x所指的存儲(chǔ)空間中， 但棧頂指針保持不變 */ if(S-top=-1) /*棧為空*/ return(FALSE); else *x = S-elemS-top; retur

8、n(TRUE); 第 3 章 限定性線性表?xiàng)：完?duì)列 在棧的共享技術(shù)中最常用的是兩個(gè)棧的共享技術(shù)： 它主要利用了?！皸５孜恢貌蛔儯鴹ｍ斘恢脛?dòng)態(tài)變化”的特性。首先為兩個(gè)棧申請一個(gè)共享的一維數(shù)組空間SM，將兩個(gè)棧的棧底分別放在一維數(shù)組的兩端，分別是0， M-1。 由于兩個(gè)棧頂動(dòng)態(tài)變化，這樣可以形成互補(bǔ)，使得每個(gè)棧可用的最大空間與實(shí)際使用的需求有關(guān)。由此可見，兩棧共享比兩個(gè)棧分別申請M/2的空間利用率高。 兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下： define M 100typedef struct StackElementType StackM; StackElementType top2; /*top0和t

9、op1分別為兩個(gè)棧頂指示器*/DqStack; 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.3 共享?xiàng)?Stack:0M1top0top1第 3 章 限定性線性表?xiàng)：完?duì)列 (1) 初始化操作。 void InitStack(DqStack *S) S-top0=-1; S-top1=M; 第 3 章 限定性線性表?xiàng)：完?duì)列 (2) 進(jìn)棧操作算法。 int Push(DqStack *S, StackElementType x, int i)/*把數(shù)據(jù)元素x壓入i號堆棧*/ if(S-top0+1=S-top1) /*棧已滿*/ return(FALSE); switch(i) case 0: S-t

10、op0+; 第 3 章 限定性線性表?xiàng)：完?duì)列 S-StackS-top0=x; break; case 1: S-top1-; S-StackS-top1=x; break; default: /*參數(shù)錯(cuò)誤*/ return(FALSE) return(TRUE); 第 3 章 限定性線性表?xiàng)：完?duì)列 (3) 出棧操作算法。 int Pop(DqStack *S, StackElementType *x, int i)/* 從i 號堆棧中彈出棧頂元素并送到x中 */ switch(i) case 0: if(S-top0=-1) return(FALSE); *x=S-StackS-top0;

11、S-top0-; break; case 1: if(S-top1=M) return(FALSE); *x=S-StackS-top1; S-top1+; break; default: return(FALSE); return(TRUE); 第 3 章 限定性線性表?xiàng)：完?duì)列 2. 鏈棧鏈棧 圖3.4 鏈棧示意圖 第 3 章 限定性線性表?xiàng)：完?duì)列 鏈棧的結(jié)構(gòu)可用C語言定義如下： typedef struct node StackElementType data; struct node *next; LinkStackNode;typedef LinkStackNode *LinkStac

12、k; 第 3 章 限定性線性表?xiàng)：完?duì)列 (1) 進(jìn)棧操作。 int Push(LinkStack top, StackElementType x)/* 將數(shù)據(jù)元素x壓入棧top中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE); /* 申請空間失敗 */ temp-data=x; temp-next=top-next; top-next=temp; /* 修改當(dāng)前棧頂指針 */ return(TRUE); 第 3 章 限定性線性表?xiàng)?/p>

13、和隊(duì)列 (2) 出棧操作。 int Pop(LinkStack top, StackElementType *x) /* 將棧top的棧頂元素彈出， 放到x所指的存儲(chǔ)空間中 */ LinkStackNode * temp; temp=top-next; if(temp=NULL) /*棧為空*/ return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 釋放存儲(chǔ)空間 */ return(TRUE); 第 3 章 限定性線性表?xiàng)：完?duì)列 3.1.3 棧的應(yīng)用舉例棧的應(yīng)用舉例 1. 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制

14、數(shù)，一個(gè)簡單的轉(zhuǎn)換算法是重復(fù)下述兩步， 直到N等于零： X = N mod d (其中mod為求余運(yùn)算)N = N div d (其中div為整除運(yùn)算) 第 3 章 限定性線性表?xiàng)：完?duì)列 void Conversion(int N)/*對于任意的一個(gè)非負(fù)十進(jìn)制數(shù)N， 打印出與其等值的二進(jìn)制數(shù)*/ Stack S; int x; /* S為順序?；蜴湕?*/ InitStack(&S); while(N0) x=N%2; Push(&S, x); /* 將轉(zhuǎn)換后的數(shù)字壓入棧S */ N=N/2; while(！IsEmpty(S) Pop(&S,&x); prin

15、tf(%d,x); 第 3 章 限定性線性表?xiàng)：完?duì)列 2. 括號匹配問題括號匹配問題 假設(shè)表達(dá)式中包含三種括號：圓括號、 方括號和花括號， 它們可互相嵌套， 如( ( ) )或( ( ( ) ) )等均為正確的格式， 而 ) 或 ( ) 或( 均為不正確的格式。 在檢驗(yàn)算法中可設(shè)置一個(gè)棧， 每讀入一個(gè)括號，若是左括號，則直接入棧， 等待相匹配的同類右括號；若讀入的是右括號， 且與當(dāng)前棧頂?shù)淖罄ㄌ柾愋?，則二者匹配， 將棧頂?shù)淖罄ㄌ柍鰲＃?否則屬于不合法的情況。另外，如果輸入序列已讀盡，而棧中仍有等待匹配的左括號，或者讀入了一個(gè)右括號，而棧中已無等待匹配的左括號，均屬不合法的情況。當(dāng)輸入序列和棧

16、同時(shí)變?yōu)榭諘r(shí)， 說明所有括號完全匹配。 第 3 章 限定性線性表?xiàng)：完?duì)列 void BracketMatch(char *str) =/* str中為輸入的字符串， 利用堆棧技術(shù)來檢查該字符串中的括號是否匹配*/ = Stack S; int i; char ch; InitStack(&S); For(i=0; stri!KG-*2=0; i+) /*對字符串中的字符逐一掃描*/ switch(stri) case (: case : case : 第 3 章 限定性線性表?xiàng)：完?duì)列 Push(&S,stri); break; case ): case : case : if(

17、IsEmpty(S) printf(n右括號多余!); return; else GetTop(&S,&ch); if(Match(ch,stri) /*用Match判斷兩個(gè)括號是否匹配*/ Pop(&S,&ch); /*已匹配的左括號出棧*/ 第 3 章 限定性線性表?xiàng)：完?duì)列 else printf(n對應(yīng)的左右括號不同類!); return; /*switch*/ /*for*/ if(IsEmpty(S) printf(n括號匹配!); else printf(n左括號多余!); 第 3 章 限定性線性表?xiàng)：完?duì)列 3. 表達(dá)式求值表達(dá)式求值 表達(dá)式求值是高

18、級語言編譯中的一個(gè)基本問題， 是棧的典型應(yīng)用實(shí)例。 任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、 運(yùn)算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)， 也可以是被說明為變量或常量的標(biāo)識符；運(yùn)算符可以分為算術(shù)運(yùn)算符、 關(guān)系運(yùn)算符和邏輯運(yùn)算符三類；基本界限符有左右括號和表達(dá)式結(jié)束符等。 第 3 章 限定性線性表?xiàng)：完?duì)列 1） 無括號算術(shù)表達(dá)式求值 表達(dá)式計(jì)算表達(dá)式計(jì)算 程序設(shè)計(jì)語言中都有計(jì)算表達(dá)式的問題， 這是語言編譯中的典型問題。 (1) 表達(dá)式形式： 由運(yùn)算對象、 運(yùn)算符及必要的表達(dá)式括號組成； (2) 表達(dá)式運(yùn)算： 運(yùn)算時(shí)要有一個(gè)正確的運(yùn)算形式順序。由于某些

19、運(yùn)算符可能具有比別的運(yùn)算符更高的優(yōu)先級，因此表達(dá)式不可能嚴(yán)格的從左到右， 見圖3.5。 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.5 表達(dá)式運(yùn)算及運(yùn)算符優(yōu)先級 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.6 無括號算術(shù)表達(dá)式的處理過程 置空棧OVS、OPTR讀字符WW是操作符OPTR棧空W優(yōu)先級OPTR棧頂優(yōu)先級取OVS頂、次頂和OPTR頂，形成運(yùn)算結(jié)果T(i),然后退OVS頂、次頂和OPTR頂，將T(i)置入OVS棧頂進(jìn)OVS進(jìn)OPTR棧W # 結(jié)束NYYYNYNN第 3 章 限定性線性表?xiàng)：完?duì)列 2） 算術(shù)表達(dá)式處理規(guī)則 (1) 規(guī)定優(yōu)先級表。 (2) 設(shè)置兩個(gè)棧： OVS(運(yùn)算數(shù)棧)和OPTR

20、(運(yùn)算符棧)。 (3) 自左向右掃描，遇操作數(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 章 限定性線性表?xiàng)：完?duì)列 圖3.7 A/BC+D*E運(yùn)算過程的棧區(qū)變化情況示意圖 CBAOVS/OPTROPTR生成BC，運(yùn)算結(jié)果T(1)T(1)AOVS/OPTROPTR/生成A/T(1),運(yùn)算結(jié)果T(2)T(2)/OPTR為空，進(jìn)棧DT(2)右邊界#OPTR * 生成D*E， 運(yùn)

21、算結(jié)果T(3)T(3)T(2)生成T(3)T(2)， 得到T(4)T(4)E*右邊界#OPTR第 3 章 限定性線性表?xiàng)：完?duì)列 3） 帶括號算術(shù)表達(dá)式 假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符， 界限符有左右括號和表達(dá)式起始、結(jié)束符“”，如： （7+15）*（23-28/4）。 引入表達(dá)式起始、 結(jié)束符是為了方便。 要對一個(gè)簡單的算術(shù)表達(dá)式求值， 首先要了解算術(shù)四則運(yùn)算的規(guī)則， 即： (1) 從左算到右； (2) 先乘除， 后加減； (3) 先括號內(nèi)， 后括號外。 第 3 章 限定性線性表?xiàng)：完?duì)列 運(yùn)算符和界限符可統(tǒng)稱為算符，它們構(gòu)成的集合命名為OPS。根據(jù)上述三條運(yùn)算規(guī)則，

22、在運(yùn)算過程中，任意兩個(gè)前后相繼出現(xiàn)的算符1和2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一： 12， 1的優(yōu)先權(quán)高于2。 第 3 章 限定性線性表?xiàng)：完?duì)列 表表 3-1 算符之間的優(yōu)先關(guān)系算符之間的優(yōu)先關(guān)系 第 3 章 限定性線性表?xiàng)：完?duì)列 實(shí)現(xiàn)算符優(yōu)先算法時(shí)需要使用兩個(gè)工作棧： 一個(gè)稱作operator， 用以存放運(yùn)算符；另一個(gè)稱作operand，用以存放操作數(shù)或運(yùn)算的中間結(jié)果。 算法的基本過程如下： 首先初始化操作數(shù)棧operand和運(yùn)算符棧operator， 并將表達(dá)式起始符“”壓入運(yùn)算符棧； 依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)則直接進(jìn)入操作數(shù)棧operand， 若是運(yùn)算符，則與運(yùn)算符棧ope

23、rator的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)比較，并做如下處理： 第 3 章 限定性線性表?xiàng)：完?duì)列 (1) 若棧頂運(yùn)算符的優(yōu)先級低于剛讀入的運(yùn)算符， 則讓剛讀入的運(yùn)算符進(jìn)operator棧； (2) 若棧頂運(yùn)算符的優(yōu)先級高于剛讀入的運(yùn)算符，則將棧頂運(yùn)算符退棧，送入，同時(shí)將操作數(shù)棧operand退棧兩次，得到兩個(gè)操作數(shù)a、b，對a、 b進(jìn)行運(yùn)算后， 將運(yùn)算結(jié)果作為中間結(jié)果推入operand棧； (3) 若棧頂運(yùn)算符的優(yōu)先級與剛讀入的運(yùn)算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運(yùn)算符（左括號）退棧即可。 第 3 章 限定性線性表?xiàng)：完?duì)列 算法具體描述如下： int ExpEvaluation()/*讀入一

24、個(gè)簡單算術(shù)表達(dá)式并計(jì)算其值。 operator和operand分別為運(yùn)算符棧和運(yùn)算數(shù)棧， OPS為運(yùn)算符集合*/ InitStack(&operand); InitStack(&operator); Push(&operator,); printf(nnPlease input an expression(Ending with ) :); ch=getchar(); while(ch!=|GetTop(operator)! =) /* GetTop()通過函數(shù)值返回棧頂元素*/ 第 3 章 限定性線性表?xiàng)：完?duì)列 if(!In(ch,OPS) a=GetNumber(&

25、amp;ch); /* 用ch逐個(gè)讀入操作數(shù)的各位數(shù)碼， 并轉(zhuǎn)化為十進(jìn)制數(shù)a */ Push(&operand,a); else switch(Compare(GetTop(operator),ch) case : Pop(&operator,&op); 第 3 章 限定性線性表?xiàng)：完?duì)列 Pop(&operand,&b); Pop(&operand,&a); v=Execute(a,op,b); /* 對a和b進(jìn)行op運(yùn)算 */ Push(&operand,v); break; v=GetTop(operand); return(

26、v); 第 3 章 限定性線性表?xiàng)：完?duì)列 3.1.4 棧與遞歸的實(shí)現(xiàn)棧與遞歸的實(shí)現(xiàn) 棧非常重要的一個(gè)應(yīng)用是在程序設(shè)計(jì)語言中用來實(shí)現(xiàn)遞歸。 遞歸遞歸是指在定義自身的同時(shí)又出現(xiàn)了對自身的調(diào)用。 如果一個(gè)函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱其為直接遞直接遞歸函數(shù)歸函數(shù)；如果一個(gè)函數(shù)經(jīng)過一系列的中間調(diào)用語句， 通過其它函數(shù)間接調(diào)用自己，則稱其為間間接遞歸函數(shù)接遞歸函數(shù)。 第 3 章 限定性線性表?xiàng)：完?duì)列 1. 遞歸特性問題遞歸特性問題 1) 遞歸函數(shù)例如， 很多數(shù)學(xué)函數(shù)是遞歸定義的， 如二階Fibonacci數(shù)列： 第 3 章 限定性線性表?xiàng)：完?duì)列 第 3 章 限定性線性表?xiàng)：完?duì)列 2) 遞歸結(jié)構(gòu)遞歸結(jié)

27、構(gòu) 例例：n階Hanoi塔問題：假設(shè)有三個(gè)分別命名為X、Y和Z的塔座， 在塔座X上插有n個(gè)直徑大小各不相同、依小到大編號為1， 2, ， n的圓盤?，F(xiàn)要求將X軸上的n個(gè)圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動(dòng)時(shí)必須遵循下列原則： (1) 每次只能移動(dòng)一個(gè)圓盤； (2) 圓盤可以插在X、 Y和Z中的任何一個(gè)塔座上； (3) 任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。 第 3 章 限定性線性表?xiàng)：完?duì)列 如何實(shí)現(xiàn)移動(dòng)圓盤的操作呢？當(dāng)n=1時(shí)，問題比較簡單，只要將編號為1的圓盤從塔座X直接移動(dòng)到塔座Z上即可；當(dāng)n1時(shí)， 需利用塔座Y作輔助塔座， 若能設(shè)法將壓在編號為n的圓盤上的n-1個(gè)圓盤

28、從塔座X(依照上述原則)移至塔座Y上， 則可先將編號為n的圓盤從塔座X 移至塔座Z上，然后再將塔座Y上的n-1個(gè)圓盤(依照上述原則)移至塔座Z上。而如何將n-1個(gè)圓盤從一個(gè)塔座移至另一個(gè)塔座問題是一個(gè)和原問題具有相同特征屬性的問題，只是問題的規(guī)模小個(gè)1，因此可以用同樣方法求解。 由此可得如下算法所示的求解n階Hanoi塔問題的函數(shù)。 第 3 章 限定性線性表?xiàng)：完?duì)列 void hanoi(int n,char x,char y,char z) /*將塔座X上按直徑由小到大且至上而下編號為1至n的n個(gè)圓盤按規(guī)則搬到塔座Z上， Y可用作輔助塔座 */ if(n=1) move(x,1,z); /*

29、 將編號為1的圓盤從X移動(dòng)Z */ else hanoi(n-1,x,z,y); /* 將X上編號為1至n-1的圓盤移到Y(jié),Z作輔助塔 */ move(x,n,z); /* 將編號為n的圓盤從X移到Z */ hanoi(n-1,y,x,z); /* 將Y上編號為1至n-1的圓盤移動(dòng)到Z， X作輔助塔 */ 第 3 章 限定性線性表?xiàng)：完?duì)列 下面給出三個(gè)盤子搬動(dòng)時(shí)hanoi(3, A, B, C) 遞歸調(diào)用過程， 如圖3.8所示。 hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1號搬到C move(A-B) 2號搬到B hanoi(1,C,A,B) move(

30、C-B) 1號搬到B move(A-c) 3號搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B-A) 1號搬到A move(B-c) 2號搬到C hanoi(1,A,B,C) move(A-C) 1號搬到C 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.8 Hanoi塔的遞歸函數(shù)運(yùn)行示意圖 321a321abc321abc321abc321abcbc321abc321abc321abc第 3 章 限定性線性表?xiàng)：完?duì)列 3) 遞歸問題的優(yōu)點(diǎn) 通過上面的例子可看出，遞歸既是強(qiáng)有力的數(shù)學(xué)方法， 也是程序設(shè)計(jì)中一個(gè)很有用的工具。其特點(diǎn)是對遞歸問題描述簡捷，結(jié)構(gòu)清晰，程序的正

31、確性容易證明。 4) 遞歸算法求解問題的要素 遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。 遞歸算法的要點(diǎn)如下： (1) 問題具有類同自身的子問題的性質(zhì)， 被定義項(xiàng)在定義中的應(yīng)用具有更小的尺度。 (2) 被定義項(xiàng)在最小尺度上有直接解。 第 3 章 限定性線性表?xiàng)：完?duì)列 設(shè)計(jì)遞歸算法的方法是： (1) 尋找方法，將問題化為原問題的子問題求解（例n!=n*(n-1)!）。 (2) 設(shè)計(jì)遞歸出口，確定遞歸終止條件(例求解n!時(shí)，當(dāng)n=1時(shí)，n! =1)。 第 3 章 限定性線性表?xiàng)：完?duì)列 5) 遞歸過程的實(shí)現(xiàn) 遞歸進(jìn)層（ii+1層）系統(tǒng)需要做三件事： (1) 保留本層參數(shù)與返回地址（將所有的實(shí)

32、在參數(shù)、 返回地址等信息傳遞給被調(diào)用函數(shù)保存）； (2) 給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)）； (3) 將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。 第 3 章 限定性線性表?xiàng)：完?duì)列 而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，遞歸退層（ii+1層）系統(tǒng)也應(yīng)完成三件工作： (1) 保存被調(diào)函數(shù)的計(jì)算結(jié)果； (2) 恢復(fù)上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）； (3) 依照被調(diào)函數(shù)保存的返回地址， 將控制轉(zhuǎn)移回調(diào)用函數(shù)。 第 3 章 限定性線性表?xiàng)：完?duì)列 2. 遞歸算法到非遞歸算法轉(zhuǎn)換遞歸算法到非遞歸算法轉(zhuǎn)換 遞歸算法具有兩個(gè)特性： (1) 遞歸算法是一種分而治之、把復(fù)雜問題分解為簡單問題的求解問題方法，對求解某

33、些復(fù)雜問題，遞歸算法的分析方法是有效的。 （2） 遞歸算法的時(shí)間效率低。 第 3 章 限定性線性表?xiàng)：完?duì)列 1) 消除遞歸的原因 其一：有利于提高算法時(shí)空性能，因?yàn)檫f歸執(zhí)行時(shí)需要系統(tǒng)提供隱式棧實(shí)現(xiàn)遞歸，效率低且費(fèi)時(shí)。 其二： 無應(yīng)用遞歸語句的語言設(shè)施環(huán)境條件，有些計(jì)算機(jī)語言不支持遞歸功能，如FORTRAN、 C語言中無遞歸機(jī)制 。 其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時(shí)不合適， 也存在一個(gè)把遞歸算法轉(zhuǎn)化為非遞歸算法的需求。 第 3 章 限定性線性表?xiàng)：完?duì)列 2) 簡單遞歸（尾遞歸和單向遞歸）消除 在簡單情況下， 將遞歸算法可簡化為線性序列執(zhí)行， 可直接轉(zhuǎn)換為循環(huán)實(shí)現(xiàn)。 例：例： )!1

34、(*0!nnnn=最小尺度(由自然數(shù)1直接定義) n1 第 3 章 限定性線性表?xiàng)：完?duì)列 其遞歸算法如下， int f(int n ) /*設(shè)n0 */ if n=0 then return(1) else return(n*f(n-1)； 第 3 章 限定性線性表?xiàng)：完?duì)列 圖圖3.9 遞歸調(diào)用變化情況示意遞歸調(diào)用變化情況示意 棧：調(diào) f(2) 前調(diào) f(1) 后2r3r返 f(1) 后2r3r返 f(3) 前調(diào) f(2) 后3r調(diào) f(0) 后2r3r1r返 f(2) 后3rf(3)f(2)f(1)f(0)6213*22*11第 3 章 限定性線性表?xiàng)：完?duì)列 遞歸進(jìn)層三件事： 保存本層參數(shù)、

35、 返回地址; ;傳遞參數(shù)， 分配局部數(shù)據(jù)空間;控制轉(zhuǎn)移。遞歸退層三件事： 恢復(fù)上層；傳遞結(jié)果；轉(zhuǎn)斷點(diǎn)執(zhí)行。 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.10 f(3)遞歸調(diào)用流程變化示意 f(3)f(2)f(1)f(0)3*22*111自下而上返回階段自上而下遞歸進(jìn)層階段第 3 章 限定性線性表?xiàng)：完?duì)列 由圖3.11可看出，整個(gè)計(jì)算包括自上而下遞歸調(diào)用進(jìn)層和自下而上遞歸返回退層兩個(gè)階段，所有遞歸調(diào)用直接或間接依賴f(0)，所以整個(gè)階段分兩步，計(jì)算順序在第二階段，先計(jì)算f(0)f(1)f(n),工作變量y記錄中間結(jié)果。 例： 斐波那契數(shù)列 )2() 1(10)(nFibnFibnFib210nnn第

36、 3 章 限定性線性表?xiàng)：完?duì)列 斐波那契數(shù)列的遞歸算法Fib(n)如下， Fib(int n) if（n= =0|n= =1） return n; /* 遞歸出口 */ else return Fib(n-1)+Fib(n-2); /* 遞歸調(diào)用 */ 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.11 Fib(5)遞歸調(diào)用過程示意 Fib(2)Fib(1)Fib(1)Fib(0)Fib(1)Fib(0)Fib(3)Fib(2)Fib(2)Fib(1)Fib(4)Fib(3)Fib(5)Fib(1)Fib(0)第 3 章 限定性線性表?xiàng)：完?duì)列 Fib(5)Fib(3)Fib(1)Fib(4)Fib(

37、2)Fib(0)3-12 Fib(5)循環(huán)調(diào)用過程示意圖第 3 章 限定性線性表?xiàng)：完?duì)列 單向遞歸單向遞歸的一個(gè)典型例子是我們討論過的計(jì)算斐波那契數(shù)列的算法Fib(n)。 其中，遞歸調(diào)用語句Fib(n-1)和Fib(n-2)只與主調(diào)用函數(shù)Fib(n)有關(guān)，相互之間參數(shù)無關(guān)，并且這些遞歸調(diào)用語句也和尾遞歸一樣處于算法的最后。 int Fib(int n): int x,y,z; if（n=0|n=1） return n; /*計(jì)算 Fib(0) , Fib(1) */ else int x=0, y=1,z; 第 3 章 限定性線性表?xiàng)：完?duì)列 / * x=Fib(0), y=Fib(1) */

38、for( i=2;i= n; i + ) z=y; /* z=Fib(i-1) */ = y=x+y; /* y=Fib(i-1)+Fib(i-2)， 求Fib(i)，形成第i項(xiàng) */ x=z; /* x=Fib(i-1) */ return y ; 第 3 章 限定性線性表?xiàng)：完?duì)列 尾遞歸尾遞歸 是指遞歸調(diào)用語句只有一個(gè)，而且是處于算法的最后。 我們以階乘問題的遞歸算法Fact(n)為例討論尾遞歸算法的運(yùn)行過程。為討論方便， 我們列出階乘問題的遞歸算法Fact(n)， 并簡化掉參數(shù)n的出錯(cuò)檢查語句， 改寫遞歸調(diào)用語句的位置在最后，算法如下： long Fact(int n) if(n=0)

39、return 1; return n * Fact(n-1); 第 3 章 限定性線性表?xiàng)：完?duì)列 循環(huán)結(jié)構(gòu)的階乘問題算法Fact(n)如下： long Fact(int n) int fac=1; for(int i=1;ifront=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(Q-front! =NULL) Q-rear=Q-front; Q-front-next=NULL; return(TRUE); else return(FALSE); /* 溢出！*/ 第 3 章 限定性線性表?xiàng)：完?duì)列 （2） 入隊(duì)操作。 int EnterQu

40、eue(LinkQueue *Q, QueueElementType x) /* 將數(shù)據(jù)元素x插入到隊(duì)列Q中 */ LinkQueueNode *NewNode; NewNode=(LinkQueueNode * )malloc(sizeof(LinkQueueNode); if(NewNode! =NULL) NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return(TRUE); else return(FALSE); /* 溢出！*/ 第 3 章 限定性線性表?xiàng)：完?duì)列 （3） 出隊(duì)操作。 i

41、nt DeleteQueue(LinkQueue * Q, QueueElementType *x) /* 將隊(duì)列Q的隊(duì)頭元素出隊(duì)， 并存放到x所指的存儲(chǔ)空間中 */ LinkQueueNode *p; if(Q-front=Q-rear) return(FALSE); p=Q-front-next; Q-front-next=p-next; /* 隊(duì)頭元素p出隊(duì) */ if(Q-rear=p) /* 如果隊(duì)中只有一個(gè)元素p， 則p出隊(duì)后成為空隊(duì) */ Q-rear=Q-front; *x=p-data; free(p); /* 釋放存儲(chǔ)空間 */ return(TRUE); 第 3 章 限定

42、性線性表?xiàng)：完?duì)列 2. 循環(huán)隊(duì)列循環(huán)隊(duì)列 圖3.14 隊(duì)列的基本操作 Queue6543210rearfront(1) 空隊(duì)列543210rearfrontcbad(2) a、b、c、d依次入隊(duì)543210rearfrontd(3) a、b、c出隊(duì)543210rearfrontdef(4) e、f入 隊(duì)第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.15 循環(huán)隊(duì)列 012354rearfront(a) 空隊(duì)列012354e6e7e8e3e4e5012354(b) 隊(duì)列滿(b) 一般情況frontreare3e4e5frontrear第 3 章 限定性線性表?xiàng)：完?duì)列 循環(huán)隊(duì)列的類型定義： define

43、MAXSIZE 50 /*隊(duì)列的最大長度*/typedef struct QueueElementType elementMAXSIZE; /* 隊(duì)列的元素空間*/ int front; /*頭指針指示器*/ int rear ; /*尾指針指示器*/SeqQueue; 第 3 章 限定性線性表?xiàng)：完?duì)列 （1） 初始化操作。 void InitQueue（SeqQueue *Q） /* 將*Q初始化為一個(gè)空的循環(huán)隊(duì)列 */ Q-front=Q-rear=0; 第 3 章 限定性線性表?xiàng)：完?duì)列 （2） 入隊(duì)操作。 int EnterQueue(SeqQueue *Q, QueueElementT

44、ype x) /*將元素x入隊(duì)*/ if(Q-rear+1)%MAXSIZE=Q-front) /*隊(duì)列已經(jīng)滿了*/ return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新設(shè)置隊(duì)尾指針 */ return(TRUE); /*操作成功*/ 第 3 章 限定性線性表?xiàng)：完?duì)列 （3） 出隊(duì)操作。 int DeleteQueue(SeqQueue *Q, QueueElementType *x) /*刪除隊(duì)列的隊(duì)頭元素， 用x返回其值*/ if（Q-front=Q-rear） /*隊(duì)列為空*/ return(FALSE);

45、*x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新設(shè)置隊(duì)頭指針*/ return(TRUE); /*操作成功*/ 第 3 章 限定性線性表?xiàng)：完?duì)列 3.2.3 隊(duì)列的應(yīng)用舉例隊(duì)列的應(yīng)用舉例 1. 打印楊輝三角打印楊輝三角 圖3.16 楊輝三角形 第 3 章 限定性線性表?xiàng)：完?duì)列 圖3.17 楊輝三角形元素入隊(duì)順序 161520156115101051146411331121111第 3 章 限定性線性表?xiàng)：完?duì)列 (1) 第7行的第一個(gè)元素1入隊(duì)。 elementrear=1;rear=(rear +1 )% MAXSIZE;(2) 循環(huán)做以下操作， 產(chǎn)生第7行的中間5個(gè)元素并入隊(duì)。 elementrear=elementfront+element(front+1) %MAXSIZE； rear=(rear +1 )% MAXSIZE;front=(front+1)%MAXSIZE; 第 3 章 限定性線性表?xiàng)：完?duì)列 (3) 第6