第3章棧和隊(duì)列

1第三章棧和隊(duì)列2

第三章棧和隊(duì)列

3.1棧

3.2棧的應(yīng)用舉例

3.3

棧與遞歸

3.4隊(duì)列3

3.1棧3.1

.1棧的概念3.1

.2棧的順序存儲(chǔ)和實(shí)現(xiàn)3.1

.3棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)43.1棧棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表（a1,a2,...,ai-1,ai,ai+1,…,an

）插入刪除3.1.1棧的概念一

什么是棧?53.1棧

將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂(Top)，棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，由一個(gè)棧頂指針指示其位置。表的另一端稱為棧底(Bottom)。當(dāng)棧中沒有元素時(shí)稱為空棧。棧的插入操作稱為進(jìn)?；蛉霔＃瑒h除操作稱為出?；蛲藯?。

6棧

棧的特點(diǎn)后進(jìn)先出(LIFO)第一個(gè)進(jìn)棧的元素在棧底，

最后一個(gè)進(jìn)棧的元素在棧頂，第一個(gè)出棧的元素為棧頂元素，最后一個(gè)出棧的元素為棧底元素7Question一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（

）。

A.23415

B.54132

C.23145

D.154328Question一個(gè)棧的輸入序列為12345，則下列序列中不可能是棧的輸出序列的是（

B

）。

A.23415

B.54132

C.23145

D.1543293.1棧棧的基本操作數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必屬于同一個(gè)數(shù)據(jù)對象。關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系。1）

構(gòu)造一個(gè)空棧S；2）進(jìn)棧操作Push3）出棧操作Pop4)取棧頂元素top103.1棧topbasebasetopbasetopbasetopAABCDEAB

棧操作圖示空棧

A進(jìn)棧

BCDE進(jìn)棧EDC出棧113.1棧3.1.2棧的順序存儲(chǔ)和實(shí)現(xiàn)

如何存儲(chǔ)棧?進(jìn)棧、出棧等操作如何實(shí)現(xiàn)？？#defineMAX50intstack[MAX];inttop=0;123.1棧約定棧頂指針指向棧頂元素的下一個(gè)位置當(dāng)棧用順序結(jié)構(gòu)存儲(chǔ)時(shí)，棧的基本操作如建空棧、進(jìn)棧、出棧等操作如何實(shí)現(xiàn)？？

順序棧的圖示topMAX-1nn-1n-210anan-1a2a1133.1棧1)進(jìn)棧操作主要語句if(top>=MAX)printf(“overflow”);else{stack[top]=x;top++;}

MAX-1nn-1n-210anan-1a2a1x進(jìn)棧前top

x進(jìn)棧后MAX-1nn-1n-210xanan-1a2a1top143.1棧2）出棧操作主要語句if(top==0){printf(“underflow”);return(NULL);}top--;return(stack[top]);

出棧操作前

出棧操作后MAX-1nn-1n-210anan-1a2a1MAX-1nn-1n-210anan-1a2a1toptop15教材中順序棧的數(shù)據(jù)類型定義：typedefstructSqStack{SElemType*base;//棧底指針

SElemType*top;//棧頂指針

intstacksize；//當(dāng)前已分配的存儲(chǔ)空間}SqStack;#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;基本操作如下：16

StatusInitStack(Stack&S)

{//

構(gòu)造一個(gè)空棧S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);

//

存儲(chǔ)分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOk;

}

StatusGetTop(StackS,ElemType&e)

{

//

若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR

if(S.top==S.base)return

ERROR;

e=*(S.top-1);

//

返回非空棧中棧頂元素

returnOK;

}17StatusPush(Stack&S,ElemTypee){插入元素e為新的棧頂元素

if(S.top–S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

if(!S.base)exit(OVERFLOW);

//

存儲(chǔ)分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;

}

S.top++=e;

//

插入新的元素

return

OK;}

18StatusPop(Stack&S,ElemType&e)

{

//

若棧不空，則刪除S的棧頂元素，用e返回其值，

//

并返回OK；否則返回ERROR

if(S.top==S.base)returnERROR;

e=*--S.top;

//

返回非空棧中棧頂元素

returnOK;

}

193.1棧3.1.3

棧的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，也稱鏈棧，如圖所示：棧頂元素為鏈?zhǔn)讞Ｎ苍貫殒溛膊辉O(shè)頭結(jié)點(diǎn)，直接用頭指針指向鏈?zhǔn)?，即棧頂元素Datanexttop棧頂棧底an-1a1an203.1棧(1)進(jìn)棧算法主要語句

p=(NODE*)malloc(sizeof(NODE));p->data=x;p->next=top;top=p;Datanexttop棧頂棧底an-1a1anan+1p213.1棧(2)出棧算法主要語句

if(top==NULL)return(NULL);p=top;top=p->next;return(p);若帶頭結(jié)點(diǎn)L的鏈棧進(jìn)棧、出棧算法主要語句？Datanexttop棧頂棧底an-1a1anp22Question輸入序列為ABC，輸出序列為CBA時(shí)，經(jīng)過的棧操作為（

）A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,popC.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop23Question輸入序列為ABC，輸出序列為CBA時(shí)，經(jīng)過的棧操作為（

B

）A.push,pop,push,pop,push,pop

B.push,push,push,pop,pop,popC.push,push,pop,pop,push,pop

D.push,pop,push,push,pop,pop24

小結(jié)

1棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表；

2棧的元素具有后進(jìn)先出的特點(diǎn)；

3棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示，進(jìn)棧、出棧操作要修改棧頂指針；

3.1棧25共享?xiàng)＜夹g(shù)（最常用的是兩個(gè)棧的共享）：主要利用?！皸５孜恢貌蛔儯瑮ｍ斘恢脛?dòng)態(tài)變化”的特性。為兩個(gè)棧申請一個(gè)共享的一維數(shù)組空間S［M］，將兩個(gè)棧的棧底分別放在一維數(shù)組的兩端，分別是0，M-1。由于兩個(gè)棧頂動(dòng)態(tài)變化，形成互補(bǔ)，使得每個(gè)?？捎玫淖畲罂臻g與實(shí)際使用的需求有關(guān)。優(yōu)點(diǎn)：兩棧共享比兩個(gè)棧分別申請M/2的空間利用率高。26設(shè)兩個(gè)棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下：

＃defineM100typedefstructDqStack{SElemTypeStack［M］;inttop［2］;//top［0］和top［1］分別為兩個(gè)棧頂指示器

}DqStack;27共享?xiàng)?/p>

28初始化操作。voidInitStack(DqStack*S){S.top［0］=0;S.top［1］=M-1;}以下三個(gè)操作具體算法自學(xué)29

進(jìn)棧操作算法? intPush(DqStack*S,SElemTypex,inti) //把數(shù)據(jù)元素x壓入i號棧30(2)進(jìn)棧操作算法。intPush(DqStack*S,StackElementTypex,inti){//把數(shù)據(jù)元素x壓入i號棧

if(S.top［0］+1==S.top［1］)//棧已滿

return(FALSE);switch(i){case0:S.Stack［S.top［0］］=x;S.top［0］++; break;31

case1:S.Stack［S.top［1］］=x;S.top［1］--;break;default://i參數(shù)錯(cuò)誤

return(FALSE)}return(TRUE);}32

出棧操作算法? intPop(DqStack*S,SElemType*x,inti) //從i號棧中彈出棧頂元素并送到x中33(3)出棧操作算法。intPop(DqStack*S,StackElementType*x,inti){switch(i){case0:if(S.top［0］==0)return(FALSE); S.top［0］--; *x=S.Stack［S.top［0］］;break;case1:if(S.top［1］==M-1)return(FALSE); S.top［1］++; *x=S.Stack［S.top［1］］;break;default:return(FALSE);}return(TRUE);}34

小結(jié)

1棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表；

2棧的元素具有后進(jìn)先出的特點(diǎn)；

3棧頂元素的位置由一個(gè)稱為棧頂指針的變量指示，進(jìn)棧、出棧操作要修改棧頂指針；

3.1棧353.2棧的應(yīng)用舉例例1數(shù)制轉(zhuǎn)換對于輸入的任意一個(gè)非負(fù)十進(jìn)制數(shù)，顯示輸出與其等值的八進(jìn)制數(shù)數(shù)制轉(zhuǎn)換方法

N=(Ndiv8)108+Nmod8N：十進(jìn)制數(shù)，div：整除運(yùn)算，mod：求余運(yùn)算；

(1348)10=283+582+08+4=(2504)8N1348168212Ndiv81682120Nmod84052

計(jì)算時(shí)從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位結(jié)果：2504顯示時(shí)按從高位到低位的順序輸出363.2棧的應(yīng)用舉例voidconversion()

{InitStack(s);//建空棧

scanf(“%d”,&x);//輸入一個(gè)非負(fù)十進(jìn)制整數(shù)

while(x!=0)//x不等于零循環(huán)

{push(s,x%8);//x/8第一個(gè)余數(shù)進(jìn)棧

x=x/8;//整除運(yùn)算

}

while(!StackEmpty(s))//輸出存放在棧中的八制數(shù)位

{x=pop(s);

printf(“%d”,x);

}

}殺雞用牛刀僅作示例37

例2.括號匹配問題設(shè)表達(dá)式中包含三種括號：圓括號、方括號和花括號，它們可互相嵌套，如(［{}］(［］))或({(［］［()］)})。 算法思想：可設(shè)一個(gè)棧，每讀入一個(gè)括號，若是左括號，直接入棧，等待相匹配的同類右括號；若是右括號，且與當(dāng)前棧頂?shù)淖罄ㄌ柾愋?，則二者匹配，將棧頂?shù)淖罄ㄌ柍鰲?，否則屬于不合法的情況。 如果輸入序列已讀盡，而棧中仍有等待匹配的左括號，或者讀入了一個(gè)右括號，棧中已無等待匹配的左括號，均屬不合法的情況。當(dāng)輸入序列和棧同時(shí)變?yōu)榭諘r(shí)，說明所有括號完全匹配。38voidBracketMatch(char*str)//str［］中為輸入的字符串，利用棧來檢查該字符串中的括號是否匹配{InitStack(&S);for(i=0;i<N;i++)//對字符串中的字符逐一掃描

{switch(str［i］){case′(′,′［′,′{′: Push(&S,str［i］);break;case′)′,′］′,′}′:if(IsEmpty(S)){printf(″\n右括號多余!″);return;}39else{GetTop(&S,&ch);if(Match(ch,str［i］))//Match（該函數(shù)需要另外定義）判斷兩個(gè)括號是否匹配Pop(&S,&ch);//已匹配的左括號出棧

else{printf(″\n對應(yīng)的左右括號不同類!″);return;}}}//switch}//forif(IsEmpty(S))printf(″\n括號匹配!″);elseprintf(″\n左括號多余!″);}40例3表達(dá)式求值以表達(dá)式A*B+C\D為例說明利用棧的求值過程：操作數(shù)：常數(shù)、變量或常量標(biāo)識符運(yùn)算符：**/*+-

界限符：()#運(yùn)算符分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符三類界限符有左右括號和表達(dá)式結(jié)束符等。

運(yùn)算符和界限符統(tǒng)稱算符。41表達(dá)式運(yùn)算順序：由于某些運(yùn)算符可能有更高的優(yōu)先級，因此表達(dá)式不可能嚴(yán)格的從左到右進(jìn)行運(yùn)算。#代表開始或結(jié)束符42表達(dá)式的求值：例5+6(1+2)-4

按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過程為：

5+6(1+2)-4=5+63-4=5+18-4=23-4=19

3.2棧的應(yīng)用舉例1234如何確定運(yùn)算符的運(yùn)算順序？？43帶括號算術(shù)表達(dá)式假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除界限符有左右括號和表達(dá)式起始、結(jié)束符“?！?，如：＃（7+15）*（23-28/4）＃。引入表達(dá)式起始、結(jié)束符是為了方便。算術(shù)四則運(yùn)算的規(guī)則，即：(1)從左算到右；(2)先乘除，后加減；(3)先括號內(nèi)，后括號外。

44

運(yùn)算符和界限符統(tǒng)稱為算符，它們構(gòu)成的集合命名為OP。根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算過程中，任意兩個(gè)前后相繼出現(xiàn)的算符θ1和θ2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一：θ1<θ2，θ1的優(yōu)先權(quán)低于θ2θ1=θ2，θ1的優(yōu)先權(quán)等于θ2θ1>θ2，θ1的優(yōu)先權(quán)高于θ2

45算符之間的優(yōu)先關(guān)系

46算符優(yōu)先算法需要兩個(gè)工作棧：存放算符的optr；存放操作數(shù)或中間結(jié)果的opnd。算法的基本思想：1、初始化操作數(shù)棧opnd和運(yùn)算符棧optr，并將表達(dá)式起始符“?！眽喝脒\(yùn)算符棧optr；2、依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)則入操作數(shù)棧opnd，若是運(yùn)算符，則與運(yùn)算符棧optr的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)比較：47

(1)若棧頂運(yùn)算符的優(yōu)先級低于剛讀入的運(yùn)算符，則讓剛讀入的運(yùn)算符進(jìn)optr棧；

(2)若棧頂運(yùn)算符的優(yōu)先級高于剛讀入的運(yùn)算符，則將棧頂運(yùn)算符退棧，送入θ，同時(shí)將操作數(shù)棧opnd出棧兩次，得到兩個(gè)操作數(shù)a、b，對a、b進(jìn)行θ運(yùn)算，將運(yùn)算結(jié)果作為中間結(jié)果入opnd棧；

(3)若棧頂運(yùn)算符的優(yōu)先級與剛讀入的運(yùn)算符的優(yōu)先級相同，說明左右括號相遇，將棧頂運(yùn)算符（左括號）退棧。483.2棧的應(yīng)用舉例5算符優(yōu)先算法

從左向右掃描表達(dá)式：

遇操作數(shù)——保存；遇運(yùn)算符號cj——與前面的剛掃描過的運(yùn)算符ci比較

若ci<cj則保存cj，（因此已保存的運(yùn)算符的優(yōu)先關(guān)系為c1<c2<c3<c4。。）

若ci>cj

則說明ci是已掃描的運(yùn)算符中優(yōu)先級最高者，可進(jìn)行運(yùn)算；

若ci=cj則ci為“（”，cj為“）”，說明括號內(nèi)的式子已計(jì)算完，需要消去括號；5+4(1+2)-6后面也許有優(yōu)先級更高的算符用兩個(gè)棧分別保存掃描過程中遇到的操作數(shù)和運(yùn)算符49表達(dá)式求值示意圖：5+6(1+2)-4

topbaseOPTR棧#OPND棧topbase5toptop+top6top×top(top1top+top2toptoptoptop3toptoptoptoptop18toptoptop23top-top4toptoptoptop19toptoptop讀入表達(dá)式過程：#5+6（1+2）-4#=191+2=36×3=185+18=2323-4=19503.2棧的應(yīng)用舉例表達(dá)式求值算法intexpress(){//OP為運(yùn)算符集合。

InitStack(OPTR);Push(OPTR,‘#‘);InitStack(OPND);w=Getchar();

While(w!=‘#’||GetTop(OPTR)!=‘#’){if(!In(w,OP))//判斷W是否是運(yùn)算符

{Push(OPND,w);w=getchar();}//不是運(yùn)算符則進(jìn)棧

else51switch(Precede(GetTop(OPTR),w){case‘<‘://新輸入的算符w優(yōu)先級高，w進(jìn)棧

Push(OPTR,w);w=getchar();break;case‘=‘://去括號并接收下一字符

Pop(OPTR，x);w=getchar();break;case‘>’://新輸入的算符優(yōu)先級低，取棧頂算符運(yùn)算

Pop(OPTR，T);Pop(OPND，b);Pop(OPND，a);Push(OPND,Operate(a,T,b));break;}//switch}//whilereturnGetTop(OPND);}523.3棧與遞歸

棧非常重要的一個(gè)應(yīng)用是用來實(shí)現(xiàn)調(diào)用與遞歸。

533.3棧與遞歸一般函數(shù)的調(diào)用機(jī)制

A(){…B();…}C(){……}B(){…C();…}調(diào)用調(diào)用返回返回函數(shù)調(diào)用順序ABC函數(shù)返回順序CBA后調(diào)用的函數(shù)先返回

函數(shù)調(diào)用機(jī)制可通過棧來實(shí)現(xiàn)計(jì)算機(jī)正是利用棧來實(shí)現(xiàn)函數(shù)的調(diào)用和返回的543.3棧與遞歸

1．什么是遞歸在數(shù)學(xué)和程序設(shè)計(jì)等許多領(lǐng)域中都用到了遞歸。遞歸定義：一個(gè)用自己定義自己的概念,稱為遞歸。例

n!=1*2*3*4*(n-1)*nn!遞歸定義n!=1當(dāng)n=1時(shí)

n!=n(n-1)!當(dāng)n>1時(shí)用(n-1)!定義n!553.3棧與遞歸2遞歸函數(shù)：如果一個(gè)函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱為直接遞歸函數(shù)；如果一個(gè)函數(shù)通過其它函數(shù)間接調(diào)用自己，則稱其為間接遞歸函數(shù)。

A（

）{

…

A();

…}B(){C(){……

C();B();……}}A直接調(diào)用自己B間接調(diào)用自己563.3棧與遞歸3．遞歸算法的編寫1）將問題用遞歸的方式定義（包括兩項(xiàng)：終止項(xiàng)、遞歸項(xiàng)）2）根據(jù)問題的遞歸定義編寫遞歸算法

終止項(xiàng)：遞歸終止時(shí)問題的求解；遞歸項(xiàng)：問題分解為與原問題性質(zhì)相同，但規(guī)模較小的問題；例

n!的遞歸定義： 終止項(xiàng)：n!=1當(dāng)n=1

遞歸項(xiàng)：n!=n(n-1)!

當(dāng)n>1用(n-1)!定義n!573.3棧與遞歸例n!的遞歸算法intfact(intn){//求解并返回n的階乘

if（n=1）return（1）；

elsereturn（n*fact(n-1)）；}58

很多數(shù)學(xué)函數(shù)是遞歸定義的，如二階Fibonacci數(shù)列：

59斐波那契數(shù)列的遞歸算法Fib(n)：

Fib(intn){if（n==0||n==1）returnn;//遞歸出口

elsereturnFib(n-1)+Fib(n-2);//遞歸調(diào)用

}6061遞歸調(diào)用過程的實(shí)現(xiàn)遞歸調(diào)用時(shí)系統(tǒng)需要做三件事：

(1)將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；

(2)為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)空間；

(3)將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。

62從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也完成三件工作：

(1)保存被調(diào)函數(shù)的計(jì)算結(jié)果；

(2)釋放被調(diào)函數(shù)所占空間；

(3)依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。63

例：n階Hanoi塔問題：設(shè)有三個(gè)分別命名為X、Y和Z的塔座，在塔座X上插有n個(gè)直徑大小各不相同、依小到大編號為1，2,…，n的圓盤?，F(xiàn)要求將X軸上的n個(gè)圓盤移至塔座Z上并仍按同樣順序疊排。圓盤移動(dòng)時(shí)必須遵循下列原則：

(1)每次只能移動(dòng)一個(gè)圓盤；

(2)圓盤可以插在X、Y和Z中的任何一個(gè)塔座上；

(3)任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。XYZ12364

如何實(shí)現(xiàn)移動(dòng)圓盤的操作呢？當(dāng)n=1時(shí)，將編號為1的圓盤從塔座X直接移動(dòng)到塔座Z上。當(dāng)n>1時(shí)，需利用塔座Y輔助，（1）將上面n-1個(gè)圓盤從塔座X(依照上述原則)移至塔座Y上，（2）將編號為n的圓盤從塔座X移至塔座Z上，（3）將塔座Y上的n-1個(gè)圓盤(依照上述原則)移至塔座Z上。而將n-1個(gè)圓盤從一個(gè)塔座移至另一個(gè)塔座問題是和原問題具有相同特征屬性的問題，只是問題的規(guī)模小1，可以用同樣方法求解。65voidhanoi(intn,charx,chary,charz)//將塔座x上按直徑由小到大且至上而下編號為1至n//的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1{2if(n==1)3move(x,1,z);//將編號為１的圓盤從x移到z4else{5hanoi(n-1,x,z,y);//將x上編號為１至n-1的

//圓盤移到y(tǒng),z作輔助塔6move(x,n,z);//將編號為n的圓盤從x移到z7hanoi(n-1,y,x,z);//將y上編號為１至n-1的

//圓盤移到z,x作輔助塔8}9}66xyzxyzxyzxyzhanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);67遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc主函數(shù)：執(zhí)行調(diào)用語句hanoi(3,a,b,c)，入棧。層1：執(zhí)行1,2,4,5語句，產(chǎn)生向下調(diào)用，進(jìn)層2。68遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc6,2,a,c,b層2

入棧，記錄層1的返回地址6等信息；執(zhí)行2層的1,2,4,5語句，執(zhí)行到語句５再向下調(diào)用，進(jìn)入層3。69遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc6,2,a,c,b6,1,a,b,c層3

入棧，記錄層2的返回地址6等信息；執(zhí)行1,2,3,9語句，過程執(zhí)行完。70層２第３層調(diào)用結(jié)束，出棧，返回第2層；從第2層的斷點(diǎn)語句６執(zhí)行；執(zhí)行到語句７，又開始向下遞歸調(diào)用到第3層。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc6,2,a,c,b6,1,a,b,c71層3

入棧,記錄層2的返回地址8等信息；執(zhí)行語句1,2,3,9,過程執(zhí)行完。出棧，返回第2層斷點(diǎn)語句8。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc6,2,a,c,b8,1,c,a,b72層２從第3層返回后，從斷點(diǎn)８開始執(zhí)行，執(zhí)行語句8,9，過程執(zhí)行完，出棧，返回第1層。層１從第2層返回后，從斷點(diǎn)６開始執(zhí)行；執(zhí)行到語句７，又開始向下遞歸調(diào)用到層2，入棧，記錄第1層的返回地址8等信息。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc6,2,a,c,b8,2,b,a,c73層２執(zhí)行到語句５，向下遞歸調(diào)用。層３執(zhí)行語句１,2,3,9，結(jié)束，返回第2層。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc8,2,b,a,c6,1,b,c,a74層２從斷點(diǎn)語句6開始執(zhí)行，執(zhí)行到語句7，向下遞歸調(diào)用，到層3。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc8,2,b,a,c6,1,b,c,a75層３執(zhí)行語句１,2,3,9，結(jié)束，返回第2層。層２從第3層返回后，從斷點(diǎn)８開始執(zhí)行，過程執(zhí)行完，返回第1層。層1

從第2層返回后，從斷點(diǎn)８開始執(zhí)行，過程執(zhí)行完，返回主函數(shù)。遞歸工作棧狀態(tài)(返址,n值,x值,y值,z值)塔與圓盤的狀態(tài)0,3,a,b,cabc8,2,b,a,c8,1,a,b,c76Hanoi塔的遞歸函數(shù)運(yùn)行示意圖

77三個(gè)盤子搬動(dòng)時(shí)hanoi(3,A,B,C)遞歸調(diào)用過程：hanoi(2,A,C,B):hanoi(1,A,B,C)move(A->C)1號搬到Cmove(A->B) 2號搬到Bhanoi(1,C,A,B)move(C->B)1號搬到Bmove(A->C) 3號搬到Chanoi(2,B,A,C):hanoi(1,B,C,A)move(B->A) 1號搬到Amove(B->C)2號搬到Chanoi(1,A,B,C)move(A->C) 1號搬到C78

遞歸算法的特點(diǎn)：

(1)遞歸算法是一種分而治之、把復(fù)雜問題分解為簡單問題的求解問題方法，對求解某些復(fù)雜問題，遞歸算法的分析方法是非常有效的。（2）遞歸算法的時(shí)間效率、空間效率較低，因?yàn)檫f歸執(zhí)行時(shí)需要系統(tǒng)提供隱式棧實(shí)現(xiàn)遞歸。

79

小結(jié)

1設(shè)計(jì)遞歸算法的方法：

(1)尋找方法，將問題化為原問題的子問題求解（例n!=n*(n-1)!）。

(2)設(shè)計(jì)遞歸出口，確定遞歸終止條件

(例當(dāng)n=1時(shí)，n!=1)。

2調(diào)用三件事：傳遞本層參數(shù)、返回地址； 分配局部變量空間;控制轉(zhuǎn)移。 調(diào)用結(jié)束三件事：恢復(fù)上層；傳遞結(jié)果； 轉(zhuǎn)斷點(diǎn)執(zhí)行。

3.3棧與遞歸80

3.4隊(duì)列3.4

.1隊(duì)列的概念3.4

.2隊(duì)列的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)3.4

.3循環(huán)隊(duì)列

——隊(duì)列的順序存儲(chǔ)和實(shí)現(xiàn)813．4隊(duì)列3.4.1隊(duì)列的概念一什么是隊(duì)列隊(duì)列是限定僅能在表頭進(jìn)行刪除，表尾進(jìn)行插入的線性表（a1,a2,...,ai-1,ai,ai+1,…,an

）插入刪除823．4隊(duì)列

a1a2a3

an入隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)列隊(duì)列的示意圖隊(duì)列的特點(diǎn)先進(jìn)先出第一個(gè)入隊(duì)的元素在隊(duì)頭，

最后一個(gè)入隊(duì)的元素在隊(duì)尾，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，最后一個(gè)出隊(duì)的元素為隊(duì)尾元素833．4隊(duì)列

隊(duì)列的基本操作1）初始化操作

2）銷毀操作

3）置空操作4）判空操作5）取隊(duì)頭元素操作

6）入隊(duì)操作

7）出隊(duì)操作843.4.3鏈隊(duì)列——隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和實(shí)現(xiàn)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個(gè)尾指針，指向鏈表的最后一個(gè)結(jié)點(diǎn)。3.4隊(duì)列rearfront∧…∧frontrear

853.4隊(duì)列二鏈隊(duì)列的類型定義typedef

structQNode{QElemTypedata;

structQNode*next;}Qnode,*QueuePtr;Typedefstruct{QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;86鏈隊(duì)列圖示

非空隊(duì)rearfronta1an∧

…a2QrearfrontQa1∧

rearfrontQ

∧

空隊(duì)

只有一個(gè)元素結(jié)點(diǎn)

頭尾指針封裝在一起的鏈隊(duì)873.4隊(duì)列入隊(duì)算法StatusEnQueue(Queue&Q,ElemTypee)

{

//

在當(dāng)前隊(duì)列的尾元素之后，插入元素e為新的隊(duì)列尾元素

p=(QueuePtr)malloc(sizeof(Qnode));

if(!p)exit(OVERFLOW);

//

存儲(chǔ)分配失敗

p->data=e;

p->next=NULL;

Q.rear->next=p;

//

修改尾結(jié)點(diǎn)的指針

Q.rear=p;

//

移動(dòng)隊(duì)尾指針

returnOK;

}

pa2an∧rear∧reara1efront883.4隊(duì)列出隊(duì)算法

boolDeQueue(Queue&Q,ElemType&e)

{

//若隊(duì)列不空，則刪除當(dāng)前隊(duì)列Q中的頭元素，用e返回其值，并返回OK；否則返回ERROR

if(Q.front==Q.rear)

//

鏈隊(duì)列中只有一個(gè)頭結(jié)點(diǎn)

returnERROR;

p=Q.front->next;

e=p->data;

//

返回被刪元素

Q.front->next=p->next;

//

修改頭結(jié)點(diǎn)指針

if(Q.rear==p)Q.rear=Q.front;//隊(duì)列中只有一個(gè)元素

free(p);

//

釋放被刪結(jié)點(diǎn)

returnOK;

}fronta1a2an∧rearp893．4隊(duì)列順序隊(duì)列類型定義#defineMAXQSIZE100//最大隊(duì)列長度

typedefstruct{QElemType*base;//初始化的動(dòng)態(tài)分配存儲(chǔ)空間

intfront;//頭指針，若隊(duì)列不空，指向隊(duì)列頭元素

intrear;//尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置}SqQueue90rearfrontJ2(c)J1出隊(duì)（a)空隊(duì)列rearfront0123453.4隊(duì)列front,rear為整數(shù)

又有J7入隊(duì),怎么辦？

？rearfrontJ1(b)J1,J2相繼入隊(duì)列J2(d)J3,J4,J5和J6相繼入隊(duì)之后,J2出隊(duì)rearfrontJ5J4J3J6913.4隊(duì)列3.循環(huán)隊(duì)列frontrearJ6J4J5312405rear540312frontJ6J7J8J9J4J5frontrear540312(b)隊(duì)空(a)隊(duì)滿隊(duì)空、隊(duì)滿都是front=rear如何判斷循環(huán)隊(duì)列隊(duì)空、隊(duì)滿？

？J7rear923.4隊(duì)列判分隊(duì)空、隊(duì)滿有兩種方法：

1）另設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)空、隊(duì)滿。

2）少用一個(gè)存儲(chǔ)單元，隊(duì)滿條件： front=rear+1;隊(duì)空：front=rear隊(duì)列中元素的個(gè)數(shù)？（rear–front+MAXQSIZE

）%MAXQSIZEfront540312J6J7J8J4J5（c）rear933.4隊(duì)列循環(huán)隊(duì)列的基本操作算法

frontrear540312建一個(gè)空隊(duì)列QStatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(sizeof(QElemType)*MAXSIZE);if(!Q.base)return(OVERFLOW);Q.front=Q.rear=0;returnOK;}//InitQueue943.4隊(duì)列入隊(duì)操作

：將元素x插入隊(duì)尾

frontrear540312J1J3J2xfront540312J1J3J2隊(duì)列滿元素x入隊(duì)后StatusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXSIZE==Q.front)return(ERROR);Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueueJ4J5rear953.4隊(duì)列入隊(duì)操作

：將元素x插入隊(duì)尾

frontrear540312J1J3J2xfrontrear540312J1J3J2元素x入隊(duì)前元素x入隊(duì)后StatusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXSIZE==Q.front)return(ERROR);Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;returnOK;}//EnQueue963.4隊(duì)列出隊(duì)操作

：刪除隊(duì)頭元素；

frontrear540312J1J3J2出隊(duì)操作前frontrear540312J1J3J2出隊(duì)操作后StatusDeQueue(SqQueue&Q,Qe