第三章棧與隊(duì)列課件

第三章棧與隊(duì)列趙建華棧隊(duì)列棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：遞歸優(yōu)先級(jí)隊(duì)列第三章棧與隊(duì)列只允許在一端插入和刪除的線性表允許插入和刪除 的一端稱為棧頂

(top)，另一端稱 為棧底(bottom)特點(diǎn) 后進(jìn)先出(LIFO)棧(Stack)退棧進(jìn)棧a0an-1an-2topbottomtemplate<classT>classStack{ //棧的類定義public:Stack(){}; //構(gòu)造函數(shù)

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

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

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

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

virtualboolIsFull()=0; //判棧滿}；棧的抽象數(shù)據(jù)類型top空棧toptoptoptopa進(jìn)棧b進(jìn)棧aababcdec,d,e進(jìn)棧abd退棧c退棧f退棧aba退棧topab退棧ctopabftoptopbtemplate<classT>classSeqStack:publicStack<T>{//順序棧類定義private:T*elements; //棧元素存放數(shù)組

inttop; //棧頂指針

intmaxSize; //棧最大容量

voidoverflowProcess(); //棧的溢出處理public: …};棧的數(shù)組存儲(chǔ)表示—

順序棧0123456789maxSize-1top(?？?elementstemplate<classT>voidSeqStack<T>::Push(T&x){//若棧不滿,則將元素x插入該棧棧頂,否則溢出處理

if(IsFull()==true)overflowProcess;

//棧滿

elements[++top]=x;

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

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

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

returntrue; //退棧成功};

template<classT>boolSeqstack<T>::getTop(T&x){//若棧不空則函數(shù)返回該棧棧頂元素的地址

if(IsEmpty()==true)returnfalse; x=elements[top];returntrue;};template<classT>voidSeqStack<T>::overflowProcess(){//私有函數(shù)：當(dāng)棧滿則執(zhí)行擴(kuò)充棧存儲(chǔ)空間處理

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

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

delete[]elements;

elements=newArray; //改變elements指針};考慮直接使用SeqList實(shí)現(xiàn)classSeqStack:publicStack{private:

SeqList st; //棧元素存放數(shù)組public: push(T&x){st.Insert(st.getLength(),x);}

pop(T&x){st.Remove(st.getLength(),x);} …};雙棧共享一個(gè)棧空間b[0]t[0]t[1]b[1]0maxSize-1V兩個(gè)棧共享一個(gè)數(shù)組空間V[maxSize]，兩個(gè)棧的棧底分別位于數(shù)組的開(kāi)頭和結(jié)尾；分別向中間生長(zhǎng)。主要目的是節(jié)約空間：兩個(gè)獨(dú)立棧，預(yù)期的最大空間max(sizeofstack1)+max(sizeofstack2)。而雙棧空間是max(sizeofstack1+sizeofstack2)。實(shí)現(xiàn)方法設(shè)立棧頂指針數(shù)組t[2]和棧底指針數(shù)組b[2]t[i]和b[i]分別指示第i

個(gè)棧的棧頂與棧底初始化t[0]=b[0]=-1,t[1]=b[1]=maxSize棧滿條件：t[0]+1==t[1]//棧頂指針相遇?？諚l件：t[0]=b[0] t[1]=b[1]//退到棧底對(duì)第一個(gè)棧壓棧時(shí):元素放入V[t[0]+1];對(duì)第二個(gè)棧壓棧時(shí):元素放入V[t[1]-1];boolpush(DualStack&DS,Typex,inti){if(DS.t[0]+1==DS.t[1])returnfalse;//棧滿

if(i==0) DS.t[0]++; //壓入第一個(gè)棧

else DS.t[1]--; //壓入第二個(gè)棧

DS.V[DS.t[i]]=x;returntrue;}假設(shè)某次調(diào)用是push(DS,x,0)，上面的程序?qū)嶋H上相當(dāng)于boolpush(DualStack&DS,Typex,inti){if(DS.t[0]+1==DS.t[1])returnfalse;//棧滿

DS.t[0]++; //棧頂指針加1

DS.V[DS.t[0]]=x; //設(shè)置壓棧數(shù)據(jù)returntrue;}可以看到，這個(gè)程序?qū)嶋H上就是前面的普通壓棧程序；當(dāng)i==1時(shí)，相當(dāng)于反向的壓棧。boolPop(DualStack&DS,Type&x,inti){if(DS.t[i]==DS.b[i])returnfalse;x=DS.V[DS.t[i]];if(i==0)DS.t[0]--; //彈出第一個(gè)棧

elseDS.t[1]++; //彈出第二個(gè)棧

returntrue;}

棧的鏈接存儲(chǔ)表示—鏈?zhǔn)綏ｆ準(zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充插入與刪除僅在棧頂處執(zhí)行，效率為O(1)鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作top鏈?zhǔn)綏?LinkedStack)類的定義實(shí)際上是使用單鏈表來(lái)實(shí)現(xiàn)棧的操作#include<iostream.h>#include“stack.h”template<classT>structStackNode{//棧結(jié)點(diǎn)類定義private:

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

StackNode<T>*link;//結(jié)點(diǎn)鏈指針public:StackNode(Td=0,StackNode<T>*next=NULL)

:data(d),link(next){}};

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

private: StackNode<T>*top;

//棧頂指針

voidoutput(ostream&os,

StackNode<T>*ptr,int&i);

//遞歸輸出棧的所有元素public:

voidPush(T&x);

//進(jìn)棧

boolPop(T&x);

//退棧

boolgetTop(T&x)const;

//取棧頂

boolIsEmpty()const{returntop==NULL;}

voidmakeEmpty();

//清空棧的內(nèi)容};鏈?zhǔn)綏ｎ惒僮鞯膶?shí)現(xiàn)LinkedStack<T>::makeEmpty(){

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

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

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

deletep;}};回憶單鏈表中的makeempty操作voidLinkedStack<T>::Push(Tx){//將元素值x插入到鏈?zhǔn)綏５臈ｍ?即鏈頭。 top=newStackNode<T>(x,top);

//創(chuàng)建新結(jié)點(diǎn)，并使得新結(jié)點(diǎn)的link執(zhí)行原來(lái)的top

assert(top!=NULL);

//創(chuàng)建失敗退出};回憶單鏈表中的Insert(0,x)操作boolLinkedStack<T>::Pop(T&x){//刪除棧頂結(jié)點(diǎn),返回被刪棧頂元素的值。

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

StackNode<T>*p=top;

//暫存棧頂元素

top=top->link;

//退棧頂指針

x=p->data;deletep;

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

returntrue; };回憶單鏈表中的delete(0);boolLinkedStack<T>::getTop(T&x)const{

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

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

returntrue; };

回憶單鏈表中的getData(0,T&x)用LinkList實(shí)現(xiàn)棧template<classT>classLinkedStack:publicStack<T>{private: LinkList<T> st; //棧中元素；public:

voidPush(Tx){st.Insert(0,x);}//進(jìn)棧

boolPop(T&x){return

st.Remove(0,x);}//退棧

boolgetTop(T&x)const//取棧頂

{ E*p=getData(x); if(!p)returnfalse; else{x=*p;returntrue;} }; boolIsEmpty()const{returnst.IsEmpty();}

voidmakeEmpty(){st.makeEmpty();};

//清空棧的內(nèi)容};注：上面對(duì)st的各個(gè)成員函數(shù)的調(diào)用都是O(1)時(shí)間的。隊(duì)列(

Queue)定義隊(duì)列是只允許在一端刪除，在另一端插入的線性表允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(rear)。特性先進(jìn)先出(FIFO,FirstInFirstOut)a0

a1

a2

an-1frontreartemplate<classE>classQueue{public:Queue(){};

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

～Queue(){};

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

virtualboolEnQueue(Ex)=0;//進(jìn)隊(duì)列

virtualboolDeQueue(E&x)=0；

//出隊(duì)列

virtualboolgetFront(E&x)=0; //取隊(duì)頭

virtualboolIsEmpty()const=0; //判隊(duì)列空

virtualboolIsFull()const=0; //判隊(duì)列滿};注：如果需要訪問(wèn)隊(duì)列內(nèi)部的元素，或者遍歷，那么仍然建議實(shí)現(xiàn)Iterator接口隊(duì)列的抽象數(shù)據(jù)類型使用數(shù)組來(lái)存放隊(duì)列中的元素；數(shù)組中的元素是循環(huán)存放的。兩個(gè)指針front和rear指示隊(duì)列的首尾位置。如果rear大于front，隊(duì)列中就包括從front到rear（不含）的元素。如果rear等于front，表示空表；如果rear小于front，那么隊(duì)列中包括從front到數(shù)組末尾，再?gòu)臄?shù)組開(kāi)頭到達(dá)rear（不含）的數(shù)據(jù)。隊(duì)空：front=rear隊(duì)滿：(rear+1)%maxSize==front隊(duì)列的數(shù)組存儲(chǔ)表示─順序隊(duì)列隊(duì)列的進(jìn)隊(duì)和出隊(duì)

frontrear空隊(duì)列frontrearA進(jìn)隊(duì)AfrontrearB進(jìn)隊(duì)ABfrontrearC,D進(jìn)隊(duì)ABCDfrontrearA退隊(duì)BCDfrontrearB退隊(duì)CDfrontrearE,F,G進(jìn)隊(duì)CDEFGfrontrearH進(jìn)隊(duì)CDEFGH隊(duì)頭、隊(duì)尾指針加1時(shí)從maxSize-1直接進(jìn)到0，可用語(yǔ)言的取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1:front=(front+1)%maxSize;隊(duì)尾指針進(jìn)1:rear=(rear+1)%maxSize;隊(duì)列初始化：front=rear=0;隊(duì)空條件：front==rear;隊(duì)滿條件：(rear+1)%maxSize==front

循環(huán)隊(duì)列(CircularQueue)classSeqQueue:publicQueue<E>{ //隊(duì)列類定義protected:intrear,front; //隊(duì)尾與隊(duì)頭指針

E*elements; //隊(duì)列存放數(shù)組

intmaxSize; //隊(duì)列最大容量public:

SeqQueue(intsz=10);//構(gòu)造函數(shù)：

//申請(qǐng)空間，設(shè)置maxSize，front，rear?！玈eqQueue(){

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

boolEnQueue(Ex);//新元素進(jìn)隊(duì)列

boolDeQueue(E&x);//退出隊(duì)頭元素

boolgetFront(E&x);

//取隊(duì)頭元素值

void

makeEmpty(){front=rear=0;}

boolIsEmpty()const{returnfront==rear;}

boolIsFull()const

{return((rear+1)%maxSize==front);}

intgetSize()const{return(rear-front+maxSize)%maxSize;}

};template<classE>bool

SeqQueue<E>::EnQueue(Ex){//若隊(duì)列不滿,則將x插入到該隊(duì)列隊(duì)尾,否則返回

if(IsFull()==true)returnfalse;elements[rear]=x;//先存入

rear=(rear+1)%maxSize;//尾指針加一

returntrue; };template<classE>boolSeqQueue<E>::DeQueue(E&x){//若隊(duì)列不空則函數(shù)退隊(duì)頭元素并返回其值

if(IsEmpty()==true)returnfalse; x=elements[front];//先取隊(duì)頭

front=(front+1)%maxSize;

//再隊(duì)頭指針加一

returntrue;};

template<classE>boolSeqQueue<E>::getFront(E&x)const{//若隊(duì)列不空則函數(shù)返回該隊(duì)列隊(duì)頭元素的值

if(IsEmpty()==true)returnfalse;//隊(duì)列空

x=elements[front]; //返回隊(duì)頭元素

returntrue;};

思考題：如果使用順序表中的Remove(0,X)和Insert(n,X)來(lái)實(shí)現(xiàn)隊(duì)列的DeQueue和EnQueue操作，效果如何？SeqQueue<E>::SeqQueue(intsz):front(0),rear(0),maxSize(sz){ elements=newT[maxSize];

assert(elements!=NULL); //在調(diào)試版本下，如果elements==NULL會(huì)報(bào)告錯(cuò)誤；

}隊(duì)列的鏈接存儲(chǔ)表示—

鏈?zhǔn)疥?duì)列隊(duì)頭在鏈頭，隊(duì)尾在鏈尾。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。隊(duì)空條件為front==NULL此時(shí)rear為空？frontreartemplate<classT>structQueueNode{//隊(duì)列結(jié)點(diǎn)類定義

private:

Edata; //隊(duì)列結(jié)點(diǎn)數(shù)據(jù)

QueueNode<T>*link;//結(jié)點(diǎn)鏈指針public:QueueNode(Ed=0,QueueNode<T>*next=NULL):data(d),link(next){}}template<classT>classLinkedQueue{

private:

QueueNode<T>*front,*rear;//隊(duì)頭、隊(duì)尾指針public:LinkedQueue():rear(NULL),front(NULL){}

~LinkedQueue();

… … … …};鏈?zhǔn)疥?duì)列類的定義template<classT>LinkedQueue<T>::~LinkedQueue(){//析構(gòu)函數(shù)

QueueNode<T>*p;

while(front!=NULL){

//逐個(gè)結(jié)點(diǎn)釋放

p=front;front=front->link;

deletep;}};template<classT>bool

LinkedQueue<T>::EnQueue(Tx){//將新元素x插入到隊(duì)列的隊(duì)尾

if(front==NULL){//創(chuàng)建第一個(gè)結(jié)點(diǎn)

front=rear=newQueueNode<T>(x); //保證rear總是指向?qū)ξ瞚f(front==NULL)returnfalse;} //分配失敗

else{

//隊(duì)列不空,插入

rear->link=newQueueNode<T>(x); if(rear->link==NULL)returnfalse; rear=rear->link;}returntrue;};template<classT>//如果隊(duì)列不空，將隊(duì)頭結(jié)點(diǎn)從鏈?zhǔn)疥?duì)列中刪去

boolLinkedQueue<T>::DeQueue(T&x){

if(IsEmpty()==true)returnfalse;//判隊(duì)空

QueueNode<T>*p=front; x=front->data;front=front->link;

deletep;

returntrue; };template<classT>bool

LinkedQueue<T>::GetFront(T&x){//若隊(duì)列不空，則函數(shù)返回隊(duì)頭元素的值

if(IsEmpty()==true)returnfalse; x=front->data;returntrue;};

思考題

增加附加的隊(duì)列頭結(jié)點(diǎn)能否簡(jiǎn)化實(shí)現(xiàn)？如使用單鏈表的Insert(n,X)和Remove(0,X)分別實(shí)現(xiàn)EnQueue和DeQueue，效率如何？帶有尾指針的單鏈表呢？棧的應(yīng)用：表達(dá)式求值棧的LIFO特性決定了它比較適合用來(lái)處理具有嵌套結(jié)構(gòu)/遞歸結(jié)構(gòu)的問(wèn)題:括號(hào)匹配，表達(dá)式求值由于LIFO特性，如果一個(gè)應(yīng)用中總是把前面求出的某個(gè)值和后續(xù)求出的某個(gè)值進(jìn)行運(yùn)算得到一個(gè)新結(jié)果，并且從此之后前面求出的值就不再需要，就可以考慮使用棧來(lái)完成計(jì)算。在計(jì)算這些值的過(guò)程中，可能還需要計(jì)算一些中間結(jié)果，那么這些中間結(jié)果的計(jì)算也需要遵循這樣的模式。此時(shí)可以把運(yùn)算分量入棧，然后在計(jì)算結(jié)果時(shí)在棧頂獲得運(yùn)算分量。結(jié)果可能還需要入棧。中綴表達(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ì)算但是括號(hào)左邊的值的計(jì)算可以先期進(jìn)行表達(dá)式示例后綴表達(dá)式的計(jì)算每個(gè)子表達(dá)式的計(jì)算結(jié)果，和下一個(gè)并列子表達(dá)式的計(jì)算結(jié)果，根據(jù)后續(xù)的運(yùn)算符進(jìn)行運(yùn)算，得到較大的子表達(dá)式的結(jié)果。從左向右順序地掃描表達(dá)式，并用一個(gè)棧暫存掃描到的操作數(shù)或計(jì)算結(jié)果。計(jì)算rst1rst2rst3rst4rst5abcd-*+ef/-計(jì)算方式從左到右掃描后綴表達(dá)式：如果是數(shù)字（最小的子表達(dá)式），壓棧如果是運(yùn)算符（和前面的子表達(dá)式一起，組成一個(gè)較大的子表達(dá)式），從棧中彈出相應(yīng)的分量，并計(jì)算結(jié)果。將結(jié)果壓棧。例如：35+2*首先3，5入棧然后處理+，3、5出棧，得到結(jié)果8（35+)，再入棧2入棧處理*，8，2出棧，得到結(jié)果(35+2*)16，再入棧，完成。思考題如果要把后綴表達(dá)式轉(zhuǎn)成中綴表達(dá)式，怎么做？如果利用上面的算法的框架？中綴表示轉(zhuǎn)后綴表示中綴表達(dá)式：用+、-連接起來(lái)的項(xiàng)的序列；項(xiàng)：用*、/連接起來(lái)的因子序列因子：整數(shù)（變量）或括號(hào)中的表達(dá)式轉(zhuǎn)化規(guī)則term1+term2-term3term1’term2’+term3’-factor1*factor2/factor3factor1’factor2’*factor3’/方法（不考慮效率）將中綴到后綴的轉(zhuǎn)換看作是一種運(yùn)算普通的+運(yùn)算是求和分量的值是其后綴表示，+運(yùn)算是把分量的后綴表示組合成為新的后綴表示同樣使用棧來(lái)存放結(jié)果和運(yùn)算符棧頂有+號(hào)下一個(gè)運(yùn)算符是+/-/)/#，將兩個(gè)運(yùn)算分量相加；下一個(gè)運(yùn)算符是*，要先進(jìn)行乘法運(yùn)算，將*壓棧；當(dāng)棧頂有*號(hào)時(shí)，…方法（不考慮效率）設(shè)置一個(gè)棧存放已經(jīng)掃描過(guò)的分量（及其后綴表示形式）和運(yùn)算符。自左向右掃描中綴表達(dá)式。如果掃描到整數(shù)，直接作為operand入棧，相應(yīng)的后綴形式就是這個(gè)整數(shù)。如果掃描到+，-號(hào)；如果之前掃描到了“operand1(+,-,*,/)operand1”的形式，就可以把這兩個(gè)項(xiàng)的歸約成為一個(gè)項(xiàng)，然后計(jì)算其后綴形式。把前面的三個(gè)元素出棧，把這個(gè)項(xiàng)和它的后綴形式一起入棧。否則不需要進(jìn)行處理。當(dāng)前掃描到的符號(hào)入棧。如果掃描到*，/號(hào)：處理方法和前面類似，但是只考慮*，/。如果掃描到(，表明要首先掃描到一個(gè)表達(dá)式和一個(gè))將(入棧。如果掃描到一個(gè))，表明要和前面的（匹配，成為一個(gè)因子。如果棧頂型如operand*operand，那么計(jì)算operand*operand的后綴形式；將三個(gè)元素出棧，計(jì)算結(jié)果入棧。第一步之后，如果棧頂型如operand+operand，那么進(jìn)行類似處理。前面兩步之后，棧頂必然是型如(operand的形式：將兩個(gè)元素出棧，然后operand入棧。掃描到結(jié)束時(shí)，按照)處理，但是不需要考慮左括號(hào)。例子輸入：A+B*(C-D)-E/F分量D-分量C(*分量B+分量A分量CD-(*分量B+分量A分量CD-*分量B+分量A分量BCD-*+分量A分量F/分量E-分量ABCD-*+計(jì)算C-D處理(C-D)計(jì)算B*(C-D)計(jì)算A+B*(C-D)，繼續(xù)入棧這個(gè)方法的框架不僅可以計(jì)算后綴，也可以直接計(jì)算表達(dá)式的值，還可以計(jì)算一個(gè)程序中的表達(dá)式的類型。更加高效的實(shí)現(xiàn)方法重要的事實(shí)對(duì)于所有的表達(dá)式，其后綴表示中的各運(yùn)算分量的順序不變。一個(gè)表達(dá)式的后綴表示是它的第一個(gè)子表達(dá)式的后綴表示，并聯(lián)上第二個(gè)表達(dá)式的后綴表示，然后加上一個(gè)運(yùn)算符。term1+term2-term3term1’term2’+term3’-factor1*factor2/factor3factor1’factor2’*factor3’/因此，我們可以考慮在掃描到運(yùn)算分量的時(shí)候直接輸出；而在原來(lái)計(jì)算新后綴的地方添加上相應(yīng)的運(yùn)算符號(hào)。請(qǐng)自己看書上的轉(zhuǎn)換方法棧的應(yīng)用：遞歸遞歸的定義

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

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

main:fact(4)參數(shù)4參數(shù)3參數(shù)2參數(shù)1參數(shù)0直接定值=1

返回1參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值計(jì)算4*fact(3)

返回24計(jì)算3*fact(2)

返回6計(jì)算2*fact(1)

返回2計(jì)算1*fact(0)

返回1數(shù)據(jù)結(jié)構(gòu)由更小的相似的數(shù)據(jù)結(jié)構(gòu)組成。對(duì)這個(gè)數(shù)據(jù)結(jié)構(gòu)的處理，分解成對(duì)較小部分的遞歸處理例如，單鏈表結(jié)構(gòu)一個(gè)指針域?yàn)镹ULL的節(jié)點(diǎn)組成一個(gè)單鏈表;一個(gè)其指針域指向單鏈表的結(jié)點(diǎn)，組成一個(gè)單鏈表。ff數(shù)據(jù)結(jié)構(gòu)是遞歸的搜索鏈表最后一個(gè)結(jié)點(diǎn)并打印其數(shù)值template<classE>

voidPrintLastNode(ListNode<E>*f){if(f->link==NULL)

cout<<f->data<<

endl;else

PrintLastNode(f->link);

//f->link所指向的鏈表的最后結(jié)點(diǎn)就是f所指向鏈表的最后結(jié)點(diǎn)}fffffa0a1a2a3a4遞歸找鏈尾在鏈表中尋找等于給定值的結(jié)點(diǎn)并打印其數(shù)值

template<classE>

voidPrint(ListNode<E>*f,Evalue){

if(f!=NULL)

if(f->data==value)

cout<<f->

data<<endl;

elsePrint(f->link,value);

}ffff遞歸找含x值的結(jié)點(diǎn)x問(wèn)題的解法是遞歸的漢諾塔(TowerofHanoi)問(wèn)題的解法： 如果n=1，則將這一個(gè)盤子直接從A柱移到C柱上。

如果n>1，必須先把n-1個(gè)盤子移動(dòng)到B，然后再把盤子n移動(dòng)到C。因此執(zhí)行以下三步：用C柱做過(guò)渡，將A柱上的(n-1)個(gè)盤子移到B柱上；將A柱上最后一個(gè)盤子直接移到C柱上；用A柱做過(guò)渡，將B柱上的(n-1)個(gè)盤子移到C柱上。#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);

}}這些參數(shù)使得問(wèn)題可以遞歸地解決(3,A,B,C)(2,A,C,B)A->CA,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CA->BA->BA->CB->CC->BA->C(2,B,A,C)A,B,C(1,A,C,B)A,B,CA->CA->C(1,B,A,C)A,B,CA->CB->CA->BB->AB->CA->C自頂向下、逐步分解的策略解決遞歸問(wèn)題的策略是把一個(gè)規(guī)模比較大的問(wèn)題分解為一個(gè)或若干規(guī)模比較小的問(wèn)題，分別對(duì)這些比較小的問(wèn)題求解，再綜合它們的結(jié)果，從而得到原問(wèn)題的解。

—分而治之策略（分治法）這些比較小的問(wèn)題的求解方法與原來(lái)問(wèn)題的求解方法一樣；子問(wèn)題應(yīng)與原問(wèn)題做同樣的事情，且更為簡(jiǎn)單；則適用遞歸構(gòu)成遞歸的條件不能無(wú)限制地調(diào)用本身必須有一個(gè)出口，化簡(jiǎn)為非遞歸狀況直接處理。必須保證分解之后的子問(wèn)題要“小于”原來(lái)的問(wèn)題，并且保證總是能夠把一個(gè)問(wèn)題分解到一個(gè)可直接處理的基本問(wèn)題。

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

{

直接處理并返回；

}else//遞歸

{

遞歸調(diào)用<name>過(guò)程，并且進(jìn)行某些綜合處理，然后返回；

}}遞歸過(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ò)程與遞歸工作棧

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

returntemp; }

voidmain(){ intn;

n=Factorial(4);

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

局部變量返回地址參數(shù)活動(dòng)記錄框架遞歸工作記錄函數(shù)遞歸時(shí)的活動(dòng)記錄……………….<下一條指令>Function(<參數(shù)表>)……………….<return>調(diào)用塊函數(shù)塊返回地址(下一條指令)局部變量參數(shù)計(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

遞歸過(guò)程改為非遞歸過(guò)程遞歸的優(yōu)點(diǎn)簡(jiǎn)潔、易編、易懂缺點(diǎn)效率低，重復(fù)計(jì)算多改為非遞歸過(guò)程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實(shí)現(xiàn)其非遞歸過(guò)程其他情形可能必須借助棧來(lái)實(shí)現(xiàn)非遞歸過(guò)程單向遞歸問(wèn)題單向遞歸一個(gè)遞歸函數(shù)遞歸地調(diào)用自身時(shí)，其參數(shù)按照特定的方向變化。比如按照特定的步長(zhǎng)變??；該函數(shù)不向全局變量賦值；對(duì)于一個(gè)特定的調(diào)用recurFun(p)，我們可以知道這個(gè)函數(shù)會(huì)以哪些參數(shù)調(diào)用recurFun?？梢钥紤]設(shè)置一些變量來(lái)記錄中間數(shù)據(jù)，并且從初始條件開(kāi)始計(jì)算各個(gè)參數(shù)的recurFun值計(jì)算斐波那契數(shù)列的函數(shù)Fib(n)的定義求解斐波那契數(shù)列的遞歸算法

longFib(longn){

if(n<=1)returnn;

elsereturnFib(n-1)+Fib(n-2);}如F0=0,F1=1,F2=1,F3=2,F4=3,F5=5

調(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)簡(jiǎn)單的迭代實(shí)現(xiàn)Fib(n)的計(jì)算依賴于Fib(n-1)和Fib(n-2)的值。參數(shù)總是不斷減?。蛔詈?jiǎn)單的想法一個(gè)足夠大的數(shù)組A，A[i]記錄Fib(i)的值。按照從小到大的方式計(jì)算，就可以得到Fib(n)。然而需要大量的空間。A[BIG_NUM];A[0]=0;A[1]=1;for(inti=2;i<=n;i++) A[i]=A[i-1]+A[i-2];returnA[n];單向遞歸用迭代法實(shí)現(xiàn)計(jì)算Fib(i)的時(shí)候，我們只需要Fib(i-1)和Fib(i-2)的值。用oneback和twoback來(lái)保存這兩個(gè)值，然后計(jì)算完Fib(i)之后，就拋棄Fib(i-2)。longFibIter(longn){if(n<=1)returnn;//對(duì)應(yīng)于初始條件；

longtwoback=0,oneback=1,Current;

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

}

returnCurrent;}其他可迭代化的遞歸調(diào)用(1)一個(gè)程序幾乎在最后遞歸調(diào)用自己，然后對(duì)返回值進(jìn)行運(yùn)算后返回。該運(yùn)算的其他分量可以根據(jù)該函數(shù)的參數(shù)計(jì)算得到。并且我們可以知道調(diào)用時(shí)的參數(shù)序列。求解階乘函數(shù)的遞歸算法

longFactorial(longn){ if(n==0)return1;

elsereturnn*Factorial(n-1); }其他可迭代化的遞歸調(diào)用(2)迭代化后的程序：result=1；//初始條件下的返回值；for(i=1;i<=n;i++) result=result*i;returnresult;尾遞歸一個(gè)函數(shù)只在代碼的最后調(diào)用自己，并且返回遞歸調(diào)用得到的值。相當(dāng)于在處理完成當(dāng)前參數(shù)的情況之后，用新的參數(shù)再次運(yùn)行自己的代碼。voidrecfunc(intA[],intn){if(n>=0){

cout

<<A[n]<<“”;n--;recfunc(A,n);}}voidsterfunc(intA[],intn){//消除了尾遞歸的非遞歸函數(shù)

while(n>=0){cout

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

}}

使用棧的迭代實(shí)現(xiàn)方法模擬遞歸棧，棧中保存局部變量參數(shù)返回值存放地址；當(dāng)前處理進(jìn)度（相當(dāng)于返回時(shí)需將執(zhí)行地址）使用入棧/出棧來(lái)模擬遞歸調(diào)用/返回調(diào)用：設(shè)置棧頂?shù)倪M(jìn)度標(biāo)記；設(shè)置參數(shù)、返回值地址入棧返回：拷貝返回值，出棧其他計(jì)算過(guò)程：根據(jù)當(dāng)前進(jìn)度標(biāo)記執(zhí)行；使用棧的Fib的迭代實(shí)現(xiàn)（1）

longFib(longn){

if(n<=1)returnn;

elsereturn

Fib(n-1)+Fib(n-2);}棧元素的類型structNode{ longn; //參數(shù)

longt1; //局部變量，存第一次調(diào)用Fib的返回值

longt2; //局部變量，存第二