數(shù)據(jù)結(jié)構(gòu)-第三章棧和隊列

第3章限定性線性表—棧和隊列3.1棧3.2隊列棧和隊列是兩種常用的數(shù)據(jù)類型

線性表棧隊列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棧與隊列

棧是限定僅在表尾進行插入和刪除的線性表。隊列是限定僅在表尾進行插入、在表頭進行刪除的線性表。23.1棧3.1.1棧的定義3.1.2棧的表示和實現(xiàn)3.1.3棧的應(yīng)用舉例3.1.4棧與遞歸的實現(xiàn)33.1.1棧的定義：ADTStack{

數(shù)據(jù)對象：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端為棧底?；静僮?

}ADTStack一、棧的類型定義棧是限定僅在表尾進行插入和刪除的線性表。表尾被稱為棧頂，表頭被稱為棧底。棧又被稱為后進先出(lifo)的線性表。4InitStack(S)初始化一個空棧S。基本操作：ClearStack(S)將S清為空棧IsEmpty(S)若S為空棧,則返回true,否則false。GetTop(S)若S非空,則返回它的棧頂元素,否則返回'false

'。Push(S,e)入棧,插入元素e為新的棧頂元素。Pop(S)出棧,若S非空,則刪除并返回它的棧頂元素,否則返回'false

'。IsFull(S)

若S為滿棧,則返回true,否則false。5二、進棧、出棧圖例

根據(jù)棧定義，每次進棧的元素都被放在原棧頂元素之上而成為新的棧頂，而每次出棧的總是當(dāng)前棧中“最新”的元素，即最后進棧的元素。進棧出棧進棧出棧棧頂棧底an…a2a163.1.2棧的表示和實現(xiàn)棧在計算機中主要有兩種基本的存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序存儲的棧為順序棧；鏈?zhǔn)酱鎯Φ臈殒湕！?一、順序棧1、順序棧的存儲結(jié)構(gòu)定義#defineMaxSize50StackElementTypeS[MaxSize];

/*用來存放棧中元素的一維數(shù)組*/inttop;

/*棧頂指針，全局變量*/82、順序棧中的進棧和出棧圖例top=-1?？誇EDCBAtop=5棧滿Atop=0插入ACBAtop=2棧長度393.順序棧的基本操作特點下溢：棧空時再做退棧運算將產(chǎn)生溢出。1）棧底位置固定在順序表的低端，即S[0]----表示棧底元素2）入棧：top++，保存元素；3）出棧：取元素,top--；4）空棧：top=-1；5）棧滿：top=MaxSize-1；上溢：棧滿時再做進棧運算（一種出錯狀態(tài)，應(yīng)設(shè)法避免）。103、順序棧基本操作的實現(xiàn)1）初始化voidInitStack(int*S){/*構(gòu)造一個空棧S*/top=-1;}112）判?？読ntIsEmpty(int*S)

/*判棧S為空棧時返回值為1，反之為0*/{return(top==-1?1:0);}123）判棧滿intIsFull(int*S)

/*判棧S為滿時返回真，否則返回假*/{return(top==MaxSize-1?TRUE:FALSE);}134）進棧intPush(int*S,intx){if(top==MaxSize-1)return(FALSE);/*棧已滿*/top++;S[top]=x;return(TRUE);}145）出棧intPop(int*S,int*x){if(top==-1)/*棧為空*/return(FALSE);else

{*x=S[top];top--;/*修改棧頂指針*/return(TRUE);}}156）取棧頂元素intGetTop（int*S,int*x）{/*將棧S的棧頂元素取出，放入x所指的單元，但棧頂指針保持不變*/ if(top==-1)/*棧為空*/return(FALSE); else

{*x=S[top];return(TRUE);} }16〖例〗設(shè)有一個空棧，棧頂指針為1000H，現(xiàn)有輸入序列為12345，PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，輸出序列為______，棧頂指針為_______

2,31003Htop=1000H1top=1001Htop=1002H23top=1003H45輸出序列：〖例〗在一個n個單元的順序棧中，假定以地址高端(下標(biāo)為n-1的單元)作為棧底，則向棧中壓入一個元素時，棧頂指針top的變化是______top不變 top=n top=top-1 top=top+1棧低棧頂top=-1n-1n-2…10〖例〗若一個棧的輸入序列是1，2，…，n，輸出序列的第一個元素是n，則第i個輸出元素是______

n-i n-i+1 i n-i-1top=-1nn-1…12top=n-1方法一：將棧的容量加到足夠大，但這種方法由于事先難以估計容量，有可能浪費空間。當(dāng)程序中同時使用幾個棧時，如何防止棧的上溢？5.順序棧上溢的解決方法方法二：使用兩個（或多個）棧共享存儲空間辦法。兩棧的棧底分別設(shè)在給定存儲空間的兩端，然后各自向中間伸延，當(dāng)兩棧的棧頂相遇時才可能發(fā)生溢出。20

利用棧“棧底位置不變，而棧頂位置動態(tài)變化”的特性，為兩個棧申請一個共享的一維數(shù)組空間S[M]，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0，M-1。

共享棧的空間示意為：top[0]和top[1]分別為兩個棧頂指示器。top[0]top[1]Stack：0M-1216、兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義#defineM100StackElementTypeS[M];inttop[2];/*全局變量*//*top[0]和top[1]分別為兩個棧頂指示器*/227、兩棧共享基本操作的實現(xiàn)1）兩棧共享的初始化操作算法voidInitStack(int*S){ top[0]=-1; top[1]=M;}232）兩棧共享的進棧操作算法intPush(int*S,intx,inti){if(top[0]+1==top[1])/*棧已滿*/return(FALSE);switch(i){case0:

top[0]++;

S[top[0]]=x;

break;

case1:

top[1]--;

S[top[1]]=x;

break;default:return(FALSE)}return(TRUE);}243）兩棧共享的出棧操作算法intPop(int*S,int*x,inti){switch(i){case0:if(top[0]==-1)return(FALSE);*x=S[top[0]];

top[0]--;break;

case1:if(top[1]==M)return(FALSE); *x=S[top[1]];top[1]++;break;default:return(FALSE);}return(TRUE);}25〖例〗設(shè)有一個輸入序列123，元素經(jīng)過一個棧到達輸出序列，并且元素一旦離開輸入序列就不能再回到輸入序列，試問經(jīng)過這個棧后可以得到多少種輸出序列？分析：每一元素只能做一次入棧、一次出棧，可以入棧后停留一段時間，然后到達輸出序列。那么該題就變?yōu)槿绾伟才湃蝡ush操作（s）和pop操作(x)的順序以得到盡量多的不同的輸出。sssxxx:321ssxsxx:231ssxxsx:213sxsxsx:123sxssxx:13226補充：如果進棧的序列為123456，能否得到435612和135426的出棧序列，并說明為什么不能得到或者如何得到（寫出以‘S’表示進棧,‘x’表示出棧的棧操作序列）二、鏈棧鏈棧是采用鏈表作為存儲結(jié)構(gòu)實現(xiàn)的棧。為便于操作，采用帶頭結(jié)點的單鏈表實現(xiàn)棧。因為棧的插入和刪除操作僅限制在表頭位置進行，所以鏈表的表頭指針就作為棧頂指針。鏈棧的示意圖為：∧a1

…an-1antoptop為棧頂指針，始終指向當(dāng)前棧頂元素前面的頭結(jié)點。若top->next=NULL，則代表空棧。注意：鏈棧在使用完畢時，應(yīng)該釋放其空間。28鏈棧的基本操作特點1）棧底位置固定在鏈表的末尾p->next=NULL----表示棧底元素2）入棧：用入棧元素建立新結(jié)點，并將其插入到鏈表的第一個結(jié)點之前；(頭插法)3）出棧：取出鏈表首元素結(jié)點的值，并將其第一個結(jié)點從鏈表中刪除；4）空棧：top->next=NULL；291、鏈棧的存儲結(jié)構(gòu)定義typedefstructnode{StackElementTypedata;structnode*next;}LinkStackNode,*LinkStack;302、鏈棧基本操作的實現(xiàn)1)鏈棧的進棧操作intPush(LinkStacktop,StackElementTypex)

/*將數(shù)據(jù)元素x壓入棧top中*/{

LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));/*申請空間*/if(temp==NULL)return(FALSE);/*失敗*/temp->data=x;/*構(gòu)造結(jié)點*/temp->next=top->next;top->next=temp;/*修改當(dāng)前棧頂指針*/return(TRUE);}312)鏈棧的出棧操作intPop(LinkStacktop,StackElementType*x){/*將棧top的棧頂元素彈出，放到x所指的存儲空間中*/LinkStackNode*temp;temp=top->next;if(temp==NULL)/*棧為空*/ return(FALSE);top->next=temp->next;*x=temp->data;free(temp);/*釋放存儲空間*/return(TRUE);}323.1.3棧的應(yīng)用舉例例1、括號匹配的檢驗則檢驗括號是否匹配可用棧來實現(xiàn)。假設(shè)在表達式中（［］（））或［（［］［］）］等為正確的格式，［（］）或（［（））或（（）］)均為不正確的格式。33分析可能出現(xiàn)的不匹配的情況:1)到來的右括弧并非是所“期待”的；2)到來的是“不速之客”；3)直到結(jié)束，也沒有到來所“期待”的括弧。不正確的格式：［（］）或（［］））或（［（）］34算法的設(shè)計思想:1）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若棧空，則表明該“右括弧”多余，否則和棧頂元素比較，若相匹配，則“左括弧出?！?，否則表明不匹配。3）表達式檢驗結(jié)束時，若?？?，則表明表達式中匹配正確，否則表明“左括弧”有余。[([][])][([])[]][([[35括號匹配算法:voidBracketMatch(char*str){StackS;inti;charch;InitStack(&S);For(i=0;str[i]!='\0';i++){switch(str[i]){case'(':case'[':case'{':Push(&S,str[i]);break;case')':case']':case'}':if(IsEmpty(S)){printf("\n右括號多余!");return;}else{GetTop(&S,&ch);if(Match(ch,str[i]))Pop(&S,&ch);else{printf("\n對應(yīng)的左右括號不同類!");return;}}}/*switch*/}/*for*/if(IsEmpty(S)) printf("\n括號匹配!");else

printf("\n左括號多余!");}36例2、數(shù)制轉(zhuǎn)換算法基于原理：

N=(Ndivd)×d+Nmodd計算順序輸出順序例如：（1348)10=(2504)8

，其運算過程如下：

NNdiv8Nmod8

13481684

168210

2125

20237十進制轉(zhuǎn)換為二進制（例如：25）有余數(shù)是1沒余數(shù)是025除2=12......112除2=6......06除2=3......03除2=1......11除2=0......1然后我們將余數(shù)按“從下往上”的順序書寫就是：11001，那么這個11001就是十進制25的二進制形式top11100toptop出棧：toptoptoptoptop數(shù)制轉(zhuǎn)換算法voidConversion(intN)

/*對任意非負(fù)十進制數(shù)N，打印等值的八進制數(shù)*/{StackS;intx;/*S為順序棧或鏈棧*/InitStack(&S); while(N>0) {x=N%8;Push(&S,x);N=N/8;} while(！IsEmpty(S)) {Pop(&S,&x);printf(“%d”,x);} }393.1.4棧與遞歸的實現(xiàn)

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

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

從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前,應(yīng)該完成下列三項任務(wù)：

保存返回的計算結(jié)果(用函數(shù)名,引用參數(shù))

；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)(局部量)；依照被調(diào)函數(shù)中保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。41多個函數(shù)嵌套調(diào)用的規(guī)則是：此時的內(nèi)存管理實行“棧式管理”后調(diào)用先返回！例如：main(){voida(){voidb(){………a();b();……}//main}//a}//bmain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)

每個函數(shù)數(shù)據(jù)區(qū)含：參數(shù)、局部變量、返回地址等信息42遞歸工作棧:遞歸函數(shù)執(zhí)行過程中占用的數(shù)據(jù)區(qū)工作記錄:每一層的參數(shù)、局部變量、返回地址等構(gòu)成的記錄(數(shù)據(jù)區(qū))當(dāng)前活動記錄:棧頂工作記錄(當(dāng)前函數(shù)數(shù)據(jù)區(qū))當(dāng)前環(huán)境指針:遞歸工作棧的棧頂指針,指向當(dāng)前活動記錄。(指示當(dāng)前函數(shù)數(shù)據(jù)區(qū))可見：棧是函數(shù)過程嵌套調(diào)用及遞歸調(diào)用管理的有效手段

遞歸函數(shù)執(zhí)行過程是直接或間接地調(diào)用自己,可視為同一函數(shù)自己對自己進行嵌套調(diào)用。例如：voida(){voida(){voidb(){………a();b();a();………}//a直接遞歸

}//a}//b間接遞歸

43例Hanoi塔問題：有3個塔座x,y,z,在塔座x上插有n個大小不同的圓盤,從小到大且自上而下編號為1,2,…n;按規(guī)則將它們一個個搬到塔座z上,y可用作輔助塔座。規(guī)則為：(1)每次只能移動一個圓盤；(2)圓盤可放在任意塔座上；(3)任何時刻塔座上都不得將大盤壓在小盤之上。分析：n=1時：直接從塔座x移動到塔座z上；n>1時：先將上面的n-1個圓盤移到塔座y上,然后將n號盤移到塔座z上,再將y上的n-1個圓盤移到塔座z上。這樣就將問題的規(guī)模縮小1,利用遞歸可實現(xiàn)。44voidhanoi(intn;charx,chary,charz)

/*將塔座x上按直徑由小到大且至上而下編號為1至n的

n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。*/1

{2IF(n==1)3move(x,1,z);/*將1號盤從x移到z*/9}4ELSE{5hanoi(n-1,x,z,y);/*將x上n-1個盤移到y(tǒng),z作輔助塔*/6move(x,n,z);/*將n號圓盤從x移到z*/7hanoi(n-1,y,x,z);/*將y上n-1個盤移到z,x作輔助塔*/8}45voidhanoi(intn;charx,chary,charz)1

{2IF(n==1)3move(x,1,z);4ELSE{hanoi(n-1,x,z,y);

move(x,n,z);hanoi(n-1,y,x,z);8}}調(diào)用程序:返回地址為0hanoi(3,'A','B','C);0......03ABC62ACB61ABC

81CAB

返址nxyz46ABC

…...move(x,1,z);1CAB…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);…...…...move(x,1,z);2BAC1BCA…...move(x,1,z);1ABC…...hanoi(n,'A','B','C');…...…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);…...…...hanoi(n-1,x,z,y);move(x,n,z);hanoi(n-1,y,x,z);………...move(x,1,z);3ABCn,x,y,z2ACB1ABCmove(x,n,z);move(x,n,z);move(x,n,z);1A->C2A->B1C->B3A->C1B->A2B->C1A->C47

遞歸程序結(jié)構(gòu)清晰、程序可讀性強，且其正確性易于證明，給用戶編程帶來很大方便。

但遞歸程序效率很低(時、空兩方面)，使用時多加權(quán)衡。當(dāng)問題滿足如下條件是，可設(shè)計地歸算法：1、原問題可以層層分解為類似的子問題，子問題規(guī)模比原問題?。?、規(guī)模最小的子問題具有直接解。設(shè)計遞歸算法的方法是：1.尋找分解方法，將原問題分解為類似的子問題求解；2.設(shè)計遞歸出口,按最小規(guī)模子問題確定遞歸終止條件;483.2隊列3.2.1隊列的定義3.2.2

隊列的表示和實現(xiàn)3.2.3隊列的應(yīng)用舉例

隊列(Queue)：只允許在表的一端進行插入,在表的另一端進行刪除的線性表，又稱先進先出(FirstInFirstOut,FIFO)線性表。允許插入的一端為隊尾(rear,tail),允許刪除的一端為隊頭(front)。它和日常生活中的排隊是一致的,在操作系統(tǒng)中的作業(yè)排隊就是它的典型應(yīng)用。49ADTQueue{

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

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

端為隊列頭，an

端為隊列尾基本操作：3.2.1隊列的類型定義}

ADTQueue50隊列的基本操作：InitQueue(Q)初始化構(gòu)造一個空隊列Q。IsEmpty(Q)若Q為空,則返回true,否則返回false。IsFull(Q)若Q為滿,則返回true,否則返回false。EnterQueue(Q,e)入隊,插入e為Q的新隊尾元素。DeleteQueue(Q,*e)出隊,若Q非空,則隊頭元素出隊由e帶回,并返回true,否則返回false。GetHead(Q,*e)取隊頭,若Q非空,由e帶回隊頭元素,

并返回true,否則返回false。ClearQueue(Q)將Q清為空隊列。513.2.2隊列的表示和實現(xiàn)一、鏈隊列typedefstructNode{QueueElementtypedatastructNode*next}LinkQueueNode/*結(jié)點類型*/typedefstruct{LinkQueueNode*front/*隊頭指針*/LinkQueueNode*rear/*隊尾指針*/

}LinkQueue

/*鏈隊列類型*/1、鏈隊列存儲結(jié)構(gòu)定義52a1∧an…q.frontq.rearq.frontq.rear∧空隊列LinkQueueq2、鏈隊列示意圖531)初始化intinitQueue(LinkQueue*q){q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));

/*申請頭結(jié)點空間*/if(q->front!=null){q->rear=q->front;q->front->next=null;

/*頭、尾指針均指向頭結(jié)點*/return(true);}elsereturn(false);}

3、鏈隊列基本操作的實現(xiàn)542)入隊intEnterqueue(LinkQueue*q,QueueElementTypex){LinkQueueNode*newnode;

newnode

=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));/*申請新結(jié)點空間*/if(newnode!=null){newnode->data=x;newnode->next=null;/*構(gòu)造結(jié)點*/

q->rear->next=newnode;q->rear=newnode;/*以尾插法方式插入結(jié)點*/return(true);}return(false);}

55intdeletequeue(LinkQueue*q,QueueElementType*x){LinkQueueNode*p;if(q->front==q->rear)/*空隊列*/return(false);

p=q->front->next;/*找到要刪除的元素*/

q->front->next=p->next;

/*重新鏈接q的隊頭元素*/if(q->rear==p)q->rear=q->front;/*若要刪除的為隊尾元素,即刪除后隊列為空,則修改尾指針*/*x=p->data;free(p);/*刪除該元素*/

return(true);}

3）出隊56二、循環(huán)隊列

盡管鏈隊列使用方便,但由于其指針多占存儲空間,有時仍需要用順序結(jié)構(gòu)來表示隊列。順序隊列中也需要兩個“指針”：頭指針front指示隊頭元素的當(dāng)前位置；尾指針rear指示隊尾元素的后一個位置。初始時front=rear=0。571、循環(huán)隊列存儲結(jié)構(gòu)定義#definemaxsize50

QueueElementtypeQ[maxsize];/*保存隊列元素值的數(shù)組*/

intfront,rear;/*隊列的頭為指針，全局變量*/58此時入隊操作為：Q[rear]=x;rear=rear+1;

出隊操作為：x=q[front]；front=front+1；

隊空條件：rear=front假隊滿：rear==maxsize,隊滿：rear–front=maxsize或rear=frontrear–front＜maxsize假rearfrontDEGrearfrontAB