數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述(第二版)課件：限定性線性表-棧和隊(duì)列

限定性線性表—棧和隊(duì)列3.1棧3.2隊(duì)列3.1棧3.1.1棧的定義

棧作為一種限定性線性表，是將線性表的插入和刪除運(yùn)算限制為僅在表的一端進(jìn)行，通常將表中允許進(jìn)行插入、刪除操作的一端稱(chēng)為棧頂(Top)，因此棧頂?shù)漠?dāng)前位置是動(dòng)態(tài)變化的，它由一個(gè)稱(chēng)為棧頂指針的位置指示器指示。同時(shí)表的另一端被稱(chēng)為棧底(Bottom)。當(dāng)棧中沒(méi)有元素時(shí)稱(chēng)為空棧。棧的插入操作被形象地稱(chēng)為進(jìn)棧或入棧，刪除操作稱(chēng)為出棧或退棧。根據(jù)上述定義，每次進(jìn)棧的元素都被放在原棧頂元素之上而成為新的棧頂，而每次出棧的總是當(dāng)前棧中“最新”的元素，即最后進(jìn)棧的元素。在圖3.1（a）所示的棧中，元素是以a1，a2，a3，…，an的順序進(jìn)棧的，而退棧的次序卻是an，…，a3，a2，a1。棧的修改是按后進(jìn)先出的原則進(jìn)行的，因此棧又稱(chēng)為后進(jìn)先出的線性表，簡(jiǎn)稱(chēng)為L(zhǎng)IFO表。在日常生活中也可以見(jiàn)到很多“后進(jìn)先出”的例子，如手槍子彈夾中的子彈，子彈的裝入與子彈彈出膛均在彈夾的最上端進(jìn)行，先裝入的子彈后發(fā)出，而后裝入的子彈先發(fā)出；又如鐵路調(diào)度站(見(jiàn)圖3.1(b))，也是棧結(jié)構(gòu)的實(shí)際應(yīng)用。圖3.1棧ADTStack

數(shù)據(jù)元素：可以是任意類(lèi)型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對(duì)象。關(guān)系：棧中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎?/p>

（1）InitStack(S)

操作前提：S為未初始化的棧。操作結(jié)果：將S初始化為空棧。（2）ClearStack(S)

操作前提：棧S已經(jīng)存在。操作結(jié)果：將棧S置成空棧。

（3）IsEmpty(S)

操作前提：棧S已經(jīng)存在。操作結(jié)果：判?？蘸瘮?shù)，若S為空棧，則函數(shù)值為T(mén)RUE，否則為FALSE。（4）IsFull(S)

操作前提：棧S已經(jīng)存在。操作結(jié)果：判棧滿函數(shù)，若S棧已滿，則函數(shù)值為T(mén)RUE，否則為FALSE。

（5）Push(S,x)

操作前提：棧S已經(jīng)存在。操作結(jié)果：在S的頂部插入(亦稱(chēng)壓入)元素x；若S棧未滿，將x插入棧頂位置，若棧已滿，則返回FALSE，表示操作失敗，否則返回TRUE。（6）Pop(S,x)

操作前提：棧S已經(jīng)存在。操作結(jié)果：刪除(亦稱(chēng)彈出)棧S的頂部元素，并用x帶回該值；若棧為空，返回值為FALSE，表示操作失敗，否則返回TRUE。（7）GetTop(S,x)

操作前提：棧S已經(jīng)存在。操作結(jié)果：取棧S的頂部元素。與Pop(S,x)不同之處在于GetTop(S,x)不改變棧頂?shù)奈恢谩?/p>

3.1.2棧的表示和實(shí)現(xiàn)1.順序棧順序棧是用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)由于棧的操作的特殊性，還必須附設(shè)一個(gè)位置指針top（棧頂指針）來(lái)動(dòng)態(tài)地指示棧頂元素在順序棧中的位置。通常以top=-1表示空棧。順序棧的存儲(chǔ)結(jié)構(gòu)可以用C語(yǔ)言中的一維數(shù)組來(lái)表示。棧的順序存儲(chǔ)結(jié)構(gòu)定義如下：＃defineTRUE1

＃defineFALSE0

＃defineStack

-Size50

typedefstruct

{

StackElementTypeelem［Stack-Size］;/*用來(lái)存放棧中元素的一維數(shù)組*/inttop;/*用來(lái)存放棧頂元素的下標(biāo)*/

}SeqStack;圖3.2順序棧中的進(jìn)棧和出棧順序?；静僮鞯膶?shí)現(xiàn)如下:

(1)初始化。voidInitStack(SeqStack*S)

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

S->top=-1;

}(2)判?？铡ntIsEmpty(SeqStack*S)/*判棧S為空棧時(shí)返回值為真，反之為假*/

{

return(S->top==-1?TRUE:FALSE);

}(3)判棧滿。intIsFull(SeqStack*S)

{

return(S->top==Stack

-Size?TRUE:FALSE);

}

(4)進(jìn)棧。intPush(SeqStack*S,StackElementTypex)

{

if(S->top==Stack

-Size)return(FALSE);/*棧已滿*/

S->top++;

S->elem［S->top］=x;

return(TRUE);

}(5)出棧。intPop(SeqStack*S,StackElementType*x)

{/*將棧S的棧頂元素彈出，放到x所指的存儲(chǔ)空間中*/

if(S->top==-1)/*棧為空*/

return(FALSE);

else

{

*x=S->elem［S->top］;

S->top--;/*修改棧頂指針*/

return(TRUE);

}

}(6)取棧頂元素。intGetTop（SeqStackS,StackElementType*x）{/*將棧S的棧頂元素彈出，放到x所指的存儲(chǔ)空間中，但棧頂指針保持不變*/

if(S->top==-1)/*棧為空*/

return(FALSE);

else

{

*x=S->elem［S->top］;

return(TRUE);

}

}

在棧的共享技術(shù)中最常用的是兩個(gè)棧的共享技術(shù)：它主要利用了?！皸５孜恢貌蛔?，而棧頂位置動(dòng)態(tài)變化”的特性。首先為兩個(gè)棧申請(qǐng)一個(gè)共享的一維數(shù)組空間S［M］，將兩個(gè)棧的棧底分別放在一維數(shù)組的兩端，分別是0，M-1。由于兩個(gè)棧頂動(dòng)態(tài)變化，這樣可以形成互補(bǔ)，使得每個(gè)?？捎玫淖畲罂臻g與實(shí)際使用的需求有關(guān)。由此可見(jiàn)，兩棧共享比兩個(gè)棧分別申請(qǐng)M/2的空間利用率高。兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義如下：＃defineM100

typedefstruct

{

StackElementTypeStack［M］;

StackElementTypetop［2］;/*top［0］和top［1］分別為兩個(gè)棧頂指示器*/

}DqStack;圖3.3共享?xiàng)３跏蓟僮?。voidInitStack(DqStack*S)

{

S->top［0］=-1;

S->top［1］=M;

}(2)進(jìn)棧操作算法。intPush(DqStack*S,StackElementTypex,inti)

{/*把數(shù)據(jù)元素x壓入i號(hào)堆棧*/

if(S->top［0］+1==S->top［1］)/*棧已滿*/

return(FALSE);

switch(i)

{

case0:

S->top［0］++;S->Stack［S->top［0］］=x;

break;

case1:

S->top［1］--;

S->Stack［S->top［1］］=x;

break;

default:/*參數(shù)錯(cuò)誤*/

return(FALSE)

}

return(TRUE);

}(3)出棧操作算法。intPop(DqStack*S,StackElementType*x,inti)

{/*從i號(hào)堆棧中彈出棧頂元素并送到x中*/

switch(i)

{

case0:

if(S->top［0］==-1)return(FALSE);

*x=S->Stack［S->top［0］］;

S->top［0］--;

break;

case1:

if(S->top［1］==M)return(FALSE);

*x=S->Stack［S->top［1］］;

S->top［1］++;

break;

default:

return(FALSE);

}

return(TRUE);

}2.鏈棧圖3.4鏈棧示意圖鏈棧的結(jié)構(gòu)可用C語(yǔ)言定義如下：typedefstructnode

{

StackElementTypedata;

structnode*next;

}LinkStackNode;

typedefLinkStackNode*LinkStack;(1)進(jìn)棧操作。intPush(LinkStacktop,StackElementTypex)

/*將數(shù)據(jù)元素x壓入棧top中*/

{

LinkStackNode*temp;

temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));

if(temp==NULL)return(FALSE);/*申請(qǐng)空間失敗*/

temp->data=x;

temp->next=top->next;

top->next=temp;/*修改當(dāng)前棧頂指針*/

return(TRUE);

}(2)出棧操作。intPop(LinkStacktop,StackElementType*x)

{/*將棧top的棧頂元素彈出，放到x所指的存儲(chǔ)空間中*/

LinkStackNode*temp;

temp=top->next;

if(temp==NULL)/*棧為空*/

return(FALSE);

top->next=temp->next;

*x=temp->data;

free(temp);/*釋放存儲(chǔ)空間*/

return(TRUE);

}3.1.3棧的應(yīng)用舉例1.數(shù)制轉(zhuǎn)換假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)，一個(gè)簡(jiǎn)單的轉(zhuǎn)換算法是重復(fù)下述兩步，直到N等于零：X=Nmodd(其中mod為求余運(yùn)算)

N=Ndivd(其中div為整除運(yùn)算)voidConversion(intN)

{/*對(duì)于任意的一個(gè)非負(fù)十進(jìn)制數(shù)N，打印出與其等值的二進(jìn)制數(shù)*/

StackS;intx;/*S為順序棧或鏈棧*/

InitStack(&S);

while(N>0)

{

x=N%2;

Push(&S,x);/*將轉(zhuǎn)換后的數(shù)字壓入棧S*/

N=N/2;

}

while(！IsEmpty(S))

{

Pop(&S,&x);

printf(″%d″,x);

}

}2.括號(hào)匹配問(wèn)題

假設(shè)表達(dá)式中包含三種括號(hào)：圓括號(hào)、方括號(hào)和花括號(hào)，它們可互相嵌套，如(［{}］(［］))或({(［］［()］)})等均為正確的格式，而{［］})}或{［()］或(［］}均為不正確的格式。在檢驗(yàn)算法中可設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)，若是左括號(hào)，則直接入棧，等待相匹配的同類(lèi)右括號(hào)；若讀入的是右括號(hào)，且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)同類(lèi)型，則二者匹配，將棧頂?shù)淖罄ㄌ?hào)出棧，否則屬于不合法的情況。另外，如果輸入序列已讀盡，而棧中仍有等待匹配的左括號(hào)，或者讀入了一個(gè)右括號(hào)，而棧中已無(wú)等待匹配的左括號(hào)，均屬不合法的情況。當(dāng)輸入序列和棧同時(shí)變?yōu)榭諘r(shí)，說(shuō)明所有括號(hào)完全匹配。voidBracketMatch(char*str)=/*str［］中為輸入的字符串，利用堆棧技術(shù)來(lái)檢查該字符串中的括號(hào)是否匹配*/={

StackS;inti;charch;

InitStack(&S);

For(i=0;str［i］![KG-*2]=′\0′;i++)/*對(duì)字符串中的字符逐一掃描*/{

switch(str［i］){

case′(′:

case′［′:

case′{′: Push(&S,str［i］);

break;

case′)′:

case′］′:

case′}′:

if(IsEmpty(S))

{printf(″\n右括號(hào)多余!″);return;}

else

{

GetTop(&S,&ch);

if(Match(ch,str［i］))/*用Match判斷兩個(gè)括號(hào)是否匹配*/

Pop(&S,&ch);/*已匹配的左括號(hào)出棧*/

else

{printf(″\n對(duì)應(yīng)的左右括號(hào)不同類(lèi)!″);return;}

}

}/*switch*/

}/*for*/

if(IsEmpty(S))

printf(″\n括號(hào)匹配!″);

else

printf(″\n左括號(hào)多余!″);

}3.表達(dá)式求值

表達(dá)式求值是高級(jí)語(yǔ)言編譯中的一個(gè)基本問(wèn)題，是棧的典型應(yīng)用實(shí)例。任何一個(gè)表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。操作數(shù)既可以是常數(shù)，也可以是被說(shuō)明為變量或常量的標(biāo)識(shí)符；運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符三類(lèi)；基本界限符有左右括號(hào)和表達(dá)式結(jié)束符等。1）無(wú)括號(hào)算術(shù)表達(dá)式求值

表達(dá)式計(jì)算

程序設(shè)計(jì)語(yǔ)言中都有計(jì)算表達(dá)式的問(wèn)題，這是語(yǔ)言編譯中的典型問(wèn)題。

(1)表達(dá)式形式：由運(yùn)算對(duì)象、運(yùn)算符及必要的表達(dá)式括號(hào)組成；

(2)表達(dá)式運(yùn)算：運(yùn)算時(shí)要有一個(gè)正確的運(yùn)算形式順序。由于某些運(yùn)算符可能具有比別的運(yùn)算符更高的優(yōu)先級(jí)，因此表達(dá)式不可能?chē)?yán)格的從左到右，見(jiàn)圖3.5。圖3.5表達(dá)式運(yùn)算及運(yùn)算符優(yōu)先級(jí)圖3.6無(wú)括號(hào)算術(shù)表達(dá)式的處理過(guò)程2）算術(shù)表達(dá)式處理規(guī)則

(1)規(guī)定優(yōu)先級(jí)表。

(2)設(shè)置兩個(gè)棧：OVS(運(yùn)算數(shù)棧)和OPTR(運(yùn)算符棧)。

(3)自左向右掃描，遇操作數(shù)進(jìn)OVS，遇操作符則與OPTR棧頂優(yōu)先數(shù)比較：當(dāng)前操作符>OPTR棧頂,當(dāng)前操作符進(jìn)OPTR棧當(dāng)前操作符≤OPTR棧頂，OVS棧頂、次頂和OPTR棧頂，退棧形成運(yùn)算T(i)，T(i)進(jìn)OVS棧。例：實(shí)現(xiàn)A/B↑C+D*E＃的運(yùn)算過(guò)程時(shí)棧區(qū)變化情況如圖3.7所示。圖3.7A/B↑C+D*E運(yùn)算過(guò)程的棧區(qū)變化情況示意圖3）帶括號(hào)算術(shù)表達(dá)式假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符，界限符有左右括號(hào)和表達(dá)式起始、結(jié)束符“?！?，如：＃（7+15）*（23-28/4）＃。引入表達(dá)式起始、結(jié)束符是為了方便。要對(duì)一個(gè)簡(jiǎn)單的算術(shù)表達(dá)式求值，首先要了解算術(shù)四則運(yùn)算的規(guī)則，即：(1)從左算到右；(2)先乘除，后加減；(3)先括號(hào)內(nèi)，后括號(hào)外。

運(yùn)算符和界限符可統(tǒng)稱(chēng)為算符，它們構(gòu)成的集合命名為OPS。根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算過(guò)程中，任意兩個(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。表3-1算符之間的優(yōu)先關(guān)系

實(shí)現(xiàn)算符優(yōu)先算法時(shí)需要使用兩個(gè)工作棧：一個(gè)稱(chēng)作operator，用以存放運(yùn)算符；另一個(gè)稱(chēng)作operand，用以存放操作數(shù)或運(yùn)算的中間結(jié)果。算法的基本過(guò)程如下：首先初始化操作數(shù)棧operand和運(yùn)算符棧operator，并將表達(dá)式起始符“?！眽喝脒\(yùn)算符棧；依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)則直接進(jìn)入操作數(shù)棧operand，若是運(yùn)算符，則與運(yùn)算符棧operator的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)比較，并做如下處理：(1)若棧頂運(yùn)算符的優(yōu)先級(jí)低于剛讀入的運(yùn)算符，則讓剛讀入的運(yùn)算符進(jìn)operator棧；

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

(3)若棧頂運(yùn)算符的優(yōu)先級(jí)與剛讀入的運(yùn)算符的優(yōu)先級(jí)相同，說(shuō)明左右括號(hào)相遇，只需將棧頂運(yùn)算符（左括號(hào)）退棧即可。算法具體描述如下：intExpEvaluation()

/*讀入一個(gè)簡(jiǎn)單算術(shù)表達(dá)式并計(jì)算其值。operator和operand分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OPS為運(yùn)算符集合*/

{

InitStack(&operand);

InitStack(&operator);

Push(&operator,′＃′);

printf(″\n\nPleaseinputanexpression(Endingwith＃):″);

ch=getchar();

while(ch!=′?！鋦|GetTop(operator)!=′?！?/*GetTop()通過(guò)函數(shù)值返回棧頂元素*/

{

if(!In(ch,OPS))

{a=GetNumber(&ch);/*用ch逐個(gè)讀入操作數(shù)的各位數(shù)碼，并轉(zhuǎn)化為十進(jìn)制數(shù)a*/

Push(&operand,a);}

else

switch(Compare(GetTop(operator),ch))

{

case′<′:Push(&operator,ch);

ch=getchar();break;

case′=′:Pop(&operator,&x);

ch=getchar();break;

case′>′:Pop(&operator,&op);

Pop(&operand,&b);

Pop(&operand,&a);

v=Execute(a,op,b);/*對(duì)a和b進(jìn)行op運(yùn)算*/

Push(&operand,v);

break;

}

}

v=GetTop(operand);

return(v);

}3.1.4棧與遞歸的實(shí)現(xiàn)

棧非常重要的一個(gè)應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中用來(lái)實(shí)現(xiàn)遞歸。遞歸是指在定義自身的同時(shí)又出現(xiàn)了對(duì)自身的調(diào)用。如果一個(gè)函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱(chēng)其為直接遞歸函數(shù)；如果一個(gè)函數(shù)經(jīng)過(guò)一系列的中間調(diào)用語(yǔ)句，通過(guò)其它函數(shù)間接調(diào)用自己，則稱(chēng)其為間接遞歸函數(shù)。1.遞歸特性問(wèn)題1)遞歸函數(shù)例如，很多數(shù)學(xué)函數(shù)是遞歸定義的，如二階Fibonacci數(shù)列：2)遞歸結(jié)構(gòu)

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

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

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

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

如何實(shí)現(xiàn)移動(dòng)圓盤(pán)的操作呢？當(dāng)n=1時(shí)，問(wèn)題比較簡(jiǎn)單，只要將編號(hào)為1的圓盤(pán)從塔座X直接移動(dòng)到塔座Z上即可；當(dāng)n>1時(shí)，需利用塔座Y作輔助塔座，若能設(shè)法將壓在編號(hào)為n的圓盤(pán)上的n-1個(gè)圓盤(pán)從塔座X(依照上述原則)移至塔座Y上，則可先將編號(hào)為n的圓盤(pán)從塔座X移至塔座Z上，然后再將塔座Y上的n-1個(gè)圓盤(pán)(依照上述原則)移至塔座Z上。而如何將n-1個(gè)圓盤(pán)從一個(gè)塔座移至另一個(gè)塔座問(wèn)題是一個(gè)和原問(wèn)題具有相同特征屬性的問(wèn)題，只是問(wèn)題的規(guī)模小個(gè)1，因此可以用同樣方法求解。由此可得如下算法所示的求解n階Hanoi塔問(wèn)題的函數(shù)。voidhanoi(intn,charx,chary,charz)/*將塔座X上按直徑由小到大且至上而下編號(hào)為1至n的n個(gè)圓盤(pán)按規(guī)則搬到塔座Z上，Y可用作輔助塔座*/

{

if(n==1)

move(x,1,z);/*將編號(hào)為1的圓盤(pán)從X移動(dòng)Z*/

else{

hanoi(n-1,x,z,y);/*將X上編號(hào)為1至n-1的圓盤(pán)移到Y(jié),Z作輔助塔*/

move(x,n,z);/*將編號(hào)為n的圓盤(pán)從X移到Z*/

hanoi(n-1,y,x,z);/*將Y上編號(hào)為1至n-1的圓盤(pán)移動(dòng)到Z，X作輔助塔*/}

}

下面給出三個(gè)盤(pán)子搬動(dòng)時(shí)hanoi(3,A,B,C)遞歸調(diào)用過(guò)程，如圖3.8所示。hanoi(2,A,C,B):

hanoi(1,A,B,C)move(A->C)1號(hào)搬到C

move(A->B) 2號(hào)搬到B

hanoi(1,C,A,B)move(C->B)1號(hào)搬到B

move(A->c) 3號(hào)搬到C

hanoi(2,B,A,C):

hanoi(1,B,C,A)move(B->A) 1號(hào)搬到A

move(B->c)2號(hào)搬到C

hanoi(1,A,B,C)move(A->C) 1號(hào)搬到C圖3.8Hanoi塔的遞歸函數(shù)運(yùn)行示意圖3)遞歸問(wèn)題的優(yōu)點(diǎn)通過(guò)上面的例子可看出，遞歸既是強(qiáng)有力的數(shù)學(xué)方法，也是程序設(shè)計(jì)中一個(gè)很有用的工具。其特點(diǎn)是對(duì)遞歸問(wèn)題描述簡(jiǎn)捷，結(jié)構(gòu)清晰，程序的正確性容易證明。

4)遞歸算法求解問(wèn)題的要素遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。遞歸算法的要點(diǎn)如下：

(1)問(wèn)題具有類(lèi)同自身的子問(wèn)題的性質(zhì)，被定義項(xiàng)在定義中的應(yīng)用具有更小的尺度。

(2)被定義項(xiàng)在最小尺度上有直接解。

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

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

(2)設(shè)計(jì)遞歸出口，確定遞歸終止條件(例求解n!時(shí)，當(dāng)n=1時(shí)，n!=1)。5)遞歸過(guò)程的實(shí)現(xiàn)遞歸進(jìn)層（i→i+1層）系統(tǒng)需要做三件事：

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

(2)給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)）；

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

而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，遞歸退層（i←i+1層）系統(tǒng)也應(yīng)完成三件工作：

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

(2)恢復(fù)上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）；

(3)依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。當(dāng)遞歸函數(shù)調(diào)用時(shí)，應(yīng)按照“后調(diào)用先返回”的原則處理調(diào)用過(guò)程，因此上述函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過(guò)棧來(lái)實(shí)現(xiàn)。系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需的數(shù)據(jù)空間安排在一個(gè)棧中，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就為它在棧頂分配一個(gè)存儲(chǔ)區(qū)，而每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲(chǔ)區(qū)。顯然，當(dāng)前正在運(yùn)行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂。在一個(gè)遞歸函數(shù)的運(yùn)行過(guò)程中調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)，因此與每次調(diào)用時(shí)相關(guān)的一個(gè)重要的概念是遞歸函數(shù)運(yùn)行的“層次”。假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)為第0層，則從主函數(shù)調(diào)用遞歸函數(shù)為進(jìn)入第1層；從第i層遞歸調(diào)用本函數(shù)為進(jìn)入“下一層”，即第i+1層。反之，退出第i層遞歸應(yīng)返回至“上一層”，即第i-1層。為了保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)需設(shè)立一個(gè)遞歸工作棧作為整個(gè)遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)。每層遞歸所需信息構(gòu)成一個(gè)工作記錄，其中包括所有的實(shí)在參數(shù)、所有的局部變量以及上一層的返回地址。每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新的工作記錄壓入棧頂。每退出一層遞歸，就從棧頂彈出一個(gè)工作記錄。因此當(dāng)前執(zhí)行層的工作記錄必為遞歸工作棧棧頂?shù)墓ぷ饔涗?，我們稱(chēng)這個(gè)記錄為活動(dòng)記錄，并稱(chēng)指示活動(dòng)記錄的棧頂指針為當(dāng)前環(huán)境指針。由于遞歸工作棧是由系統(tǒng)來(lái)管理的，不需用戶操心，所以用遞歸法編制程序非常方便。例：更小尺度其遞歸算法如下，n=3時(shí)的遞歸調(diào)用的變化情況如圖3.9所示。intf(intn)

/*設(shè)n>0*/

{

if(n==0)thenreturn(1);

elsereturn(n*f(n-1))；}遞歸進(jìn)層三件事：保存本層參數(shù)、返回地址;

傳遞參數(shù)，分配局部數(shù)據(jù)空間;

控制轉(zhuǎn)移。遞歸退層三件事：恢復(fù)上層；傳遞結(jié)果；轉(zhuǎn)斷點(diǎn)執(zhí)行。圖3.10遞歸調(diào)用流程變化示意由圖3.10可看出，整個(gè)計(jì)算包括自上而下遞歸調(diào)用進(jìn)層和自下而上遞歸返回退層兩個(gè)階段，所有遞歸調(diào)用直接或間接依賴(lài)f(0)，所以整個(gè)階段分兩步，計(jì)算順序在第二階段，先計(jì)算f(0)→f(1)→…→f(n),并用工作變量y記錄中間結(jié)果。

2.遞歸算法到非遞歸算法轉(zhuǎn)換

遞歸算法具有兩個(gè)特性：

(1)遞歸算法是一種分而治之、把復(fù)雜問(wèn)題分解為簡(jiǎn)單問(wèn)題的求解問(wèn)題方法，對(duì)求解某些復(fù)雜問(wèn)題，遞歸算法的分析方法是有效的。（2）遞歸算法的時(shí)間效率低。1)消除遞歸的原因其一：有利于提高算法時(shí)空性能，因?yàn)檫f歸執(zhí)行時(shí)需要系統(tǒng)提供隱式棧實(shí)現(xiàn)遞歸，效率低且費(fèi)時(shí)。其二：無(wú)應(yīng)用遞歸語(yǔ)句的語(yǔ)言設(shè)施環(huán)境條件，有些計(jì)算機(jī)語(yǔ)言不支持遞歸功能，如FORTRAN、C語(yǔ)言中無(wú)遞歸機(jī)制。其三：遞歸算法是一次執(zhí)行完，這在處理有些問(wèn)題時(shí)不合適，也存在一個(gè)把遞歸算法轉(zhuǎn)化為非遞歸算法的需求。2)簡(jiǎn)單遞歸（尾遞歸和單向遞歸）消除在簡(jiǎn)單情況下，將遞歸算法可簡(jiǎn)化為線性序列執(zhí)行，可直接轉(zhuǎn)換為循環(huán)實(shí)現(xiàn)。例：斐波那契數(shù)列圖3.11

Fib(5)遞歸調(diào)用過(guò)程示意intFib(intn)

{

if（n==0||n==1）returnn;

/*遞歸出口*/

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

}

圖3.11中的15個(gè)點(diǎn)表示15次運(yùn)算。如果合并重合點(diǎn)，按圖3.12所示粗黑線循環(huán)實(shí)現(xiàn)計(jì)算，共需進(jìn)行5次運(yùn)算。圖3.12

Fib(5)循環(huán)調(diào)用過(guò)程示意

單向遞歸的一個(gè)典型例子是我們討論過(guò)的計(jì)算斐波那契數(shù)列的算法Fib(n)。其中，遞歸調(diào)用語(yǔ)句Fib(n-1)和Fib(n-2)只與主調(diào)用函數(shù)Fib(n)有關(guān)，相互之間參數(shù)無(wú)關(guān)，并且這些遞歸調(diào)用語(yǔ)句也和尾遞歸一樣處于算法的最后。intFib(intn):

{intx,y,z;

if（n==0||n==1）returnn;/*計(jì)算Fib(0),Fib(1)*/

else{intx=0,y=1,z;

/*x=Fib(0),y=Fib(1)*/

for(i=2;i<=n;i++)

{z=y;/*z=Fib(i-1)*/=

y=x+y;/*y=Fib(i-1)+Fib(i-2)，求Fib(i)，形成第i項(xiàng)*/

x=z};/*x=Fib(i-1)*/

}

returny;

}

尾遞歸是指遞歸調(diào)用語(yǔ)句只有一個(gè)，而且是處于算法的最后。我們以階乘問(wèn)題的遞歸算法Fact(n)為例討論尾遞歸算法的運(yùn)行過(guò)程。為討論方便，我們列出階乘問(wèn)題的遞歸算法Fact(n)，并簡(jiǎn)化掉參數(shù)n的出錯(cuò)檢查語(yǔ)句，改寫(xiě)遞歸調(diào)用語(yǔ)句的位置在最后，算法如下：longFact(intn)

{

if(n==0)return1;

returnn*Fact(n-1);

}循環(huán)結(jié)構(gòu)的階乘問(wèn)題算法Fact(n)如下：longFact(intn)

{

intfac=1;

for(inti=1;i<=n;i++)/*依次計(jì)算f(1)，…，f(n)*/

fac=fac*i;/*f(i)=f(i)*i*/

returnfac;

}3.2隊(duì)列3.2.1隊(duì)列的定義隊(duì)列

(Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出(FistInFistOut，縮寫(xiě)為FIFO)的特性。在隊(duì)列中，允許插入的一端叫做隊(duì)尾(rear)，允許刪除的一端則稱(chēng)為隊(duì)頭(front)。假設(shè)隊(duì)列為q=(a1，a2，…，an)，那么a1就是隊(duì)頭元素，an則是隊(duì)尾元素。隊(duì)列中的元素是按照a1，a2，…，an的順序進(jìn)入的，退出隊(duì)列也必須按照同樣的次序依次出隊(duì)，也就是說(shuō)，只有在a1，a2，…，an-1都離開(kāi)隊(duì)列之后，an才能退出隊(duì)列。

數(shù)據(jù)元素：可以是任意類(lèi)型的數(shù)據(jù)，但必須屬于同一個(gè)數(shù)據(jù)對(duì)象。

關(guān)系：隊(duì)列中數(shù)據(jù)元素之間是線性關(guān)系?；静僮鳎?/p>

（1）InitQueue(&Q)：初始化操作。設(shè)置一個(gè)空隊(duì)列。（2）IsEmpty(Q)：判空操作。若隊(duì)列為空，則返回TRUE，否則返回FALSE。（3）EnterQueue(&Q，x)：進(jìn)隊(duì)操作。在隊(duì)列Q的隊(duì)尾插入x。操作成功，返回值為T(mén)RUE，否則返回值為FALSE。

（4）DeleteQueue(&Q,&x)：出隊(duì)操作。使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用x帶回其值。操作成功，返回值為RUE，否則返回值為FALSE。（5）GetHead（Q,&x）：取隊(duì)頭元素操作。用x取得隊(duì)元素的值。操作成功，返回值為T(mén)RUE，否則返回值為FALSE。（6）ClearQueue(&Q)：隊(duì)列置空操作。將隊(duì)列Q置為空隊(duì)列。（7）DestroyQueue(&Q)：隊(duì)列銷(xiāo)毀操作。釋放隊(duì)列的空間。3.2.2隊(duì)列的表示和實(shí)現(xiàn)1.鏈隊(duì)列圖3.13鏈隊(duì)列鏈隊(duì)列可以定義如下：＃defineTRUE1

＃defineFALSE0

typedefstructNode

{

QueueElementTypedata;/*數(shù)據(jù)域*/

structNodenext;/*指針域*/

}LinkQueueNode;

typedefstruct

{

LinkQueueNode*front;

LinkQueueNode*rear;

}LinkQueue;（1）初始化操作。intInitQueue(LinkQueue*Q)

{/*將Q初始化為一個(gè)空的鏈隊(duì)列*/

Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));

if(Q->front!=NULL)

{

Q->rear=Q->front;

Q->front->next=NULL;

return(TRUE);

}

elsereturn(FALSE);/*溢出！*/

}（2）入隊(duì)操作。intEnterQueue(LinkQueue*Q,QueueElementTypex)

{/*將數(shù)據(jù)元素x插入到隊(duì)列Q中*/

LinkQueueNode*NewNode;

NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));

if(NewNode!=NULL)

{

NewNode->data=x;

NewNode->next=NULL;

Q->rear->next=NewNode;

Q->rear=NewNode;

return(TRUE);

}

elsereturn(FALSE);/*溢出！*/

}（3）出隊(duì)操作。intDeleteQueue(LinkQueue*Q,QueueElementType*x)

{/*將隊(duì)列Q的隊(duì)頭元素出隊(duì)，并存放到x所指的存儲(chǔ)空間中*/

LinkQueueNode*p;

if(Q->front==Q->rear)

return(FALSE);

p=Q->front->next;

Q->front->next=p->next;/*隊(duì)頭元素p出隊(duì)*/

if(Q->rear==p)/*如果隊(duì)中只有一個(gè)元素p，則p出隊(duì)后成為空隊(duì)*/

Q->rear=Q->front;

*x=p->data;

free(p);/*釋放存儲(chǔ)空間*/

return(TRUE);

}2.循環(huán)隊(duì)列圖3.14隊(duì)列的基本操作圖3.15循環(huán)隊(duì)列循環(huán)隊(duì)列的類(lèi)型定義：＃defineMAXSIZE50/*隊(duì)列的最大長(zhǎng)度*/

typedefstruct

{

QueueElementTypeelement［MAXSIZE］;/*隊(duì)列的元素空間*/

intfront;/*頭指針指示器*/

intrear;/*尾指針指示器*/

}SeqQueue;（1）初始化操作。voidInitQueue（SeqQueue*Q）{/*將*Q初始化為一個(gè)空的循環(huán)隊(duì)列*/

Q->front=Q->rear=0;

}（2）入隊(duì)操作。intEnterQueue(SeqQueue*Q,QueueElementTypex)

{/*將元素x入隊(duì)*/

if((Q->rear+1)%MAXSIZE==Q->front)/*隊(duì)列已經(jīng)滿了*/

return(FALSE);

Q->element［Q->rear］=x;

Q->rear=(Q->rear+1)%MAXSIZE;/*重新設(shè)置隊(duì)尾指針*/

return(TRUE);/*操作成功*/

}（3）出隊(duì)操作。

intDeleteQueue(SeqQueue*Q,QueueElementType*x)

{/*刪除隊(duì)列的隊(duì)頭元素，用x返回其值*/

if（Q->front==Q->rear）/*隊(duì)列為空*/

return(FALSE);

*x=Q->element［Q->front］;

Q->front=(Q->front+1)%MAXSIZE;/*重新設(shè)置隊(duì)頭指針*/

return(TRUE);/*操作成功*/

}3.2.3隊(duì)列的應(yīng)用舉例1.打印楊輝三角圖3.16楊輝三角形圖3.17楊輝三角形元素入隊(duì)順序(1)第7行的第一個(gè)元素1入隊(duì)。