《數(shù)據(jù)結(jié)構(gòu)》課件1第3章 棧與隊(duì)列

3.1棧的類型定義3.3棧的應(yīng)用舉例3.2棧類型的實(shí)現(xiàn)3.4隊(duì)列的類型定義3.5隊(duì)列類型的實(shí)現(xiàn)總目錄知識(shí)點(diǎn)：重點(diǎn)：難點(diǎn)：2、在順序棧、循環(huán)隊(duì)列上基本操作的實(shí)現(xiàn)。1、棧與隊(duì)列的特點(diǎn)；棧的應(yīng)用順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列

通常稱，棧和隊(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+1

Delete(L,

i)Delete(S,

n)Delete(Q,

1)

1≤i≤n

棧和隊(duì)列是兩種操作受限的線性表，是兩種常用的數(shù)據(jù)類型1.棧是限制僅在表尾進(jìn)行插入和刪除操作的特

殊線性表，限制操作的表尾端稱為“棧頂”,

另一端稱為“棧底”3.1

棧的類型定義一、棧的邏輯結(jié)構(gòu)定義及特性2.棧是“后進(jìn)先出”的線性表（LIFO）或“先進(jìn)后出”的線性表（FILO）a1a2a3…an棧底棧頂進(jìn)出

如下圖所示的鐵路調(diào)度站形象地表示棧的“后進(jìn)先出”特點(diǎn)。

思考題：

設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)一個(gè)棧式結(jié)構(gòu)的站臺(tái)，具體寫出這四輛列車開出車站的所有可能的順序。解答：四輛車出站的所有可能順序?yàn)椋?）1、2、3、4；2）1、2、4、33）1、3、2、4；4）1、3、4、25）1、4、3、2；6）2、1、3、47）2、1、4、3；8）2、3、4、19）2、3、1、4；10）2、4、3、111）3、2、1、4；12）3、2、4、113）3、4、2、1；14）4、3、2、1ADTStack

{

數(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>

}ADTStack二、棧的抽象數(shù)據(jù)類型定義1、構(gòu)造空棧操作：DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())2、判?？詹僮鳎篒nitStack(&S)3、取棧頂元素操作：4、進(jìn)棧（插入）操作：5、出棧（刪除）操作：6、置棧空操作：7、求棧中元素個(gè)數(shù)操作：8、棧銷毀操作：9、棧遍歷操作：最常用的操作

GetTop(S,&e)

初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。a1a2an……Push(&S,e)

初始條件：棧S已存在。

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

a1a2ane……Pop(&S,&e)

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

操作結(jié)果：刪除S的棧頂元素，并用e返回其值。a1a2anan-1

……順序棧鏈棧3.2

棧類型的實(shí)現(xiàn)//-----棧的順序存儲(chǔ)表示

-----

#defineSTACK_INIT_SIZE100;//存儲(chǔ)空間初始分配量

#defineSTACKINCREMENT10;//存儲(chǔ)空間分配增量

typedefstruct{

SElemType

*base;//棧底指針

SElemType

*top;//棧頂指針

intstacksize;

}

SqStack;SqStacks;

類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。一.順序棧?？諚l件：棧滿條件：

s.tops.base空棧DCBAs.tops.base當(dāng)stacksize=4時(shí)是滿棧s.top=s.base

s.top-s.base=s.stacksize二.順序?；静僮鞯膶?shí)現(xiàn)1.構(gòu)造一個(gè)空棧操作：InitStack(&S)：操作思路：1）用malloc標(biāo)準(zhǔn)函數(shù)分配一個(gè)適當(dāng)大小的連續(xù)空間；2）使其滿足空棧條件。S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType))s.top=s.base3）確定其它值s.stacksize=STACK_INIT_SIZE

StatusInitStack(SqStack&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;P47statusStackempty(SqStackS)

{

}2、判?？詹僮鳎?/p>

StackEmpty(S)if(S.top==S.base)returnTRUE;

elsereturnFALSE;要求：若棧S為空，則返回TRUE值，否則返回

FALSE值。算法：（同學(xué)先自己做）3.壓（進(jìn)或入）棧操作push(&s,e)：要求：將元素e插入到棧頂，作為新的棧頂元素。操作步驟：1）若棧滿，則追加空間,若追加成功則修正有關(guān)棧的值，若追加失敗則結(jié)束操作。2）將新元素e壓棧，棧頂指針后移。S.base=(SElemtype*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType))；S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMEN;*S.top++=e*S.top=e;S.top=s.top+1;a1a2ane……

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

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;}//if*S.top++=e;returnOK;P474.退（出）棧操作pop(&S,&e)：要求：將棧頂元素刪除，并用e保留其值。操作步驟：1）若?？眨瑒t結(jié)束操作。2)若棧不空，則刪除棧頂元素，并用e返回其值If(S.top=S.base)returnERRORe=*--S.tops.top=s.top-1;e=*s.top;a1a2an……an-1es.topStatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

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

//否則返回ERROR}if

(S.top

==

S.base)

returnERROR;e=*--S.top;

returnOK;P475.取棧頂元素操作GetTop(S,&e)：要求：讀取棧頂元素并用e保留其值。操作步驟：1）若?？眨瑒t結(jié)束操作。2)否則讀取棧頂元素，并用e返回其值If(S.top==S.base)returnERRORe=*（S.top-1）a1a2an……an-1s.topeanStatusGetTop(SqStackS,SElemType&e){//若棧不空，則刪除S的棧頂元素，

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

//否則返回ERROR}if

(S.top

==

S.base)

returnERROR;

e=*(S.top-1);

returnOK;P47

棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈棧，是運(yùn)算受限的單鏈表，其插入和刪除操作僅限制在鏈表的表頭位置上進(jìn)行，故鏈棧沒有必要象單鏈表一樣附加頭結(jié)點(diǎn)，棧頂指針即為鏈表的頭指針。二.鏈棧棧頂指針∧a1an注意:鏈棧中指針的方向an-1棧底

//-----棧的鏈?zhǔn)酱鎯?chǔ)表示

-----

typedefstruckSNODE{SElemTypedata;structSNODE*next;}SNODE,*Linkstack;

Linkstacks;注意：若輸入的數(shù)據(jù)是順序輸入a1,a2,...,an，則建鏈棧時(shí)一般用頭插法,2.鏈棧的其它操作與鏈表的操作類似（因棧是線性表的特例）.作業(yè)11.分別寫出對(duì)鏈棧的入棧和出棧操作的算法。

*2.P24/3.15

鏈棧的結(jié)點(diǎn)類型定義如下：TypedefstructSNODE{SElemTypedata;structSNODE*next;}SNODE，*Linkstack;1)鏈棧的入棧push(&top,x)的函數(shù)如下：statuspush(Linkstack&top,SElemTypex)

//在棧頂指針為top的鏈棧中插入一個(gè)值為x的結(jié)點(diǎn){p=(node*)malloc(sizeof(node));if(p)//分配空間失敗returnERROR;p->data=x;//產(chǎn)生一個(gè)值為x的新結(jié)點(diǎn)

p->next=top;top=p;//將p插入到棧頂

returnOK;}解答：2）鏈棧的出棧pop(&top,&e)函數(shù)如下：statuspop(Linkstack&top,SElemType&e)//將棧頂指針為top的鏈棧的棧頂元素出棧，并通過參數(shù)e返回{if(top==NULL)//如果?？?/p>

returnERROR;e=top->data;//將棧頂元素值存入e中p=top;//p指向棧頂結(jié)點(diǎn)top=top->next;//修改指針，使棧頂結(jié)點(diǎn)從棧中脫離出來free(p);

//釋放空間returnOK；}2、設(shè)共享?xiàng)５慕Y(jié)構(gòu)圖如下：a1a2……

an…

bm……

b2b1C的元素序號(hào)12……n……….m-1m棧1底棧1頂棧2頂棧2底top1top2兩棧的最多元素個(gè)數(shù)為m，假設(shè)top1是棧1的棧頂指針，top2是棧2的棧頂指針，分別指向棧頂元素注意：當(dāng)top2=top1+1時(shí)，棧滿；當(dāng)top1=0時(shí)，棧1空；當(dāng)top2=m+1時(shí),棧2空.inttop1,top2,m,c[m+1];

//將其說明成全局變量Voidpush(x,i)Inti;elemtypex;{if(top2==top1+1)print(“overflow”);elseif(i==1)//對(duì)第一個(gè)棧進(jìn)行入棧操作

{top1++;c[top1]=x;}else//對(duì)第二個(gè)棧進(jìn)行入棧操作

{top2--;c[top2]=x;}}根據(jù)上述原理得到如下函數(shù)：函數(shù)pop如下：Voidpop(i)inti;{if(i==1)//對(duì)第一個(gè)棧進(jìn)行出棧操作

if(top1==0)print(“棧1為空\(chéng)n”）;elsetop1--;else//對(duì)第二個(gè)棧進(jìn)行出棧操作

top2++;}*補(bǔ)充實(shí)驗(yàn)1：

假設(shè)一個(gè)算術(shù)表達(dá)式中只包含圓括號(hào)，編寫一個(gè)判別表達(dá)式是否正確配對(duì)的函數(shù)correct(exp,tag);其中，exp為字符串類型的變量，表示被判別的表達(dá)式，tag為標(biāo)志變量，標(biāo)志是否正確配對(duì)。解：引進(jìn)一個(gè)順序棧S，存放未配對(duì)的括號(hào)思想：掃描到‘（‘時(shí)，則入棧;當(dāng)掃描到’）’時(shí),

檢查當(dāng)前棧頂元素是否是對(duì)應(yīng)的‘（’,

若是則退棧，否則，若棧為空及棧頂元素不是對(duì)應(yīng)的‘（’，都屬不配對(duì);當(dāng)整個(gè)算術(shù)表達(dá)式檢查完畢時(shí)棧為空，表示括號(hào)正確配對(duì)；否則也屬不配對(duì)。實(shí)現(xiàn)本題功能的函數(shù)如下：#definemaxsize100

//maxsize為算術(shù)表達(dá)式中最多字符個(gè)數(shù)

typedefstruct{charelem[maxsize];inttop;}stack;correct(charexp[maxsize],intflag){stackS//定義了一個(gè)順序棧SS.top=0,i=0;flag=1;//標(biāo)識(shí)是否配對(duì)

while(exp[i]==‘\0’&&flag){if(exp[i]==‘(‘)//遇‘（’，則入棧

S.elem[top++]=exp[i];if(exp[i]==‘)’)//遇‘）’，則判斷棧頂情況

if(S.top==0)flag=0;elseif(s[top-1]==‘(‘)S.top--;elseflag=0;i++;}if(S.top>0)flag=0;//若棧不空，則不配對(duì)}例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)例三、行編輯程序問題例四、迷宮求解例五、表達(dá)式求值例六、實(shí)現(xiàn)遞歸3.3

棧的應(yīng)用舉例

NNdiv8Nmod8

13481684

168210

2125

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

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

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

（十進(jìn)制數(shù)N到d進(jìn)制數(shù)的轉(zhuǎn)換）

動(dòng)畫播放(3-2-1)voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);//“余數(shù)”入棧

N=N/8;//“非零商”繼續(xù)運(yùn)算

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversionP48/算法3.1假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（）]或[（）］)均為不正確的格式。則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。例二、括號(hào)匹配的檢驗(yàn)

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

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

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

2．棧中并沒有左括弧等在那里

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

算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余，否則和棧頂元素比較，若相匹配，則“左括弧出棧”

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

intstate=1,i=0;

while(i<Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)==“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?

并不恰當(dāng)！例三、行編輯程序問題

設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，現(xiàn)假設(shè)“#”為退格符，“@”為退行符。合理的作法是：假設(shè)從終端接受了這樣兩行字符：

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

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

while(*s)

putchar(*s++);

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();

while(ch!=EOF){//EOF為全文結(jié)束符}將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；P50/算法3.2通常用的是“窮舉求解”的方法例四、迷宮求解動(dòng)畫3-3-1動(dòng)畫3-3-2求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，并繼續(xù)朝“下一位置”探索

若當(dāng)前位置“不可通”，則應(yīng)順著“來的方向”退回到“前一通道塊”，然后朝著除"來向"之外的其他方向繼續(xù)探索；若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置；

do｛

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

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

若該位置是出口位置，則算法結(jié)束；

否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條路徑的偽碼算法：

…

…詳見P52/算法3.2若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針方向旋轉(zhuǎn)

找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測(cè)試新的棧頂位置，

直至找到一個(gè)可通的相鄰塊或出棧至?？?；｝若?？?，則表明迷宮沒有通路。

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

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

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

在計(jì)算機(jī)中,表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

例如: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)算的次序不確定;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á)式。動(dòng)畫3-3-4如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：

ab

cde/

f

+a

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

f動(dòng)畫3-3-6如何從原表達(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

c

d/e

f

后綴式:abc

+de/f

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

運(yùn)算符#(+-X/**

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

從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立運(yùn)算符棧；2)設(shè)表達(dá)式的結(jié)束符為“#”，

予設(shè)運(yùn)算符棧的棧底為“#”；3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式。4)若當(dāng)前字符為運(yùn)算符時(shí)，當(dāng)其優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧；5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式；

6)遇到左括號(hào)“（”時(shí)，將其壓進(jìn)運(yùn)算符棧；遇到右括號(hào)“）”時(shí)，當(dāng)棧頂符號(hào)不是左括號(hào)時(shí)，反復(fù)將棧頂符號(hào)彈出送給后綴式。7)掃描到“#”時(shí)，將運(yùn)算符棧頂符號(hào)依次彈出送給后綴表達(dá)式，直到棧頂為“#”號(hào)，轉(zhuǎn)換結(jié)束。

動(dòng)畫3-3-7如：3*（7-2）#轉(zhuǎn)換成后綴表達(dá)式372-*的過程為：步驟后綴表達(dá)式運(yùn)算符棧原表達(dá)式說明

1#3*（7-2）#23*(7-2)#*>#3#*(7-2)#4#*(7-2)#537#*(-2)#->(637#*(-2)#7372#*(-)#遇）

8372-#*(#)遇(9372-#*#10372-*##結(jié)束voidtransform(charsuffix[],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;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

(

)

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

break;

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

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

if(ch!=

#

)Push(S,ch);

break;

}

//switch例六、實(shí)現(xiàn)遞歸

在程序設(shè)計(jì)中，經(jīng)常會(huì)碰到多個(gè)函數(shù)的嵌套調(diào)用。和匯編程序設(shè)計(jì)中主程序和子程序之間的鏈接和信息交換相類似，在高級(jí)語言編制的程序中，調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換也是由編譯程序通過棧來實(shí)施的。將所有的實(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ù)：保存被調(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ù)：多個(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ū)

再看P56遞歸工作棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，例如：voidhanoi(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}漢諾塔問題61bca03abc返址nxyz62acb61abcvoidhanoi(intn,charx,chary,charz)1{2if(n==1)3move(x,1,z);4else{5hanoi(n-1,x,z,y);6move(x,n,z);7hanoi(n-1,y,x,z);8}9}運(yùn)行見P57-58頁的圖3.7

81cab

漢諾塔問題動(dòng)畫播放一、隊(duì)列的邏輯結(jié)構(gòu)定義及特性1.隊(duì)列是只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除操作的一種特殊線性表。允許插入的一端稱為“隊(duì)尾”，允許刪除的一端稱為“隊(duì)頭（首）”。2.隊(duì)列是“先進(jìn)先出”（FIFO）或“后進(jìn)后出”（LILO）的線性表a1a2a3…an隊(duì)首隊(duì)尾入隊(duì)出隊(duì)3.4隊(duì)列的類型定義ADTQueue{

數(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ì)列尾基本操作：}

ADTQueue二、隊(duì)列的抽象數(shù)據(jù)類型定義1、構(gòu)造空隊(duì)列操作：DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e)QueueTraverse(Q,visit())2、判隊(duì)空操作：InitQueue(&Q)3、取隊(duì)頭元素操作：4、入隊(duì)（插入）操作：5、出隊(duì)（刪除）操作：6、置隊(duì)空操作：7、求隊(duì)列長(zhǎng)度操作：8、銷毀隊(duì)列操作：9、隊(duì)列遍歷操作：最常用的操作GetHead(Q,&e)

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

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

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

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

DeQueue(&Q,&e)

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

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

鏈隊(duì)列——鏈?zhǔn)接诚箜樞蚺c循環(huán)隊(duì)列

——順序映象3.5

隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列一.鏈隊(duì)列(鏈?zhǔn)接诚?的結(jié)構(gòu)描述二.鏈隊(duì)列基本操作的實(shí)現(xiàn)

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

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;typedefstruct{//鏈隊(duì)列類型

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

QueuePtrrear;//隊(duì)尾指針}LinkQueue;LinkQueueQ;一.鏈隊(duì)列(鏈?zhǔn)接诚?的結(jié)構(gòu)描述a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊(duì)列鏈隊(duì)的隊(duì)空條件：Q.front=Q.rear1.構(gòu)造一個(gè)空隊(duì)列InitQueue(&Q)：操作思路：1）用malloc標(biāo)準(zhǔn)函數(shù)分配一個(gè)適當(dāng)大小的空間作為隊(duì)列的頭結(jié)點(diǎn)，并使隊(duì)頭、隊(duì)尾指針指向它；2）若分配空間成功則置頭結(jié)點(diǎn)的指針域?yàn)榭?，否則結(jié)束算法。Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));Q.front->next=NULL;二.鏈隊(duì)列基本操作的實(shí)現(xiàn)P62

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

returnOK;}Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));

//分配隊(duì)的表頭結(jié)點(diǎn)空間，并使隊(duì)頭、隊(duì)尾指針指向它。if(!Q.front)exit(OVERFLOW);//存儲(chǔ)分配失敗Q.front->next=NULL;P622、鏈隊(duì)列的插入操作：EnQueue(Q,e)：1）產(chǎn)生新的結(jié)點(diǎn)e，并使p指針指向它；2）將新結(jié)點(diǎn)插入鏈隊(duì)的尾部（修改鏈）。p=(QueuePtr)malloc(sizeof(QNode));P->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;操作思路：要求：∧an…Q.frontQ.rear插入元素e為Q的新的隊(duì)尾元素e∧pP62

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊(duì)尾元素returnOK;}p=(QueuePtr)malloc(sizeof(QNode));

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

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;P623、鏈隊(duì)列的刪除操作：DeQueue(&Q，&e)：1）若隊(duì)列空，則結(jié)束算法；2）若隊(duì)列非空，則將隊(duì)頭元素刪除，并用e保留其值。if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;操作思路：要求：刪除隊(duì)首元素，并用e保留其值；∧an…Q.frontQ.reara1a2P4)釋放空間：free(p);算法如下：3)若刪除的是隊(duì)尾元素，則修改隊(duì)尾指針I(yè)f(Q.rear==p)Q.rear=Q.front;

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

//用e返回其值，并返回OK；否則返回ERROR

}if(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;P62一、順序與循環(huán)隊(duì)列的結(jié)構(gòu)描述順序與循環(huán)隊(duì)列二、循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

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

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

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

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

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

}SqQueue;QElemTypedata[MAXQSIZE];靜態(tài)存儲(chǔ)空間一、順序與循環(huán)隊(duì)列的結(jié)構(gòu)描述SqQueueQ;Q.baseQ.frontQ.rear

空隊(duì)列Q.baseQ.frontQ.rear序號(hào)值：012345Q.front=Q.rearQ.rear=MAXQSIZE假溢出現(xiàn)象入隊(duì)EnQueue(&Q,e):

Q.base[Q.rear++]=e;出隊(duì)DeQueue(&Q,e):e=Q.base[Q.front++];順序隊(duì)空條件：順序隊(duì)滿條件：ea1a2a3a4a5循環(huán)隊(duì)列：

將順序隊(duì)列看成是首尾相聯(lián)的隊(duì)列。3-3-13假設(shè)：MAXQSIZE=6054321Q.frontQ.reara1a2a3a4a5循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：Q.front=Q.rearQ.front=Q.rear隊(duì)空與隊(duì)滿的條件相同，無法判斷，怎么辦？a62、少用一個(gè)元素空間：如下圖循環(huán)隊(duì)空條件：循環(huán)隊(duì)滿條件：Q.front=Q.rear（Q.rear+1）%MAXQSIZE=Q.front1、設(shè)一個(gè)標(biāo)志位以區(qū)分隊(duì)列是“空”，還是“滿”；處理方法有兩種：054321Q.frontQ.reara1a2a3a4a5空1.構(gòu)造一個(gè)空循環(huán)隊(duì)列InitQ