北京師范大學(xué)數(shù)據(jù)結(jié)構(gòu)教學(xué)資料-第3章-棧與隊列-復(fù)

棧隊列棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：遞歸隊列的應(yīng)用：打印楊輝三角形優(yōu)先級隊列第三章棧與隊列1精選PPTa1a2a3a4a5a6插入xi刪除xj插入刪除棧(Stack)2精選PPT只允許在一端插入和刪除的線性表允許插入和刪除 的一端稱為棧頂

(top)，另一端稱 為棧底(bottom)特點 后進(jìn)先出(LIFO)棧(Stack)退棧進(jìn)棧a0an-1an-2

topbottom3精選PPTtemplate<classE>classStack{ //棧的類定義public:Stack(){}; //構(gòu)造函數(shù)

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

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

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

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

virtualboolIsFull()=0; //判棧滿}；棧的抽象數(shù)據(jù)類型4精選PPT#include<assert.h>#include<iostream.h>template<classE>classSeqStack{//順序棧類定義private:

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

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

inttop; //棧頂指針

intmaxSize; //棧最大容量

voidoverflowProcess(); //棧的溢出處理public:

SeqStack(intsz=50); //構(gòu)造函數(shù)

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

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

boolPop(E&x);

//出棧

boolgetTop(E&x);

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

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

boolIsFull()const{returntop==maxSize-1;}};6精選PPT

top空棧toptoptoptoptopa進(jìn)棧b進(jìn)棧aababcdee進(jìn)棧abcdef進(jìn)棧溢出abdee退棧c7精選PPTtopc退棧b退棧abaa退?？諚opabdd退棧ctopabctoptop8精選PPT順序棧的操作template<classE>voidSeqStack<E>::overflowProcess(){//私有函數(shù)：當(dāng)棧滿則執(zhí)行擴充棧存儲空間處理

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

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

delete[]elements;

elements=newArray; //改變elements指針}9精選PPTtemplate<classE>voidSeqStack<E>::Push(Ex){//若棧不滿,則將元素x插入該棧棧頂,否則溢出處理

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

elements[++top]=x;

//棧頂指針先加1,再進(jìn)棧}template<classE>boolSeqStack<E>::Pop(E&x){//函數(shù)退出棧頂元素并返回棧頂元素的值

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

returntrue; //退棧成功}10精選PPTtemplate<classE>boolSeqStack<E>::getTop(E&x){//若棧不空則函數(shù)返回該棧棧頂元素的地址

if(IsEmpty())returnfalse; x=elements[top];returntrue;}11精選PPT雙棧共享一個?？臻gb[0]t[0]t[1]b[1]0maxSize-1V兩個棧共享一個數(shù)組空間V[maxSize]。設(shè)立棧頂指針數(shù)組

t[2]

和棧底指針數(shù)組

b[2]

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

i

個棧的棧頂與棧底。初始

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

。

棧滿條件：t[0]+1==t[1]//棧頂指針相遇。棧空條件：t[0]=b[0]或t[1]=b[1]

//棧頂指針退到棧底。12精選PPT棧的鏈接存儲表示—

鏈?zhǔn)綏ｆ準(zhǔn)綏o棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行鏈?zhǔn)綏５臈ｍ斣阪滎^適合于多棧操作top13精選PPT鏈?zhǔn)綏?LinkedStack)類的定義#include<iostream.h>template<classE>structStackNode{//棧結(jié)點類定義

Edata; //棧結(jié)點數(shù)據(jù)

StackNode<E>*link;//結(jié)點鏈指針

StackNode(Ed=0,StackNode<E>*next=NULL)

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

14精選PPTtemplate<classE>classLinkedStack{//鏈?zhǔn)綏ｎ惗x

private: StackNode<E>*top;

//棧頂指針

voidoutput(ostream&os,

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

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

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

～LinkedStack(){makeEmpty();

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

voidPush(Ex);

//進(jìn)棧

boolPop(E&x);

//退棧15精選PPT

boolgetTop(E&x)const;

//取棧頂

boolIsEmpty()const{returntop==NULL;}

voidmakeEmpty();

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

friendostream&operator<<(ostream&os,LinkedStack<E>&s){output(os,s.top,1);}

//輸出棧元素的重載操作<<};16精選PPT鏈?zhǔn)綏ｎ惒僮鞯膶崿F(xiàn)template<classE>voidLinkedStack<E>::makeEmpty(){

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

StackNode<E>*p; while(top!=NULL) //逐個結(jié)點釋放

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

deletep;}}template<classE>voidLinkedStack<E>::Push(Ex){//將元素值x插入到鏈?zhǔn)綏５臈ｍ?即鏈頭。17精選PPTtop=newStackNode<E>(x,top);

//創(chuàng)建新結(jié)點

assert(top!=NULL);

//創(chuàng)建失敗退出}template<classE>boolLinkedStack<E>::Pop(E&x){//刪除棧頂結(jié)點,返回被刪棧頂元素的值。

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

StackNode<E>*p=top;

//暫存棧頂元素

top=top->link;

//退棧頂指針

x=p->data;deletep;

//釋放結(jié)點

returntrue; }18精選PPTtemplate<classE>boolLinkedStack<E>::getTop(E&x)const{

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

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

returntrue; }template<classE>voidLinkedStack<E>::output(ostream&os,StackNode<E>*ptr,int&i){//遞歸輸出棧中所有元素（沿鏈逆向輸出）

if(ptr!=NULL){19精選PPT

if(ptr->link!=NULL)output(os,ptr->link,i++);os<<i<<“:”<<p->data<<

endl;

//逐個輸出棧中元素的值

}}20精選PPTa1a2a3a4a5a6插入xi刪除xj插入刪除插入刪除棧(Stack)隊列(Queue)21精選PPT隊列(

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

FirstInFirstOut)a0

a1

a2

an-1frontrear

22精選PPTtemplate<classE>classQueue{public:Queue(){};

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

～Queue(){};

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

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

virtualboolDeQueue(E&x)=0; //出隊列

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

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

virtualboolIsFull()const=0; //判隊列滿};隊列的抽象數(shù)據(jù)類型23精選PPT#include<assert.h>#include<iostream.h>template<classE>classSeqQueue{ //隊列類定義protected:intrear,front; //隊尾與隊頭指針

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

intmaxSize; //隊列最大容量public:

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

隊列的數(shù)組存儲表示─順序隊列24精選PPT

～SeqQueue(){

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

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

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

boolgetFront(E&x);

//取隊頭元素值

void

makeEmpty(){front=rear=0;}

boolIsEmpty()const{returnfront==rear;}

boolIsFull()const

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

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

};25精選PPT隊列的進(jìn)隊和出隊

frontrear空隊列frontrearA進(jìn)隊AfrontrearB進(jìn)隊ABfrontrearC,D進(jìn)隊ABCDfrontrearA退隊BCDfrontrearB退隊CDfrontrearE,F,G進(jìn)隊CDEFGCDEFGfrontrearH進(jìn)隊,溢出26精選PPT隊列的進(jìn)隊和出隊原則進(jìn)隊時先將新元素按rear指示位置加入，再將隊尾指針加一rear=rear+1。隊尾指針指示實際隊尾的后一位置。出隊時按隊頭指針指示位置取出元素，再將隊頭指針進(jìn)一front=front+1，隊頭指針指示實際隊頭位置。隊滿時再進(jìn)隊將溢出出錯（假溢出）；隊空時再出隊將隊空處理。解決假溢出的辦法之一：將隊列元素存放數(shù)組首尾相接，形成循環(huán)（環(huán)形）隊列。27精選PPT隊列存放數(shù)組被當(dāng)作首尾相接的表處理。隊頭、隊尾指針加1時從maxSize-1直接進(jìn)到0，可用語言的取模(余數(shù))運算實現(xiàn)。隊頭指針進(jìn)1:front=(front+1)%maxSize;隊尾指針進(jìn)1:

rear=(rear+1)%maxSize;隊列初始化：front=rear

=0;隊空條件：front

==

rear;隊滿條件：(rear+1)%maxSize==front

循環(huán)隊列(CircularQueue)28精選PPT01234567front01234567front01234567frontrearAABCrearrear空隊列A進(jìn)隊B,C進(jìn)隊0123456701234567A退隊B退隊01234567D,E,F,G,H,I進(jìn)隊frontBCrearAfrontBCrearfrontCrearDEFGHI29精選PPT循環(huán)隊列操作的定義voidMakeEmpty(){front=rear=0;

}

intIsEmpty()const

{returnfront==rear;}

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

template<classE>SeqQueue<E>::SeqQueue(intsz)

:front(0),rear(0),maxSize(sz){//構(gòu)造函數(shù)

elements=newE[maxSize];

assert(elements!=NULL);}30精選PPTtemplate<classE>boolSeqQueue<E>::EnQueue(Ex){//若隊列不滿,則將x插入到該隊列隊尾,否則返回

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

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

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

if(IsEmpty())returnfalse;

31精選PPT

x=elements[front];//先取隊頭

front=(front+1)%maxSize;

//再隊頭指針加一

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

if(IsEmpty())returnfalse;//隊列空

x=elements[front]; //返回隊頭元素

returntrue;}32精選PPT隊列的鏈接存儲表示—

鏈?zhǔn)疥犃嘘狀^在鏈頭，隊尾在鏈尾。鏈?zhǔn)疥犃性谶M(jìn)隊時無隊滿問題，但有隊空問題。隊空條件為

front==NULLfrontrear33精選PPT#include<iostream.h>template<classE>structQueueNode{//隊列結(jié)點類定義

private:

Edata; //隊列結(jié)點數(shù)據(jù)

QueueNode<E>*link;//結(jié)點鏈指針public:QueueNode(Ed=0,QueueNode<E>*next=NULL):data(d),link(next){}};

鏈?zhǔn)疥犃蓄惖亩x34精選PPTtemplate<classE>classLinkedQueue{

private:

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

~LinkedQueue();

boolEnQueue(Ex);boolDeQueue(E&x);

boolGetFront(E&x);

voidMakeEmpty();//實現(xiàn)與~Queue()同

boolIsEmpty()const

{returnfront==NULL;

}};35精選PPTtemplate<classE>LinkedQueue<E>::~LinkedQueue(){//析構(gòu)函數(shù)

QueueNode<E>*p;

while(front!=NULL){

//逐個結(jié)點釋放

p=front;front=front->link;

deletep;}}template<classE>boolLinkedQueue<E>::EnQueue(Ex){//將新元素x插入到隊列的隊尾36精選PPT

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

front=rear=newQueueNode<E>(x);if(front==NULL)returnfalse;} //分配失敗

else{

//隊列不空,插入

rear->link=newQueueNode<E>(x);if(rear->link==NULL)returnfalse;rear=rear->link;}returntrue;}template<classE>//如果隊列不空，將隊頭結(jié)點從鏈?zhǔn)疥犃兄袆h去

37精選PPTboolLinkedQueue<E>::DeQueue(E&x){

if(IsEmpty())returnfalse;//判隊空

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

deletep;

returntrue; }template<classE>boolLinkedQueue<E>::GetFront(E&x){//若隊列不空，則函數(shù)返回隊頭元素的值

if(IsEmpty())returnfalse; x=front->data;returntrue;}38精選PPT設(shè)將整數(shù)1，2，3，4依次進(jìn)棧，但只要出棧時棧非空，則可將出棧操作按任何次序夾入其中，請回答下述問題：若入、出棧次序為Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),則出棧的數(shù)字序列為何(這里Push(i)表示i進(jìn)棧，Pop()表示出棧)?能否得到出棧序列1423和1432?并說明為什么不能得到或者如何得到。可能的出站序列有多少種？

39精選PPT棧的應(yīng)用：表達(dá)式求值一個表達(dá)式由操作數(shù)（亦稱運算對象）、操作符（亦稱運算符）和分界符組成。算術(shù)表達(dá)式有三種表示：中綴(infix)表示

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

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

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

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

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

算術(shù)操作符

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

關(guān)系操作符

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

邏輯操作符

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

括號‘(’和‘)’

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

(

(

((A+B)*D)

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

)

)

)+C)后綴表示AB+D*EFAD*+/-C+44精選PPT中綴表示→轉(zhuǎn)前綴表示先對中綴表達(dá)式按運算優(yōu)先次序通統(tǒng)加上括號，再把操作符前移到左括號前并以就近移動為原則，最后將所有括號消去。

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

(

(

((A+B)*D)

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

)

)

)+C)前綴表示+-*+ABD/E+F*ADC45精選PPT利用棧將中綴表示轉(zhuǎn)換為后綴表示使用?？蓪⒈磉_(dá)式的中綴表示轉(zhuǎn)換成它的前綴表示和后綴表示。為了實現(xiàn)這種轉(zhuǎn)換， 需要考慮各操作符 的優(yōu)先級。

優(yōu)先級

操作符

1 單目-、！

2 *、/、% 3 +、-

4 <、<=、>、>=5==、!= 6 && 7 || 46精選PPT各個算術(shù)操作符的優(yōu)先級isp叫做棧內(nèi)(instackpriority)優(yōu)先數(shù)icp叫做棧外(incomingpriority)優(yōu)先數(shù)。操作符優(yōu)先數(shù)相等的情況只出現(xiàn)在括號配對或棧底的“#”號與輸入流最后的“#”號配對時。47精選PPT中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法操作符棧初始化，將結(jié)束符‘#’進(jìn)棧。然后讀入中綴表達(dá)式字符流的首字符ch。重復(fù)執(zhí)行以下步驟，直到ch=‘#’，同時棧頂?shù)牟僮鞣彩恰?’，停止循環(huán)。若ch是操作數(shù)直接輸出，讀入下一個字符ch。若ch是操作符，判斷ch的優(yōu)先級icp和位于棧頂?shù)牟僮鞣鹢p的優(yōu)先級isp：48精選PPT若icp(ch)>isp(op)，令ch進(jìn)棧，讀入下一個字符ch。若icp(ch)<isp(op)，退棧并輸出。若icp(ch)==isp(op)，退棧但不輸出，若退出的是“(”號讀入下一個字符ch。算法結(jié)束，輸出序列即為所需的后綴表達(dá)式。49精選PPT50精選PPT51精選PPTvoidCalculator::Run(){ charch; doublenewOperand; doubleresult; while(cin>>ch,ch!='#'){ switch(ch){ case'+':case'-':case'*':case'/': DoOperator(ch); break; default:

cin.putback(ch); cin>>newOperand; AddOperand(newOperand); break; } } s.getTop(result); cout<<result<<endl;}52精選PPT棧的應(yīng)用：遞歸遞歸的定義

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

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

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

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

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

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

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

返回1參數(shù)傳遞結(jié)果返回遞歸調(diào)用回歸求值55精選PPT例如，單鏈表結(jié)構(gòu)一個結(jié)點，它的指針域為NULL，是一個單鏈表;一個結(jié)點，它的指針域指向單鏈表，仍是一個單鏈表。f

f

數(shù)據(jù)結(jié)構(gòu)是遞歸的56精選PPT搜索鏈表最后一個結(jié)點并打印其數(shù)值template<classE>

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

cout<<f->data<<

endl;elsePrint(f->link);}fffff

a0a1a2a3a4遞歸找鏈尾57精選PPT在鏈表中尋找等于給定值的結(jié)點并打印其數(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é)點x58精選PPT問題的解法是遞歸的例，漢諾塔(TowerofHanoi)問題的解法： 如果n=1，則將這一個盤子直接從A柱移到C柱上。否則，執(zhí)行以下三步：用C柱做過渡，將A柱上的(n-1)個盤子移到B柱上：將A柱上最后一個盤子直接移到C柱上；用A柱做過渡，將B柱上的(n-1)個盤子移到C柱上。59精選PPT60精選PPT#include<iostream.h>void

Hanoi(intn,

charA,

charB,

charC){//解決漢諾塔問題的算法

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

else{

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

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

}}61精選PPT(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->C62精選PPT自頂向下、逐步分解的策略子問題應(yīng)與原問題做同樣的事情，且更為簡單；解決遞歸問題的策略是把一個規(guī)模比較大的問題分解為一個或若干規(guī)模比較小的問題，分別對這些比較小的問題求解，再綜合它們的結(jié)果，從而得到原問題的解。

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

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

return(initialvalue);else//遞歸

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

遞歸調(diào)用

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

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

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

returntemp; }

voidmain(){ intn;

n=Factorial(4);

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

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

24

return3*2//返回

6

return

1//返回

1

return1*1//返回

1

return2*1//返回

2

69精選PPT遞歸過程改為非遞歸過程遞歸過程簡潔、易編、易懂遞歸過程效率低，重復(fù)計算多改為非遞歸過程的目的是提高效率單向遞歸和尾遞歸可直接用迭代實現(xiàn)其非遞歸過程其他情形必須借助棧實現(xiàn)非遞歸過程70精選PPT計算斐波那契數(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

71精選PPT調(diào)用次數(shù)

NumCall(k)=2*Fib(k+1)-1斐波那契數(shù)列的遞歸調(diào)用樹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)72精選PPT單向遞歸用迭代法實現(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;}73精選PPTvoidrecfunc(intA[],intn){if(n>=0){

cout

<<A[n]<<“”;n--;recfunc(A,n);}}

2536721899495463

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

while(n>=0){cout

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

}}

75精選PPT遞歸問題的非遞歸算法編寫技巧確定入棧的返回信息，這些返回信息在出棧時可以幫助計算函數(shù)值或者新的返回信息確定入棧的條件，即非遞歸終點的條件確定出棧時對棧頂?shù)牟僮鳎翘鎿Q成新的返回信息還是直接出棧確定算法終止的條件遞歸工作棧每一次遞歸調(diào)用時，需要為過程中使用的參數(shù)、局部變量等另外分配存儲空間。每層遞歸調(diào)用需分配的空間形成遞歸工作記錄，按后進(jìn)先出的棧組織。

76精選PPT初始化棧,確保棧頂參數(shù)就是當(dāng)前待解決的問題將棧頂問題分解成規(guī)模更小的問題,新的參數(shù)入棧,直到遇到遞歸終點棧頂是遞歸終點,出棧后,棧頂?shù)膮?shù)不是遞歸終點,利用棧頂參數(shù)生成新的問題或者不斷出棧?？?退出遞歸問題的非遞歸算法編寫技巧77精選PPT遞歸與回溯對一個包含有許多結(jié)點，且每個結(jié)點有多個分支的問題，可以先選擇一個分支進(jìn)行搜索。當(dāng)搜索到某一結(jié)點，發(fā)現(xiàn)無法再繼續(xù)搜索下去時，可以沿搜索路徑回退到前一結(jié)點，沿另一分支繼續(xù)搜索。如果回退之后沒有其他選擇，再沿搜索路徑回退到更前結(jié)點，…。依次執(zhí)行，直到搜索到問題的解，或搜索完全部可搜索的分支沒有解存在為止?；厮莘ㄅc分治法本質(zhì)相同，可用遞歸求解。78精選PPT迷宮問題小型迷宮

路口動作 結(jié)果

1

(入口)正向走進(jìn)到2

2

左拐彎進(jìn)到3

3

右拐彎進(jìn)到4

4

(堵死)回溯 退到3

3

(堵死)回溯 退到2

2

正向走進(jìn)到5

5

(堵死)回溯 退到2

2

右拐彎進(jìn)到6

6

左拐彎進(jìn)到7(出口)

4352176

6

左0 直2右0

行3行5行60 040 000 00700

7小型迷宮的數(shù)據(jù)79精選PPT

迷宮maze4

352176回溯此路不通，返回回溯此路不通，返回回溯此路不通，返回回溯此路不通，返回80精選PPT迷宮的類定義#include<iostream.h>#include<fstream.h>#include<stdlib.h>classMaze{private:intMazeSize; intEXIT;

Intersection*intsec; public:Maze(char*filename);

boolTraverseMaze(intCurrentPos);}交通路口結(jié)構(gòu)定義structIntersection{

intleft;

intforward;

intright;}81精選PPTMaze::Maze(char*filename){

//構(gòu)造函數(shù)：從文件filename

中讀取各路口

//和出口的數(shù)據(jù)

ifstreamfin;

fin.open(filename,ios::in|ios::nocreate);

//為輸入打開文件,文件不存在則打開失敗

if(!fin){

cerr<<“迷宮數(shù)據(jù)文件”<<filename

<<“打不開”<<endl;

exit(1);

}

fin>>MazeSize;

//輸入迷宮路口數(shù)82精選PPT

intsec=newIntersection[MazeSize+1];

//創(chuàng)建迷宮路口數(shù)組

for(inti=1;i<=MazeSize;i++)

fin>>intsec[i].left>>intsec[i].forward

>>intsec[i].right;

fin>>EXIT;//輸入迷宮出口

fin.close();}迷宮漫游與求解算法

boolMaze::TraverseMaze(intCurrentPos){

if(CurrentPos>0){

//路口從1開始83精選PPT

if(CurrentPos==EXIT){

//出口處理

cout<<CurrentPos<<"";

return

true;}

else//遞歸向左搜尋可行

if(TraverseMaze(intsec[CurrentPos].left))

{cout<<CurrentPos<<“”;

return

true;}

else//遞歸向前搜尋可行

if(TraverseMaze(intsec[CurrentPos].forward))

{cout<<CurrentPos<<“”;

return

true;}

else//遞歸向右搜尋可行

if(TraverseMaze(intsec[CurrentPos].right))

{cout<<CurrentPos<<"";

return

true;}

}

return

false;

}84精選PPTn皇后問題 在n行n列的國際象棋棋盤上，若兩個皇后位于同一行、同一列、同一對角線上，則稱為它們?yōu)榛ハ喙簟皇后問題是指找到這n個皇后的互不攻擊的布局。85精選PPT1#主對角線3#主對角線5#主對角線

0#次對角線2#次對角線4#次對角線6#次對角線1#次對角線3#次對角線5#次對角線0#主對角線2#主對角線4#主對角線6#主對角線

01230123k=i+jk=n+i-j-186精選PPT解題思路安放第i行皇后時，需要在列的方向從0到n-1試探(j=0,…,n-1)在第

j列安放一個皇后：如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第

j

列安放的皇后。如果沒有出現(xiàn)攻擊，在第

j

列安放的皇后不動，遞歸安放第i+1行皇后。87精選PPT設(shè)置4個數(shù)組

col[n]

：col[i]標(biāo)識第i列是否安放了皇后

md[2n-1]:md[k]標(biāo)識第k條主對角線是否安放了皇后

sd[2n-1]:sd[k]標(biāo)識第k條次對角線是否安放了皇后

q[n]:q[i]記錄第i行皇后在第幾列88精選PPTvoidQueen(inti){for(intj=0;j<n;j++){if(第i行第j列沒有攻擊

){

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

if(i==n-1)

輸出一個布局；

elseQueen(i+1

);

撤消第i行第j列的皇后；

}}}89精選PPT隊列的應(yīng)用：打印楊輝三角形算法逐行打印二項展開式

(a+b)i的系數(shù)：楊輝三角形(Pascal’striangle)90精選PPT分析第i行元素與第i+1行元素的關(guān)系從前一行的數(shù)據(jù)可以計算下一行的數(shù)據(jù)i=2i=3i=401331014641012100110sts+t91精選PPT從第i行數(shù)據(jù)計算并存放第i+1行數(shù)據(jù)121013310

146s=0t=1t=2t=1t=0t=1t=3t=3t=1t=0t=1s+ts=ts=ts=ts=ts=ts=ts=ts=ts+t

s+t

s+t

s+t

s+t

s+ts+ts+t92精選PPT利用隊列打印二項展開式系數(shù)的算法#include

<stdio.h>#include

<iostream.h>#include"queue.h"voidYANGHVI(intn){Queueq(n+3);

//隊列初始化

q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);

ints=0,t;