第3章限定性線性表-棧和隊列

1、第第3章章 限定性線性表限定性線性表棧和隊列棧和隊列3.1 棧棧3.2 隊列隊列3.3 總結與提高總結與提高3.1 3.1 棧棧3.1.1 棧的定義棧的定義3.1.2 棧的表示和實現棧的表示和實現3.1.3 棧的應用舉例棧的應用舉例3.1.4 棧與遞歸的實現棧與遞歸的實現棧的定義：棧的定義： 棧作為一種限定性線性表，是將線性表的插入和刪除運算限制為僅在表的一端進行。通常將表中允許進行插入、刪除操作的一端稱為棧頂 (Top)，表的另一端被稱為棧底 (Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔＃瑒h除操作稱為出棧或退棧。 根據棧定義，每次進棧的元素都被放在原棧頂元素

2、之上而成為新的棧頂，而每次出棧的總是當前棧中“最新”的元素，即最后進棧的元素。因此，棧又稱為后進先出的線性表。簡稱為LIFO表。如下圖所示： 進棧、出棧圖例進棧、出棧圖例進棧進棧出棧出棧進棧出棧棧頂棧底ana2a1棧的抽象數據類型定義棧的抽象數據類型定義關系：關系：棧中數據元素之間是棧中數據元素之間是線性關系線性關系數據元素數據元素：可以是任意類型的數據，但必須屬于：可以是任意類型的數據，但必須屬于同同一個數據對象一個數據對象。 基本操作基本操作：InitStack（S） 2. ClearStack（S）3. IsEmpty（S） 4. IsFull（S） 5. Push（S，x） 1. 6.

3、 Pop（S，x） 7. GetTop（S，x）3.1.2 棧的表示和實現棧的表示和實現棧棧在計算機中主要有在計算機中主要有兩種兩種基本的存儲結基本的存儲結構：構：順序存儲結構順序存儲結構和和鏈式存儲結構鏈式存儲結構。順序存儲的棧為順序存儲的棧為順序棧；順序棧；鏈式存儲的棧為鏈式存儲的棧為鏈棧鏈棧。1.1.順序棧順序棧 順序棧是用順序存儲結構實現的棧，即順序棧是用順序存儲結構實現的棧，即利用一組利用一組地址連續(xù)地址連續(xù)的存儲單元依次存放的存儲單元依次存放自棧自棧底到棧頂底到棧頂的數據元素，同時由于棧的操作的的數據元素，同時由于棧的操作的特殊性，還必須附設一個特殊性，還必須附設一個位置指針位置指

4、針top（棧（棧頂指針）來動態(tài)地指示棧頂元素在順序棧中頂指針）來動態(tài)地指示棧頂元素在順序棧中的位置。通常以的位置。通常以top = -1表示空棧。表示空棧。棧的順序存儲結構定義如下棧的順序存儲結構定義如下 ：#define Stack_Size 50typedef struct StackElementType elemStack_Size; /*用來存放棧中元素的一維數組用來存放棧中元素的一維數組*/ int top; /*用來存放棧頂元素的下標，用來存放棧頂元素的下標，top為為-1表示空棧表示空棧*/SeqStack; 順序棧中的進棧和出棧圖例順序棧中的進棧和出棧圖例AEDCBABAto

5、p top top top順序?；静僮鞯膶崿F順序?；静僮鞯膶崿F1）初始化）初始化void InitStack(SeqStack *S)/*構造一個空棧構造一個空棧S*/ S-top= -1;2）進棧）進棧int Push(SeqStack * S, StackElementType x)if(S-top= Stack_Size-1) return(FALSE); /*棧已滿棧已滿*/S-top+;S-elemS-top=x;return(TRUE);3）出棧）出棧int Pop(SeqStack * S, StackElementType *x) if(S-top=-1) /*棧為空棧為空

6、*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改棧頂指針修改棧頂指針 */ return(TRUE); 4） 取棧頂元素取棧頂元素int GetTop（SeqStack S, StackElementType *x） /* 將棧將棧S的棧頂元素彈出，放到的棧頂元素彈出，放到x所指的存儲空間中，但所指的存儲空間中，但棧頂指針保持不變棧頂指針保持不變 */if(S-top=-1) /*棧為空棧為空*/ return(FALSE);else *x = S-elemS-top; return(TRUE); 兩棧共享技術（雙端棧）：兩棧共享技術（

7、雙端棧）：主要利用了棧主要利用了?！皸５孜恢貌蛔儣５孜恢貌蛔?，而棧頂位置動態(tài)變而棧頂位置動態(tài)變化化”的特性。首先為兩個棧申請一個共享的一維數的特性。首先為兩個棧申請一個共享的一維數組空間組空間SM，將兩個棧的棧底分別放在一維數組的，將兩個棧的棧底分別放在一維數組的兩端，分別是兩端，分別是0，M-1。 共享棧的空間示意為：共享棧的空間示意為：top0和和top1分別為兩個棧分別為兩個棧頂指示器頂指示器 。top0top1Stack：0M-1兩棧共享的數據結構定義兩棧共享的數據結構定義#define M 100typedef struct StackElementType StackM; int

8、top2; /*top0和和top1分別為兩個棧頂分別為兩個棧頂指示器指示器*/DqStack;（1） 兩棧共享的初始化操作算法兩棧共享的初始化操作算法void InitStack(DqStack *S)S-top0=-1;S-top1=M;（2） 兩棧共享的進棧操作算法兩棧共享的進棧操作算法int Push(DqStack *S, StackElementType x, int i) /*把數據元素把數據元素x壓入壓入i號堆棧號堆棧*/ if(S-top0+1=S-top1) /*棧已滿棧已滿*/ return(FALSE);switch(i)case 0:S-top0+; S-StackS

9、-top0=x; break; case 1: S-top1-; S-StackS-top1=x; break; default: return(FALSE) /*參數錯誤參數錯誤*/ return(TRUE);（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;

10、 case 1:if(S-top1=M) return(FALSE); *x=S-StackS-top1;S-top1+;break;default: return(FALSE);return(TRUE);2. 鏈棧鏈棧鏈棧鏈棧是采用是采用鏈表鏈表作為存儲結構實現的棧。為作為存儲結構實現的棧。為便于操作，采用帶頭結點的單鏈表實現棧。便于操作，采用帶頭結點的單鏈表實現棧。由于棧的插入和刪除操作僅限制在表頭位置由于棧的插入和刪除操作僅限制在表頭位置進行，所以鏈表的表頭指針就作為棧頂指針。進行，所以鏈表的表頭指針就作為棧頂指針。 鏈棧的示意圖為：鏈棧的示意圖為：anan-1 a1top top為棧頂

11、指針，始終指向當前棧頂元素前面的頭結為棧頂指針，始終指向當前棧頂元素前面的頭結點。若點。若top-next=NULL，則代表空棧。，則代表空棧。注意：注意：鏈棧在使用完畢時，應該釋放其空間。鏈棧在使用完畢時，應該釋放其空間。鏈棧結構的用鏈棧結構的用C語言定義語言定義typedef struct node StackElementType data; struct node *next;LinkStackNode;typedef LinkStackNode *LinkStack;鏈棧的進棧操作鏈棧的進棧操作int Push(LinkStack top, StackElementType x)/*

12、 將數據元素將數據元素x壓入棧壓入棧top中中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(sizeof(LinkStackNode); if(temp=NULL) return(FALSE); /* 申請空間失敗申請空間失敗 */temp-data=x; temp-next=top-next;top-next=temp; /* 修改當前棧頂指針修改當前棧頂指針 */ return(TRUE);鏈棧的出棧操作鏈棧的出棧操作int Pop(LinkStack top, StackElementType *x) /* 將棧將棧top

13、的棧頂元素彈出，放到的棧頂元素彈出，放到x所指的存儲空間中所指的存儲空間中 */ LinkStackNode * temp; temp=top-next; if(temp=NULL) /*棧為空棧為空*/return(FALSE); top-next=temp-next; *x=temp-data; free(temp); /* 釋放存儲空間釋放存儲空間 */ return(TRUE);如果將可利用的空閑結點空間組織成鏈棧來管理，則申如果將可利用的空閑結點空間組織成鏈棧來管理，則申請一個新結點（類似請一個新結點（類似C語言中的語言中的malloc函數）相當于鏈函數）相當于鏈棧的什么操作？歸還一

14、個無用結點（類似棧的什么操作？歸還一個無用結點（類似C語言中的語言中的free函數）相當于鏈棧的什么操作？試分別寫出從鏈棧函數）相當于鏈棧的什么操作？試分別寫出從鏈棧中申請一個新結點和歸還一個空閑結點的算法。中申請一個新結點和歸還一個空閑結點的算法。 【思考題】【思考題】（3）多棧運算）多棧運算將多個鏈棧的棧頂指針放在一個一維指針數組中來統(tǒng)一管理，將多個鏈棧的棧頂指針放在一個一維指針數組中來統(tǒng)一管理，從而實現同時管理和使用多個棧。從而實現同時管理和使用多個棧。 0M-1231C1 C2 D1 E1 E2 E3 F1 G1 G2 top#define M 10 /*M個鏈棧*/typedef s

15、truct node StackElementType data; struct node *next;LinkStackNode, *LinkStack; LinkStack topM; 用用c語言定義語言定義(1)第i號棧的進棧操作int pushi(LinkStack topM, int i, StackElementType x)/*將元素x進入第i號鏈棧*/LinkStackNode *temp;temp=(LinkStackNode * )malloc(sizeof(LinkStackNode);if(temp=NULL) return(FALSE); /* 申請空間失敗 */te

16、mp-data=x;temp-next=topi-next; topi-next=temp; /* 修改當前棧頂指針 */ return(TRUE); (2) 第第i號棧元素的出棧操作號棧元素的出棧操作int Pop(LinkStack topM, int i, StackElementType *x) /* 將棧將棧top的棧頂元素彈出，放到的棧頂元素彈出，放到x所指的存儲空間中所指的存儲空間中 */ LinkStackNode *temp; temp=topi-next; if(temp=NULL) /*第第i號棧為空棧號棧為空棧*/return(FALSE); topi-next=tem

17、p-next; *x=temp-data; free(temp); /* 釋放存儲空間釋放存儲空間 */ return(TRUE); 例如：例如：（1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序1、 數制轉換數制轉換算法原理：N = (N div d)d + N mod d 3.1.3 棧的應用舉例棧的應用舉例void conversion () InitStack(S); scanf (%d,&N); while (N) Push(S, N %

18、 8); N = N/8; while (!IsEmpty(S) Pop(S,e); printf ( %d, e ); / conversion2. 括號匹配問題括號匹配問題算法的設計思想：算法的設計思想： 1 1）凡出現左括弧左括弧，則進棧進棧；2 2）凡出現右括弧右括弧，首先檢查棧是否空 若?？諚？?，則表明該“右括弧右括弧”多余多余， 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，則“左括弧出棧左括弧出?！?” ， 否則表明不匹配不匹配。3 3）表達式表達式檢驗結束時結束時， 若?？諚？眨瑒t表明表達式中匹配正確匹配正確， 否則表明“左括弧左括弧”有余有余。算法算法: :void Bra

19、cketMatch(char *str)Stack S; int i; char ch;InitStack(&S);For(i=0; stri!=0; i+) switch(stri) case (:case :case : Push(&S,stri); break; case ): case : case :if(IsEmpty(S) printf(n右括號多余右括號多余!); return;elseGetTop (&S,&ch);if(Match(ch,stri) Pop(&S,&ch); else printf(n對應的左右括號不同類對應的

20、左右括號不同類!); return;/*switch*/*for*/if(IsEmpty(S)printf(n括號匹配括號匹配!);elseprintf(n左括號多余左括號多余!);3. 表達式求值表達式求值1) 無括號算術表達式求值無括號算術表達式求值表達式運算及運算符表達式運算及運算符優(yōu)先級優(yōu)先級3+4*5 # +- */ * 0 1 2 3 置空棧置空棧OVS、OPTR進進OVS讀字符W退退OVS頂、次頂，頂、次頂，OPTR頂頂將將T(i)=OVS新頂新頂進進OPTR棧棧W是操作符是操作符N結束結束NYNYYYW=#OPTRZ棧?？湛誝W優(yōu)先級優(yōu)先級OPTR棧棧頂優(yōu)先級頂優(yōu)先級N無括號算

21、術表達式的無括號算術表達式的處處理過程理過程如右圖如右圖2) 算術表達式處理規(guī)則算術表達式處理規(guī)則規(guī)定優(yōu)先級表；規(guī)定優(yōu)先級表；(2) 設置兩個棧：設置兩個棧：OVS(運算數棧運算數棧)和和OPTR(運算運算符棧符棧)；(3) 自左向右掃描，遇操作符則與自左向右掃描，遇操作符則與OPTR棧頂優(yōu)棧頂優(yōu)先級比較：當前操作符先級比較：當前操作符OPTR棧頂則進棧頂則進OPTR棧；當前操作符棧；當前操作符 OPTR棧頂，棧頂，OVS棧頂、次頂棧頂、次頂和和OPTR棧頂，退棧形成運算棧頂，退棧形成運算T（i），）， T（i）進進OVS棧。棧。例：實現例：實現A/BC+D*E#的運算過程時棧區(qū)變化情況的運算

22、過程時棧區(qū)變化情況3) 帶括號算術表達式帶括號算術表達式實現算符優(yōu)先算法時需要使用兩個工作棧：一個稱實現算符優(yōu)先算法時需要使用兩個工作棧：一個稱作作運算符棧運算符棧operator；另一個稱作；另一個稱作操作數棧操作數棧operand。算法的基本過程如下：算法的基本過程如下：A.初始化操作數棧初始化操作數棧operand和運算符棧和運算符棧operator，并，并將表達式起始符將表達式起始符“#”壓入運算符棧；壓入運算符棧；B.讀入表達式中的每個字符，若是操作數則直接進讀入表達式中的每個字符，若是操作數則直接進入操作數棧入操作數棧operand，若是運算符，則與運算符棧，若是運算符，則與運算符

23、棧operator的棧頂運算符進行優(yōu)先權比較，并做如下的棧頂運算符進行優(yōu)先權比較，并做如下處理：處理： (1) 若棧頂運算符的優(yōu)先級低于剛讀入的運算符，若棧頂運算符的優(yōu)先級低于剛讀入的運算符，則讓剛讀入的運算符進則讓剛讀入的運算符進operator棧；棧； (2) 若棧頂運算符的優(yōu)先級高于剛讀入的運算符，若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧，送入則將棧頂運算符退棧，送入，同時將操作數棧，同時將操作數棧operand退棧兩次，得到兩個操作數退棧兩次，得到兩個操作數a、b，對，對a、b進進行行運算后，將運算結果作為中間結果推入運算后，將運算結果作為中間結果推入operand棧

24、；棧； (3) 若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運算符先級相同，說明左右括號相遇，只需將棧頂運算符（左括號）退棧即可。（左括號）退棧即可。當當operator棧的棧頂元素和當前讀入的字符均為棧的棧頂元素和當前讀入的字符均為“#”時，說明表達式起始符時，說明表達式起始符“#”與表達式結束符與表達式結束符“#”相相遇，整個表達式求值完畢。遇，整個表達式求值完畢。優(yōu)先關系表（部分運算符）優(yōu)先關系表（部分運算符） + * i ( ) #+ * i ( ) # 例：利用上述優(yōu)先關系表描述表達式（例：利用上述優(yōu)先關系表描

25、述表達式（B*C+D E）的）的計算過程。計算過程。3.1.4 棧與遞歸的實現棧與遞歸的實現遞歸遞歸 :在定義自身的同時又出現了對自身的調用。在定義自身的同時又出現了對自身的調用。直接遞歸函數直接遞歸函數:如果一個函數在其定義體內直接調如果一個函數在其定義體內直接調用自己，則稱直接遞歸函數。用自己，則稱直接遞歸函數。間接遞歸函數：間接遞歸函數：如果一個函數經過一系列的中間調如果一個函數經過一系列的中間調用語句，通過其它函數間接調用自己，則稱間接遞用語句，通過其它函數間接調用自己，則稱間接遞歸函數。歸函數。1.1.具有遞歸特性的問題具有遞歸特性的問題 1）遞歸定義的數學函數）遞歸定義的數學函數如

26、二階Fibonacci數列： Ackerman函數： Fib(n)= 0 若n=0 1 若n=1 Fib(n-1)+Fib(n-2) 其它情況 Ack(m,n)= n+1 當m=0時 Ack(m-1,1) 當m0, n=0時 Ack(m-1,Ack(m,n-1) 當m0, n0時 Ackerman函數可用一個簡單的C語言函數描述: int ack(int m,int n) if(m= =0) return n+1; else if (n= =0) return ack(m-1,1); else return ack(m-1, ack(m,n-1); 2 2）實現遞歸）實現遞歸n將所有的實在參數

27、、返回地址等信息傳遞給將所有的實在參數、返回地址等信息傳遞給被調用函數保存；被調用函數保存；n為被調用函數的局部變量分配存儲區(qū)；為被調用函數的局部變量分配存儲區(qū)；n將控制轉移到被調用函數的入口。將控制轉移到被調用函數的入口。 當在一個函數的運行期間調用另一個函數時，在運行該被調用函數之前，需先完成三項任務：n保存被調函數的計算結果；n釋放被調函數的數據區(qū)；n依照被調函數保存的返回地址將控制轉移到調用函數。從被調用函數返回返回調用函數之前之前，應該完成下列三項任務：多個函數嵌套調用的規(guī)則是：此時的內存管理實行“棧式管理棧式管理”后調用先返回后調用先返回 ！例如：void main( ) void

28、 a( ) void b( ) a( ); b( ); /main / a / bMain的數據區(qū)函數a的數據區(qū)函數b的數據區(qū)3）遞歸求解方法）遞歸求解方法 許多問題的求解過程可以用遞歸分解的方法許多問題的求解過程可以用遞歸分解的方法描述，一個典型的例子是著名的漢諾塔問題描述，一個典型的例子是著名的漢諾塔問題（hanoihanoi）問題。）問題。 漢諾（漢諾（Hanoi) 塔問題塔問題 設設：有有X、Y、Z三個塔座，在三個塔座，在X上按直徑大小遞減次序依上按直徑大小遞減次序依次插有次插有n個直徑各不相同的圓盤，各圓盤按直徑從小到大編個直徑各不相同的圓盤，各圓盤按直徑從小到大編為為1n。 要求：

29、要求：將將X 塔上的塔上的n個圓盤按規(guī)則移至個圓盤按規(guī)則移至Z上，并仍按同樣順上，并仍按同樣順序疊排序疊排 移動規(guī)則：移動規(guī)則： 每次只能移動一個圓盤；每次只能移動一個圓盤；移動的圓盤可以移動的圓盤可以插在任一塔座上，但是在任一時刻都不能將大盤壓在小盤插在任一塔座上，但是在任一時刻都不能將大盤壓在小盤上。上。XYZ1n算法思想：算法思想：當當n=1時，只要將編號為時，只要將編號為1的圓盤從座的圓盤從座X直接移動到塔直接移動到塔座座Z上即可；上即可；當當n1時，需利用塔座時，需利用塔座Y作輔助塔座，若能設法將壓在作輔助塔座，若能設法將壓在編號為編號為n的圓盤上的的圓盤上的n-1個圓盤從塔座個圓盤

30、從塔座X(依照上述原則依照上述原則)移至移至塔座塔座Y上，則可先將編號為上，則可先將編號為n的圓盤從塔座的圓盤從塔座X 移至塔座移至塔座Z上，上，然后再將塔座然后再將塔座Y上的上的n-1個圓盤個圓盤(依照上述原則依照上述原則)移至塔座移至塔座Z上。上。而如何將而如何將n-1個圓盤從一個塔座移至另一個塔座問題是一個個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小于和原問題具有相同特征屬性的問題，只是問題的規(guī)模小于1，因此可以用同樣方法求解。因此可以用同樣方法求解。 求解求解n階階Hanoi塔問題的遞歸算法塔問題的遞歸算法 void hanoi(int n,

31、 char x, char y, char z)/* 將塔座將塔座X上從上到下編號為上從上到下編號為1至至n，且按直徑由小到大疊放的，且按直徑由小到大疊放的n個圓盤，按規(guī)則個圓盤，按規(guī)則搬到塔座搬到塔座Z上，上，Y用作輔助塔座。用作輔助塔座。*/ if(n=1) move(x,1,z); /*將編號為將編號為1的圓盤從的圓盤從x移動移動z*/ else hanoi(n-1,x,z,y); /* 將將X上編號為上編號為1至至n-1的圓盤移到的圓盤移到y(tǒng),z作輔助塔作輔助塔 */ move(x,n,z); /* 將編號為將編號為n的圓盤從的圓盤從x移到移到z */ hanoi(n-1, y,x ,

32、z); /* 將將y上編號為上編號為1至至n-1的圓盤移到的圓盤移到z，x作輔助塔作輔助塔 */ if(n=1) move(x,1,z); else hanoi(2,x,z,y); move(x,n,z); hanoi(n-1, y,x ,z); hanoi(3, x, y, z) if(n=1) move(x,1,y); else hanoi(1,x,y,z); move(x,n,y); hanoi(1, z,x ,y); hanoi(2, x, z, y) if(n=1) move(x,1,z); else hanoi(1,x,z,y); move(x,n,z); hanoi(n-1, y

33、,x ,z); hanoi(1, x, y, z) if(n=1) move(y,1,z); else hanoi(1,y,z,x); move(x,n,z); hanoi(n-1, x,y ,z); hanoi(1, y, x, z) if(n=1) move(y,1,z); else hanoi(1,y,x,z); move(x,n,z); hanoi(1, x,y ,z); hanoi(2, y, x, z)函函數數 調調用用過過程程hanoi(3, A, B , C) hanoi(2, A, C, B): hanoi(1, A, B, C) move(A-C) 1號搬到號搬到C mov

34、e(A-B) 2號搬到號搬到B hanoi(1, 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 下面給出三個盤子搬動時下面給出三個盤子搬動時hanoi(3, A, B , C) 的遞歸調用過程的遞歸調用過程遞歸方法的優(yōu)點遞歸方法的優(yōu)點 ：對問題描述簡潔對問題描述簡潔 結構清晰結構清晰 程序的正確性容易程序的正確性容易證明證明 設

35、計遞歸算法的方法設計遞歸算法的方法 遞歸算法就是在算法中直接或間接調用算法本身的算法。遞歸算法就是在算法中直接或間接調用算法本身的算法。 使用遞歸算法的前提有兩個：使用遞歸算法的前提有兩個： 規(guī)模最小的子問題具有直接解。規(guī)模最小的子問題具有直接解。 原問題可以層層分解為類似的的子問題，且子問題比原問題可以層層分解為類似的的子問題，且子問題比原問題的規(guī)模更小。原問題的規(guī)模更小。設計遞歸算法的方法設計遞歸算法的方法 尋找分解方法尋找分解方法 設計遞歸出口設計遞歸出口 2.2.遞歸過程的實現遞歸過程的實現 遞歸退層（遞歸退層（ii +1層）系統(tǒng)也應完成三件工作：層）系統(tǒng)也應完成三件工作：遞歸進層（遞

36、歸進層（ii +1層）系統(tǒng)需要做三件事：層）系統(tǒng)需要做三件事： 保留本層參數與返回地址；保留本層參數與返回地址； 為被調用函數的局部變量分配存儲區(qū)，給下層參數賦值；為被調用函數的局部變量分配存儲區(qū)，給下層參數賦值； 將程序轉移到被調函數的入口。將程序轉移到被調函數的入口。 保存保存被調函數的計算結果；被調函數的計算結果； 釋放被調函數的數據區(qū)，恢復上層參數；釋放被調函數的數據區(qū)，恢復上層參數； 依照被調函數保存的返回地址，將控制轉移回調用函數。依照被調函數保存的返回地址，將控制轉移回調用函數。 3.3.遞歸算法到非遞歸算法的轉換遞歸算法到非遞歸算法的轉換 遞歸算法具有兩個特性：遞歸算法具有兩個

37、特性： (1) 遞歸算法是一種分而治之、把復雜問遞歸算法是一種分而治之、把復雜問題分解為簡單問題的求解問題方法，對題分解為簡單問題的求解問題方法，對求解某些復雜問題，遞歸算法的分析方求解某些復雜問題，遞歸算法的分析方法是有效的。法是有效的。（2）遞歸算法的效率較低。）遞歸算法的效率較低。1）消除遞歸的原因：）消除遞歸的原因： 第一：有利于提高算法時空性能第一：有利于提高算法時空性能 第二：無應用遞歸語句的語言設施環(huán)境條第二：無應用遞歸語句的語言設施環(huán)境條件件 第三：遞歸算法是一次執(zhí)行完第三：遞歸算法是一次執(zhí)行完 消除遞歸方法有兩類消除遞歸方法有兩類 一類是簡單遞歸問題的轉換，對于尾遞歸和單向遞

38、歸的一類是簡單遞歸問題的轉換，對于尾遞歸和單向遞歸的算法，可用循環(huán)結構的算法替代。算法，可用循環(huán)結構的算法替代。 另一類是基于棧的方式，即將遞歸中隱含的棧機制轉化為另一類是基于棧的方式，即將遞歸中隱含的棧機制轉化為由用戶直接控制的明顯的棧。由用戶直接控制的明顯的棧。 2) 簡單遞歸的消除簡單遞歸的消除 單向遞歸單向遞歸 單向遞歸是指遞歸函數中雖然有一處以上的遞歸調用語句，單向遞歸是指遞歸函數中雖然有一處以上的遞歸調用語句，但各次遞歸調用語句的參數只和主調用函數有關，相互之間參數但各次遞歸調用語句的參數只和主調用函數有關，相互之間參數無關，并且這些遞歸調用語句處于算法的最后。無關，并且這些遞歸調

39、用語句處于算法的最后。 例如計算斐波那契數列的遞歸算法例如計算斐波那契數列的遞歸算法 計算斐波那契數列的遞歸算法如下：計算斐波那契數列的遞歸算法如下： Fib(int n) if（n= =0|n= =1） return n; /* 遞歸出口遞歸出口 */ else return Fib(n-1)+Fib(n-2); /* 遞歸調用遞歸調用 */ 斐波那齊數列斐波那齊數列 Fib(N)= 0 n=01 n=1Fib(N-1)+Fib(N-2) n2計算斐波那契數列的非遞歸算法計算斐波那契數列的非遞歸算法int Fib(int n): int x, y, z;if（n= =0|n= =1）retu

40、rn n; /*計算計算 Fib (0)或或Fib(1) */ else x=0, y=1; /* 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) */ x=z; /* x= Fib (i-1) */ return y ; 尾遞歸尾遞歸 尾遞歸是指遞歸調用語句只有一個，而且是處于算法的尾遞歸是指遞歸調用語句只有一個，而且是處于算法的最后，尾遞歸是單向遞歸的特例。最后，尾遞歸是單向遞歸的特例。 求求n!非遞歸算法非遞歸

41、算法 ： 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); /* 溢出！溢出！*/ (2) (2) 入隊操作入隊操作 int EnterQueue(LinkQueue *Q, QueueElementType x) /* 將數據元素將數據元素x插入到隊列插入到隊列Q中中 */ LinkQue

42、ueNode * 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) (3) 出隊操作出隊操作 int DeleteQueue(LinkQueue * Q, QueueElementType *x) /* 將隊列將隊列Q的隊頭元素出隊，并存放到

43、的隊頭元素出隊，并存放到x所指的存儲空間中所指的存儲空間中 */ LinkQueueNode * p; if(Q-front=Q-rear) 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); 2.2.循環(huán)隊列循環(huán)隊列 循環(huán)隊列循環(huán)隊列是隊列的一種是隊

44、列的一種順序順序表示和實現方法。表示和實現方法。 1 14 40 02 23 35 5frontfrontrearrear(a)(a)空隊列空隊列1 14 40 02 23 35 5e e6 6e e7 7e e8 8e e4 4e e3 3e e5 5frontfrontrearrear(b) (b) 隊列滿隊列滿時時1 14 40 02 23 35 5e e4 4e e3 3e e5 5frontfrontrearrear(c) (c) 一般情況一般情況#define MAXSIZE 50 /*隊列的最大長度隊列的最大長度*/typedef structQueueElementType e

45、lementMAXSIZE; /* 隊列隊列的元素空間的元素空間*/int front; /*頭指針指示器頭指針指示器*/int rear ; /*尾指針指示器尾指針指示器*/ SeqQueue; 循環(huán)隊列的類型定義：循環(huán)隊列的類型定義：循環(huán)隊列的基本操作循環(huán)隊列的基本操作 (1)(1)初始化操作初始化操作 void InitQueue（SeqQueue * Q） /* 將將*Q初始化為一個空的循環(huán)隊列初始化為一個空的循環(huán)隊列 */Q-front=Q-rear=0; (2)(2)入隊操作入隊操作 int EnterQueue(SeqQueue *Q, QueueElementType x) /

46、*將元素將元素x入隊入隊*/ if(Q-rear+1)%MAXSIZE=Q-front) /*隊列已經滿了隊列已經滿了*/return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新設置隊尾指針重新設置隊尾指針 */ return(TRUE); /*操作成功操作成功*/ (3)(3)出隊操作出隊操作 int DeleteQueue(SeqQueue *Q, QueueElementType * x) /*刪除隊列的隊頭元素，用刪除隊列的隊頭元素，用x返回其值返回其值*/ if（Q-front=Q-rear） /*隊列為空隊

47、列為空*/return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新設置隊頭指針重新設置隊頭指針*/ return(TRUE); /*操作成功操作成功*/ 3.2.3 隊列的應用舉例隊列的應用舉例 1打印楊輝三角打印楊輝三角 【算法思想算法思想】由圖可看出楊輝三角形的特點：即每由圖可看出楊輝三角形的特點：即每一行的第一個元素和最后一個元素均為一行的第一個元素和最后一個元素均為1，其它位置，其它位置上的數字是其上一行中與之相鄰的兩個整數之和。上的數字是其上一行中與之相鄰的兩個整數之和。所以第所以第i行上的元素要由第行

48、上的元素要由第i-1行中的元素來生成。我行中的元素來生成。我們可以利用循環(huán)隊列實現打印楊輝三角形的過程：們可以利用循環(huán)隊列實現打印楊輝三角形的過程：在循環(huán)隊列中依次存放第在循環(huán)隊列中依次存放第i-1行上的元素，然后逐個行上的元素，然后逐個出隊并打印，同時生成第出隊并打印，同時生成第i行元素并入隊。行元素并入隊。 void YangHuiTriangle( ) SeqQueue Q; InitQueue (&Q); InitQueue (&Q); EnterQueue (&Q,1); / EnterQueue (&Q,1); /* * 第一行元素入隊第一行元素入隊

49、* */ / for(n=2;n=N;n+) / for(n=2;n=N;n+) /* * 產生第產生第n n行元素并入隊，同時打印第行元素并入隊，同時打印第n-1n-1行的元素行的元素* */ / EnterQueue (&Q,1); / EnterQueue (&Q,1); /* * 第第n n行的第一個元素入隊行的第一個元素入隊* */ / for(i=1;i=n-2;i+) / for(i=1;i=n-2;i+) /* * 利用隊中第利用隊中第n-1n-1行元素產生第行元素產生第n n行的中間行的中間n-2n-2個元素并入隊個元素并入隊* */ / DeleteQueu

50、e (&Q,&temp); DeleteQueue (&Q,&temp); Printf( Printf(“%d%d”,temp); /,temp); /* * 打印第打印第n-1n-1行的元素行的元素* */ / GetHead(Q,&x); GetHead(Q,&x); temp=temp+x; / temp=temp+x; /* *利用隊中第利用隊中第n-1n-1行元素產生第行元素產生第n n行元素行元素* */ / EnterQueue (&Q,temp); EnterQueue (&Q,temp); DeleteQueue (&Q, &x); DeleteQueue (&Q, &x); printf( printf(“%d%d”, x); /, x); /* * 打印第打印第n-1n-1行的最后一個元素行的最后一個元素 * */ / EnterQueue (&Q, 1) / Ente