chapt3+棧和隊(duì)列-棧（二）

第3章棧和隊(duì)列

§1棧

§2

隊(duì)列

本章小結(jié)

1§

1.1棧的概述

§

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

§

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

1.4棧的應(yīng)用§

1棧

§

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

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

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

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

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

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

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

返回答案；

else

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

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

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

在高級(jí)語(yǔ)言編制的程序中，調(diào)用函數(shù)和被調(diào)函數(shù)之間的鏈接和信息交換需要通過(guò)堆棧來(lái)進(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ù)的局部變量分配存儲(chǔ)區(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)移均通過(guò)堆棧來(lái)實(shí)現(xiàn)。每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就在堆棧頂端為它分配一個(gè)存儲(chǔ)區(qū)，保存其參數(shù)（實(shí)參、局部變量）和返回地址等信息；每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)，使得當(dāng)前正在運(yùn)行函數(shù)的數(shù)據(jù)區(qū)總是在棧頂。最后被調(diào)用的函數(shù)，其相關(guān)的參數(shù)和返回地址等信息作為棧頂元素，我們稱(chēng)之為棧頂工作記錄，因?yàn)槭钱?dāng)前執(zhí)行函數(shù)的工作記錄，也稱(chēng)之為“活動(dòng)記錄”。指向活動(dòng)記錄的指針通常也被稱(chēng)為“環(huán)境指針?！?【例3.6】?jī)蓚€(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ù)的下一語(yǔ)句，控制轉(zhuǎn)移至調(diào)用函數(shù)）、實(shí)參、局部變量。執(zhí)行完最后調(diào)用的函數(shù)second后，棧頂記錄被pop出去，控制轉(zhuǎn)移至返回地址‘2’，接著執(zhí)行first函數(shù)的其它語(yǔ)句。執(zhí)行完first函數(shù)語(yǔ)句，當(dāng)前棧頂記錄（first的記錄）又被pop出去，控制轉(zhuǎn)移至返回主函數(shù)地址‘1’，接著執(zhí)行主函數(shù)中的其它語(yǔ)句。2ixy

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

棧頂主函數(shù)工作區(qū)82.遞歸函數(shù)的調(diào)用過(guò)程一個(gè)遞歸函數(shù)的嵌套過(guò)程類(lèi)似于多個(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ū)，不需用戶(hù)自己管理，而由系統(tǒng)完成管理工作。

每一層遞歸函數(shù)所需信息也構(gòu)成一個(gè)“工作記錄”。最“高”層的工作記錄就是棧頂?shù)幕顒?dòng)記錄。指示活動(dòng)記錄的棧頂指針為“當(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相加。算法如下頁(yè)。

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

主函數(shù)對(duì)遞歸函數(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ì)語(yǔ)言都有它自己約定的傳遞方法，包括被調(diào)函數(shù)的執(zhí)行結(jié)果如何返回到調(diào)用函數(shù)等等。

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

遞歸求解過(guò)程的特征

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

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

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

(1)對(duì)原問(wèn)題f(s)進(jìn)行分析,假設(shè)出合理的“較小問(wèn)題”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í)等式成立的過(guò)程相似)；

(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)可求，對(duì)于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】采用遞歸算法求解皇后問(wèn)題：在n×n的方格棋盤(pán)上，放置n個(gè)皇后，要求每個(gè)皇后不同行、不同列、不同左右對(duì)角線。

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

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

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

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