數(shù)據(jù)結構第3章

1、第 3 章 棧和隊列 第第3章章 限定性線性表限定性線性表棧和隊列棧和隊列 3.1 棧棧 3.2 隊列隊列 第 3 章 棧和隊列 3.1 棧棧 3.1.1 棧的定義棧的定義 棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表的一端進行，通常將表中允許進行插入、刪除操作的一端稱為棧頂(Top)，因此棧頂?shù)漠斍拔恢檬莿討B(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端被稱為棧底(Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進棧或入棧，刪除操作稱為出?；蛲藯?。 第 3 章 棧和隊列 圖圖3.1 棧棧 ana2a1進棧出棧棧頂棧底進棧出棧(a) 棧的示意圖

2、(b) 鐵路調序棧的表示第 3 章 棧和隊列 ADT Stack 數(shù)據(jù)元素數(shù)據(jù)元素： 可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。 關系關系： 棧中數(shù)據(jù)元素之間是線性關系。 基本操作：基本操作： （1） InitStack(S) 操作前提： S為未初始化的棧。 操作結果： 將S初始化為空棧。 （2） ClearStack(S) 操作前提： 棧S已經(jīng)存在。 操作結果： 將棧S置成空棧。 第 3 章 棧和隊列 （3） IsEmpty(S) 操作前提：棧S已經(jīng)存在。 操作結果：判?？蘸瘮?shù)，若S為空棧，則函數(shù)值為TRUE，否則為FALSE。 （4） IsFull(S) 操作前提： 棧S已經(jīng)存在。

3、操作結果： 判棧滿函數(shù)，若S棧已滿，則函數(shù)值為TRUE， 否則為FALSE。 第 3 章 棧和隊列 （5） Push(S,x) 操作前提：棧S已經(jīng)存在。 操作結果：在S的頂部插入(亦稱壓入)元素x；若S棧未滿，將x插入棧頂位置，若棧已滿，則返回FALSE，表示操作失敗，否則返回TRUE。 （6） Pop(S, x) 操作前提：棧S已經(jīng)存在。 操作結果：刪除(亦稱彈出)棧S的頂部元素，并用x帶回該值；若棧為空，返回值為FALSE，表示操作失敗，否則返回TRUE。 （7） GetTop(S, x) 操作前提： 棧S已經(jīng)存在。 操作結果：取棧S的頂部元素。與Pop(S, x)不同之處在于GetTop

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

5、lemStack-Size; /*用來存放棧中元素的一維數(shù)組*/ int top; /*用來存放棧頂元素的下標*/SeqStack; 第 3 章 棧和隊列 圖3.2 順序棧中的進棧和出棧 第 3 章 棧和隊列 順序?；静僮鞯膶崿F(xiàn)如下:(1) 初始化。 void InitStack(SeqStack *S)/*構造一個空棧S*/ S-top= -1; (2) 判棧空。 int IsEmpty(SeqStack *S) /*判棧S為空棧時返回值為真， 反之為假*/ return(S-top=-1?TRUE:FALSE); 第 3 章 棧和隊列 (3) 判棧滿。 int IsFull(SeqSta

6、ck *S) return(S-top = Stack-Size?TRUE:FALSE); (4) 進棧。 int Push(SeqStack *S, StackElementType x) if(S-top= Stack-Size) return(FALSE); /*棧已滿*/ S-top+; S-elemS-top=x; return(TRUE); 第 3 章 棧和隊列 (5) 出棧。 int Pop(SeqStack * S, StackElementType *x) /* 將棧S的棧頂元素彈出， 放到x所指的存儲空間中 */ if(S-top=-1) /*棧為空*/ return(FA

7、LSE); else *x= S-elemS-top; S-top-; /* 修改棧頂指針 */ return(TRUE); 第 3 章 棧和隊列 (6) 取棧頂元素。 int GetTop（SeqStack S, StackElementType *x） /* 將棧S的棧頂元素彈出， 放到x所指的存儲空間中， 但棧頂指針保持不變 */ if(S-top=-1) /*棧為空*/ return(FALSE); else *x = S-elemS-top; return(TRUE); 第 3 章 棧和隊列 在棧的共享技術中最常用的是兩個棧的共享技術： 它主要利用了?！皸５孜恢貌蛔儯鴹ｍ斘恢脛討B(tài)變

8、化”的特性。首先為兩個棧申請一個共享的一維數(shù)組空間SM，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0， M-1。 由于兩個棧頂動態(tài)變化，這樣可以形成互補，使得每個?？捎玫淖畲罂臻g與實際使用的需求有關。由此可見，兩棧共享比兩個棧分別申請M/2的空間利用率高。 兩棧共享的數(shù)據(jù)結構定義如下： define M 100typedef struct StackElementType StackM; StackElementType top2; /*top0和top1分別為兩個棧頂指示器*/DqStack; 第 3 章 棧和隊列 圖3.3 共享棧 Stack:0M1top0top1第 3 章 棧和隊列

9、(1) 初始化操作。 void InitStack(DqStack *S) S-top0=-1; S-top1=M; 第 3 章 棧和隊列 (2) 進棧操作算法。 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-top0+; 第 3 章 棧和隊列 S-StackS-top0=x; break; case 1: S-top1-; S-StackS-top1=x; break; default:

10、 /*參數(shù)錯誤*/ return(FALSE) return(TRUE); 第 3 章 棧和隊列 (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; S-top0-; break; case 1: if(S-top1=M) return(FALSE); *x=S-StackS-top1; S-top1+; break; default: return(

11、FALSE); return(TRUE); 第 3 章 棧和隊列 2. 鏈棧鏈棧 圖3.4 鏈棧示意圖 第 3 章 棧和隊列 鏈棧的結構可用C語言定義如下： typedef struct node StackElementType data; struct node *next; LinkStackNode;typedef LinkStackNode *LinkStack; 第 3 章 棧和隊列 (1) 進棧操作。 int Push(LinkStack top, StackElementType x)/* 將數(shù)據(jù)元素x壓入棧top中 */ LinkStackNode * temp; temp=

12、(LinkStackNode * )malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE); /* 申請空間失敗 */ temp-data=x; temp-next=top-next; top-next=temp; /* 修改當前棧頂指針 */ return(TRUE); 第 3 章 棧和隊列 (2) 出棧操作。 int Pop(LinkStack top, StackElementType *x) /* 將棧top的棧頂元素彈出， 放到x所指的存儲空間中 */ LinkStackNode * temp; temp=top-next;

13、 if(temp=NULL) /*棧為空*/ return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 釋放存儲空間 */ return(TRUE); 第 3 章 棧和隊列 3.1.3 棧的應用舉例棧的應用舉例 1. 數(shù)制轉換數(shù)制轉換 假設要將十進制數(shù)N轉換為d進制數(shù)，一個簡單的轉換算法是重復下述兩步， 直到N等于零： X = N mod d (其中mod為求余運算)N = N div d (其中div為整除運算) 第 3 章 棧和隊列 void Conversion(int N)/*對于任意的一個非負十進制數(shù)N， 打印出與

14、其等值的二進制數(shù)*/ Stack S; int x; /* S為順序?；蜴湕?*/ InitStack(&S); while(N0) x=N%2; Push(&S, x); /* 將轉換后的數(shù)字壓入棧S */ N=N/2; while(！IsEmpty(S) Pop(&S,&x); printf(%d,x); 第 3 章 棧和隊列 2. 括號匹配問題括號匹配問題 假設表達式中包含三種括號：圓括號、 方括號和花括號， 它們可互相嵌套， 如( ( ) )或( ( ( ) ) )等均為正確的格式， 而 ) 或 ( ) 或( 均為不正確的格式。 在檢驗算法中可設置一個棧

15、， 每讀入一個括號，若是左括號，則直接入棧， 等待相匹配的同類右括號；若讀入的是右括號， 且與當前棧頂?shù)淖罄ㄌ柾愋?，則二者匹配， 將棧頂?shù)淖罄ㄌ柍鰲＃?否則屬于不合法的情況。另外，如果輸入序列已讀盡，而棧中仍有等待匹配的左括號，或者讀入了一個右括號，而棧中已無等待匹配的左括號，均屬不合法的情況。當輸入序列和棧同時變?yōu)榭諘r， 說明所有括號完全匹配。 第 3 章 棧和隊列 void BracketMatch(char *str) =/* str中為輸入的字符串， 利用堆棧技術來檢查該字符串中的括號是否匹配*/ = Stack S; int i; char ch; InitStack(&S

16、); For(i=0; stri!KG-*2=0; i+) /*對字符串中的字符逐一掃描*/ switch(stri) case (: case : case : 第 3 章 棧和隊列 Push(&S,stri); break; case ): case : case : if(IsEmpty(S) printf(n右括號多余!); return; else GetTop(&S,&ch); if(Match(ch,stri) /*用Match判斷兩個括號是否匹配*/ Pop(&S,&ch); /*已匹配的左括號出棧*/ 第 3 章 棧和隊列 else p

17、rintf(n對應的左右括號不同類!); return; /*switch*/ /*for*/ if(IsEmpty(S) printf(n括號匹配!); else printf(n左括號多余!); 第 3 章 棧和隊列 3. 表達式求值表達式求值 表達式求值是高級語言編譯中的一個基本問題， 是棧的典型應用實例。 任何一個表達式都是由操作數(shù)(operand)、 運算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)， 也可以是被說明為變量或常量的標識符；運算符可以分為算術運算符、 關系運算符和邏輯運算符三類；基本界限符有左右括號和表達式結束符等。 第 3 章 棧和隊

18、列 1） 無括號算術表達式求值 表達式計算表達式計算 程序設計語言中都有計算表達式的問題， 這是語言編譯中的典型問題。 (1) 表達式形式： 由運算對象、 運算符及必要的表達式括號組成； (2) 表達式運算： 運算時要有一個正確的運算形式順序。由于某些運算符可能具有比別的運算符更高的優(yōu)先級，因此表達式不可能嚴格的從左到右， 見圖3.5。 第 3 章 棧和隊列 圖3.5 表達式運算及運算符優(yōu)先級 第 3 章 棧和隊列 圖3.6 無括號算術表達式的處理過程 置空棧OVS、OPTR讀字符WW是操作符OPTR?？誛優(yōu)先級OPTR棧頂優(yōu)先級取OVS頂、次頂和OPTR頂，形成運算結果T(i),然后退OVS

19、頂、次頂和OPTR頂，將T(i)置入OVS棧頂進OVS進OPTR棧W # 結束NYYYNYNN第 3 章 棧和隊列 2） 算術表達式處理規(guī)則 (1) 規(guī)定優(yōu)先級表。 (2) 設置兩個棧： OVS(運算數(shù)棧)和OPTR(運算符棧)。 (3) 自左向右掃描，遇操作數(shù)進OVS，遇操作符則與OPTR棧頂優(yōu)先數(shù)比較：當前操作符OPTR棧頂, 當前操作符進OPTR棧當前操作符OPTR棧頂，OVS棧頂、次頂和OPTR棧頂，退棧形成運算T(i)，T(i)進OVS棧。 例： 實現(xiàn)A/BC+D*E的運算過程時棧區(qū)變化情況如圖3.7所示。 第 3 章 棧和隊列 圖3.7 A/BC+D*E運算過程的棧區(qū)變化情況示意圖

20、 CBAOVS/OPTROPTR生成BC，運算結果T(1)T(1)AOVS/OPTROPTR/生成A/T(1),運算結果T(2)T(2)/OPTR為空，進棧DT(2)右邊界#OPTR * 生成D*E， 運算結果T(3)T(3)T(2)生成T(3)T(2)， 得到T(4)T(4)E*右邊界#OPTR第 3 章 棧和隊列 3） 帶括號算術表達式 假設操作數(shù)是整型常數(shù)，運算符只含加、減、乘、除等四種運算符， 界限符有左右括號和表達式起始、結束符“”，如： （7+15）*（23-28/4）。 引入表達式起始、 結束符是為了方便。 要對一個簡單的算術表達式求值， 首先要了解算術四則運算的規(guī)則， 即： (

21、1) 從左算到右； (2) 先乘除， 后加減； (3) 先括號內， 后括號外。 第 3 章 棧和隊列 運算符和界限符可統(tǒng)稱為算符，它們構成的集合命名為OPS。根據(jù)上述三條運算規(guī)則，在運算過程中，任意兩個前后相繼出現(xiàn)的算符1和2之間的優(yōu)先關系必為下面三種關系之一： 12， 1的優(yōu)先權高于2。 第 3 章 棧和隊列 表表 3-1 算符之間的優(yōu)先關系算符之間的優(yōu)先關系 第 3 章 棧和隊列 實現(xiàn)算符優(yōu)先算法時需要使用兩個工作棧： 一個稱作operator， 用以存放運算符；另一個稱作operand，用以存放操作數(shù)或運算的中間結果。 算法的基本過程如下： 首先初始化操作數(shù)棧operand和運算符棧op

22、erator， 并將表達式起始符“”壓入運算符棧； 依次讀入表達式中的每個字符，若是操作數(shù)則直接進入操作數(shù)棧operand， 若是運算符，則與運算符棧operator的棧頂運算符進行優(yōu)先權比較，并做如下處理： 第 3 章 棧和隊列 (1) 若棧頂運算符的優(yōu)先級低于剛讀入的運算符， 則讓剛讀入的運算符進operator棧； (2) 若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧，送入，同時將操作數(shù)棧operand退棧兩次，得到兩個操作數(shù)a、b，對a、 b進行運算后， 將運算結果作為中間結果推入operand棧； (3) 若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左右括號相

23、遇，只需將棧頂運算符（左括號）退棧即可。 第 3 章 棧和隊列 算法具體描述如下： int ExpEvaluation()/*讀入一個簡單算術表達式并計算其值。 operator和operand分別為運算符棧和運算數(shù)棧， OPS為運算符集合*/ InitStack(&operand); InitStack(&operator); Push(&operator,); printf(nnPlease input an expression(Ending with ) :); ch=getchar(); while(ch!=|GetTop(operator)! =) /* G

24、etTop()通過函數(shù)值返回棧頂元素*/ 第 3 章 棧和隊列 if(!In(ch,OPS) a=GetNumber(&ch); /* 用ch逐個讀入操作數(shù)的各位數(shù)碼， 并轉化為十進制數(shù)a */ Push(&operand,a); else switch(Compare(GetTop(operator),ch) case : Pop(&operator,&op); 第 3 章 棧和隊列 Pop(&operand,&b); Pop(&operand,&a); v=Execute(a,op,b); /* 對a和b進行op運算 */ P

25、ush(&operand,v); break; v=GetTop(operand); return(v); 第 3 章 棧和隊列 3.1.4 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) 棧非常重要的一個應用是在程序設計語言中用來實現(xiàn)遞歸。 遞歸遞歸是指在定義自身的同時又出現(xiàn)了對自身的調用。 如果一個函數(shù)在其定義體內直接調用自己，則稱其為直接遞直接遞歸函數(shù)歸函數(shù)；如果一個函數(shù)經(jīng)過一系列的中間調用語句， 通過其它函數(shù)間接調用自己，則稱其為間間接遞歸函數(shù)接遞歸函數(shù)。 第 3 章 棧和隊列 1. 遞歸特性問題遞歸特性問題 1) 遞歸函數(shù)例如， 很多數(shù)學函數(shù)是遞歸定義的， 如二階Fibonacci數(shù)列： 第

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

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

28、1) move(x,1,z); /* 將編號為1的圓盤從X移動Z */ else hanoi(n-1,x,z,y); /* 將X上編號為1至n-1的圓盤移到Y,Z作輔助塔 */ move(x,n,z); /* 將編號為n的圓盤從X移到Z */ hanoi(n-1,y,x,z); /* 將Y上編號為1至n-1的圓盤移動到Z， X作輔助塔 */ 第 3 章 棧和隊列 下面給出三個盤子搬動時hanoi(3, A, B, C) 遞歸調用過程， 如圖3.8所示。 hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1號搬到C move(A-B) 2號搬到B hanoi(1,

29、C,A,B) move(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 章 棧和隊列 圖3.8 Hanoi塔的遞歸函數(shù)運行示意圖 321a321abc321abc321abc321abcbc321abc321abc321abc第 3 章 棧和隊列 3) 遞歸問題的優(yōu)點 通過上面的例子可看出，遞歸既是強有力的數(shù)學方法， 也是程序設計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結構清晰，程序的正

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

31、傳遞給被調用函數(shù)保存）； (2) 給下層參數(shù)賦值（為被調用函數(shù)的局部變量分配存儲區(qū)）； (3) 將程序轉移到被調函數(shù)的入口。 第 3 章 棧和隊列 而從被調用函數(shù)返回調用函數(shù)之前，遞歸退層（ii+1層）系統(tǒng)也應完成三件工作： (1) 保存被調函數(shù)的計算結果； (2) 恢復上層參數(shù)（釋放被調函數(shù)的數(shù)據(jù)區(qū)）； (3) 依照被調函數(shù)保存的返回地址， 將控制轉移回調用函數(shù)。 第 3 章 棧和隊列 2. 遞歸算法到非遞歸算法轉換遞歸算法到非遞歸算法轉換 遞歸算法具有兩個特性： (1) 遞歸算法是一種分而治之、把復雜問題分解為簡單問題的求解問題方法，對求解某些復雜問題，遞歸算法的分析方法是有效的。 （2）

32、 遞歸算法的時間效率低。 第 3 章 棧和隊列 1) 消除遞歸的原因 其一：有利于提高算法時空性能，因為遞歸執(zhí)行時需要系統(tǒng)提供隱式棧實現(xiàn)遞歸，效率低且費時。 其二： 無應用遞歸語句的語言設施環(huán)境條件，有些計算機語言不支持遞歸功能，如FORTRAN、 C語言中無遞歸機制 。 其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時不合適， 也存在一個把遞歸算法轉化為非遞歸算法的需求。 第 3 章 棧和隊列 2) 簡單遞歸（尾遞歸和單向遞歸）消除 在簡單情況下， 將遞歸算法可簡化為線性序列執(zhí)行， 可直接轉換為循環(huán)實現(xiàn)。 例：例： )!1(*0!nnnn=最小尺度(由自然數(shù)1直接定義) n1 第 3 章 棧和

33、隊列 其遞歸算法如下， int f(int n ) /*設n0 */ if n=0 then return(1) else return(n*f(n-1)； 第 3 章 棧和隊列 圖圖3.9 遞歸調用變化情況示意遞歸調用變化情況示意 棧：調 f(2) 前調 f(1) 后2r3r返 f(1) 后2r3r返 f(3) 前調 f(2) 后3r調 f(0) 后2r3r1r返 f(2) 后3rf(3)f(2)f(1)f(0)6213*22*11第 3 章 棧和隊列 遞歸進層三件事： 保存本層參數(shù)、 返回地址; ;傳遞參數(shù)， 分配局部數(shù)據(jù)空間;控制轉移。遞歸退層三件事： 恢復上層；傳遞結果；轉斷點執(zhí)行。

34、第 3 章 棧和隊列 圖3.10 f(3)遞歸調用流程變化示意 f(3)f(2)f(1)f(0)3*22*111自下而上返回階段自上而下遞歸進層階段第 3 章 棧和隊列 由圖3.11可看出，整個計算包括自上而下遞歸調用進層和自下而上遞歸返回退層兩個階段，所有遞歸調用直接或間接依賴f(0)，所以整個階段分兩步，計算順序在第二階段，先計算f(0)f(1)f(n),工作變量y記錄中間結果。 例： 斐波那契數(shù)列 )2() 1(10)(nFibnFibnFib210nnn第 3 章 棧和隊列 斐波那契數(shù)列的遞歸算法Fib(n)如下， Fib(int n) if（n= =0|n= =1） return n

35、; /* 遞歸出口 */ else return Fib(n-1)+Fib(n-2); /* 遞歸調用 */ 第 3 章 棧和隊列 圖3.11 Fib(5)遞歸調用過程示意 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 章 棧和隊列 Fib(5)Fib(3)Fib(1)Fib(4)Fib(2)Fib(0)3-12 Fib(5)循環(huán)調用過程示意圖第 3 章 棧和隊列 單向遞歸單向遞歸的一個典型例子是我們討論過的計算斐波那契數(shù)列的算法Fib(n)。 其中，遞

36、歸調用語句Fib(n-1)和Fib(n-2)只與主調用函數(shù)Fib(n)有關，相互之間參數(shù)無關，并且這些遞歸調用語句也和尾遞歸一樣處于算法的最后。 int Fib(int n): int x,y,z; if（n=0|n=1） return n; /*計算 Fib(0) , Fib(1) */ else int x=0, y=1,z; 第 3 章 棧和隊列 / * x=Fib(0), y=Fib(1) */ 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項 */ x=z

37、; /* x=Fib(i-1) */ return y ; 第 3 章 棧和隊列 尾遞歸尾遞歸 是指遞歸調用語句只有一個，而且是處于算法的最后。 我們以階乘問題的遞歸算法Fact(n)為例討論尾遞歸算法的運行過程。為討論方便， 我們列出階乘問題的遞歸算法Fact(n)， 并簡化掉參數(shù)n的出錯檢查語句， 改寫遞歸調用語句的位置在最后，算法如下： long Fact(int n) if(n=0) return 1; return n * Fact(n-1); 第 3 章 棧和隊列 循環(huán)結構的階乘問題算法Fact(n)如下： long Fact(int n) int fac=1; for(int i

38、=1;ifront=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(Q-front! =NULL) Q-rear=Q-front; Q-front-next=NULL; return(TRUE); else return(FALSE); /* 溢出！*/ 第 3 章 棧和隊列 （2） 入隊操作。 int EnterQueue(LinkQueue *Q, QueueElementType x) /* 將數(shù)據(jù)元素x插入到隊列Q中 */ LinkQueueNode *NewNode; NewNode=(LinkQueueNode * )malloc

39、(sizeof(LinkQueueNode); if(NewNode! =NULL) NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return(TRUE); else return(FALSE); /* 溢出！*/ 第 3 章 棧和隊列 （3） 出隊操作。 int DeleteQueue(LinkQueue * Q, QueueElementType *x) /* 將隊列Q的隊頭元素出隊， 并存放到x所指的存儲空間中 */ LinkQueueNode *p; if(Q-front=Q-rear)

40、 return(FALSE); p=Q-front-next; Q-front-next=p-next; /* 隊頭元素p出隊 */ if(Q-rear=p) /* 如果隊中只有一個元素p， 則p出隊后成為空隊 */ Q-rear=Q-front; *x=p-data; free(p); /* 釋放存儲空間 */ return(TRUE); 第 3 章 棧和隊列 2. 循環(huán)隊列循環(huán)隊列 圖3.14 隊列的基本操作 Queue6543210rearfront(1) 空隊列543210rearfrontcbad(2) a、b、c、d依次入隊543210rearfrontd(3) a、b、c出隊54

41、3210rearfrontdef(4) e、f入 隊第 3 章 棧和隊列 圖3.15 循環(huán)隊列 012354rearfront(a) 空隊列012354e6e7e8e3e4e5012354(b) 隊列滿(b) 一般情況frontreare3e4e5frontrear第 3 章 棧和隊列 循環(huán)隊列的類型定義： define MAXSIZE 50 /*隊列的最大長度*/typedef struct QueueElementType elementMAXSIZE; /* 隊列的元素空間*/ int front; /*頭指針指示器*/ int rear ; /*尾指針指示器*/SeqQueue; 第

42、3 章 棧和隊列 （1） 初始化操作。 void InitQueue（SeqQueue *Q） /* 將*Q初始化為一個空的循環(huán)隊列 */ Q-front=Q-rear=0; 第 3 章 棧和隊列 （2） 入隊操作。 int EnterQueue(SeqQueue *Q, QueueElementType x) /*將元素x入隊*/ if(Q-rear+1)%MAXSIZE=Q-front) /*隊列已經(jīng)滿了*/ return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新設置隊尾指針 */ return(TRUE); /

43、*操作成功*/ 第 3 章 棧和隊列 （3） 出隊操作。 int DeleteQueue(SeqQueue *Q, QueueElementType *x) /*刪除隊列的隊頭元素， 用x返回其值*/ if（Q-front=Q-rear） /*隊列為空*/ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新設置隊頭指針*/ return(TRUE); /*操作成功*/ 第 3 章 棧和隊列 3.2.3 隊列的應用舉例隊列的應用舉例 1. 打印楊輝三角打印楊輝三角 圖3.16 楊輝三角形 第 3 章 棧和隊列 圖3.17 楊輝三角形元素入隊順序 161520156115101051146411331121111第 3 章 棧和隊列 (1) 第7行的第一個元素1入隊。 elementrear=1;rear=(rear +1 )% MAXSIZE;(2) 循環(huán)做以下操作， 產(chǎn)生第7行的中間5個元素并入隊。 elementrear=elementfront+element(front+1) %MAXSIZE； rear=(rear +1 )% MAXSIZE;front=(front+1)%MAXSIZE; 第 3 章 棧和隊列 (3) 第6行的最后一個元素1出隊。 fro