第3章棧和隊(duì)列

§1棧

§2

隊(duì)列

本章小結(jié)

1§

1.1棧的概述

§

1.2棧的順序存儲結(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)

§

1.3棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)及其基本運(yùn)算實(shí)現(xiàn)§

1.4棧的應(yīng)用§

1棧

§

1.5棧與遞歸的實(shí)現(xiàn)2

堆棧在程序設(shè)計(jì)語言中的一項(xiàng)重要應(yīng)用是實(shí)現(xiàn)遞歸。

1.1.1遞歸的定義在程序設(shè)計(jì)語言中，一個(gè)函數(shù)直接調(diào)用自己，或通過一系列的調(diào)用語句間接地調(diào)用自己的過程，稱為遞歸。若函數(shù)調(diào)用自身，稱之為直接遞歸。若過程或函數(shù)p調(diào)用過程或函數(shù)q，而q又調(diào)用p，稱之為間接遞歸。如果一個(gè)遞歸過程或遞歸函數(shù)中遞歸調(diào)用語句是最后一條執(zhí)行語句，則稱這種遞歸調(diào)用為尾遞歸。§1.5棧與遞歸的實(shí)現(xiàn)

31.1.2遞歸的作用遞歸是程序設(shè)計(jì)中一個(gè)強(qiáng)有力的工具。幫助程序設(shè)計(jì)者解決復(fù)雜的問題，并精簡程序結(jié)構(gòu)。它的作用表現(xiàn)在：

第一，解決很多的數(shù)學(xué)問題。很多數(shù)學(xué)函數(shù)是遞歸定義的，比如階乘、費(fèi)氏級數(shù)、求最大公因子、組合公式等。第二，有的數(shù)據(jù)結(jié)構(gòu)，如二叉樹、廣義表等，結(jié)構(gòu)本身就具備遞歸特性，對它們的操作就可以遞歸地描述。第三，還有一類問題，本身并沒有明顯的遞歸結(jié)構(gòu)，但使用遞歸求解可以簡化算法。比如著名的漢諾塔問題、八皇后問題等。41.1.3遞歸的步驟求解遞歸問題的步驟（1）判斷題意是否適合用遞歸來遞解；（2）決定遞歸結(jié)束的條件（StoppingCases）（3）決定遞歸執(zhí)行部分（RecursiveStap）遞歸模型—遞歸函數(shù)的算法格式

處理遞歸問題，常采用if語句來判斷是否符合遞歸結(jié)束條件，算法格式如下：

if(符合遞歸結(jié)束條件)

返回答案；

else

調(diào)用遞歸程序；/*傳遞參數(shù)遞減(增)，表示更高一層的遞歸*/

遞歸出口遞歸體51.1.4遞歸的執(zhí)行過程—函數(shù)調(diào)用、信息傳遞

1.普通函數(shù)的調(diào)用過程

在高級語言編制的程序中，調(diào)用函數(shù)和被調(diào)函數(shù)之間的鏈接和信息交換需要通過堆棧來進(jìn)行。

系統(tǒng)將整個(gè)程序運(yùn)行所需的數(shù)據(jù)空間安排在一個(gè)堆棧中。通常，在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)函數(shù)之前，系統(tǒng)先要完成三件事：1、將所有的實(shí)參、返回地址等信息傳遞給被調(diào)函數(shù)保存；2、為被調(diào)函數(shù)的局部變量分配存儲區(qū)；3、將控制轉(zhuǎn)移到被調(diào)函數(shù)的入口。當(dāng)執(zhí)行完被調(diào)函數(shù)，在返回調(diào)用函數(shù)之前，系統(tǒng)也先要完成三件事：1、保存被調(diào)函數(shù)的計(jì)算結(jié)果；2、釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；3、依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。6當(dāng)有多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí)，按照“后調(diào)用先返回”的原則，函數(shù)之間的信息傳遞和控制轉(zhuǎn)移均通過堆棧來實(shí)現(xiàn)。每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就在堆棧頂端為它分配一個(gè)存儲區(qū)，保存其參數(shù)（實(shí)參、局部變量）和返回地址等信息；每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲區(qū)，使得當(dāng)前正在運(yùn)行函數(shù)的數(shù)據(jù)區(qū)總是在棧頂。最后被調(diào)用的函數(shù)，其相關(guān)的參數(shù)和返回地址等信息作為棧頂元素，我們稱之為棧頂工作記錄，因?yàn)槭钱?dāng)前執(zhí)行函數(shù)的工作記錄，也稱之為“活動記錄”。指向活動記錄的指針通常也被稱為“環(huán)境指針?！?【例3.6】兩個(gè)子函數(shù)first、second的嵌套調(diào)用

intfirst(inta,intb){inti;……second(i);

2：……}

intsecond(intd);{intx,y;……}當(dāng)前運(yùn)行函數(shù)為second時(shí)，堆棧狀態(tài)如右上圖所示。工作記錄的內(nèi)容：返回地址（被調(diào)函數(shù)的下一語句，控制轉(zhuǎn)移至調(diào)用函數(shù)）、實(shí)參、局部變量。執(zhí)行完最后調(diào)用的函數(shù)second后，棧頂記錄被pop出去，控制轉(zhuǎn)移至返回地址‘2’，接著執(zhí)行first函數(shù)的其它語句。執(zhí)行完first函數(shù)語句，當(dāng)前棧頂記錄（first的記錄）又被pop出去，控制轉(zhuǎn)移至返回主函數(shù)地址‘1’，接著執(zhí)行主函數(shù)中的其它語句。2ixy

1mni……mn……（second工作記錄）（first的記錄）

棧頂主函數(shù)工作區(qū)82.遞歸函數(shù)的調(diào)用過程一個(gè)遞歸函數(shù)的嵌套過程類似于多個(gè)函數(shù)的嵌套調(diào)用。只是調(diào)用函數(shù)和被調(diào)函數(shù)均為同一個(gè)函數(shù)。唯一的不同點(diǎn)是其中的一個(gè)傳入?yún)?shù)每次執(zhí)行函數(shù)調(diào)用時(shí)都遞減（增）。

這個(gè)傳入?yún)?shù)可以表明遞歸函數(shù)運(yùn)行的“層次”。若調(diào)用遞歸函數(shù)的主函數(shù)為第0層，那么從主函數(shù)調(diào)用遞歸函數(shù)為進(jìn)入第一層。從第i層遞歸函數(shù)調(diào)用自身為進(jìn)入第i+1層。反之，第i層函數(shù)執(zhí)行完退回至i-1層。系統(tǒng)也需要設(shè)立一個(gè)“遞歸工作棧”作為整個(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)區(qū)，不需用戶自己管理，而由系統(tǒng)完成管理工作。

每一層遞歸函數(shù)所需信息也構(gòu)成一個(gè)“工作記錄”。最“高”層的工作記錄就是棧頂?shù)幕顒佑涗?。指示活動記錄的棧頂指針為“?dāng)前環(huán)境指針”。9【例3.7】設(shè)計(jì)一個(gè)乘法器（只能做加法）

分析：A*B=A+(A*(B－1))=A+A+(A*(B－2))=A+A+……+A*1

B個(gè)AB=1為循環(huán)結(jié)束的條件（遞歸結(jié)束）運(yùn)算規(guī)律：每次運(yùn)算時(shí)，A所乘的數(shù)B依次遞減，將所乘的積返回再與A相加。算法如下頁。

主函數(shù)定義了一個(gè)乘積變量product。實(shí)參A、B；形參M、N；局部變量result。result返回運(yùn)算值給product。

主函數(shù)對遞歸函數(shù)的調(diào)用：product=multiply(NumA,NumB)

遞歸體：result=M+multiply(M,N-1)10乘法器算法如下：intMultiply(intM,intN){intResult;if(N==1)Result=M;elseResult=M+Multiply(

M,N-1);20returnResult;}voidmain(){intNumA,NumB,Product;printf(“PleaseenternumberA:”);scanf(“%d”,&NumA);printf(“PleaseenternumberB:”);scanf(“%d”,&NumB);38

Product=Multiply(NumA,NumB);39printf(“%d*%d=%d”,NumA,NumB,Product);printf("\n");}11表述乘法器算法的遞歸工作棧如下：

棧頂記錄M第4層20;A,B;ResultMultiply(13,1)M+M第3層20;A,B;ResultMultiply(13,2)M+M+M第2層20;A,B;ResultMultiply(13,3)M+M+M+M第1層39;A,B;ResultMultiply(13,4)

實(shí)際上，在調(diào)用函數(shù)和被調(diào)函數(shù)之間不一定傳遞參數(shù)的值，也可以傳遞參數(shù)的地址。每種程序設(shè)計(jì)語言都有它自己約定的傳遞方法，包括被調(diào)函數(shù)的執(zhí)行結(jié)果如何返回到調(diào)用函數(shù)等等。

121.1.5遞歸算法的設(shè)計(jì)

遞歸求解過程的特征

遞歸過程先將整個(gè)問題劃分為若干個(gè)子問題，而這些子問題具有與原問題相同的求解方法。于是可以再將它們劃分成若干個(gè)子問題，如此反復(fù)進(jìn)行，直到不能再劃分成子問題，已經(jīng)可以求解為止（此時(shí)分解到遞歸出口）。

遞歸分解不是隨意的分解，要保證“大問題”與“小問題”相似，即求解過程與環(huán)境都相似。

遞歸算法設(shè)計(jì)先要給出遞歸模型，再轉(zhuǎn)換成對應(yīng)的C/C++語言函數(shù)。13遞歸設(shè)計(jì)的步驟

(1)對原問題f(s)進(jìn)行分析,假設(shè)出合理的“較小問題”f(s')(與數(shù)學(xué)歸納法中假設(shè)n=k-1時(shí)等式成立相似)；

(2)假設(shè)f(s')是可解的,在此基礎(chǔ)上確定f(s)的解。即給出f(s)與f(s')之間的關(guān)系(與數(shù)學(xué)歸納法中求證n=k時(shí)等式成立的過程相似)；

(3)確定一個(gè)特定情況(如f(1)或f(0))的解,由此作為遞歸出口(與數(shù)學(xué)歸納法中求證n=1時(shí)等式成立相似)。14【例3.8】采用遞歸算法求實(shí)數(shù)數(shù)組A[0..n-1]中的最小值。解：設(shè)f(A,i)函數(shù)，求數(shù)組元素A[0]～A[i]中的最小值。當(dāng)i=0時(shí),有f(A,i)=A[0]；假設(shè)f(A,i-1)已求出,則f(A,i)=MIN(f(A,i-1),A[i]),其中MIN()為求兩個(gè)值較小值函數(shù)。因此得到如下遞歸模型：

A[0] 當(dāng)i=0時(shí)f(A,i)=MIN(f(A,i-1),A[i])其他情況15遞歸求解算法如下：

floatf(floatA[],inti){floatm;if(i==0)returnA[0];else{m=f(A,i-1); if(m>A[i])returnA[i]; elsereturnm; }}16【例3.9】求1，2，…，n的全排列。

解：設(shè)a是含n個(gè)不同字符的字符串，f(a,k-1,n)為a[0..k-1]的所有字符的全排序，f(a,k,n)為a[0..k]的所有字符的全排序。假設(shè)f(a,k-1,n)可求，對于a[k]位置，可以取a[0..k]任何之值，再組合f(a,k-1,n)，則得到f(a,k,n)遞歸模型為：

f(a,k,n)：輸出a 當(dāng)k=0時(shí)f(a,k,n)：a[k]位置取a[0..k]任何之值,并組合f(a,k-1,n)的結(jié)果;其他情況17遞歸求解算法如下：voidf(chara[],intk,intn){ inti,j; chartmp; if(k==0) {for(j=0;j<n;j++) printf("%c",a[j]); printf("\n"); } else {for(i=0;i<=k;i++) { a[k]<->a[i];

f(a,k-1,n); a[k]<->a[i] } }}18【例3.10】采用遞歸算法求解皇后問題：在n×n的方格棋盤上，放置n個(gè)皇后，要求每個(gè)皇后不同行、不同列、不同左右對角線。

解：設(shè)place(k,n)表示前面已將1，…，k-1個(gè)皇后放置好，用于放置k，…，n的皇后。求解皇后問題的遞歸模型如下：

place(i,n)：n個(gè)皇后放置完畢，輸出解 若i=n

place(k,n)：對于第k列的每個(gè)合適的位置i，在其上放置一個(gè)皇后;place(k+1,n);其他情況遞歸過程與算法教材p14419【例3.11】求解漢諾塔問題。源塔X；輔助塔Y；目標(biāo)塔Z。設(shè)圓盤從小到大的順序編號為1，2，……，n。實(shí)現(xiàn)全部圓盤從X移動至Z。要求移動過程中不破壞圓盤原來的次序。

分析：①當(dāng)n=1時(shí)，