網(wǎng)頁(yè)設(shè)計(jì)一部分課程龍巖學(xué)院3 three

1

第三章棧和隊(duì)列2棧和隊(duì)列是重要的數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列是線性表的子集（是插入和刪除受限的線性表）前言3【學(xué)習(xí)目標(biāo)】

1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。

2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法。

3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。

4.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。

【重點(diǎn)和難點(diǎn)】

棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問(wèn)題中正確使用。

4【學(xué)習(xí)指南】

在這一章中，主要是學(xué)習(xí)如何在求解應(yīng)用問(wèn)題中適當(dāng)?shù)貞?yīng)用棧和隊(duì)列，棧和隊(duì)列在兩種存儲(chǔ)結(jié)構(gòu)中的實(shí)現(xiàn)都不難，但應(yīng)該對(duì)它們了如指掌，特別要注意它們的基本操作實(shí)現(xiàn)時(shí)的一些特殊情況，如棧滿和棧空、隊(duì)滿和隊(duì)空的條件以及它們的描述方法。5【課前思考】

1.什么是線性結(jié)構(gòu)？

簡(jiǎn)單地說(shuō)，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的序列。

2.你見(jiàn)過(guò)餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的,那么使用時(shí)候的次序應(yīng)是什么樣的？

必然是依從上往下的次序，即n,…,2,1。它們遵循的是"后進(jìn)先出"的規(guī)律，這正是本章要討論的"棧"的結(jié)構(gòu)特點(diǎn)。

3.在日常生活中，為了維持正常的社會(huì)秩序而出現(xiàn)的常見(jiàn)現(xiàn)象是什么？

是"排隊(duì)"。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是"隊(duì)列"。6棧必須按“后進(jìn)先出”的規(guī)則進(jìn)行操作，隊(duì)列必須按“先進(jìn)先出”的規(guī)則進(jìn)行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結(jié)構(gòu)。從“數(shù)據(jù)結(jié)構(gòu)”的角度看:

它們都是線性結(jié)構(gòu)，即數(shù)據(jù)元素之間的關(guān)系相同。

但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對(duì)插入和刪除操作的"限定"。7

通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。

線性表?xiàng)ｊ?duì)列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類型83.1

棧的類型定義9

3.1棧的類型定義

棧（Stack）是限定只能在表的一端進(jìn)行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂(top)”，不允許插入和刪除的另一端稱作“棧底(bottom)"。

10

通常稱往棧頂插入元素的操作為"入棧"，稱刪除棧頂元素的操作為"出棧"。因?yàn)楹笕霔５脑叵扔谙热霔５脑爻鰲?，故被稱為是一種"后進(jìn)先出"的結(jié)構(gòu)，因此又稱LIFO（LastInFirstOut的縮寫）表。很多書上都以如下圖所示的鐵路調(diào)度站形象地表示棧的這個(gè)特點(diǎn)。

11棧的類型定義

ADTStack{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底?；静僮鳎?/p>

}ADTStack12InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())13

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。14StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，則返回

TRUE，否則FALSE。

判定棧是否為空棧是棧在應(yīng)用程序

中經(jīng)常使用的操作，通常以它作為循環(huán)

結(jié)束的條件。15

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)，

即棧的長(zhǎng)度。16GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：用e返回S的棧頂元素,并

不將它從棧中刪除。

a1a2an……17ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。

18Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧

頂元素。

a1a2ane……19Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素，

并用e返回其值。a1a2anan-1

……20

StackTraverse(S,visit())

初始條件：棧S已存在且非空，visit()

為元素的訪問(wèn)函數(shù)。

操作結(jié)果：從棧底到棧頂依次對(duì)S的每個(gè)元素調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗。

這是對(duì)棧進(jìn)行從棧底到棧頂?shù)摹氨闅v”操作，應(yīng)用較多的場(chǎng)合是，輸出棧中所有數(shù)據(jù)元素。213.2棧的應(yīng)用舉例

由于棧的操作具有后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中的有用工具。凡應(yīng)用問(wèn)題求解的過(guò)程具有"后進(jìn)先出"的天然特性的話，則求解的算法中也必然需要利用"棧"。

22棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)例三、行編輯程序問(wèn)題例四、迷宮求解例五、表達(dá)式求值例六、實(shí)現(xiàn)遞歸23例一、數(shù)制轉(zhuǎn)換

十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是

計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方

法很多，其中一個(gè)簡(jiǎn)單算法基于下列原

理：

N=(Ndivd)×d+Nmodd

(其中：div為整除運(yùn)算，mod為求余運(yùn)算)24

NNdiv8Nmod8

210

2125

202計(jì)算順序輸出順序例如：（1348)10=(2504)8，

其運(yùn)算過(guò)程如下：25voidconversion(){InitStack(S);//構(gòu)造空棧

scanf("%d",&N);//輸入一個(gè)十進(jìn)制數(shù)

while(N){Push(S,N%8);//"余數(shù)"入棧

N=N/8;

//非零"商"繼續(xù)運(yùn)算

}while(!StackEmpty(S)){

//和"求余"所得相逆的順序輸出八進(jìn)制的各位數(shù)

Pop(S,&e);printf("%d",e);}}//conversion26例二、括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中［］（））或［（［］［］）］等為正確的格式，［（］）或（［]（）或（（）））均為不正確的格式。

則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。27

即后出現(xiàn)的"左括弧"，它等待與其匹配的"右括弧"出現(xiàn)的"急迫"心情要比先出現(xiàn)的左括弧高。換句話說(shuō)，對(duì)"左括弧"來(lái)說(shuō)，后出現(xiàn)的比先出現(xiàn)的"優(yōu)先"等待檢驗(yàn)，對(duì)"右括弧"來(lái)說(shuō)，每個(gè)出現(xiàn)的右括弧要去找在它之前"最后"出現(xiàn)的那個(gè)左括弧去匹配。顯然，必須將先后出現(xiàn)的左括弧依次保存，為了反映這個(gè)優(yōu)先程度，保存左括弧的結(jié)構(gòu)用棧最合適。這樣對(duì)出現(xiàn)的右括弧來(lái)說(shuō)，只要"棧頂元素"相匹配即可。如果在棧頂?shù)哪莻€(gè)左括弧正好和它匹配，就可將它從棧頂刪除。

28分析可能出現(xiàn)的不匹配的情況:到來(lái)的右括弧并非是所“期待”的；例如：考慮下列括號(hào)序列：

[([][])]12345678到來(lái)的是“不速之客”；直到結(jié)束，也沒(méi)有到來(lái)所“期待”的括弧。29這三種情況對(duì)應(yīng)到棧的操作即為：

1．和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?/p>

2．棧中并沒(méi)有左括弧等在哪里；

3．棧中還有左括弧沒(méi)有等到和它 相匹配的右括弧。

30算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空

若?？?，則表明該“右括弧”多余，

否則和棧頂元素比較，

若相匹配，則“左括弧出?！?/p>

，

否則表明不匹配。3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，

若?？?，則表明表達(dá)式中匹配正確，

否則表明“左括弧”有余。31Statusmatching(charexp[]){intstate=1;while(i<=Length(exp)&&state){switchexp[i]{case'('||'['

:{Push(S,exp[i]);i++;break;}case')'

:{if(！StackEmpty(S)&&GetTop(S)='('）

{Pop(S,e);i++;}else{state=0;}break;}case‘]'

:{if(！StackEmpty(S)&&GetTop(S)=‘['）

{Pop(S,e);i++;}else{state=0;}break;}}if(StackEmpty(S)&&state)returnOK;…...32boolmatching(charexp[]){//檢驗(yàn)表達(dá)式中所含括弧是否正確嵌套，

//若是，則返回TRUE，否則返回FALSE.//'#'為表達(dá)式的結(jié)束符

intstate=1;ch=*exp++;while(ch!='#'&&state){switchch{

33 case'('||'[':{Push(S,ch);break;}

//凡左括弧一律入棧

case')':{if(!StackEmpty(S)&&GetTop(S)='(')Pop(S,e);elsestate=0break;}case']':{if(!StackEmpty(S)&&GetTop(S)='[')34Pop(S,e);elsestate=0break;}}//switchch=*exp++;}//whileif(state&&StackEmpty(S))returnTRUE;elsereturnFALSE;}//matching35例三、行編輯程序問(wèn)題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?并不恰當(dāng)！36

設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū),并假設(shè)“#”為退格符，“@”為退行符。

在用戶輸入一行的過(guò)程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。合理的作法是：37假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：

while(*s)putchar(*s++);38

可設(shè)這個(gè)輸入緩沖區(qū)為一個(gè)棧結(jié)構(gòu)，每當(dāng)從終端接受了一個(gè)字符之后先作如下判斷：

1、既不是退格也不是退行符，則將該字符壓入棧頂；

2、如果是一個(gè)退格符，則從棧頂刪去一個(gè)字符；

3、如果是一個(gè)退行符，則將字符棧清為空棧。39

while(ch!=EOF&&ch!='\n'){ switch(ch){case‘#’:Pop(S,c);break;//棧非空，退棧

case'@':ClearStack(S);break;//重置S為空棧

default:Push(S,ch);break;//未考慮棧滿

}ch=getchar();//從終端接收下一個(gè)字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();}

ch=getchar();while(ch!=EOF){//EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過(guò)程的數(shù)據(jù)區(qū)；40例四、迷宮求解通常用的是“窮舉求解”的方法41

為了保證在任何位置上都能沿原路退回,需要用一個(gè)“后進(jìn)先出”的結(jié)構(gòu)即棧來(lái)保存從入口到當(dāng)前位置的路徑。并且在走出出口之后,棧中保存的正是一條從入口到出口的路徑所謂“下一位置”指的是“當(dāng)前位置”四周四個(gè)方向（東、南、西、北）上相鄰的方塊。假設(shè)以棧S記錄“當(dāng)前路徑”，則棧頂中存放的是“當(dāng)前路徑上最后一個(gè)通道塊”。

“納入路徑”的操作即為“當(dāng)前位置入棧；

“從當(dāng)前路徑上刪除前一通道塊”的操作即為"出棧"。42迷宮路徑算法的基本思想：若當(dāng)前位置“可通”,則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”,則后退,換方向繼續(xù)探索;若四周“均無(wú)通路”,則將當(dāng)前位置從路徑中刪除出去。43設(shè)定當(dāng)前位置的初值為入口位置；

do｛

若當(dāng)前位置可通，

則｛將當(dāng)前位置插入棧頂；

若該位置是出口位置，則算法結(jié)束；否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

}

否則

{

若棧不空且棧頂位置尚有其他方向未被探索，求迷宮中一條從入口到出口的路徑的算法：44

則設(shè)定新的當(dāng)前位置為:沿順時(shí)針?lè)较蜣D(zhuǎn)找到的棧頂位置的下一相鄰塊；

若棧不空但棧頂位置的四周均不可通，則{刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測(cè)試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至?？眨?/p>

}

}

}while(棧不空)；若棧空，則表明迷宮沒(méi)有通路。45例五、表達(dá)式求值

任何一個(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)算符等三類；

基本界限符有左右括弧和表達(dá)式結(jié)束符等。46

限于二元運(yùn)算符的表達(dá)式定義:

表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))

操作數(shù)::=簡(jiǎn)單變量|表達(dá)式簡(jiǎn)單變量::=標(biāo)識(shí)符|無(wú)符號(hào)整數(shù)

注：二元表達(dá)式是由（第一）操作數(shù)（S1）、運(yùn)算符（OP）和（第二）操作數(shù)（S2）三部分依次聯(lián)接而成；其中的操作數(shù)可以是簡(jiǎn)單變量，也可以是表達(dá)式；而簡(jiǎn)單變量可以是標(biāo)識(shí)符，也可以是無(wú)符號(hào)整數(shù)。47

由于算術(shù)運(yùn)算的規(guī)則是：先乘除后加減、先左后右和先括弧內(nèi)后括弧外，則對(duì)表達(dá)式進(jìn)行運(yùn)算不能按其中運(yùn)算符出現(xiàn)的先后次序進(jìn)行

那么怎么辦？

其中一個(gè)方法是先將它轉(zhuǎn)換成另一種形式。48

表達(dá)式的三種標(biāo)識(shí)方法：

設(shè)

Exp=S1+OP+S2

則稱OP+S1+S2為前綴表示法

S1+OP+S2為中綴表示法

S1+S2+OP為后綴表示法49例如:Exp=

a

b

+

(c

d/e)

f前綴式:

+

ab

c/def中綴式:

a

b

+

c

d/e

f后綴式:

ab

cde/

f

+結(jié)論:1）操作數(shù)之間的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同;3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;504)前綴式的運(yùn)算規(guī)則為:

連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;

5)后綴式的運(yùn)算規(guī)則為:

運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式。51如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)

例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f52運(yùn)算過(guò)程為：

對(duì)后綴式從左向右"掃描"，遇見(jiàn)操作數(shù)則暫時(shí)保存，遇見(jiàn)運(yùn)算符即可進(jìn)行運(yùn)算；此時(shí)參加運(yùn)算的兩個(gè)操作數(shù)應(yīng)該是在它之前剛剛碰到的兩個(gè)操作數(shù)，并且先出現(xiàn)的是第一操作數(shù)，后出現(xiàn)的是第二操作數(shù)。由此可見(jiàn)，在運(yùn)算過(guò)程中保存的操作數(shù)結(jié)構(gòu)應(yīng)該是個(gè)棧。53如何從原表達(dá)式求得后綴式？

每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來(lái)定，在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:原表達(dá)式:

a+b

c

d/e

f

后綴式:

abc

+de/f

54

先引進(jìn)一個(gè)運(yùn)算符的“優(yōu)先數(shù)”的概念。給每個(gè)運(yùn)算符賦以一個(gè)優(yōu)先數(shù)的值，如下所列：

運(yùn)算符

優(yōu)先數(shù)

其“**”為乘冪運(yùn)算，“#”為結(jié)束符。容易看出，優(yōu)先數(shù)反映了算術(shù)運(yùn)算中的優(yōu)先關(guān)系，即優(yōu)先數(shù)“高”的運(yùn)算符應(yīng)優(yōu)先于優(yōu)先數(shù)低的運(yùn)算符進(jìn)行運(yùn)算。

顯然，保存運(yùn)算符的結(jié)構(gòu)應(yīng)該是個(gè)棧，從棧底到棧頂?shù)倪\(yùn)算符的優(yōu)先數(shù)是從低到高的，因此它們運(yùn)算的先后應(yīng)是從棧頂?shù)綏５椎摹?5從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立操作數(shù)棧；2)設(shè)表達(dá)式的結(jié)束符為“#”，予設(shè)運(yùn)算符棧的棧底為“#”；3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式。564)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧；否則，退出棧頂運(yùn)算符發(fā)送給后綴式；

5)若當(dāng)前字符是結(jié)束符，則自棧頂至棧底依次將棧中所有運(yùn)算符發(fā)送給后綴式；

從原表達(dá)式求得后綴式的規(guī)律為：576)“(”對(duì)它之前后的運(yùn)算符起隔離作用，則若當(dāng)前運(yùn)算符為“(”時(shí)進(jìn)棧；

7)“)”可視為自相應(yīng)左括弧開(kāi)始的表達(dá)式的結(jié)束符，則從棧頂起，依次退出棧頂運(yùn)算符發(fā)送給后綴式直至棧頂字符為"("止。從原表達(dá)式求得后綴式的規(guī)律為：58void

transform(char

suffix[],charexp[])

{InitStack(S);Push(S,

#

);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=

#

){p++;ch=*p;}

}//while}//transform……59switch(ch){case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

(

)

{Pass(Suffix,c);Pop(S,c)}

break;

default:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#

)Push(S,ch);

}

//switch60

OP為運(yùn)算符的集合，若ch是運(yùn)算符，則函數(shù)IN(ch,OP)的值為“TRUE”。函數(shù)Pass(suffix,ch)的功能是將字符ch復(fù)制到數(shù)組suffix中。若c(棧頂運(yùn)算符)的優(yōu)先數(shù)大于或等于ch(當(dāng)前運(yùn)算符)的優(yōu)先數(shù)，則函數(shù)precede(c,ch)值為"TRUE"。算法的時(shí)間復(fù)雜度為O(n)，其中n為表達(dá)式字符串的長(zhǎng)度。61例六、實(shí)現(xiàn)遞歸

將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三項(xiàng)任務(wù)：62

保存被調(diào)函數(shù)的計(jì)算結(jié)果；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。

從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：63多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：此時(shí)的內(nèi)存管理實(shí)行“棧式管理”后調(diào)用先返回！例如：voidmain(){voida(){voidb(){………a();b();……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)64遞歸函數(shù)的實(shí)現(xiàn)

一個(gè)遞歸函數(shù)的運(yùn)行過(guò)程類似于多個(gè)函數(shù)的嵌套調(diào)用，差別僅在于“調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個(gè)函數(shù)”。為了保證“每一層的遞歸調(diào)用”都是對(duì)“本層”的數(shù)據(jù)進(jìn)行操作，在執(zhí)行遞歸函數(shù)的過(guò)程中需要一個(gè)“遞歸工作?！?。

它的作用是:

一、將遞歸調(diào)用時(shí)的實(shí)在參數(shù)和函數(shù)返回地址傳遞給下一層執(zhí)行的遞歸函數(shù)；二、保存本層的參數(shù)和局部變量，以便從下一層返回時(shí)重新使用它們。65遞歸工作棧：遞歸過(guò)程執(zhí)行過(guò)程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。66voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n//的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號(hào)為１的圓盤從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的

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

//圓盤移到z,x作輔助塔7}8}6783abc返址nxyz52acb51abc71cabvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else{4hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}

68

在此，稱調(diào)用遞歸函數(shù)的主函數(shù)為"第0層"，則從主函數(shù)調(diào)用遞歸函數(shù)被稱為進(jìn)入遞歸函數(shù)的"第1層"，從遞歸函數(shù)的"第i層"遞歸調(diào)用本函數(shù)被稱為進(jìn)入遞歸函數(shù)的"第i+1層"。顯然，當(dāng)遞歸函數(shù)執(zhí)行到第i層時(shí)，從第1層到第i-1層的數(shù)據(jù)都必須被保存下來(lái)，以便一層一層退回時(shí)繼續(xù)使用。遞歸函數(shù)執(zhí)行過(guò)程中每一層所占用的內(nèi)存數(shù)據(jù)區(qū)合起來(lái)就是一個(gè)"遞歸工作棧"。693.3棧類型的實(shí)現(xiàn)——順序棧、鏈棧70

和順序表類似，對(duì)順序棧也需要事先為它分配一個(gè)可以容納最多元素的存儲(chǔ)空間，base為這個(gè)存儲(chǔ)空間的基地址，也即一維數(shù)組的地址。

從名稱來(lái)講，“棧頂指針”意為指示棧頂元素在棧中的位置，但它的值實(shí)際是棧中元素的個(gè)數(shù)，和順序表中的length值的意義相同。

為了應(yīng)用方便，這個(gè)"最大空間的容量"應(yīng)由使用這個(gè)順序棧的程序員決定,它的默認(rèn)值和順序表的默認(rèn)值相同。

71//-----棧的順序存儲(chǔ)表示結(jié)構(gòu)定義-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;//存儲(chǔ)空間基址

SElemType

*top;//棧頂指針

intstacksize;//允許的最大存儲(chǔ)空間以元素為單位

}

SqStack;

類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。72//基本操作接口(函數(shù)聲明)：voidInitStack(Stack&S，intmaxsize);

//構(gòu)造一個(gè)最大存儲(chǔ)容量為maxsize

的空棧S。

voidDestroyStack(Stack&S);

//銷毀棧S，S不再存在。

voidClearStack(Stack&S);

//將S置為空棧。

73

boolStackEmpty(StackS);

//若棧S為空棧，則返回TRUE，否則返回FALSE。

intStackLength(StackS);

//返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。

boolGetTop(StackS,ElemType&e);

//若棧不空，則用e返回S的棧頂元素，并返回TRUE；否則返回FALSE。

74

boolPush(Stack&S,ElemTypee);

//若棧的存儲(chǔ)空間不滿,則插入元素e為新的棧頂元素,并返回TRUE;否則返回

FALSE。

boolPop(Stack&S,ElemType&e);

//若棧不空,則刪除S的棧頂元素,用e返回其值,并返回TRUE;否則返回FALSE。

voidStackTraverse(StackS,void(*visit(ElemType))

//依次對(duì)S的每個(gè)元素調(diào)用函數(shù)visit()，一旦visit()失敗，則操作失敗。75用圖表示順序棧如下：

圖中的順序棧的最大容量為7，當(dāng)前棧中元素個(gè)數(shù)為4，因此，我們也可認(rèn)為棧頂指針總是指在棧頂元素的后面一個(gè)位置上。76

StatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base;S.stacksize=STACK_INIT_SIZE;

returnOK;}77

StatusGetTop(SqStack

S,Selemtype&e){//若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORif(S.top==S.base)returnERROR;

e=*(S.top-1);

returnOK;}//GetTop78StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿，追加存儲(chǔ)空間

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

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

}

*S.top++=e;returnOK;}79StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERROR

if(S.top

==

S.base)returnERROR;e=*--S.top;

returnOK;}80棧頂指針鏈?！腶1an注意:鏈棧中指針的方向an-1好處是什么？81//鏈棧的結(jié)構(gòu)說(shuō)明TypedefstructSnode{ ElemTypedata;structSnode*next;}Snode,*Slink;Typestruct{Slinkbase; SLinktop;}*LinkStack;82//鏈棧的PUSH操作Statuspush(LinkStackL,ElemTypex){SLinkp;p=(SLink)malloc(sizeof(Snode));//建新的結(jié)點(diǎn)

if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=x;p->next=L->top;//鏈接到原來(lái)的棧頂

L->top=p;

//移動(dòng)棧頂指針

returnOK;}//PUSH83//鏈棧的pop操作

Statuspop(LinkStackL,ElemType&x){if(L->top==L->base)returnERROR;else{x=*L->top;//返回棧頂元素

p=L->top;L->top=L->top->next;//修改棧頂指針

free(p);//釋放被刪除的結(jié)點(diǎn)空間

}returnOK;}84ADTQueue{

數(shù)據(jù)對(duì)象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為隊(duì)列頭，an

端為隊(duì)列尾基本操作：3.4隊(duì)列的類型定義}

ADTQueue85隊(duì)列的基本操作：InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())86InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：隊(duì)列Q被銷毀，不再存在。

87QueueEmpty(Q)

初始條件:隊(duì)列Q已存在。

操作結(jié)果:若Q為空隊(duì)列,則返回TRUE，

否則返回FALSE。QueueLength(Q)

初始條件:隊(duì)列Q已存在。

操作結(jié)果:返回Q的元素個(gè)數(shù)，即隊(duì)列

的長(zhǎng)度。8889

GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：用e返回Q的隊(duì)頭元素。a1a2an……90ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。91EnQueue(&Q,e)

初始條件:隊(duì)列Q已存在。

操作結(jié)果:插入元素e為Q的新的隊(duì)尾元素。a1a2ane……92

DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返

回其值。a1a2an……933.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚笱h(huán)隊(duì)列——順序映象94typedefstructQNode{//結(jié)點(diǎn)類型

QElemTypedata;structQNode*next;}QNode,*QueuePtr;鏈隊(duì)列——鏈?zhǔn)接诚?5typedefstruct{//鏈隊(duì)列類型

QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;a1∧anQ.frontQ.rearQ.frontQ.rear∧空隊(duì)列96

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front->next=NULL;returnOK;}97StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}98

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//用e返回其值，并返回OK；否則返回

ERRORif(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;

free(p);returnOK;}99循環(huán)隊(duì)列——順序映象

初始化建空隊(duì)列時(shí)，令front=rear=0，每當(dāng)插入一個(gè)新的隊(duì)尾元素后，尾指針增1；每當(dāng)刪除一個(gè)隊(duì)頭元素之后，頭指針front增1。因此，在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素，而尾指針指向隊(duì)尾元素的"下一個(gè)"位置。如下圖所示。100

假設(shè)在這之后又有兩個(gè)元素f和g相繼入隊(duì)列，而隊(duì)列中的元素b和c又相繼出隊(duì)列。則隊(duì)頭指針指向元素d，隊(duì)尾指針則指到數(shù)組"之外"的位置上去了，致使下一個(gè)入隊(duì)操作無(wú)法進(jìn)行(請(qǐng)注意此時(shí)隊(duì)列空間并未滿)。為此，設(shè)想這個(gè)數(shù)組的存儲(chǔ)空間是個(gè)"環(huán)"，認(rèn)定"7"的下一個(gè)位置是"0"。如下圖所示。隊(duì)101#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

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

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

//指向隊(duì)列頭元素

intrear;//尾指針，若隊(duì)列不空，指向

//隊(duì)列尾元素的下一個(gè)位置}SqQueue;循環(huán)隊(duì)列——順序映象

intemptyflag;//隊(duì)列空的標(biāo)志，空為1102

StatusInitQueue(SqQueue&Q){//構(gòu)造一個(gè)空隊(duì)列QQ.base=(ElemType*)malloc

(MAXQSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

Q.front=Q.rear=0;Q.emptyflag=1;

returnOK;}103StatusClearQueue(SqQueue&Q)//清空隊(duì)列{Q.rear=Q.front;Q.emptyflag=1;returnOK;}StatusQueueEmpty(SqQueueQ)//判斷隊(duì)列是否為空{(diào)if(Q.emptyflag)returnTRUE;elsereturnFALSE;}104intQueueLength(SqQueueQ){if(Q.emptyflag)return0;elseif(Q.front==Q.rear)returnMAXQSIZE;elsereturn(Q.rear–Q.front +MAXQSIZE)%MAXQSIZE;}

因?yàn)樵谘h(huán)隊(duì)列中，隊(duì)尾指針的“數(shù)值”有可能比隊(duì)頭指針的數(shù)值小，因此為避免在求隊(duì)列長(zhǎng)度兩者相減時(shí)出現(xiàn)負(fù)值的情況，在作取模運(yùn)算之前先加上一個(gè)最大容量的值。