數(shù)據(jù)結(jié)構(gòu)(清華)第三章 棧和隊(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+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類型第三章棧和隊(duì)列3.1棧3.2棧的應(yīng)用舉例3.4隊(duì)列3.3棧與遞歸的實(shí)現(xiàn)學(xué)習(xí)提要：1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問(wèn)題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法，特別應(yīng)注意棧滿和?？盏臈l件以及它們的描述方法。3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法，特別注意隊(duì)滿和隊(duì)空的描述方法。4.理解遞歸算法執(zhí)行過(guò)程中棧的狀態(tài)變化過(guò)程。重難點(diǎn)內(nèi)容：順序棧的相關(guān)操作、循環(huán)隊(duì)列的判空判滿3.1棧（stack）3.1.1

棧的類型定義3.1.2

棧的表示和實(shí)現(xiàn)

棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表。不含元素的空表稱空棧。ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)特點(diǎn)：后進(jìn)先出（LIFO）3.1.1棧的類型定義表尾—棧頂

表頭—棧底

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>

}ADTStack棧的抽象數(shù)據(jù)類型定義：InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())一、順序棧3.1.2棧的表示和實(shí)現(xiàn)//-----棧的順序存儲(chǔ)表示

-----

#defineSTACK_INIT_SIZE100;

#defineSTACKINCREMENT10;

typedef

struct{

SElemType

*base;//棧底指針

SElemType

*top;//棧頂指針

int

stacksize;

}

SqStack;實(shí)現(xiàn)：一維數(shù)組s[M]top123450進(jìn)棧Push(&S,e)A棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=base,棧空，此時(shí)出棧，則下溢（underflow)top=M,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450空棧topbasebasetoptop出棧Pop(&S,&e)123450ABCDEFtoptoptoptop?？誦asetoptop棧底指針base,始終指向棧底位置；棧頂指針top,其初值指向棧底，始終在棧頂元素的下一個(gè)位置

Status

InitStack(SqStack

&S){

//構(gòu)造一個(gè)空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*

sizeof(SElemType));

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

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;}

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;}

*S.top++=e;

returnOK;

}StatusPop(SqStack

&S,SElemType

&e){//若棧不空，則刪除S的棧頂元素，

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

//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}0M-1棧1底棧1頂棧2底棧2頂在一個(gè)程序中同時(shí)使用兩個(gè)棧二、鏈棧棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

棧頂指針就是鏈表的頭指針。注意:鏈棧中指針的方向棧頂指針∧a1anan-1入棧操作push(&S,e)出棧操作pop(&S,&e)^…...棧底toptopxptop^…...棧底topqp->next=top;top=p

q=top;top=top->next

3.2棧的應(yīng)用3.2.1數(shù)制轉(zhuǎn)換3.2.2括號(hào)匹配的檢驗(yàn)3.2.3行編輯程序問(wèn)題3.2.4迷宮求解3.2.5表達(dá)式求值3.2.1數(shù)制轉(zhuǎn)換十進(jìn)制N和其他d進(jìn)制數(shù)的轉(zhuǎn)換原理:

N=(Ndivd)*d+Nmodd

其中：div為整除運(yùn)算，

mod為求余運(yùn)算toptop4top40top405

例如：

(1348)10=(2504)8，其運(yùn)算過(guò)程如下：

NNdiv8Nmod8134816841682102125202計(jì)算順序輸出順序top4052

voidconversion(){

//對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，

//打印輸出與其等值的八進(jìn)制數(shù)

initstack(S);

scanf(“%d”,N);

while(N){

push(S，N%8);N=N/8;}

while(!Stackempty(s)){

pop(S,e);

printf

(“%d”,e);}}//conversion3.3.2括號(hào)匹配的檢驗(yàn)則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來(lái)描述。假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或（（）］)均為不正確的格式。分析可能出現(xiàn)的不匹配的情況:到來(lái)的右括弧并非是所“期待”的；例如：考慮下列括號(hào)序列：

[([][])]12345678到來(lái)的是“不速之客”；直到結(jié)束，也沒有到來(lái)所“期待”的括弧。算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余，否則和棧頂元素比較，若相匹配，則“左括弧出棧”，否則表明不匹配。3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？眨瑒t表明表達(dá)式中匹配正確，否則表明“左括弧”有余。3.2.3行編輯程序問(wèn)題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?

不恰當(dāng)!合理的作法是：設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(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)用過(guò)程的數(shù)據(jù)區(qū)；3.2.4迷宮求解通常用的是“窮舉求解”的方法。求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無(wú)通路”，則將當(dāng)前位置從路徑中刪除出去。設(shè)定當(dāng)前位置的初值為入口位置；

do｛

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

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

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

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的算法：……若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為:沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則｛刪去棧頂位置；//從路徑中刪去該通道塊

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

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

typedef

struct{

int

ord;//通道塊在路徑上的“序號(hào)”

PosTypeseat;//通道塊在迷宮中的“坐標(biāo)位置”

int

di;//從此通道塊走向下一通道塊的“方向”}SElemType;//棧的元素類型

Status

MazePath(MazeTypemaze,PosTypestart,

PosTypeend){

InitStack(S);

curpos=start;

//設(shè)定“當(dāng)前位置”為“入口位置”

curstep=1;//探索第一步

do{

if(Pass(curpos)){//當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊

}

else{}}while(!StackEmpty(S));return(FALSE);}//MazePath

…………FootPrint(curpos);e=(curstep,curpos,1);Push(S,e);//加入路徑if(curpos==end)return(TRUE);

//到達(dá)終點(diǎn)curpos=NextPos(curpos,1);

//下一位置是當(dāng)前位置的東鄰curstep++;

else{//當(dāng)前位置不能通過(guò)

if(!StackEmpty(S)){Pop(S,e);

while(e.di==4&&!StackEmpty(S)){

MarkPrint(e.seat);Pop(S,e);

//留下不能通過(guò)的標(biāo)記，并退回一步

}//while

if(e.di<4){

e.di++;Push(S,e);//換下一個(gè)方向探索

curpos=NextPos(curpos,e.di);

//設(shè)定當(dāng)前位置是該新方向上的相鄰塊

}//if}//if}//else

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

Exp=S1OP

S2

操作數(shù):

變量、常量、表達(dá)式

運(yùn)算符:

算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、

邏輯運(yùn)算符

界限符：括號(hào)、結(jié)束符3.2.5表達(dá)式求值表達(dá)式求值的算法：算符優(yōu)先法根據(jù)運(yùn)算優(yōu)先關(guān)系的規(guī)定來(lái)實(shí)現(xiàn)對(duì)表達(dá)式的編譯或解釋執(zhí)行。例：3*(7–2)OPND棧OPTR棧＃＃CCC3*(C7C－C2C－275C*5315例：3*(7–2)

OPTR棧OPND棧輸入操作1# 3*(7–2)#PUSH(OPND,‘3’)2#

3*(7–2)#PUSH(OPTR,‘*’)3#*3(7–2)#PUSH(OPTR,‘(’)4#*(37–2)#PUSH(OPND,‘7’)5#*(37–2)#PUSH(OPTR,‘–’)6#*(–372)#PHSH(OPND,‘2’)7#*(–372)#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR)9#*35#operate(‘3’,‘*’,‘5’)10#15#returnGetTop(OPND)OperandType

EvaluateExpression(){

//設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。

InitStack(OPTR);Push(OPTR,'#');

initStack(OPND);c=getchar();

while(c!='#'||

GetTop(OPTR)!='#')

{

if(!In(c,OP)){Push((OPND,c);c=getchar();}

//不是運(yùn)算符則進(jìn)棧

else}//while

return

GetTop(OPND);}//EvaluateExpression……switch(precede(GetTop(OPTR),c){

case'<'://棧頂元素優(yōu)先權(quán)低

Push(OPTR,c);c=getchar();

break;

case'='://脫括號(hào)并接收下一字符

Pop(OPTR,x);c=getchar();

break;

case'>'://退棧并將運(yùn)算結(jié)果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));

break;

}//switchr主程序srrrs子過(guò)程1rst子過(guò)程2rst子過(guò)程33.3棧與遞歸的實(shí)現(xiàn)當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，需先完成三件事:(1)將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;(2)為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū);(3)將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成:(1)保存被調(diào)函數(shù)的計(jì)算結(jié)果;(2)釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);(3)依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是：后調(diào)用先返回此時(shí)的內(nèi)存管理實(shí)行“棧式管理”。遞歸過(guò)程指向過(guò)程中占用的數(shù)據(jù)區(qū)，

稱之為遞歸工作棧每一層的遞歸參數(shù)合成一個(gè)記錄，

稱之為遞歸工作記錄棧頂記錄指示當(dāng)前層的執(zhí)行情況，

稱之為當(dāng)前活動(dòng)記錄棧頂指針，

稱之為當(dāng)前環(huán)境指針例：遞歸的執(zhí)行情況分析voidprint(intw){inti;if(w!=0){print(w-1);for(i=1;i<=w;++i)

printf(“%3d,”,w);

printf(“/n”);}}運(yùn)行結(jié)果：1，2，2，3，3，3，遞歸調(diào)用執(zhí)行情況如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)輸出：2,2(2)2(1)3top(4)輸出：1(3)1(2)2(1)3top(2)輸出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0結(jié)束(1)例：n階Hanoi問(wèn)題。問(wèn)題描述：有X,Y,Z三個(gè)塔座，X上套有n個(gè)直徑不同的圓盤，按直徑從小到大疊放，形如寶塔，編號(hào)1,2,3……n。要求將n個(gè)圓盤從X移到Z，疊放順序不變，移動(dòng)過(guò)程中遵循下列原則：(1)每次只能移一個(gè)圓盤;(2)圓盤可在三個(gè)塔座上任意移動(dòng);(3)任何時(shí)刻都不能將大盤壓到小盤上;解決方法：n=1時(shí)，直接把圓盤從X移到Z；n>1時(shí)，先把上面n-1個(gè)圓盤從X移到Y(jié)，然后將n號(hào)盤從X移到Z，再將n-1個(gè)盤從Y移到Z。即把求解n個(gè)圓盤的Hanoi問(wèn)題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問(wèn)題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問(wèn)題。voidhanoi(intn,charx,chary,charz)

//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n

//的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1{2if(n==1)3move(x,1,z);//將編號(hào)為１的圓盤從x移到z4else{5hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的圓

//盤移到y(tǒng),z作輔助塔6move(x,n,z);//將編號(hào)為n的圓盤從x移到z

hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的圓

//盤移到z,x作輔助塔8}9}執(zhí)行情況：

遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址（返回地址用語(yǔ)句行號(hào)表示）。

工作記錄結(jié)構(gòu)：返回地址nxyz

voidhanoi(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}abc1230

3abc0

3abc6

2acb0

3abc6

2acb6

1abcabc0

3abc6

2acbabc0

3abc6

2acb8

1cababc0

3abc0

3abc6

2acb

voidhanoi(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}abc0

3abc6

2acbabc0

3abc8

2bac0

3abc8

2bac6

1bcaabc0

3abc

voidhanoi(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}0

3abc8

2bac

voidhanoi(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}abc0

3abc8

2bac8

1abcabc0

3abc?？?

3abc8

2bac0

3abc8

2bac3.4隊(duì)列3.4.1

隊(duì)列的類型定義3.4.2

鏈隊(duì)列3.4.3

循環(huán)隊(duì)列隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。a1a2a3…….an入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,……,an)隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)3.4.1

隊(duì)列的類型定義隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端

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ì)列尾基本操作：隊(duì)列的抽象數(shù)據(jù)類型定義：}

ADTQueue隊(duì)列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())typedef

struct

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

QElemTypedata;

struct

QNode*next;

}QNode,*QueuePtr;typedef

struct{//鏈隊(duì)列類型

QueuePtr*front;

//隊(duì)頭指針

QueuePtr*rear;//隊(duì)尾指針}LinkQueue;3.4.2鏈隊(duì)列－隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊(duì)列

Status

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

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

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

Q.front->next=NULL;

returnOK;}

Status

EnQueue(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;}

Status

DeQueue(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;}3.4.3

循環(huán)隊(duì)列－隊(duì)列的順序表示和實(shí)現(xiàn)

#defineMAXQSIZE100//最大隊(duì)列長(zhǎng)度

typedef

struct{

QElemType

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

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

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

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

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

}

SqQueue;實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)base[M]123450空隊(duì)列rear=0front=0J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6frontrearrear123450frontJ1,J2,J3入隊(duì)rear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfrontfront存在問(wèn)題：當(dāng)front=0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front≠0,rear=M時(shí)，再有元素入隊(duì)發(fā)生溢出——假溢出解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓base[0]接在base[M-1]之后，若rear+1==M,則令rear=0;實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：base[rear]=e;rear=(rear+1)%M;出隊(duì)：e