算法與數(shù)據(jù)結(jié)構(gòu)課件棧和隊(duì)列

第3章棧和隊(duì)列3.1棧3.2隊(duì)列3.3典型例題1棧和隊(duì)列的特點(diǎn)兩者的邏輯結(jié)構(gòu)與線性表相同，但是插入和刪除操作受到了限制，稱為操作受限的線性表；棧只允許在線性表的一端進(jìn)行插入和刪除操作，隊(duì)列那么允許在一端插入另一端刪除；棧按照“后進(jìn)先出〞的規(guī)那么進(jìn)行操作，隊(duì)列那么按照“先進(jìn)先出〞的規(guī)那么進(jìn)行。23.1.1棧的定義及其根本運(yùn)算3.1.2棧的存儲(chǔ)結(jié)構(gòu)和根本運(yùn)算的實(shí)現(xiàn)3.1.3棧的應(yīng)用舉例3.1.4棧與遞歸的實(shí)現(xiàn)3.1棧33.1.1棧的定義及其根本運(yùn)算定義限制在表的一端進(jìn)行插入和刪除操作的線性表；表中允許進(jìn)行插入、刪除操作的一端稱為棧頂，另一個(gè)固定端稱為棧底。當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)，稱為空棧。操作原那么后進(jìn)先出〔LastInFirstOut〕,LIFO先進(jìn)后出〔FirstInLastOut〕,FILO舉例穿衣、脫衣過(guò)程；餐館洗好的一疊盤(pán)子；建筑工地上使用的磚；函數(shù)的嵌套調(diào)用；4棧的示意圖a1a2a3an…棧頂top棧底bottom入棧出棧5練習(xí)1依次輸入3個(gè)元素A、B、C到棧中，可得到哪幾種不同的輸出？解：共5種(1)A,B,C

(2)A,C,B(3)B,A,C

(4)B,C,A(5)C,B,A6設(shè)一個(gè)棧的輸入序列為A、B、C、D，那么借助一個(gè)棧所得到的輸出序列不可能是。 (A)A,B,C,D (B)D,C,B,A (C)A,C,D,B (D)D,A,B,C練習(xí)2答案：D7棧結(jié)構(gòu)的根本操作〔1〕棧初始化Init_Stack(s)〔2〕判棧空Empty_Stack(s)〔3〕入棧Push_Stack(s,x)〔4〕出棧Pop_Stack(s)〔5〕讀棧頂元素Top_Stack(s)8a1a2an……Push_Stack(s,x)初始條件：棧s已存在操作結(jié)果：插入x為新的棧頂元素棧發(fā)生變化x9a1a2an-1……Pop_Stack(s)初始條件：棧s存在且非空操作結(jié)果：刪除s的棧頂元素棧發(fā)生變化an10a1a2an……Top_Stack(s)初始條件：棧s存在且非空操作結(jié)果：返回s的棧頂元素棧不發(fā)生變化113.1.2棧的存儲(chǔ)結(jié)構(gòu)和根本運(yùn)算的實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)：順序棧鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈棧121.順序棧利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素；在數(shù)組上實(shí)現(xiàn)時(shí)，棧底位置可以設(shè)置在數(shù)組的任一個(gè)端點(diǎn)〔通常設(shè)置在0下標(biāo)處〕，而棧頂是隨著插入和刪除而變化的，可以用一個(gè)整形變量top指示棧頂元素在順序棧中的位置；數(shù)據(jù)入棧或出棧時(shí)，整形變量top分別執(zhí)行加1或減1的操作。13

toptop=-1空棧toptoptoptoptoptop=0a進(jìn)棧top=1b進(jìn)棧aababcdetop=4e進(jìn)棧abcdetop=4f進(jìn)棧上溢abdetop=3e退棧c14toptop=1c退棧top=0b退棧abaa退?？諚opabdtop=2d退棧ctopabctoptop1516順序棧的類型描述類型定義如下所示：

#defineMAXSIZE100typedefstruct{datatypedata[MAXSIZE];inttop;}SeqStack;

定義一個(gè)指向順序棧的指針：

SeqStack*s;教材有誤17順序棧根本操作的實(shí)現(xiàn)⑴置空棧【算法思想】首先建立?？臻g，然后初始化棧頂指針。SeqStack*Init_SeqStack(){SeqStack*s;s=malloc(sizeof(SeqStack));

s->top=-1;

returns;}時(shí)間復(fù)雜度為O(1)18⑵判空棧

intEmpty_SeqStack(SeqStack*s){ if(s->top==-1)return1; elsereturn0; }19

⑶入棧intPush_SeqStack(SeqStack*s,datatypex){

if(s->top==MAXSIZE-1)return0;

//棧滿不能入棧

else{s->top++;s->data[s->top]=x;return1;}}此時(shí)為上溢20⑷出棧intPop_SeqStack(SeqStack*s,datatype*x){

if(Empty_SeqStack(s))return0;//?？詹荒艹鰲lse { *x=s->data[s->top];s->top--; return1; }}棧頂元素仍然在，但是指針已經(jīng)不指向它了21⑸取棧頂元素

datatypeTop_SeqStack(SeqStack*s){ if(Empty_SeqStack(s))return0;/*?？?/ elsereturn(s->data[s->top]);}注意:

取棧頂元素與出棧的操作是不同的，雖然取得了棧頂元素，但是指針沒(méi)有改變。222.鏈棧假設(shè)是棧中元素的數(shù)目變化范圍較大或不清楚棧元素的數(shù)目，就應(yīng)該考慮使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧稱為鏈棧。通常鏈棧用單鏈表表示，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同。鏈棧結(jié)點(diǎn)的類型描述：typedefstructnode{

datatypedata;structnode*next;}StackNode，*LinkStack;教材有誤23鏈棧的棧頂？棧的插入刪除操作只能在一端進(jìn)行，對(duì)于單鏈表來(lái)說(shuō)，在頭部插入刪除結(jié)點(diǎn)要比尾部相對(duì)容易；所以，將單鏈表的頭部作為棧頂端，即將單鏈表的頭指針作為棧頂指針。24鏈棧示意圖top

∧

不帶頭結(jié)點(diǎn)說(shuō)明top為棧頂指針：LinkStacktop;25⑴置空棧LinkStackInit_LinkStack〔〕{ returnNULL;}⑵判棧空intEmpty_LinkStack〔LinkStacktop〕{ if〔top==NULL〕return1; elsereturn0;}26⑶入棧LinkStackPush_LinkStack〔LinkStacktop,datatypex〕{ StackNode*s;s=malloc〔sizeof〔StackNode〕〕;s->data=x;s->next=top;top=s;returntop;}入棧不需要判斷棧是否已滿27⑷出棧LinkStackPop_LinkStack(LinkStacktop,datatype*x){ StackNode*p; if〔top==NULL〕returnNULL;else{ *x=top->data; p=top; top=top->next; free(p); returntop;}}出棧需要判斷棧是否為空28〔3467)10轉(zhuǎn)換成(6613)8的過(guò)程如下：

NN/8(整除)N%8(取余)計(jì)算順序輸出順序34674333

433541

5466

6063.1.3棧的應(yīng)用舉例例3.1數(shù)制轉(zhuǎn)換問(wèn)題。29【

算法思想】當(dāng)N>0時(shí)重復(fù)1，21.假設(shè)N≠0，那么將N%r壓入棧s中，執(zhí)行2;假設(shè)N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。2.用N/r代替N棧的應(yīng)用:數(shù)制轉(zhuǎn)換30棧的應(yīng)用:數(shù)制轉(zhuǎn)換typedefintdatatype;voidconversion(intN,intr){//將非負(fù)十進(jìn)制整數(shù)轉(zhuǎn)換為八進(jìn)制整數(shù) SeqStacks; datatypex; Init_SeqStack(&s); while(N!=0) {Push_Stack(&s,N%r); N=N/r;} while(!Empty_SeqStack(&s)) {Pop_SeqStack(&s,&x);printf(“%d〞,x);}}31#defineL10voidconversion(intN，intr){ ints[L],top;/*定義一個(gè)順序棧*/intx;top=-1;/*初始化棧*/while(N){s[++top]=N%r;/*余數(shù)入棧*/N=N/r;/*商作為被除數(shù)繼續(xù)*/}while(top!=-1){x=s[top--];printf(“%d〞,x);}}32這里限定的表達(dá)式求值問(wèn)題是：用戶輸入一個(gè)包含“+〞、“-〞、“*〞、“/〞、正整數(shù)和圓括號(hào)的合法數(shù)學(xué)表達(dá)式，計(jì)算該表達(dá)式的運(yùn)算結(jié)果。例3.2表達(dá)式求值問(wèn)題33表達(dá)式求值：算符優(yōu)先法x=4-6/3+2*(3+8)操作數(shù)(operand)+運(yùn)算符(operator)+界限符(delimiter)把運(yùn)算符和界限符統(tǒng)稱為算符算符優(yōu)先法

4-6/3+2*(3+8)=4-2+2*(3+8)=2+2*(3+8)=2+2*11=2+22=24運(yùn)算規(guī)那么：從左到右；先乘除，后加減；先括號(hào)內(nèi)，后括號(hào)外；34表達(dá)式求值：算符優(yōu)先法不管操作數(shù)或運(yùn)算符，先輸入，后參與運(yùn)算可以考慮使用棧實(shí)現(xiàn)算法設(shè)置兩個(gè)棧opnd和optr，分別存放操作數(shù)和運(yùn)算符；運(yùn)算過(guò)程就是比較運(yùn)算符優(yōu)先級(jí)的過(guò)程〔a1b2)1優(yōu)先權(quán)低于2，不能運(yùn)算1優(yōu)先權(quán)等于2，結(jié)束〔‘#’〕或退括號(hào)〔‘〕’〕1優(yōu)先權(quán)高于2，可以運(yùn)算35算符間的優(yōu)先關(guān)系設(shè)兩個(gè)運(yùn)算符：

1

和

2

1<2, 1

優(yōu)先權(quán)低于2

1=2, 1

優(yōu)先權(quán)等于2

1>2, 1

優(yōu)先權(quán)高于2+－*/()#+>><<<>>－>><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=36【例】#4+2*3–8/(7–5)#

4

#

2

4

+

#

3

2

4*

+

#

4

+

#

6

4

+

#

#10

#

810

/

-

#opndoptropndoptropndoptropndoptra=3；b=2；op=*；c=2*3=6；a=6；b=4；op=+；c=4+6=10；opndoptropndoptropndoptropndoptr37【例】#4+2*3–8/(7–5)#

810（

/

-

#

5

7

810

-（

/

-

#

810

（

/

-

#a=5；b=7；op=-；c=7-5=2；

2

810

（

/

-

#

2

810

/

-

#

10

-

#a=2；b=8；op=/；c=8/2=4；

410

-

#

#opndoptropndoptropndoptropndoptropndoptropndoptropndoptropndoptra=4；b=10；c=10-4=6；383.1.4棧與遞歸的實(shí)現(xiàn)遞歸：假設(shè)在一個(gè)函數(shù)、過(guò)程或者數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)部，直接〔或間接〕出現(xiàn)定義本身的應(yīng)用，那么稱它們是遞歸的，或者是遞歸定義的。以下三種情況，常常要用到遞歸的方法定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問(wèn)題的解法是遞歸的如階乘定義,Fibonacci定義等如單鏈表，二叉樹(shù)等如Hanoi塔等39棧與遞歸的實(shí)現(xiàn)遞歸可以把一個(gè)大型復(fù)雜的問(wèn)題轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，通過(guò)少量的語(yǔ)句，實(shí)現(xiàn)重復(fù)計(jì)算。求n的階乘0 longFact(intn)1 {2if(n==0)//遞歸終止條件3 return1;4else5 return(n*Fact(n-1));6 }

40棧與遞歸的實(shí)現(xiàn)n=3fac(3)

﹕3*fac(2)n=2fac(2)

﹕﹕﹕2*fac(1)n=1fac(1)﹕﹕﹕1*fac(0)n=0fac(0){

if(n==0)return1﹕﹕}returnfac(3)=3*2*1returnfac(2)=2*1returnfac(1)=1*1遞歸的實(shí)現(xiàn)過(guò)程類似于多層函數(shù)的嵌套調(diào)用，只是調(diào)用者和被調(diào)用者是同一個(gè)函數(shù)而已原那么：后調(diào)用先返回41遞歸工作棧遞歸工作棧是遞歸函數(shù)運(yùn)行期間使用的數(shù)據(jù)存儲(chǔ)區(qū)每一次遞歸調(diào)用時(shí)，需要將實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存，并且要保存調(diào)用函數(shù)本層的參數(shù)和局部變量，以便從下一層返回時(shí)重新使用;上述信息組成一個(gè)遞歸工作記錄保存在遞歸工作棧中，按后進(jìn)先出的原那么組織。局部變量返回地址參數(shù)遞歸工作記錄活動(dòng)記錄框架42棧與遞歸的實(shí)現(xiàn):Hanoi漢諾塔問(wèn)題是印度的一個(gè)古老的傳說(shuō)。在世界中心貝拿勒斯〔在印度北部〕的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不管白天黑夜，總有一個(gè)僧侶在按照下面的法那么移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。43棧與遞歸的實(shí)現(xiàn):Hanoin階Hanoi塔問(wèn)題：假設(shè)有三個(gè)分別命名為X,Y,Z的塔座，在X塔座上插有n個(gè)直徑大小各不相同，依小到大編號(hào)為1，2，…,n的圓盤(pán)，要求：把X上的n個(gè)圓盤(pán)移到Z上，排列順序相同，移動(dòng)規(guī)那么為：每次只能移動(dòng)一個(gè)圓盤(pán)；圓盤(pán)可以在任一塔上做屢次移動(dòng)；在任何時(shí)刻，大盤(pán)不能壓小盤(pán)；XYZ44棧與遞歸的實(shí)現(xiàn):HanoivoidHanoi(intn,charx,chary,charz){ if(n==1) Move(1,x,z); //把1號(hào)盤(pán)，從x移到z else {Hanoi(n–1,x,z,y);//把n-1個(gè)盤(pán)，從x移到y(tǒng)，z為輔助塔

Move(n,x,z); //把n號(hào)盤(pán)，從x移到z Hanoi(n–1,y,x,z);//把n-1個(gè)盤(pán)，從y移到z，x為輔助塔

}}45463.2隊(duì)列3.2.1隊(duì)列的定義隊(duì)列：隊(duì)列是一種只允許在表的一端插入，在另一端刪除的操作受限的線性表。概念：隊(duì)尾rear：允許插入的一端隊(duì)頭front：允許刪除的一端FIFO〔FirstInFirstOut〕出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾a1a2a3an-1……47舉例到醫(yī)院看病，需要到掛號(hào)處掛號(hào)，然后按號(hào)碼順序救診。乘坐公共汽車，需要在車站排隊(duì)，車來(lái)后按順序上車。48〔1〕隊(duì)列初始化Init_Queue(q)〔2〕入隊(duì)In_Queue(q,x)〔3〕出隊(duì)Out_Queue(q,x)〔4〕讀隊(duì)頭元素Front_Queue(q,x)〔5〕判隊(duì)空Empty_Queue(q)隊(duì)列的根本操作49順序存儲(chǔ)結(jié)構(gòu)：循環(huán)隊(duì)列；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：鏈隊(duì)列；3.2.2隊(duì)列的存儲(chǔ)結(jié)構(gòu)和根本運(yùn)算的實(shí)現(xiàn)501.順序隊(duì)012n-2n-1a1a2a3...an-1anfrontrear51存在的問(wèn)題1：隊(duì)空時(shí)，隊(duì)頭和隊(duì)尾指針都為-1。此時(shí)假設(shè)進(jìn)行入隊(duì)操作，隊(duì)頭和隊(duì)尾指針都增1，再將新數(shù)據(jù)元素放入該位置。即，用這種方法設(shè)置隊(duì)頭、隊(duì)尾指針位置，在進(jìn)行入隊(duì)操作時(shí)，空隊(duì)與非空隊(duì)需要執(zhí)行的操作不完全一樣。解決方法：讓隊(duì)頭指針指向隊(duì)列真正隊(duì)頭元素的前一個(gè)位置。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)012...n-2n-1front=rear=-152隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置隊(duì)尾指針rear指向隊(duì)尾元素空隊(duì)時(shí)：front=rear=-1入隊(duì)原那么：隊(duì)尾指針rear=rear+1，再將新元素按rear指示位置參加出隊(duì)原那么：隊(duì)頭指針front=front+1，再將下標(biāo)為front的元素取出隊(duì)中元素的個(gè)數(shù)：m=rear-front012n-2n-1a1a2a3...an-1anfrontrear53順序隊(duì)的類型定義如下：

#defineMAXSIZE100/*隊(duì)列的最大容量*/typedefstruct{datatypedata[MAXSIZE];/*隊(duì)列的存儲(chǔ)空間*/intrear,front;/*隊(duì)頭隊(duì)尾指針*/}SeQueue;

定義一個(gè)指向順序隊(duì)的指針變量：

SeQueue*sq;54用數(shù)組實(shí)現(xiàn)隊(duì)列存在的問(wèn)題2問(wèn)題：如何解決“假溢出〞現(xiàn)象？frontrearJ1J2J3J5J4frontrearJ5J3J4frontrearfrontrearJ6J3J5J4J1frontrear空隊(duì)J1入隊(duì)J2、J3、J4、J5入隊(duì)J1、J2出隊(duì)J6入隊(duì)后再插入元素55循環(huán)隊(duì)列“假溢出〞現(xiàn)象的解決方法：將存放隊(duì)列元素的一維數(shù)組首尾相接，形成一個(gè)環(huán)狀。這種形式表示的隊(duì)列稱之為循環(huán)隊(duì)列。入隊(duì)：

rear=(rear+1)%MAXSIZE出隊(duì)：

front=(front+1)%MAXSIZE元素個(gè)數(shù)：m=(rear-front+MAXSIZE)%MAXSIZE56用數(shù)組實(shí)現(xiàn)隊(duì)列存在的問(wèn)題3front=4,rear=8有4個(gè)元素front=4,rear=4隊(duì)列滿front=8,rear=8隊(duì)空f(shuō)ront=4,rear=3少用一個(gè)元素空間時(shí)的隊(duì)列滿57循環(huán)隊(duì)列區(qū)別隊(duì)空和隊(duì)滿的三種方法問(wèn)題：如何區(qū)別隊(duì)空和隊(duì)滿？有三種方法1.少用一個(gè)元素空間2.引入一個(gè)標(biāo)志變量區(qū)別空和滿3.使用計(jì)數(shù)器(rear+1)%MAXSIZE==front58typedefstruct{

datatypedata[MAXSIZE];/*數(shù)據(jù)的存儲(chǔ)區(qū)*/

intfront,rear;/*隊(duì)頭隊(duì)尾指針*/

intnum;/*隊(duì)中元素的個(gè)數(shù)*/}c_SeQueue;/*循環(huán)隊(duì)*/循環(huán)隊(duì)列的類型定義59⑴置空隊(duì)c_SeQueue*Init_SeQueue(){

q=malloc(sizeof(c_SeQueue));

q->front=q->rear=-1;

q->num=0;

returnq;}60⑵入隊(duì)intIn_SeQueue(c_SeQueue*q,datatypex){

if(q->num==MAXSIZE){

printf(＂隊(duì)滿＂);

return–1;/*隊(duì)滿不能入隊(duì)*/}else{

q->rear=(q->rear+1)%MAXSIZE;

q->data[q->rear]=x;

q->num++;

return1;/*入隊(duì)完成*/

}}61⑶出隊(duì)intOut_SeQueue(c_SeQueue*q,datatype*x){

if(q->num==0){

printf(＂隊(duì)空＂)；

return–1;/*隊(duì)空不能出隊(duì)*/}else{

q->front=(q->front+1)%MAXSIZE;

*x=q->data[q->front];/*讀出隊(duì)頭元素*/

q->num--;

return1;/*出隊(duì)完成*/

}}62⑷判隊(duì)空intEmpty_SeQueue(c_SeQueue*q){

if(q->num==0)return1;elsereturn0;}632.鏈隊(duì)列用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)列。一個(gè)鏈隊(duì)列顯然需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。

…a2rearfronta1an∧64typedefstructnode{

datatypedata;

structnode*next;}QNode;

/*鏈隊(duì)列結(jié)點(diǎn)的類型*/typedefstruct{

QNode*front,*rear;}LQueue;

/*將頭尾指針?lè)庋b在一起的鏈隊(duì)列*/定義一個(gè)指向鏈隊(duì)列的指針：LQueue*q;鏈隊(duì)列的類型定義教材有誤65鏈隊(duì)列示意圖(a)非空隊(duì)q

frontreara1an∧

…a2(b)空隊(duì)qrearfront

∧

(c)鏈隊(duì)中只有一個(gè)元素結(jié)點(diǎn)frontrearqa1∧

66(1)創(chuàng)立一個(gè)帶頭結(jié)點(diǎn)的空隊(duì)LQueue*Init_LQueue(){ LQueue*q,*p; q=malloc(sizeof(LQueue));/*申請(qǐng)頭尾指針結(jié)點(diǎn)*/ p=malloc(sizeof(QNode));/*申請(qǐng)鏈隊(duì)頭結(jié)點(diǎn)*/ p->next=NULL;q->front=q->rear=p; returnq;}67(2)

入隊(duì)void