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

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

線性表?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ì)列

棧是限定僅在表尾進(jìn)行插入和刪除的線性表。隊(duì)列是限定僅在表尾進(jìn)行插入、在表頭進(jìn)行刪除的線性表。23.1棧3.1.1棧的定義3.1.2棧的表示和實(shí)現(xiàn)3.1.3棧的應(yīng)用舉例3.1.4棧與遞歸的實(shí)現(xiàn)33.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端為棧底?；静僮?

}ADTStack一、棧的類型定義棧是限定僅在表尾進(jìn)行插入和刪除的線性表。表尾被稱為棧頂，表頭被稱為棧底。棧又被稱為后進(jìn)先出(lifo)的線性表。4InitStack(S)初始化一個(gè)空棧S?；静僮鳎篊learStack(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ìn)棧、出棧圖例

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

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

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

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

/*判棧S為滿時(shí)返回真，否則返回假*/{return(top==MaxSize-1?TRUE:FALSE);}134）進(jìn)棧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è)有一個(gè)空棧，棧頂指針為1000H，現(xiàn)有輸入序列為12345，PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，輸出序列為______，棧頂指針為_______

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

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

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

共享?xiàng)５目臻g示意為：top[0]和top[1]分別為兩個(gè)棧頂指示器。top[0]top[1]Stack：0M-1216、兩棧共享的數(shù)據(jù)結(jié)構(gòu)定義#defineM100StackElementTypeS[M];inttop[2];/*全局變量*//*top[0]和top[1]分別為兩個(gè)棧頂指示器*/227、兩棧共享基本操作的實(shí)現(xiàn)1）兩棧共享的初始化操作算法voidInitStack(int*S){ top[0]=-1; top[1]=M;}232）兩棧共享的進(jìn)棧操作算法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è)有一個(gè)輸入序列123，元素經(jīng)過一個(gè)棧到達(dá)輸出序列，并且元素一旦離開輸入序列就不能再回到輸入序列，試問經(jīng)過這個(gè)棧后可以得到多少種輸出序列？分析：每一元素只能做一次入棧、一次出棧，可以入棧后停留一段時(shí)間，然后到達(dá)輸出序列。那么該題就變?yōu)槿绾伟才湃蝡ush操作（s）和pop操作(x)的順序以得到盡量多的不同的輸出。sssxxx:321ssxsxx:231ssxxsx:213sxsxsx:123sxssxx:13226補(bǔ)充：如果進(jìn)棧的序列為123456，能否得到435612和135426的出棧序列，并說明為什么不能得到或者如何得到（寫出以‘S’表示進(jìn)棧,‘x’表示出棧的棧操作序列）二、鏈棧鏈棧是采用鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧。為便于操作，采用帶頭結(jié)點(diǎn)的單鏈表實(shí)現(xiàn)棧。因?yàn)闂５牟迦牒蛣h除操作僅限制在表頭位置進(jìn)行，所以鏈表的表頭指針就作為棧頂指針。鏈棧的示意圖為：∧a1

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

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

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

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

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

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

NNdiv8Nmod8

13481684

168210

2125

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

/*對(duì)任意非負(fù)十進(jìn)制數(shù)N，打印等值的八進(jì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棧與遞歸的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

{2IF(n==1)3move(x,1,z);/*將1號(hào)盤從x移到z*/9}4ELSE{5hanoi(n-1,x,z,y);/*將x上n-1個(gè)盤移到y(tǒng),z作輔助塔*/6move(x,n,z);/*將n號(hào)圓盤從x移到z*/7hanoi(n-1,y,x,z);/*將y上n-1個(gè)盤移到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)清晰、程序可讀性強(qiáng)，且其正確性易于證明，給用戶編程帶來很大方便。

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

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

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

數(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ì)列尾基本操作：3.2.1隊(duì)列的類型定義}

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

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

}LinkQueue

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

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

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

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

newnode

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

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

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

p=q->front->next;/*找到要?jiǎng)h除的元素*/

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

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

return(true);}

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

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

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

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

出隊(duì)操作為：x=q[front]；front=front+1；

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