清華大學(xué)數(shù)據(jù)結(jié)構(gòu)課件(考研必備)dsweekchapstack

1第三章棧與隊(duì)列（1）數(shù)據(jù)結(jié)構(gòu)電子教案殷人昆王宏2棧隊(duì)列棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：遞歸隊(duì)列的應(yīng)用：打印楊輝三角形優(yōu)先級(jí)隊(duì)列第三章棧與隊(duì)列3只允許在表的一端進(jìn)行插入和刪除的線性表

//考慮指針個(gè)數(shù)和?？铡M表示允許插入和刪除 的一端稱為棧頂

(top)，另一端稱 為棧底(bottom)特點(diǎn) 后進(jìn)先出（LIFO-LastInFirstOut)棧(Stack)退棧進(jìn)棧a0an-1an-2topbottom4定義&ADT棧（Stack）特殊的線性表插入、刪除操作只能在一端進(jìn)行,另一端禁止嚴(yán)格說(shuō)，查找操作也是如此Push()/Pop()/getTop()特點(diǎn)后進(jìn)先出—LIFO兒童玩具手槍的子彈夾,鐵路調(diào)度編組站都是棧在實(shí)際生活中的應(yīng)用原型PushPop5template<classT>classStack{ //棧的類定義public:Stack(){}; //構(gòu)造函數(shù)

virtualvoidPush(Tx)=0;//進(jìn)棧

virtualboolPop(T&x)=0; //出棧

virtualboolgetTop(T&x)const=0;//取棧頂

virtualboolIsEmpty()const=0; //判?？?/p>

virtualboolIsFull()const=0; //判棧滿}；//教材中尚包括getsize()，取棧中元素個(gè)數(shù)棧的抽象數(shù)據(jù)類型6#include<assert.h>#include<iostream.h>#include“stack.h”template<classT>classSeqStack:publicStack<T>{//順序棧類定義private:

棧的數(shù)組存儲(chǔ)表示—

順序棧0123456789maxSize-1top(?？?elements7T*elements; //棧元素存放數(shù)組

inttop; //棧頂指針

intmaxSize; //棧最大容量

voidoverflowProcess();//棧的溢出處理，順序棧必備public:

SeqStack(intsz=50); //構(gòu)造函數(shù)，建立空棧

～SeqStack(){delete[]elements;}//析構(gòu)函數(shù)

voidPush(Tx); //進(jìn)棧

boolPop(T&x);

//出棧

boolgetTop(T&x);

//取棧頂內(nèi)容

boolIsEmpty()const{returntop==-1;}

boolIsFull()const{returntop==maxSize-1;}};8

順序棧的構(gòu)造函數(shù)template<classT>SeqStack<T>::SeqStack(intsz):top(-1),maxSize(sz){//建立一個(gè)最大尺寸為sz的空棧，若分配不成功則錯(cuò)誤處理

elements=newT[maxSize]；//創(chuàng)建棧的數(shù)組空間

assert(elements!=NULL)；//動(dòng)態(tài)分配是否成功}；

//斷言（assert）機(jī)制—若斷言語(yǔ)句assert參數(shù)表中給定的條件滿足，則繼續(xù)執(zhí)行后續(xù)的語(yǔ)句；否則將調(diào)用stdlib.h中的函數(shù)abort,打印出錯(cuò)行號(hào)和文件名，出錯(cuò)處理，終止程序的執(zhí)行。9

top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧c10topc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptop進(jìn)棧時(shí)先修改指針，然后元素進(jìn)棧。退棧時(shí)先退棧頂元素再修改指針11順序棧的操作template<classT>voidSeqStack<T>::overflowProcess(){//私有函數(shù)：當(dāng)棧滿則執(zhí)行擴(kuò)充棧存儲(chǔ)空間處理

T*newArray=newT[2*maxSize]; //創(chuàng)建更大的存儲(chǔ)數(shù)組，創(chuàng)建成功檢查省略

for(inti=0;i<=top;i++)newArray[i]=elements[i]; maxSize+=maxSize;

delete[]elements;

elements=newArray; //改變elements指針};12template<classT>voidSeqStack<T>::Push(Tx){//若棧不滿,則將元素x插入該棧棧頂,否則溢出處理

if(IsFull()==true)overflowProcess; //棧滿

elements[++top]=x;

//棧頂指針先加1,再進(jìn)棧};

template<classT>boolSeqStack<T>::Pop(T&x){//退出棧頂元素并返回棧頂元素的值

if(IsEmpty()==true)returnfalse; x=elements[top--]; //先退棧頂元,然后指針退1

returntrue; //退棧成功};

13template<classT>boolSeqstack<T>::getTop(T&x){//若棧不空則函數(shù)返回棧頂元素,棧頂指針不變

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;};一個(gè)棧利用一片連續(xù)空間難免造成浪費(fèi)解決辦法：雙棧共享一個(gè)?？臻g14雙棧共享一個(gè)?？臻gb[0]t[0]t[1]b[1]0maxSize-1V兩個(gè)棧共享一個(gè)數(shù)組空間V[maxSize]設(shè)立棧頂指針數(shù)組和棧底指針數(shù)組//考慮僅用棧頂指針可否

t[i]和b[i]分別指示第

i

個(gè)棧(i=0,1)的棧頂與棧底初始

t[0]=b[0]=-1,t[1]=b[1]=maxSize

棧滿條件：t[0]+1==t[1]//棧頂指針相遇?？諚l件：t[0]==b[0]或t[1]==b[1]

//退到棧底

15boolPush(DualStack&DS,Tx,inti){//i=0,1,棧號(hào)

if(DS.t[0]+1==DS.t[1])returnfalse;//棧滿

if(i==0)DS.t[0]++;elseDS.t[1]--;//修改棧頂指針

DS.V[DS.t[i]]=x;//元素入棧，p92修改

returntrue;}boolPop(DualStack&DS,T&x,inti){if(DS.t[i]==DS.b[i])returnfalse;//?？?/p>

x=DS.V[DS.t[i]];//元素出棧

if(i==0)DS.t[0]--;elseDS.t[1]++;//修改指針

returntrue;}

//多個(gè)棧共享?xiàng)？臻g時(shí)用順序表示處理相對(duì)復(fù)雜16棧的鏈接存儲(chǔ)表示—

鏈?zhǔn)綏ｆ準(zhǔn)綏：雎詶M問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪準(zhǔn)走m合于多棧操作top17鏈?zhǔn)綏?LinkedStack)類的定義#include<iostream>//具體實(shí)現(xiàn)時(shí)的一種頭文件形式#include<assert.h>#include“stack.h”usingnamespacestd;template<classT>structStackNode{//棧結(jié)點(diǎn)類定義

Tdata; //棧結(jié)點(diǎn)數(shù)據(jù)

StackNode<T>*link;//結(jié)點(diǎn)鏈指針

StackNode(Td=0,StackNode<T>*next=NULL)

:data(d),link(next){}//構(gòu)造函數(shù)};

//VC6.0庫(kù)文件有iostream.h,編譯可以通過(guò).但是VS2005和VS2008沒(méi)有這個(gè)庫(kù)文件,只能用標(biāo)準(zhǔn)命名空間:

#include<iostream>

usingnamespacestd;

18template<classT>classLinkedStack:publicStack<T>{//鏈?zhǔn)綏ｎ惗x

private: StackNode<T>*top;

//棧頂指針

static

voidoutput(ostream&os,

StackNode<T>*ptr,inti);

//遞歸輸出棧的所有元素public:LinkedStack():top(NULL){}

//構(gòu)造函數(shù)

～LinkedStack(){makeEmpty();

}//析構(gòu)函數(shù)

voidPush(Tx);

//進(jìn)棧

boolPop(T&x);

//退棧19

boolgetTop(T&x)const;

//取棧頂

boolIsEmpty()const{returntop==NULL;}

boolIsFull()const

{returnfalse;}//思考為何直接返回為假

voidmakeEmpty();

//清空棧的內(nèi)容

friendostream&operator<<(ostream&os,LinkedStack<T>&s)//教材94頁(yè)給出一種簡(jiǎn)單實(shí)現(xiàn)

{cout<<“Showstack”<<endl;

output(os,s.top,0);returnos;}//函數(shù)實(shí)現(xiàn)

//輸出棧元素的重載操作<<};20鏈?zhǔn)綏ｎ惒僮鞯膶?shí)現(xiàn)template<classT>LinkedStack<T>::makeEmpty(){

//逐次刪去鏈?zhǔn)綏Ｖ械脑刂敝翖ｍ斨羔槥榭铡?/p>

StackNode<T>*p; while(top!=NULL) //逐個(gè)結(jié)點(diǎn)釋放

{p=top;top=top->link;

deletep;}};template<classT>voidLinkedStack<T>::Push(Tx){//將元素值x插入到鏈?zhǔn)綏５臈ｍ?即鏈頭。

top=newStackNode<T>(x,top);//創(chuàng)建含x新結(jié)點(diǎn)

assert(top!=NULL);

//創(chuàng)建失敗退出};21

template<classT>boolLinkedStack<T>::Pop(T&x){//刪除棧頂結(jié)點(diǎn),返回被刪棧頂元素的值。

if(IsEmpty()==true)returnfalse;//棧空返回

StackNode<T>*p=top;

//暫存棧頂元素

top=top->link;

//退棧頂指針

x=p->data;deletep;

//釋放結(jié)點(diǎn)

returntrue; };//鏈?zhǔn)綏Ｔ谕藯r(shí)有?？张袛?，Pop操作完成結(jié)果有不同的返回形式。//但鏈?zhǔn)綏Ｔ谶M(jìn)棧時(shí)不判斷棧滿，Push函數(shù)為無(wú)值類型。22template<classT>voidLinkedStack<T>::output(ostream&os,StackNode<T>*ptr,inti){//遞歸輸出棧中所有元素（沿鏈逆向輸出）

if(ptr!=NULL){

i++;

if(ptr->link!=NULL)output(os,ptr->link,i);//遞歸輸出

os<<i<<“:”<<ptr->data<<

endl;

//逐個(gè)輸出棧中元素的值

}//ptr最開(kāi)始指向棧頂，i=0};23

template<classT>boolLinkedStack<T>::getTop(T&x)const{

if(IsEmpty()==true)returnfalse;//?？辗祷?/p>

x=top->data;//返回棧頂元素的值

returntrue; };問(wèn)題：當(dāng)進(jìn)棧元素的編號(hào)為1,2,…,n時(shí)，可能的出棧序列有多少種？關(guān)于棧的進(jìn)一步討論24設(shè)進(jìn)棧元素?cái)?shù)為n，可能出棧序列數(shù)為mn:n=0，m0=1:出棧序列{}。n=1，m1=1:出棧序列{1}。n=2，m2=2：=m0*m1+m1*m0出棧序列中1在第1位。1進(jìn)1出2進(jìn)2出，出棧序列為{1,2}。=m0*m1=1出棧序列中1在第2位。1進(jìn)2進(jìn)2出1出，出棧序列為{2,1}。=m1*m0=1n=3，m3=5:=m0*m2+m1*m1+m2*m0出棧序列中1在第1位。后面2個(gè)元素有m2=2個(gè)出棧序列：{1,2,3},{1,3,2}。25

=m0*m2=2出棧序列中1在第2位。1前有2后有3，出棧序列為{2,1,3}。=m1*m1=1出棧序列中1在第3位。前面2個(gè)元素有m2=2個(gè)出棧序列：{2,3,1},{3,2,1}。

=m2*m0=2n=4，m4=14:

=m0*m3+m1*m2+m2*m1+m3*m0出棧序列中1在第1位。后面3個(gè)元素有m3=5個(gè)出棧序列：{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,3,4,2},{1,4,3,2}。26

=m0*m3=5出棧序列中1在第2位。前面有2，后面3、4有m2=2個(gè)出棧序列:{2,1,3,4},{2,1,4,3}。=

m1*m2=2出棧序列中1在第3位。前面2、3有m2=2個(gè)出棧序列，后面有4:{2,3,1,4},{3,2,1,4}。=

m2*m1=2出棧序列中1在第4位。前面3個(gè)元素有m3=5個(gè)出棧序列：{2,3,4,1},{2,4,3,1},{3,2,4,1},{3,4,2,1},{4,3,2,1}。

=m3*m0=527一般地，設(shè)有n個(gè)元素按序號(hào)1,2,…,n進(jìn)棧，輪流讓1在出棧序列的第1,第2,…第n位，則可能的出棧序列數(shù)為： 推導(dǎo)結(jié)果為：?；煜矗哼^(guò)程與定義StackPermutation：給定n個(gè)對(duì)象{a1,a2,...,an}的序列，任何時(shí)刻只要有對(duì)象尚未入棧，則可令其中最小者進(jìn)棧；或者只要棧非空，也可出棧所有對(duì)象都經(jīng)入、出棧之后，其出棧序列{ak1,ak2,...,akn}

即為一種混洗同一序列的混洗不唯一：{1,2,3,4}，{4,3,2,1}，{3,2,1,4}，{3,2,4,1}123429關(guān)于?；煜慈糨斎胄蛄衶1,2,3,...,n}對(duì)于任一排列{p1,p2,p3,...,pn}，如何判定它是否一種?；煜?？簡(jiǎn)單的情況：{1,2,3}，n=3?；煜垂灿校?!/4!/3!=5種全排列共有：3!=6種少的那個(gè)排列是...？312//為什么是它？充分性*（Knuth,1968）Apermutationisastackpermutationiffitdoesnotinvolvethepermutation312*利用一個(gè)堆棧從12…n得到排列p1p2,...,pn,當(dāng)且僅當(dāng),不存在下標(biāo)i<j<k

使得pj<pk<pi

（參考Knuth計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)第1卷）30?；煜吹目倲?shù)與相關(guān)問(wèn)題可能的混洗總數(shù)SP(n)=？觀察SP(n)<n!定理：SP(n)=Catalan(n)=(2n)!/(n+1)!/n!SP(3)=5SP(6)=132證明......一些經(jīng)典的數(shù)學(xué)問(wèn)題最后都可歸結(jié)為該問(wèn)題的求解

n個(gè)結(jié)點(diǎn)不同形態(tài)二叉樹(shù)的數(shù)目

n+1個(gè)矩陣相乘的不同方法數(shù)31棧的應(yīng)用：表達(dá)式求值一個(gè)表達(dá)式由操作數(shù)（亦稱運(yùn)算對(duì)象）、操作符（亦稱運(yùn)算符）和分界符組成。算術(shù)表達(dá)式有三種表示：中綴(infix)表示

<操作數(shù)><操作符><操作數(shù)>，如A+B；前綴(prefix)表示

<操作符><操作數(shù)><操作數(shù)>，如+AB；后綴(postfix)表示

<操作數(shù)><操作數(shù)><操作符>，如AB+；32中綴表達(dá)式

a+b*(c-d)-e/f后綴表達(dá)式abcd-*+ef/-前綴表達(dá)式

-+a*b–cd/ef表達(dá)式中相鄰兩個(gè)操作符的計(jì)算次序?yàn)椋簝?yōu)先級(jí)高的先計(jì)算；優(yōu)先級(jí)相同的自左向右計(jì)算；當(dāng)使用括號(hào)時(shí)從最內(nèi)層括號(hào)開(kāi)始計(jì)算。表達(dá)式舉例33應(yīng)用后綴表示計(jì)算表達(dá)式的值從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。讀到運(yùn)算符則計(jì)算在后綴表達(dá)式的計(jì)算順序中已隱含了加括號(hào)的優(yōu)先次序，括號(hào)在后綴表達(dá)式中不出現(xiàn)。計(jì)算例abcd-*+ef/-rst1rst2rst3rst4rst534一般表達(dá)式的操作符有4種類型：

算術(shù)操作符

如雙目操作符（+、-、*、/和%）以及單目操作符（-）。

關(guān)系操作符

包括<、<=、==、!=、>=、>。這些操作符主要用于比較。

邏輯操作符

如與(&&)、或(||)、非(!)。

括號(hào)‘(’和‘)’

它們的作用是改變運(yùn)算順序。35中綴表示→轉(zhuǎn)后綴表示先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序加上括號(hào)，再把操作符后移到右括號(hào)的后面并以就近移動(dòng)為原則，最后將所有括號(hào)消去。如中綴表示(A+B)*D-E/(F+A*D)+C，其轉(zhuǎn)換為后綴表達(dá)式的過(guò)程如下：

(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)后綴表示

AB+D*EFAD*+/-C+

借助二叉樹(shù)形式可方便轉(zhuǎn)換

36中綴表示→轉(zhuǎn)前綴表示先對(duì)中綴表達(dá)式按運(yùn)算優(yōu)先次序通統(tǒng)加上括號(hào)，再把操作符前移到左括號(hào)前并以就近移動(dòng)為原則，最后將所有括號(hào)消去。

如中綴表示(A+B)*D-E/(F+A*D)+C，其轉(zhuǎn)換為前綴表達(dá)式的過(guò)程如下：

(

(

((A+B)*D)

–(E/(F+(A*D)

)

)

)+C)前綴表示

+-*+ABD/E+F*ADC

借助二叉樹(shù)形式可方便轉(zhuǎn)換37利用棧將中綴表示轉(zhuǎn)換為后綴表示使用?？蓪⒈磉_(dá)式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。為了實(shí)現(xiàn)這種轉(zhuǎn)換， 需要考慮各操作符 的優(yōu)先級(jí)。一元運(yùn)算優(yōu)先于二元運(yùn)算算術(shù)運(yùn)算優(yōu)先于關(guān)系運(yùn)算關(guān)系運(yùn)算優(yōu)先于邏輯運(yùn)算

優(yōu)先級(jí)

操作符

1 單目-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 38各個(gè)算術(shù)操作符的優(yōu)先級(jí)isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的“#”號(hào)與輸入流最后的“#”號(hào)配對(duì)時(shí)。39中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法操作符棧初始化，將結(jié)束符‘#’進(jìn)棧。然后讀入中綴表達(dá)式字符流的首字符ch。重復(fù)執(zhí)行以下步驟，直到ch=‘#’，同時(shí)棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個(gè)字符ch。若ch是操作符，判斷ch的優(yōu)先級(jí)icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級(jí)isp：40若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個(gè)字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號(hào)讀入下一個(gè)字符ch。算法結(jié)束，輸出序列即為所需的后綴表達(dá)式。414243應(yīng)用中綴表示計(jì)算表達(dá)式的值使用兩個(gè)棧，操作符棧OPTR(operator)，操作數(shù)棧OPND(operand)為了實(shí)現(xiàn)這種計(jì)算，需要考慮各操作符的優(yōu)先級(jí)rst1rst2rst3rst4rst5a+b*

(c-d)-e/f44各個(gè)算術(shù)操作符的優(yōu)先級(jí)isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號(hào)配對(duì)或棧底的“#”號(hào)與輸入流最后的“#”號(hào)配對(duì)時(shí)。45中綴算術(shù)表達(dá)式求值對(duì)中綴表達(dá)式求值的一般規(guī)則：建立并初始化OPTR棧和OPND棧，然后在OPTR棧中壓入一個(gè)“#”掃描中綴表達(dá)式，取一字符送入ch。當(dāng)ch==‘#’

并且OPTR棧的棧頂==‘#’時(shí),結(jié)束算法,在OPND棧的棧頂?shù)玫竭\(yùn)算結(jié)果。否則執(zhí)行以下工作;若ch是操作數(shù)，進(jìn)OPND棧，從中綴表達(dá)式取下一字符送入ch；

46

若ch是操作符，比較icp(ch)的優(yōu)先級(jí)和isp(OPTR)的優(yōu)先級(jí)：若icp(ch)>isp(OPTR)，則ch進(jìn)OPTR棧，從中綴表達(dá)式取下一字符送入ch；若icp(ch)<isp(OPTR)，則從OPND棧退出a2和a1，從OPTR棧退出θ,形成運(yùn)算指令(a1)θ(a2)，結(jié)果進(jìn)OPND棧；若icp(ch)==isp(OPTR)

且ch==

')'，則從OPTR棧退出'('，對(duì)消括號(hào)，然后從中綴表達(dá)式取下一字符送入ch；47voidInFixRun(){

stack<char>OPTR,OPND;//操作符棧OPTR

操作數(shù)棧OPNDcharch,op;OPTR.makeEmpty();OPND.makeEmpty();OPTR.Push(‘#’);//兩個(gè)棧初始化,操作符棧進(jìn)棧底標(biāo)志

getchar(ch);//讀入一個(gè)字符

op=

'#';while(ch!='#'||op!='#'){if(isdigit(ch))//是操作數(shù),進(jìn)棧

{OPND.Push(ch);getchar(ch);}

else{//是操作符,比較優(yōu)先級(jí)

OPTR.getTop(op);

//讀一個(gè)操作符

48

if

(icp(ch)>isp(op))//棧頂優(yōu)先級(jí)低

{OPTR.Push(ch);

getchar(ch);}

else

if(icp(ch)<isp(op)){//棧頂優(yōu)先級(jí)高

OPTR.Pop(op);

OPND.DoOperator(op);//從OPND退出兩操作數(shù)運(yùn)算

}//結(jié)果進(jìn)OPND棧

elseif(ch

==‘)’)

//優(yōu)先級(jí)相等且ch==')'

{

OPTR.Pop(op);getchar(ch);}//對(duì)消括號(hào)

}

OPTR.getTop(op);//取出操作符棧棧頂元素準(zhǔn)備下一輪比較

}/*endofwhile*/

OPND.Pop(ch);cout<<ch<<endl;//輸出OPND棧頂結(jié)果}49505152棧的應(yīng)用：遞歸遞歸的定義

若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義,則稱這個(gè)對(duì)象是遞歸的；若一個(gè)過(guò)程直接地或間接地調(diào)用自己,則稱這個(gè)過(guò)程是遞歸的過(guò)程。以下三種情況常常用到遞歸方法。定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的53定義是遞歸的求解階乘函數(shù)的遞歸算法longfactorial(longn){if(n==0)return1;

elsereturnn*factorial(n-1);}例如，階乘函數(shù)54求解階乘n!的過(guò)程主程序

main:fact(4)參數(shù)4計(jì)算4*fact(3)

返回24參數(shù)3計(jì)算3*fact(2)

返回6參數(shù)2計(jì)算2*fact(1)

返回2參數(shù)1計(jì)算1*fact(0)

返回1參數(shù)0直接定值=1

返回1參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值55例如，單鏈表結(jié)構(gòu)一個(gè)結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個(gè)單鏈表;一個(gè)結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個(gè)單鏈表。ff數(shù)據(jù)結(jié)構(gòu)是遞歸的56搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template<classT>

voidPrint(LinkNode<T>*f){if(f->link==NULL)

cout<<f->data<<

endl;elsePrint(f->link);}fffffa0a1a2a3a4遞歸找鏈尾57在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值

template<classT>

voidPrint(LinkNode<T>*f,Tvalue){

if(f!=NULL)

if(f->data==value)

cout<<f->

data<<endl;

elsePrint(f->link,value);

}ffff遞歸找含x值的結(jié)點(diǎn)x58問(wèn)題的解法是遞歸的例，漢諾塔(TowerofHanoi)問(wèn)題的解法： 如果n=1，則將這一個(gè)盤(pán)子直接從A柱移到C柱上。否則，執(zhí)行以下三步：用C柱做過(guò)渡，將A柱上的(n-1)個(gè)盤(pán)子移到B柱上;//Hanoi(n-1,A,C,B);將A柱上最后一個(gè)盤(pán)子直接移到C柱上；用A柱做過(guò)渡，將B柱上的(n-1)個(gè)盤(pán)子移到C柱上。//Hanoi(n-1,B,A,C);5960#include<iostream.h>void

Hanoi(intn,

charA,

charB,

charC){//解決漢諾塔問(wèn)題的算法

if(n==1)cout<<"move"<<A<<"to"<<C<<endl;

else{Hanoi(n-1,A,C,B);

cout<<"move"<<A<<"to"<<C<<endl; Hanoi(n-1,B,A,C);

}}61(3,A,B,C)(2,A,C,B)A->CA,B,C(1,A,B,C)A,B,CA->CA->C(1,C,A,B)A,B,CA->CA->BA->CC->BA->C(2,B,A,C)A,B,C(1,B,C,A)A,B,CA->CA->C(1,A,B,C)A,B,CA->CB->CB->AA->C62自頂向下、逐步分解的策略子問(wèn)題應(yīng)與原問(wèn)題做同樣的事情，且更為簡(jiǎn)單；解決遞歸問(wèn)題的策略是把一個(gè)規(guī)模比較大的問(wèn)題分解為一個(gè)或若干規(guī)模比較小的問(wèn)題，分別對(duì)這些比較小的問(wèn)題求解，再綜合它們的結(jié)果，從而得到原問(wèn)題的解。

—分而治之策略（分治法）這些比較小的問(wèn)題的求解方法與原來(lái)問(wèn)題的求解方法一樣。63構(gòu)成遞歸的條件不能無(wú)限制地調(diào)用本身，必須有一個(gè)出口，化簡(jiǎn)為非遞歸狀況直接處理。

Procedure<name>(<parameterlist>){if(<initialcondition>)//遞歸結(jié)束條件

return(initialvalue);else//遞歸

return(<name>(parameterchange));}64遞歸過(guò)程在實(shí)現(xiàn)時(shí)，需要自己調(diào)用自己。層層向下遞歸，退出時(shí)的次序正好相反：

遞歸調(diào)用

n!(n-1)!(n-2)!1!0!=1

返回次序主程序第一次調(diào)用遞歸過(guò)程為外部調(diào)用；遞歸過(guò)程每次遞歸調(diào)用自己為內(nèi)部調(diào)用。它們返回調(diào)用它的過(guò)程的地址不同。遞歸過(guò)程與遞歸工作棧65

longFactorial(longn){inttemp;if(n==0)return1;elsetemp=n*Factorial(n-1);

returntemp; }

voidmain(){ intn;

n=Factorial(4);

}RetLoc1RetLoc266遞歸工作棧每一次遞歸調(diào)用時(shí)，需要為過(guò)程中使用的參數(shù)、局部變量等另外分配存儲(chǔ)空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。

局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄67函數(shù)遞歸時(shí)的活動(dòng)記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)68計(jì)算Fact時(shí)活動(dòng)記錄的內(nèi)容遞歸調(diào)用序列01RetLoc211RetLoc222RetLoc236RetLoc2424RetLoc1參數(shù)返回值返回地址返回時(shí)的指令return4*6//返回

24

return3*2//返回

6

return

1//返回

1

return1*1//返回

1

return2*1//返回

2

69遞歸過(guò)程改為非遞歸過(guò)程遞歸過(guò)程簡(jiǎn)潔、易編、易懂遞歸過(guò)程效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形必須借助棧實(shí)現(xiàn)非遞歸過(guò)程70調(diào)用次數(shù)

NumCall(k)=2*Fib(k+1)-1斐波那契數(shù)列的遞歸調(diào)用樹(shù)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)71斐波那契數(shù)列的非遞歸實(shí)現(xiàn)longFibIter(longn){if(n<=1)returnn;

longtwoback=0,oneback=1,Current;

for(inti=2;i<=n;i++){Current=twoback+oneback;twoback=oneback;oneback=Current;

}

returnCurrent;}72voidrecfunc(intA[],intn){//逆序打印數(shù)組元素

if(n>=0){

cout

<<A[n]<<“”;n--;recfunc(A,n);//具有尾遞歸的函數(shù)

}}

2536721899495463

尾遞歸用迭代法實(shí)現(xiàn)73voidsterfunc(intA[],intn){//消除了尾遞歸的非遞歸函數(shù)

while(n>=0){cout

<<A[n]<<endl;n--;

}}

//開(kāi)始打印的尾端下標(biāo)通過(guò)參數(shù)代入。

74回溯對(duì)一個(gè)包含有許多結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)有多個(gè)分支的問(wèn)題，可以先選擇一個(gè)分支進(jìn)行搜索。當(dāng)搜索到某一結(jié)點(diǎn)，發(fā)現(xiàn)無(wú)法再繼續(xù)搜索下去時(shí)，可以沿搜索路徑回退到前一結(jié)點(diǎn)，沿另一分支繼續(xù)搜索。如果回退之后沒(méi)有其他選擇，再沿搜索路徑回退到更前結(jié)點(diǎn)，…。依次執(zhí)行，直到搜索到問(wèn)題的解，或?qū)⑷靠伤阉鞯姆种Ф妓阉魍甏_認(rèn)沒(méi)有解存在為止?；厮莘ㄅc分治法本質(zhì)相同，可用遞歸求解。75在n行n列的國(guó)際象棋棋盤(pán)上，若兩個(gè)皇后位于同一行、同一列、同一對(duì)角線上，則稱它們?yōu)榛ハ喙簟皇后問(wèn)題是指找到這

n個(gè)皇后的互不攻擊的布局。舉例：n皇后問(wèn)題76解題思路在第i行安放皇后時(shí)，需要在列的方向從0到n-1試探(j=0,…,n-1)在第

j列安放一個(gè)皇后：如果在列、主對(duì)角線、次對(duì)角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。轉(zhuǎn)而試探下一列。如果沒(méi)有出現(xiàn)攻擊，在第j列安放的皇后不動(dòng)，遞歸安放第i+1行皇后。77voidQueen(inti){for(intj=0;j<n;j++){

//在第i行嘗試所有列后結(jié)束

if(第i行第j列沒(méi)有攻擊){

在第i行第j列安放皇后；

if(i==n-1)

輸出一個(gè)布局；

elseQueen(i+