數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第3章 操作受限的線性表：棧和隊(duì)列

第3章操作受限的線性表：棧和隊(duì)列導(dǎo)學(xué)問題1：數(shù)制轉(zhuǎn)換問題【問題描述】

已知十進(jìn)制數(shù)n，試將其轉(zhuǎn)換成對(duì)應(yīng)的八進(jìn)制數(shù)。【分析】以n=1269為例

計(jì)算過程中，取余數(shù)的順序正好與計(jì)算產(chǎn)生余數(shù)的順序相反的，因此可將每次產(chǎn)生的余數(shù)依次保存起來，轉(zhuǎn)換結(jié)束后，再按保存的逆序取出余數(shù)打印即可。

顯然，保存的余數(shù)應(yīng)該具備“后進(jìn)先出”的特點(diǎn)，可用棧作為數(shù)據(jù)結(jié)構(gòu)。導(dǎo)學(xué)問題2：銀行排隊(duì)問題【問題描述】

請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡單的模擬銀行排隊(duì)系統(tǒng)，要求程序具有三項(xiàng)菜單：1）取號(hào)。選擇該菜單后，為客戶產(chǎn)生一個(gè)排隊(duì)號(hào)。2）叫號(hào)。選擇該菜單后，顯示可服務(wù)的客戶排隊(duì)號(hào)。3）退出系統(tǒng)?！痉治觥?/p>

銀行排隊(duì)問題屬于典型的先來先服務(wù)，因此需要將產(chǎn)生的排隊(duì)號(hào)存放在具有“先進(jìn)先出”特性的數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列結(jié)構(gòu)可以滿足要求。

3.1棧3.1.1知識(shí)學(xué)習(xí)棧：限定僅在表尾進(jìn)行插入和刪除操作的線性表。空棧：不含任何數(shù)據(jù)元素的棧。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。（a1,a2,……,an）棧頂棧底abc入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖3.1棧棧的操作特性：后進(jìn)先出abc入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂3.1棧棧的示意圖例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：3.1棧例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂情況2：3.1棧出棧序列：b棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒有限定插入和刪除操作進(jìn)行的時(shí)間。情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？3.1棧如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top棧的順序存儲(chǔ)結(jié)構(gòu)及基本操作出棧：top減1進(jìn)棧：top加1?？眨簍op=-1

012345678a1topa2topa3top棧滿：top=MaxSize-1棧的順序存儲(chǔ)及基本操作constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; inttop;}SeqStack;順序棧的類型定義voidInitStack(SeqStack&S){S.top=-1;}順序棧的實(shí)現(xiàn)——初始化voidPush(SeqStack&S,ElemTypex){if(S.top==MAXSIZE-1){cout<<"棧已滿"<<endl;exit(1);}

S.top++;

S.data[S.top]=x;}順序棧的實(shí)現(xiàn)——入棧ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"棧已空"<<endl;exit(1);}

ElemTypex=S.data[S.top];

S.top--; returnx;}順序棧的實(shí)現(xiàn)——出棧ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"棧已空"<<endl;exit(1);}

returnS.data[S.top];}順序棧的實(shí)現(xiàn)——取棧頂元素boolStackEmpty(SeqStack&S){ returnS.top==-1;}順序棧的實(shí)現(xiàn)——判斷棧空boolStackEmpty(SeqStack&S){ returnS.top==MAXSIZE-1;}順序棧的實(shí)現(xiàn)——判斷棧滿heada1a2an∧ai鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。棧的鏈?zhǔn)酱鎯?chǔ)及基本操作棧頂棧底鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)topanan-1a1∧兩種示意圖在內(nèi)存中對(duì)應(yīng)同一種狀態(tài)topa1an-1an∧棧頂棧底棧的鏈?zhǔn)酱鎯?chǔ)及基本操作typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}*LinkStack;鏈棧的類型定義voidInitStack(LinkStack&S){ S=NULL;}鏈棧的實(shí)現(xiàn)——初始化算法描述：voidPush(LinkStack&S,ElemTypex){LinkStackp=newNode;

p->data=x;

p->next=S;

S=p;}Sanan-1a1∧xpS鏈棧的實(shí)現(xiàn)——入棧算法描述：ElemTypePop(LinkStack&S){

if(S==NULL)

{cout<<"棧已空";exit(1);}

ElemTypex=S->data;//暫存棧頂元素

LinkStackp=S;

S=S->next;//刪除棧頂結(jié)點(diǎn)

deletep;

returnx;}Sanan-1a1∧Sp

鏈棧的實(shí)現(xiàn)——出棧ElemTypeTop(LinkStack&S){ if(S==NULL) {cout<<"棧已空";exit(1);} returnS->data;}鏈棧的實(shí)現(xiàn)——取棧頂元素boolStackEmpty(LinkStack&S){ returnS==NULL;}鏈棧的實(shí)現(xiàn)——判斷棧空voidDestroyListStack(LinkStack&S){LinkStackp;

while(S)

{

p=S;

S=S->next;

deletep;

}}鏈棧的實(shí)現(xiàn)——銷毀順序棧和鏈棧的比較時(shí)間性能：相同，都是常數(shù)時(shí)間O(1)。空間性能：順序棧：有元素個(gè)數(shù)的限制和空間浪費(fèi)的問題。鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時(shí)才會(huì)出現(xiàn)棧滿，但是每個(gè)元素都需要一個(gè)指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷?？傊?dāng)棧的使用過程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。3.1.2知識(shí)應(yīng)用——導(dǎo)學(xué)問題1voidconversion(intn){SeqStackS;InitStack(S);while(n){Push(S,n%8);n=n/8;}while(!StackEmpty(S))cout<<Pop(S);cout<<endl;}3.1.3知識(shí)拓展——算術(shù)表達(dá)式求值1、中綴表達(dá)式直接求值為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)工作棧：

1）運(yùn)算符OPTR棧,用以寄存運(yùn)算符；2）操作數(shù)OPND棧,用以寄存操作數(shù)或運(yùn)算結(jié)果。算法步驟：參見教材3.1.3知識(shí)拓展——算術(shù)表達(dá)式求值2、利用后綴表達(dá)式求值

將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí)，表達(dá)式中操作數(shù)次序不變，而操作符次序會(huì)發(fā)生變化，同時(shí)需要去掉圓括號(hào)。因此設(shè)置一個(gè)棧OPTR用以存放操作符。。算法步驟：參見教材3.1.3知識(shí)拓展——棧和遞歸求階乘的遞歸算法intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}3.1.3知識(shí)拓展——棧和遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程⑴運(yùn)行開始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；⑵每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；⑶每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。3.1.3知識(shí)拓展——棧和遞歸哪些問題可以用遞歸解決大問題可以分解為小問題可以確定遞歸到何時(shí)終止3.2隊(duì)列3.2.1知識(shí)學(xué)習(xí)隊(duì)列的基本概念

隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。隊(duì)尾隊(duì)頭a1a2a3入隊(duì)出隊(duì)隊(duì)列的操作特性：先進(jìn)先出constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; intrear;}SeqQueue;隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（1）循環(huán)隊(duì)列的初始化voidInitQueue(SeqQueue&Q){Q.front=Q.rear=0;}（2）循環(huán)隊(duì)列的入隊(duì)操作voidEnQueue(SeqQueue&Q,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {cout<<"隊(duì)列已滿"<<endl;exit(1);}Q.rear=(Q.rear+1)%MAXSIZE; Q.data[Q.rear]=x;

}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（3）循環(huán)隊(duì)列的出隊(duì)操作ElemTypeDeQueue(SeqQueue&Q){if(Q.front==Q.rear) {cout<<"隊(duì)列已空"<<endl;exit(1);} Q.front=(Q.front+1)%MAXSIZE; ElemTypex=Q.data[Q.front];returnx;}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（4）判斷循環(huán)隊(duì)列是否為空的操作boolQueueEmpty(SeqQueue&Q){ returnQ.front==Q.rear;}（5）判斷循環(huán)隊(duì)列是否為滿的操作boolQueueFull(SeqQueue&Q){ return(Q.rear+1)%MAXSIZE==Q.front;}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)隊(duì)頭指針即為鏈表的頭指針heada1a2an∧如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？rearfront隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）非空鏈隊(duì)列fronta1a2an∧rear空鏈隊(duì)列front∧rear隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstruct{ Node*front; Node*rear;}LinkQueue;隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）voidInitQueue(LinkQueue&Q){Q.front=Q.rear=newNode; Q.front->next=NULL;}front∧rear鏈隊(duì)列的操作——初始化xpfronta1an∧rearrearfrontxp∧∧rearrear算法描述：p->next=NULL;rear->next=p;rear=p;有了頭結(jié)點(diǎn)兩種情況下的處理是一致的。鏈隊(duì)列的操作——入隊(duì)∧voidEnQueue(LinkQueue&Q,ElemTypex){

Node*p=newNode;//產(chǎn)生新結(jié)點(diǎn)p p->data=x; p->next=NULL; Q.rear->next=p;//將結(jié)點(diǎn)p插入到隊(duì)尾 Q.rear=p; }鏈隊(duì)列的操作——入隊(duì)fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;鏈隊(duì)列的操作——出隊(duì)fronta1a2an∧rearp考慮邊界情況：隊(duì)列中只有一個(gè)元素？fronta1p∧rear∧rear僅1個(gè)元素的隊(duì)列判斷：if(rear==p)rear=front;如何判斷邊界情況？鏈隊(duì)列的操作——出隊(duì)ElemTypeDeQueue(LinkQueue&Q){

if(Q.front==Q.rear)

{cout<<"隊(duì)列已空"<<endl;exit(1);} Node*p=Q.front->next; ElemTypex=p->data; Q.front->next=p->next; if(Q.rear==p)

Q.r