第4章 棧和隊(duì)列

1數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程(修訂版)配套課件2第4章棧和隊(duì)列

棧和隊(duì)列是對(duì)線性表的某些操作加以限定而派生出的結(jié)構(gòu)。它們的操作本身并不難掌握，難點(diǎn)是理解棧和隊(duì)列的應(yīng)用思想、掌握其算法的設(shè)計(jì)技巧。講授本章課程大約需6課時(shí)。

3

通常稱，棧和隊(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ù)類型43.1棧3.2棧的應(yīng)用舉例3.3隊(duì)列3.4隊(duì)列應(yīng)用舉例53.1棧一、棧的結(jié)構(gòu)特點(diǎn)和操作二、棧的表示和操作的實(shí)現(xiàn)6一、棧的結(jié)構(gòu)特點(diǎn)和操作7棧(Stack)的定義a2a1a4a3棧底棧頂

棧(stack)是限定只能在表的一端進(jìn)行插入和刪除的線性表。在棧中,

允許插入和刪除的一端稱為“棧頂”(top),不允許插入和刪除的一端稱為“棧底”(bottom)。8InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S)棧的基本操作:(9個(gè)基本操作）

比一般線性表少了三種操作求前驅(qū)，求后繼，定位(LocateElem)9

InitStack(&S)(初始化)

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

DestroyStack(&S)

初始條件：棧S已存在。

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

StackEmpty(S)（判空）

初始條件：棧S已存在

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

則返回TRUE，

否則FALSE。11

StackLength(S)（棧長(zhǎng)）

初始條件：棧S已存在。

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

即棧的長(zhǎng)度。12

GetTop(S,&e)（取棧頂元素）

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

操作結(jié)果：用e返回S的棧頂元素。a1a2an……13

ClearStack(&S)（清空）

初始條件：棧S已存在。

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

14

Push(&S,e)（入棧-插入）

初始條件：棧S已存在。

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

新的棧頂元素。

a1a2ane……15

Pop(&S,&e)（出棧-刪除）

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

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

并用e返回其值。a1a2anan-1

……16

順序棧

鏈棧二、棧的表示和操作的實(shí)現(xiàn)17

順序棧

類似于線性表的順序表示法，指向表尾的指針可以作為棧頂指針。棧頂指針top---不是地址，而是數(shù)組的下標(biāo)，其值是棧頂元素的下標(biāo)。18//-----棧的順序存儲(chǔ)表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*elem;

inttop;----棧頂下標(biāo),順序表是length

intstacksize;

intincrement;

}

SqStack;補(bǔ)充：length=top+1；19

void

InitStack_Sq(SqStack&S){

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

S.elem=newSElemType[maxsize];//表示棧已經(jīng)存在

S.top=-1;//棧為空

S.stacksize=maxsize;S.incrementsize=incresize;

//對(duì)棧的其他成員附初值}20void

Push_Sq(SqStack&S,SElemTypee){

if

(S.top==S.stacksize-1)

incrementStacksize(S);//如果順序棧的空間已滿，應(yīng)為棧擴(kuò)容

S.elem[++S.top]=e;//在棧頂插入數(shù)據(jù)元素}S.elem[++S.top]=e;可以改為如下兩句：S.top++;S.elem[S.top]=e;總結(jié)：先改變top（top+1），再賦值。21bool

Pop_Sq(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

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

//否則返回FALSE。

if

(S.top

==

-1)return

FALSE;e=S.elem[S.top-

-];

return

TRUE;}e=S.elem[S.top-

-];此語(yǔ)句可以改為：e=S.elem[S.top];S.top-

-；總結(jié)：先賦值再改變top（top-1）22棧頂指針∧a1an注意:鏈棧中指針的方向an-1

鏈棧top233.2棧的應(yīng)用舉例

棧在算法設(shè)計(jì)中占有重要的地位，運(yùn)用的技巧也性也較高，本節(jié)安排五個(gè)例子來討論棧的使用。24例一數(shù)制轉(zhuǎn)換例二括號(hào)匹配的檢驗(yàn)例三背包求解例四表達(dá)式求值例五遞歸函數(shù)的實(shí)現(xiàn)25

例一、數(shù)制轉(zhuǎn)換

算法基于數(shù)制轉(zhuǎn)換公式：

N=(Ndivd)×d+Nmodd

26

例如：（1348)10=(2504)8

其運(yùn)算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序27void

conversion()

{InitStack(S);

cin>>N;

while

(N)

{

Push(S,N%8);N=N/8;

}

while

(!StackEmpty(S)){

Pop(S,e);

cout<<e;

}}

//conversion28例二、括號(hào)匹配的檢驗(yàn)假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或（（）］)均為不正確的格式。

則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。29分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號(hào)序列：

[([][])]12345678到來的是“不速之客”；直到結(jié)束，也沒有到來所“期待”的括弧。30算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若棧空，則表明該“右括弧”多余，否則和棧頂元素比較，若相匹配，則“左括弧出?！?/p>

，否則表明不匹配。3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？眨瑒t表明表達(dá)式中匹配正確，否則表明“左括弧”有余。31boolmatching(charexp[]){

intstate=1;ch=*exp++;

while(ch!=‘#’&&state){

switchofch{

case

左括弧:{Push(S,ch);i++;break;}//左括弧進(jìn)棧

case”)”:{//

匹配‘）’

if(!StackEmpty(S)&&GetTop(S)=‘(‘)Pop(S,e);

else

state=0;

break;}

case”]”:{……}//

匹配‘]’

}

ch=*exp++;

}

if(StackEmpty(S)&&state)

return

TRUE;

elsereturn

FALSE;

}32例三.背包問題:

假設(shè)有n件體積分別為w1,w2,…wn的物品和一個(gè)能裝載體積為T的背包.能否從n件物品中選擇若干件恰好裝滿背包,

即

wi1+wi2+…+wik=

T,則背包問題有解；否則無(wú)解.

以W(1,8,4,3,5,2),

T=10為例

(1,4,3,2

),

(1,4,5

),(8,2)和(3,5,2)是其解。3354381435822WT=101+4+3+2=10

利用回溯的算法思想求解背包問題

從背包中取出物品再繼續(xù)搜索的策略稱之為回溯，其規(guī)則是“后進(jìn)先出”，即背包以棧的操作完成求解。34voidknapsack(intw[],intT,int

n){//T在算法中是剩余的容積，初值為背包的體積

InitStack(S);k=0;

do{

while(T>0&&k<n){

if

(T-w[k]>=0){

//第k件物品可以進(jìn)棧

Push(S,k);T─

=w[k];

}k++;

}

if(T==0)StackTraverse(S);//輸出一個(gè)解

Pop(S,k);

T+=w[k];//退出棧頂物品

k++;

}while

(!StackEmpty(S)||k<n);}35

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

表達(dá)式::=

操作數(shù)運(yùn)算符操作數(shù)操作數(shù)::=

簡(jiǎn)單變量|

表達(dá)式簡(jiǎn)單變量::=

標(biāo)識(shí)符|

無(wú)符號(hào)整數(shù)例四、表達(dá)式求值例如:exp=ab

+

(7d/e)f36

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

Exp=S1OP

S2則稱OP

S1S2

為前綴表示法

S1

OP

S2

為中綴表示法

S1

S2

OP

為后綴表示法

37例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+結(jié)論:1）操作數(shù)之間的相對(duì)次序不變;2）運(yùn)算符的相對(duì)次序不同;3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;4)前綴式的運(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á)式。38如何從后綴式求值？例如：

abcde/f+abd/ec-d/e(c-d/e)f先找運(yùn)算符，再找操作數(shù):Exp=ab

+

(cd/e)f39后綴表達(dá)式：算法思想abcde/f+#1、遇到操作數(shù)入棧，2、遇到操作符就出棧（連續(xù)出兩個(gè)棧頂元素），進(jìn)行計(jì)算，將結(jié)果壓棧3、直到表達(dá)式掃描完畢。難點(diǎn)：如何將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式（樹的知識(shí)。）40Computy(suffix[]){Stacks;i=0;InitStack(&x);while(suffix[i++]!=‘#’){ifsuffix

[i]是操作數(shù)嗎？

push(&s,suffix[i]);else{x=pop(&s,&e);y=pop(&s,&e);N=operate(x,y,suffix[i]);push(&s,N);}//else//i++;}//whileret=pop(&s,&e);return(ret);}suffix[]=abcde/f+#41ifsuffix

[i]是操作數(shù)嗎?if（‘0’<=suffix

[i]

<=‘9”）;擴(kuò)展思考：如果是多位數(shù)的數(shù)字如何判斷？42N=operate(x,y,suffix[i]);//是操作符進(jìn)行運(yùn)算=========================operate(x,y,suffix[i]){switch(suffix[i]){case’+’:N=y+x;returnN;break;case’-’:N=y-x;returnN;break;case’*’:N=y*x;returnN;break;case’\’:N=y\x;returnN;break;default:returnERROR;}//switch}43

如何從原表達(dá)式求得后綴式？

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

cd/e

f

后綴式:abc+de/f

44運(yùn)算符優(yōu)先數(shù)表

運(yùn)算符#（+–）/^優(yōu)先數(shù)-1011222345從原表達(dá)式求得后綴式的規(guī)律為：1)

設(shè)立操作符棧；2)設(shè)表達(dá)式的結(jié)束符為“#”，

予設(shè)運(yùn)算符棧的棧底為“#”；3)

若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴。4)

若當(dāng)前運(yùn)算符的優(yōu)先數(shù)大于棧頂運(yùn)算符,則進(jìn)棧；5)

否則（小于等于），退出棧頂運(yùn)算符發(fā)送給后綴式；6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，

“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。46從原表達(dá)式求得后綴式的規(guī)律為：設(shè)立一數(shù)組放原表達(dá)式：exp[]=原表達(dá)式設(shè)立操作符棧；S

設(shè)立一個(gè)數(shù)組放后綴表達(dá)式suffix[]

2)設(shè)表達(dá)式的結(jié)束符為“#”，

予設(shè)運(yùn)算符棧的棧底為“#”；//push（&s,“#”)準(zhǔn)備工作：47從原表達(dá)式求得后綴式的規(guī)律為：3)

若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式。if(ch)為操作數(shù)，suffix[k++]=ch;逐個(gè)讀取原表達(dá)式的字符，進(jìn)行對(duì)應(yīng)處理：分別考慮操作數(shù)，操作符（考慮優(yōu)先級(jí)），左括號(hào)（，右括號(hào)）的處理方法。若為操作符：48從原表達(dá)式求得后綴式的規(guī)律為：若為操作符：4)

若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符,則進(jìn)棧；5)

否則，退出棧頂運(yùn)算符發(fā)送給后綴式；幾種情況：情況1：符號(hào)為+-*/:比較優(yōu)先級(jí)，確定是進(jìn)棧還是給后

綴表達(dá)式情況2：(-----進(jìn)棧情況3：）---）不進(jìn)棧，

自棧頂至（之前的運(yùn)算符出棧并發(fā)給后綴式，

）出棧6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，

“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。49從原表達(dá)式求得后綴式的規(guī)律為：1)

設(shè)立操作符棧；2)設(shè)表達(dá)式的結(jié)束符為“#”，

予設(shè)運(yùn)算符棧的棧底為“#”；3)

若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式。4)

若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符,則進(jìn)棧；5)

否則，退出棧頂運(yùn)算符發(fā)送給后綴式；6)“(”對(duì)它之前后的運(yùn)算符起隔離作用，

“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。50voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;k=0；

while(!StackEmpty(S)){

if(!opmenber(ch))suffix[k++]=ch;

else

{

}

if(ch!=#){p++;ch=*p;}}//whilesuffix[k]=\0;}//transform……//如果為操作符看后面swich部分}51switch(ch)

{

case

(

:Push(S,ch);break;//左括號(hào)入棧

case

)

:

Pop(S,c);自頂?shù)剑ㄈ砍鰲＝o后綴數(shù)組

while(c!=

()

{suffix[k++]=c;Pop(S,c)}

break;

defult:{//其他情況比較優(yōu)先級(jí)

while(Gettop(S,c)&&

(precede(c,ch)))

{suffix[k++]=c;Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

}//switchC為棧頂操作符，ch為當(dāng)前操作符precede（c,ch）return1為ch<=cintopermanber(ch){if(‘0’<=ch<=‘9’;}return0;elsereturn1;說明：為操作數(shù)，則返回0intprecede(c,ch)c為棧頂?shù)倪\(yùn)算符；ch為當(dāng)前的運(yùn)算符當(dāng)ch<=c,則返回1，反之(ch>c)返回0{Switch(ch)case+:case–:{if（

棧頂c是#或者（），return0;//ch>celse返回1;//其他情況ch<=c;}case*:case/:{if（

棧頂c是*或者/）retrun1;//ch<=celseretrun0;//ch>c}}//switch如果表達(dá)式是：234+56/2*11-8怎么處理多位數(shù)？55例五、實(shí)現(xiàn)遞歸

將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；--保護(hù)現(xiàn)場(chǎng)為被調(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ù)：56保存被調(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ù)：57多個(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ū)遞歸的定義：一個(gè)函數(shù)自己直接或間接調(diào)用自己。對(duì)計(jì)算機(jī)而言，某函數(shù)調(diào)用別的函數(shù)與調(diào)用自己本身，沒有不同，至于難以理解，那是人的思維而已。59

遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，在執(zhí)行遞歸函數(shù)的過程中也需要一個(gè)“遞歸工作?！?。作用：（1）將遞歸調(diào)用的實(shí)際參數(shù)、返回地址傳遞給下一層執(zhí)行的遞歸函數(shù)；（2）保存本層的參數(shù)和局部變量，以便從下一層返回時(shí)重新使用它們。60A(n,x,y)=x+1,n=0x,n=1,y=00,n=2,y=01,n=3,y=02,n≥4,y=0A(n-1,A(n,x,y-1),x)，n≠0,y≠0Ackerman函數(shù)定義：用實(shí)例模仿編譯程序解決遞歸問題的過程（無(wú)需掌握）61A(3,2,1)=A(2,A(3,2,0),2)=A(2,1,2)A(3,2,0)=1=A(1,A(2,1,1),1)=A(1,A(1,A(2,1,0),1),1)=A(1,A(1,0,1),1)A(2,1,0)=0=A(1,A(0,A(1,0,0),0),1)=A(1,A(0,0,0),1)A(1,0,0)=x=0=A(1,1,1)A(0,0,0)=x+1=1=A(0,A(1,1,0),1)=A(0,1,1)A(1,1,0)=x=1=2A(0,1,1)=x+1=2

Ackerman函數(shù)A(3,2,1)的遞歸運(yùn)行模擬321320212211210101100000111110011

遞歸過程的實(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ù)。設(shè)計(jì)遞歸的條件及方法：一、將問題化為原問題的子問題的求解（砍頭去尾，中間切）假設(shè)n個(gè)規(guī)模問題，判斷：1、砍頭：取第一個(gè)元素，n-1個(gè)元素與原問題是否相似2、去尾：剩n-1個(gè)問題與原問題是否相似3、中間切：將原問題一分為2，Q1，Q2與原問題是否相似（排序大多用此）二、終止條件：設(shè)計(jì)遞歸出口，確定終止條件(能在最小值上有直接解，并作為終止條件條件，告知何時(shí)停止遞歸)例：1+2+3+…..+n條件滿足否？(1)去尾1+2+…+(n-1)(2)終止條件：n==0，return0;

或n==1，retrun1;

或n==2，retrun3;intSum（n）{if(n==1)，total=1；

elsetotal=sum（n-1）+n

returntotal；}求階乘：

n！=1*2*3*……*(n-1)*n去尾，與原問題相似終止條件：n=1時(shí)，result=1

intfunction（intn）{if（n==1）result=1；

elseresult=function（n-1）*n}Hanoi塔問題Hannoi的傳說

相傳在印度的貝納雷斯有座大寺廟，寺廟內(nèi)有一塊紅木板，上面插著三根鉆石棒，在盤古開天地，世界剛創(chuàng)造不久之時(shí)，神便在其中的一根鉆石棒上放了６４枚純金的圓盤。

有一個(gè)叫婆羅門的門徒，不分日夜地向這座寺廟趕路，抵達(dá)后，就盡力將６４枚純金的圓盤移到另一根鉆石棒上。等到婆羅門完成這項(xiàng)工作，寺廟和婆羅門本身都崩潰了，世界在一聲霹靂中也毀滅了。不管這個(gè)傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。這需要多少次移動(dòng)呢?這里需要遞歸的方法。假設(shè)有n片，移動(dòng)次數(shù)是f(n).顯然f⑴=1,f⑵=3,f⑶=7，且f(k+1）=2*f(k)+1。此后不難證明f(n)=2^n-1。n=64時(shí)，

f（64）=2^64-1=18446744073709551615

假如每秒鐘一次，共需多長(zhǎng)時(shí)間呢？一個(gè)平年365天有31536000秒，閏年366天有31622400秒，平均每年31556952秒，計(jì)算一下，18446744073709551615/31556952=584554049253.855年

這表明移完這些金片需要5845億年以上，而地球存在至今不過45億年，太陽(yáng)系的預(yù)期壽命據(jù)說也就是數(shù)百億年。真的過了5845億年，不說太陽(yáng)系和銀河系，至少地球上的一切生命，連同梵塔、廟宇等，都早已經(jīng)灰飛煙滅。漢諾塔問題：有三根桿子A，B，C。A桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿：每次只能移動(dòng)一個(gè)圓盤；大盤不能疊在小盤上面。

提示：可將圓盤臨時(shí)置于B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須遵循上述兩條規(guī)則。

問：如何移？最少要移動(dòng)多少次？n個(gè)盤子,A->C去尾，前面n-1個(gè)盤子作為小問題，將n-1個(gè)盤子黏起來，就成了兩個(gè)盤子，如何移呢？(D1是上面的小盤（假想成n-1個(gè)黏起來的盤），D2是下面的大盤)1、D1AB2.D2A->C3D1B->Chanoi(n,A,B,C)//A-C借助B{If（n=1）{

printf（“n從A移動(dòng)C”）；return1；}else{hanoi（n-1，A,C,B）

printf（n,A-C）hanoi(n-1，B,A,C)}}723.3隊(duì)列一、隊(duì)列的結(jié)構(gòu)特點(diǎn)和操作二、隊(duì)列的表示和操作的實(shí)現(xiàn)73一、隊(duì)列的結(jié)構(gòu)特點(diǎn)和操作使用場(chǎng)合：用于仿真，服務(wù)窗口的設(shè)置是否合理74隊(duì)列(Queue)的定義

隊(duì)列(queue)是限定只能在表的一端進(jìn)行刪除，而在另一端插入的線性表。在隊(duì)列中，允許刪除的一端稱為“隊(duì)頭”(front)，允許插入的一端稱為“隊(duì)尾”(rear)。

a1a2a3a4a5隊(duì)頭隊(duì)尾75

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

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

DestroyQueue(&Q)

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

操作結(jié)果：隊(duì)列Q被銷毀，

不再存在。

77QueueEmpty(Q)

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

操作結(jié)果：若Q為空隊(duì)列，

則返回TRUE，

否則返回FALSE。78

QueueLength(Q)

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

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

即隊(duì)列的長(zhǎng)度。79

GetHead(Q,&e)

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

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

ClearQueue(&Q)

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

操作結(jié)果：將Q清為空隊(duì)列。81

EnQueue(&Q,e)

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

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

新的隊(duì)尾元素。a1a2ane……82

DeQueue(&Q,&e)

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

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

并用e返回其值。a1a2an……83

鏈隊(duì)列

循環(huán)隊(duì)列二、隊(duì)列的表示和操作的實(shí)現(xiàn)84

typedefstruct

QNode{//結(jié)點(diǎn)類型

QElemTypedata;

struct

QNode*next;

}QNode,*QueuePtr;

鏈隊(duì)列85Q.frontQ.reartypedefstruct{//鏈隊(duì)列類型

QueuePtrfront;//隊(duì)頭指針（指向頭結(jié)點(diǎn)）

QueuePtrrear;//隊(duì)尾指針（指向尾元素）}

LinkQueue;a1∧an…Q.frontQ.rear∧空隊(duì)列86

void

InitQueue_L(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列Q

Q.front=Q.rear=newQNode;

Q.front->next=

NULL;}產(chǎn)生一個(gè)空結(jié)點(diǎn)，并讓front與rear都指向它。87

void

EnQueue_L(LinkQueue&Q,QElemTypee)

{//插入元素e為Q的新的隊(duì)尾元素

p=

new

QNode;p->data=e;p->next=NULL;Q.rear->next=p;

Q.rear=p;}注意：鏈的變化；rear指向尾函數(shù)。88

bool

DeQueue_L(LinkQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值,并返回TRUE；否則返回FALSE

if(Q.front==Q.rear)returnFALSE;p=Q.front->next;e=p->data;

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

if(Q.rear==p)Q.rear=Q.front;//當(dāng)原隊(duì)列只有一個(gè)元素時(shí)，

要特殊處理

。

delete

p;

returnTRUE;}注意：釋放刪除的結(jié)點(diǎn)；只有一元素時(shí)的特殊處理；fornt始終指向頭結(jié)點(diǎn)（不變）89#define

MAXQSIZE100//最大隊(duì)列長(zhǎng)度typedefstruct{

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

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

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

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

//隊(duì)列尾元素的下一個(gè)位置

int

queuesize;

int

incrementsize;}

SqQueue;

循環(huán)隊(duì)列（順序隊(duì)列）少了隊(duì)列長(zhǎng)度queuelength，因?yàn)橥ㄟ^front與rear運(yùn)算可得90由于插入刪除分別在隊(duì)尾和隊(duì)頭進(jìn)行。思考：能否做到，用數(shù)組表示隊(duì)列時(shí)，做到不頻繁移動(dòng)元素，并保持線性的特點(diǎn)？解決方法：移動(dòng)front或者rear就可。問題：產(chǎn)生假溢（假滿）解決方法：頭尾相連，讓數(shù)組形成一個(gè)環(huán)—循環(huán)數(shù)組（循環(huán)隊(duì)列）。如何實(shí)現(xiàn)(取模實(shí)現(xiàn))：rear=(rear+1)%queuesize(queuesize是隊(duì)列/數(shù)組的最大容量)91循環(huán)隊(duì)列：保留了數(shù)組存儲(chǔ)的簡(jiǎn)單，且插入刪除無(wú)須元素的移動(dòng)。還有一個(gè)問題有待解決：隊(duì)列滿：front==rear;隊(duì)列空：front==rear;按照算法的特性：算法要有確定性，不能出現(xiàn)歧義。92如何解決：1、設(shè)置標(biāo)志當(dāng)入隊(duì)，使front==rear，則為滿，當(dāng)出隊(duì)，使front==rear，則為空。2、犧牲一個(gè)內(nèi)存單元，讓空和滿的判斷條件都唯一。空：

front==rear滿：（rear+1）%queuesize==front;93循環(huán)隊(duì)列非循環(huán)隊(duì)列入隊(duì)rear=(rear+1)%queuesize;Rear=rear+1出隊(duì)front==(front+1)%queuesize;Front=front+1隊(duì)空rear==front；rear==front；隊(duì)滿(rear+1)%queuesize==front；rear==front；Rear+1=queuesize(rear-front+queuesize)%queuesize94abcdQ.elemQ.fronteQ.rearQ.front:

指向隊(duì)頭元素Q.rear:

指向隊(duì)尾下一元素隊(duì)列的入隊(duì)和出隊(duì)操作：95e01234567Q.frontQ.rear初態(tài)（空隊(duì)）:Q.frontQ.rear隊(duì)空:當(dāng)頭尾指針重合時(shí):隊(duì)為空9601234567acbQ.frontQ.rear隊(duì)滿狀態(tài)的約定:acbQ.rear01234567Q.rearQ.frontabcdefg假滿真滿Q.rearQ.rear隊(duì)滿時(shí)還富裕一個(gè)單元的空間以區(qū)別“隊(duì)空”和“隊(duì)滿”的條件9701234567abcQ.rearQ.frontQ.reard循環(huán)隊(duì)列（按循環(huán)機(jī)制使用順序空間）

front和rear都按逆時(shí)針操作98Q.rear=(Q.rear+1)Q.front=(Q.front+1)

通過頭尾指針的循環(huán)使用,順序空間即可當(dāng)循環(huán)空間來使用，稱循環(huán)隊(duì)。循環(huán)使用指針在技術(shù)上是由取模實(shí)現(xiàn)的：%

MAXQSIZE;%

MAXQSIZE;99

void

InitQueue_Sq(SqQueue&Q){//構(gòu)造一個(gè)空隊(duì)列Q

Q.elem=

new

QElemType

[MAXQSIZE+1];

Q.queuesize=MAXQSIZE；

Q.front=Q.rear=0;

}100void

EnQueue_Sq(SqQueue&Q,ElemTypee){

//插入元素e為Q的新的隊(duì)尾元素

if

((Q.rear+1)%MAXQSIZE==Q.front)

incrementQueuesize(Q);

//隊(duì)列已滿需擴(kuò)容

Q.elem[Q.rear]=e;

Q.rear=(Q.rear+1)%

MAXQSIZE;}101void

DeQueue_Sq(SqQueue&Q,ElemType&e)

{

//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用e返回其值，并返回TRUE;否則返回FALSE

if(Q.front==Q.rear)

returnFALSE;e=Q.elem[Q.front];Q.front=(Q.front+1)%MAXQSIZE;

return

TRUE;}1023.4隊(duì)列的應(yīng)用舉例利用循環(huán)隊(duì)列求二項(xiàng)式系數(shù)（楊輝三角）楊輝三角形特點(diǎn)：1、頭尾均為12、其他元素是上層相鄰元素之和。問題描述：n為第n層，輸出具有n層楊輝三角形。給第n-1層，如何產(chǎn)生第n層。假如知道第三層，1,3,3,1（已全部入隊(duì)），如何產(chǎn)生第四層的數(shù)？1、每次出隊(duì)一個(gè)元素x（三層的）2、讀取一元素y=Gethead()3、x+y入隊(duì)（第四層的元素），3、循環(huán)1-3。出隊(duì)1；Gethead（）3；1+3=4，入隊(duì)；出隊(duì)3；Gethead（）3；1+3=6，入隊(duì)；出隊(duì)3；Gethead（）1；3+1=4，入隊(duì)；在兩行之間加上輔助變量0，作為行界值（為了便于編程）013310|0146410楊三角算法：1、根據(jù)楊三角第n-1層數(shù)產(chǎn)生編程，m=1（當(dāng)前層數(shù)）2、每次從隊(duì)列里面出隊(duì)一個(gè)元素x，讀取頭元素y3、將x+y入隊(duì)4、不斷重復(fù)2,3，直到y(tǒng)=0；（小循環(huán)）5、不斷重復(fù)1,2,3,直到m=n；（大循環(huán)）存在小問題：1、頭尾問題；2、何時(shí)小循環(huán)結(jié)束106第1行11