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

第三章棧和隊(duì)列1ppt課件第三章棧和隊(duì)列本章學(xué)習(xí)兩種特殊的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，它們特殊在定義的操作不同，即插入和刪除操作只能在線(xiàn)性表的兩端進(jìn)行。

只能在一端進(jìn)行的-----棧

分別在兩端進(jìn)行的-----隊(duì)列2ppt課件重點(diǎn)

本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問(wèn)題中正確使用。知識(shí)點(diǎn)

順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列

3ppt課件１.你見(jiàn)過(guò)餐館中一疊一疊的盤(pán)子嗎？如果它們是按1,2,…,n的次序往上疊的，那么使用時(shí)候的次序應(yīng)是什么樣的？２.在日常生活中，為了維持正常的社會(huì)秩序而出現(xiàn)的常見(jiàn)現(xiàn)象是什么？

4ppt課件

棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線(xiàn)性數(shù)據(jù)結(jié)構(gòu)．

棧必須按“后進(jìn)先出”的規(guī)則進(jìn)行操作，而隊(duì)列必須按“先進(jìn)先出”的規(guī)則進(jìn)行操作。

和線(xiàn)性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱(chēng)為限定性的線(xiàn)性表結(jié)構(gòu)。

5ppt課件

插入刪除

線(xiàn)性表：Insert(L,i,x)

Delete(L,i)

(1≤i≤n+1)

(1≤i≤n)

棧：Insert(L,n+1,x)

Delete(L,n)

隊(duì)列：Insert(L,n+1,x)

Delete(L,1)6ppt課件第三章棧和隊(duì)列

3.1棧1、棧（stack)：是一種特殊的線(xiàn)性表（數(shù)據(jù)元素之間的關(guān)系是線(xiàn)性關(guān)系），其插入、刪除只能在表的一端進(jìn)行，另一端固定不動(dòng)。棧頂（top)：插入、刪除的一端；

棧底（bottom)：固定不動(dòng)的一端；

入棧（push)：又稱(chēng)壓入，即插入一個(gè)元素；出棧（pop)：又稱(chēng)彈出，即刪除一個(gè)元素；一、抽象數(shù)據(jù)類(lèi)型棧的定義7ppt課件2、說(shuō)明：設(shè)（a1,a2,a3,…,an）是一個(gè)棧

（a1,a2,...,ai-1,ai,ai+1,…,an）棧底棧頂進(jìn)棧出棧1）表尾稱(chēng)為棧頂，表頭稱(chēng)為棧底，即a1為棧底元素，an為棧頂元素;

2）在表尾插入元素的操作稱(chēng)進(jìn)棧操作，在表頭刪除元素的操作稱(chēng)為出棧操作;

3）元素按a1,a2,a3,…,an的次序進(jìn)棧,第一個(gè)進(jìn)棧的元素一定在棧底，最后一個(gè)進(jìn)棧的元素一定在棧頂,第一個(gè)出棧的元素為棧頂元素；8ppt課件棧的示意圖棧特點(diǎn)：由于限制了插入刪除只能在一端進(jìn)行，那么元素的操作順序有“先進(jìn)后出”或“后進(jìn)先出”的特點(diǎn)(LastInFirstout-LIFOFirstInLastout---FILO)第一個(gè)進(jìn)棧的元素在棧底，最后一個(gè)進(jìn)棧的元素在棧頂，第一個(gè)出棧的元素為棧頂元素，最后一個(gè)出棧的元素為棧底元素9ppt課件課堂練習(xí)假設(shè)有A，B,C,D四個(gè)元素；它們?nèi)霔４涡驗(yàn)锳一＞B一＞C一＞D出棧次序任意，請(qǐng)問(wèn)不可能得到下面哪些出棧序列？(1)ABCD

(2)DBCA

(3)CDBA(4)CBAD

(5)ACBD

(6)DBAC(7)ADCB

(8)CABD

10ppt課件3、棧的基本操作1）

初始化操作InitStack(&S)

功能：構(gòu)造一個(gè)空棧S；

2）銷(xiāo)毀棧操作DestroyStack(&S)

功能：銷(xiāo)毀一個(gè)已存在的棧;

3）置空棧操作ClearStack(&S)

功能：將棧S置為空棧;

4）判空棧操作StackEmpty(S)

功能：若棧為空棧，返回TRUE，否則FALSE

5）取長(zhǎng)度操作StackLength(S)

功能：返回棧S的元素個(gè)數(shù)

11ppt課件

6）取棧頂元素操作GetTop(S,&e)

功能：取棧頂元素，并用e返回;7）進(jìn)棧操作Push(&S,e)

功能：元素e進(jìn)棧;8）退棧操作Pop(&S,&e)

功能：棧頂元素退棧，并用e返回;7）棧遍歷StackTraverse(S)

功能：從棧底到棧頂依次調(diào)用函數(shù)visit().12ppt課件4、棧的ADT描述棧的抽象數(shù)據(jù)類(lèi)型定義為：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

13ppt課件二棧的存儲(chǔ)表示和操作的實(shí)現(xiàn)和線(xiàn)性表類(lèi)似，棧也有兩種存儲(chǔ)表示，其順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為順序棧。

和順序表類(lèi)似，對(duì)順序棧也需要事先為它分配一個(gè)可以容納最多元素的存儲(chǔ)空間。14ppt課件順序存儲(chǔ)方式：同一般線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)完全相同。是利用一組連續(xù)的內(nèi)存單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，棧頂元素的位置由一個(gè)稱(chēng)為棧頂指針的變量指示。15ppt課件實(shí)際是棧中元素的個(gè)數(shù)順序棧類(lèi)型的定義//結(jié)構(gòu)定義：

typedefstruct{

ElemType*base;//存儲(chǔ)空間基址

inttop;

//棧頂指針

intstacksize;

//允許的最大存儲(chǔ)空間

}Stack;

棧頂指針總是指在棧頂元素的后面一個(gè)位置上16ppt課件top=0123450?？誸op123450進(jìn)棧Atop出棧棧滿(mǎn)BCDEF設(shè)數(shù)組維數(shù)為stacksizetop=0,?？?，此時(shí)出棧，則下溢（underflow)top=stacksize,棧滿(mǎn)，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptop17ppt課件特點(diǎn)：簡(jiǎn)單、方便，但易產(chǎn)生溢出。上溢（Overflow)棧已經(jīng)滿(mǎn)，又要壓入元素；下溢（Underflow)棧已經(jīng)空，還要彈出元素；注：上溢是一種錯(cuò)誤，使問(wèn)題的處理無(wú)法進(jìn)行下去；而下溢一般認(rèn)為是一種結(jié)束條件，即問(wèn)題處理結(jié)束。18ppt課件#defineSTACK_INIT_SIZE100//棧存儲(chǔ)空間的初始分配量#defineSTACKINCREMENT10//棧存儲(chǔ)空間的分配增量

typedefstruct{

SElemType*base;//?？臻g基址稱(chēng)為棧底指針，指向棧底位置

SElemType*top//棧頂指針,約定棧頂指針指向棧頂元素的//下（后面）一個(gè)位置；

intstacksize;//當(dāng)前分配的?？臻g大小//（以sizeof(SElemType)為單位）

}SqStack;//SqStack:：結(jié)構(gòu)類(lèi)型名順序棧的存儲(chǔ)表示19ppt課件

nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZE初始化操作圖示順序?；静僮鞯乃惴?/p>

1）初始化操作InitStack_Sq(SqStack&S)

參數(shù)：S是存放棧的結(jié)構(gòu)變量；功能：建一個(gè)空棧S；20ppt課件StatusInitStack_Sq(SqStack&S){

//構(gòu)造一個(gè)空棧S

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//為順序棧動(dòng)態(tài)分配存儲(chǔ)空間

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

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;}//InitStack_Sq21ppt課件StatusDetroyStack_Sq(SqStack&S){

If(!S.base)returnERROR;//若棧未建立（尚未分配?？臻g）

free(S.base);//回收棧空間

S.base=S.top=null;

S.stacksize=0;

returnOK;}//DetroyStack_Sq2）銷(xiāo)毀棧操作DestroyStack_Sq(SqStack&S)

功能：銷(xiāo)毀一個(gè)已存在的棧;22ppt課件S.top=nullS.stacksizeS.base=null0

nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE銷(xiāo)毀前銷(xiāo)毀后銷(xiāo)毀棧操作圖示23ppt課件3）置空棧操作ClearStack_Sq(SqStack&S)

功能：將棧S置為空棧算法

StatusClearStack_Sq(SqStack&S){

If(!S.base)returnERROR;//若棧未建立（尚未分

//配?？臻g）

S.top=S.base;

returnOK;}//ClearStack_Sq24ppt課件

nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZE

nn-1i-1i-210S.topS.stacksizeS.baseSTACK_INIT_SIZEanaiai-1a2a1置空棧操作圖示S.base=S.top表明棧為空置空前置空后25ppt課件StatusGetTop_Sq(SqStackS,SelemType&e){

//若棧不空，則用e返回S的棧頂元素，并返回//OK；否則返回ERROR

if(S.top==S.base)returnERROR;//若棧為空

e=*(S.top-1);

returnOK;

}//GetTop_Sq4）

取棧頂元素操作GetTop_Sq(SqStackS,SElemType&e)

功能：取棧頂元素，并用e返回;26ppt課件

nn-1i-1i-210anaiai-1a2a1S.topS.stacksizeS.baseSTACK_INIT_SIZEean

取棧頂元素操作圖示27ppt課件5）進(jìn)棧操作Push(SqStack&S,SElemTypee)

功能：元素e進(jìn)棧;

進(jìn)棧操作主要步驟：1）S是否已滿(mǎn)，若棧滿(mǎn)，重新分配存儲(chǔ)空間；2）將元素e寫(xiě)入棧頂；3）修改棧頂指針，使棧頂指針指向棧頂元素的下（后面）一個(gè)位置；28ppt課件

nn-1i-1i-20n+1nn-1i-1i-20S.topS.stacksizeS.baseSTACK_INIT_SIZEeanaiai-1a1anaiai-1a1S.topS.stacksizeS.baseSTACK_INIT_SIZE

e進(jìn)棧前

e進(jìn)棧后進(jìn)棧操作圖示29ppt課件StatusPush(SqStack&S,SElemTypee){

//將元素e插入棧成為新的棧頂元素,要考慮上溢情況

if(S.top-S.base>=S.stacksize){//棧滿(mǎn)，追加存儲(chǔ)空間

S.base=(SElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)sizeof(ElemType));if(!S.base)exit(OVERFLOW);//存儲(chǔ)分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;//元素e插入棧頂，修改棧頂指針

returnOK;}//Push進(jìn)棧操作算法：30ppt課件StatusPop(SqStack&S,SElemType&e){

//若棧不空，則刪除S的棧頂元素，用e返回其值并返回OK

//否則返回ERROR

if(S.top==S.base)returnERROR;//?？眨祷谽RROR

e=*--S.top;//刪除棧頂元素，用e返回其值，并修

//改棧頂指針

returnOK;

}//Pop

6）出棧操作Pop(SqStack&S,SElemType&e)

功能：棧頂元素退棧，并用e返回;

31ppt課件S.topS.stacksizeS.base

nn-1i-1i-20anaiai-1a1STACK_INIT_SIZE出棧操作前nn-1i-1i-20S.topS.stacksizeS.baseSTACK_INIT_SIZEanaiai-1a1出棧操作后ane出棧操作圖示32ppt課件鏈棧鏈棧即為棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈棧的結(jié)點(diǎn)結(jié)構(gòu)和單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)相同。由于棧只在棧頂作插入和刪除操作，因此鏈棧中不需要頭結(jié)點(diǎn)，但是鏈棧中指針的方向是從棧頂指向棧底的，這正好和單鏈表是相反的。

33ppt課件鏈棧中結(jié)點(diǎn)的定義：鏈棧結(jié)構(gòu)定義：typedefstructLNode{ElemTypedata;structLNode*next;}*SLink;typedefstruct{SLinktop;//棧頂指針

intlength;//棧中元素個(gè)數(shù)}LStack;34ppt課件鏈棧的基本操作和順序棧操作基本相同，只需修改兩處：１．初始化時(shí)不需要maxsize的參數(shù)２．在進(jìn)行入棧操作時(shí)不需要顧忌棧的空間是否已經(jīng)被填滿(mǎn)。

35ppt課件voidInitStack(LStack&S)

{

//構(gòu)造一個(gè)空棧S

S.top=NULL;

//設(shè)棧頂指針的初值為空

S.length=0;

//空棧中元素個(gè)數(shù)為0

}//InitStack

36ppt課件voidPush(LStack&S,ElemTypee)

{

//在棧頂之上插入元素e為新的棧頂元素

p=(LNode*)malloc(sizeof(LNode);

//建新的結(jié)點(diǎn)

if(!p)exit(1);

//存儲(chǔ)分配失敗

p->data=e;

p->next=S.top;

//鏈接到原來(lái)的棧頂

S.top=p;

//移動(dòng)棧頂指針

++S.length;

//棧的長(zhǎng)度增1

}//Push

^…...棧底toptopxp37ppt課件boolPop(LStack&S,ElemType&e)

{

//若棧不空，則刪除S的棧頂元素，用e返回其值，

//并返回TRUE；否則返回FALSE

if(!S.top)

returnFALSE;

else

{

e=S.top->data;

//返回棧頂元素

q=S.top;

S.top=S.top->next;

//修改棧頂指針

--S.length;

//棧的長(zhǎng)度減1

deleteq;

//釋放被刪除的結(jié)點(diǎn)空間

returnTRUE;

}

}//Poptop^…...棧底topq38ppt課件

小結(jié)

1.棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線(xiàn)性表；2.棧的元素具有后進(jìn)先出的特點(diǎn)；3.棧頂元素的位置由一個(gè)稱(chēng)為棧頂指針的變量表示，進(jìn)棧、出棧操作要修改棧頂指針；39ppt課件§3.2棧的應(yīng)用舉例

NNdiv8Nmod8134816841682102125202輸出順序計(jì)算順序１．?dāng)?shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問(wèn)題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：

N=(Ndivd)×d+Nmodd

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

例如：(1348)10=(2504)8

40ppt課件由上述求解過(guò)程可以看出，在計(jì)算過(guò)程中是從低位到高位順序產(chǎn)生八進(jìn)制數(shù)的各個(gè)數(shù)位，而顯示時(shí)按照我們的習(xí)慣是高位在前，低位在后，即按從高位到低位的順序輸出,即后計(jì)算出的（高）位數(shù)先輸出，具有后進(jìn)先出的特點(diǎn)，因此可將計(jì)算過(guò)程中得到的八進(jìn)制數(shù)順序進(jìn)棧，出棧序列打印輸出的就是對(duì)應(yīng)的八進(jìn)制數(shù)。41ppt課件3）算法voidconversion(){//對(duì)于輸入的任意一個(gè)非負(fù)十//進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)

InitStack(S);//建空棧

scanf(“%d”,N);//輸入一個(gè)非負(fù)十進(jìn)制整數(shù)

while(N){//N不等于零，循環(huán)

Push(S,N%8);//N/8第一個(gè)余數(shù)進(jìn)棧

N=N/8};//整除運(yùn)算while(!StackEmpty){

//輸出存放在棧中的八進(jìn)制數(shù)。

Pop(S,e);

Printf(“%d”,e);}}//conversion42ppt課件2表達(dá)式求值1）表達(dá)式的構(gòu)成操作數(shù)+運(yùn)算符+界符（如括號(hào)）2）表達(dá)式的求值：例5+6(1+2)-4按照四則運(yùn)算法則，上述表達(dá)式的計(jì)算過(guò)程為：5+6(1+2)-4=5+63-4=5+18-4=23-4=19

表達(dá)式中運(yùn)算符的運(yùn)算順序?yàn)椋?，，+，-如何確定運(yùn)算符的運(yùn)算順序？43ppt課件3）算符優(yōu)先關(guān)系表表達(dá)式中任何相鄰運(yùn)算符1、2的優(yōu)先關(guān)系有：

1<2：1的優(yōu)先級(jí)低于2

1=2：1的優(yōu)先級(jí)等于2

1>2：1的優(yōu)先級(jí)高于2

由四則運(yùn)算法則，可得到如下的算符優(yōu)先關(guān)系表：44ppt課件+

θ2θ1-*/()#+-*/()#>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=算符間的優(yōu)先關(guān)系表注：

θ1

θ2是相鄰算符，θ1在左θ2在右45ppt課件4)

算符優(yōu)先算法我們?cè)賮?lái)分析一下表達(dá)式5+4(1+2)-6

計(jì)算過(guò)程：

從左向右掃描表達(dá)式：遇操作數(shù)——保存；遇運(yùn)算符號(hào)j——與前面的剛掃描過(guò)的運(yùn)算符i比較若i<j則保存j，（因此已保存的運(yùn)算符的優(yōu)先關(guān)系為1<2<3<4。。

）

若i>j

則說(shuō)明i是已掃描的運(yùn)算符中優(yōu)先級(jí)最高者，可進(jìn)行運(yùn)算；

若i=j則i為（，j為），說(shuō)明括號(hào)內(nèi)的式子已計(jì)算完，需要消去括號(hào)；5+4(1+2)-6后面也許有優(yōu)先級(jí)更大的算符46ppt課件算法思想：

(1)設(shè)置兩個(gè)棧：運(yùn)算符棧（OPTR)和操作數(shù)棧（OPND)(2)設(shè)置數(shù)據(jù)棧為空棧，表達(dá)式起始符“#”為算符棧的棧底元素。(3)自左向右，依次掃描表達(dá)式中的基本符號(hào)，若掃描的基本符號(hào)為操作數(shù)，則將操作數(shù)入OPND棧。(4)若基本符號(hào)為運(yùn)算符，則和OPTR棧頂元素的優(yōu)先級(jí)比較（棧頂元素為C1,讀到的算符為C2）：（a）c1<c2，c2進(jìn)棧，繼續(xù)掃描后續(xù)符號(hào)。（b）c1=c2，即”(“=“)”,括號(hào)內(nèi)的運(yùn)算已經(jīng)結(jié)束，將c1出棧，放棄c2，繼續(xù)掃描。（c）c1>c2，c1出棧，從OPND棧取出兩個(gè)元素（a和b），按c1進(jìn)行運(yùn)算，并把運(yùn)算結(jié)果放入OPND棧。(5)重復(fù)上述過(guò)程，直到表達(dá)式求值完畢（OPTR棧為空棧）47ppt課件表達(dá)式求值示意圖：5+6(1+2)-4topbaseOPTR棧#OPND棧topbase5toptop+top6top×top(top1top+top2toptoptoptop3toptoptoptoptop18toptoptoptop23top-top4toptoptoptop19toptoptop5讀入表達(dá)式過(guò)程：+6×(1+2)-4#=191+2=36×3=185+18=2323-4=193.4棧的應(yīng)用舉例48ppt課件在算符優(yōu)先算法中，建立了兩個(gè)工作棧。一個(gè)是OPTR棧，用以保存運(yùn)算符,一個(gè)是OPND棧，用以保存操作數(shù)或運(yùn)算結(jié)果。

operandTypeEvaluateExpression(){

//算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OP為運(yùn)算符集合。InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=qetchar();While(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP)){Push(OPND,c);c=getchar()}

//不是運(yùn)算符則進(jìn)棧,In(c,OP)判斷c是否是運(yùn)算符的函數(shù)

else

49ppt課件續(xù)switch(Precede(GetTop(OPTR),c){case<://新輸入的算符c優(yōu)先級(jí)高，c進(jìn)棧Push(OPTR,c);c=getchar();break;case=://脫括號(hào)并接收下一字符Pop(OPTR,x);c=getchar();break;case>://新輸入的算符c優(yōu)先級(jí)低，即棧頂算符優(yōu)先權(quán)

//高,出棧并將運(yùn)算結(jié)果入棧OPNDPop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression50ppt課件3．括弧匹配檢驗(yàn)

假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，如（［］（））或［（［］［］）］等為正確的匹配，［（]）或（［］（）或(())）均為錯(cuò)誤的匹配。

問(wèn)題：如何檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？

解決辦法：用"期待的急迫程度"這個(gè)概念來(lái)描述。

51ppt課件

對(duì)于后出現(xiàn)的左括號(hào),它等待與其匹配的右括號(hào)出現(xiàn)的急迫心情要比先出現(xiàn)的左括號(hào)高,也就是說(shuō),對(duì)左括號(hào)來(lái)說(shuō),后出現(xiàn)的比先出現(xiàn)的優(yōu)先等待檢測(cè).

對(duì)右括號(hào)來(lái)說(shuō),每個(gè)出現(xiàn)的右括號(hào)要去找在它之前最后出現(xiàn)的那個(gè)左括號(hào)去匹配.52ppt課件例如考慮下列括號(hào)序列：

[([][])]

12345678

顯然,必須將先后出現(xiàn)的左括號(hào)依次保存,為了反映這個(gè)優(yōu)先程度,保存左括號(hào)的結(jié)構(gòu)應(yīng)該使用棧

對(duì)于出現(xiàn)的右括號(hào)來(lái)說(shuō),只要棧頂元素相匹配即可.如果棧頂?shù)淖罄ㄌ?hào)正好和它匹配,就可將它從棧頂刪除.53ppt課件什么樣的情況是“不匹配”的情況呢？1．和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?．棧中并沒(méi)有左括弧等在那里；3．棧中還有左括弧沒(méi)有等到和它相匹配的右括弧。54ppt課件Boolmatch(){InitStack(S);//初始化棧

ch=getchar();//接收第一個(gè)括號(hào)

while(ch!=‘#’)//不是結(jié)束符

{if(ch==‘(‘||ch==‘[‘)//左括號(hào)時(shí)進(jìn)棧

{push(S,ch);}//ifelseif(ch==‘)’)//‘)’時(shí)檢測(cè)匹配

{if(!StackEmpty(S)){gettop(S,e);//取棧頂元素

if(e==‘(‘)//匹配成功

{pop(S);}//ifelsereturnfalse;//匹配失敗

}//if}//elseElse//’]’時(shí)檢測(cè)匹配{if(!StackEmpty(S)){gettop(S,e);//取棧頂元素

if(e==‘[‘)//匹配成功

{pop(S);}//ifelsereturnfalse;//匹配失敗

}//if}//elsech=getchar();}//whileIf(!StackEmpty(S))returnfalse;//棧中還有沒(méi)有匹配

//成功的左括號(hào)

elsereturntrue;}//match算法實(shí)現(xiàn)55ppt課件4.迷宮求解問(wèn)題

計(jì)算機(jī)解迷宮時(shí)，通常用的是“窮舉求解”的方法.1．進(jìn)入迷宮之后，不管在迷宮的哪一個(gè)位置上，都先往東走，如果走得通就繼續(xù)往東走，如果在某個(gè)位置上往東走不通的話(huà)，就依次試探往南、往西和往北方向，從一個(gè)走得通的方向繼續(xù)往前直到出口為止；2．如果某個(gè)位置上四個(gè)方向都走不通的話(huà)，就退回到前一個(gè)位置，換一個(gè)方向再試，如果這個(gè)位置已經(jīng)沒(méi)有方向可試了就再退一步，如果所有已經(jīng)走過(guò)的位置的四個(gè)方向都試探過(guò)了，一直退到起始點(diǎn)都沒(méi)有走通，那就說(shuō)明這個(gè)迷宮根本不通；56ppt課件

為了保證在任何位置上都能沿原路退回，需要用一個(gè)“后進(jìn)先出”的結(jié)構(gòu)即棧來(lái)保存從入口到當(dāng)前位置的路徑。并且在走出出口之后，棧中保存的正是一條從入口到出口的路徑。

57ppt課件算法的基本思想是：若當(dāng)前位置“可通”，則納入“當(dāng)前路徑”，并繼續(xù)朝“下一位置”探索；若當(dāng)前位置“不可通”，則應(yīng)順著“來(lái)的方向”退回到“前一通道塊”，然后朝著除“來(lái)向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個(gè)方塊均“不可通”，則應(yīng)從“當(dāng)前路徑”上刪除該通道塊。58ppt課件偽碼算法：設(shè)定當(dāng)前位置的初值為入口位置；

do{

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

則{

將當(dāng)前位置插入棧頂；//納入路徑

若該位置是出口位置，則算法結(jié)束；

否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；

}

否則

{

若棧不空且棧頂位置尚有其他方向未被探索，

則設(shè)定新的當(dāng)前位置為:沿順時(shí)針?lè)较蛐D(zhuǎn)找到的棧頂位置的下一相鄰塊；

若棧不空但棧頂位置的四周均不可通，

則{刪去棧頂位置；//從路徑中刪去該通道塊

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

直至找到一個(gè)可通的相鄰塊或出棧至棧空；

}

}

}while(棧不空)；

沒(méi)有路徑存在59ppt課件3.3棧與遞歸由上看到：應(yīng)用中如果處理數(shù)據(jù)處理過(guò)程具有后進(jìn)先出的特性，可利用棧來(lái)實(shí)現(xiàn)數(shù)據(jù)處理過(guò)程。下面我們將看到可以用棧來(lái)實(shí)現(xiàn)遞歸。1．什么是遞歸遞歸是一個(gè)很有用的工具，在數(shù)學(xué)和程序設(shè)計(jì)等許多領(lǐng)域中都用到了遞歸。遞歸定義：簡(jiǎn)單地說(shuō)，一個(gè)用自己定義自己的概念,稱(chēng)為遞歸定義。例

n!=1234(n-1)nn!遞歸定義n!=1當(dāng)n=0時(shí)n!=n(n-1)!當(dāng)n>0時(shí)用(n-1)!定義n!60ppt課件棧與遞歸2.遞歸函數(shù)：一個(gè)直接調(diào)用自己或通過(guò)一系列調(diào)用間接調(diào)用自己的函數(shù)稱(chēng)為遞歸函數(shù)。

A（

）{

…

A();

…}B(){C(){

…

…

C();B();

…

…

}}A直接調(diào)用自己B間接調(diào)用自己61ppt課件棧與遞歸遞歸是程序設(shè)計(jì)中的有用工具，下面舉例說(shuō)明遞歸算法的編寫(xiě)和執(zhí)行過(guò)程。2．遞歸算法的編寫(xiě)1）將問(wèn)題用遞歸的方式描述（定義）2）根據(jù)問(wèn)題的遞歸描述（定義）編寫(xiě)遞歸算法

問(wèn)題的遞歸描述（定義）遞歸定義包括兩項(xiàng)

基本項(xiàng)（終止項(xiàng)）：描述遞歸終止時(shí)問(wèn)題的求解；

遞歸項(xiàng)：將問(wèn)題分解為與原問(wèn)題性質(zhì)相同，但規(guī)模較小的問(wèn)題；

62ppt課件棧與遞歸例1

編寫(xiě)求解階乘n!

的遞歸算法首先給出階乘n!

的遞歸定義

n!的遞歸定義基本項(xiàng)：n!=1當(dāng)n=1遞歸項(xiàng)：n!=n(n-1)!

當(dāng)n>1有了問(wèn)題的遞歸定義，很容易寫(xiě)出對(duì)應(yīng)的遞歸算法：intfact(intn){//算法功能是求解并返回n的階乘If（n=1）return（1）；Elsereturn（n*fact(n-1)）；}//fact

63ppt課件棧與遞歸例2.編寫(xiě)求解Hanoi塔問(wèn)題的遞歸算法有三個(gè)各為X，Y，Z的塔座，在X項(xiàng)有n個(gè)大小不同，依小到大編號(hào)為1，2…n的圓盤(pán)。

現(xiàn)要求將X上的n個(gè)圓盤(pán)移至Z上，并仍以同樣順序疊放，

圓盤(pán)移動(dòng)時(shí)必須遵守下列原則：1）每次移動(dòng)一個(gè)盤(pán)子；2）圓盤(pán)可以放在X，Y，Z中的任一塔座上；3）任何時(shí)刻都不能將較大的圓盤(pán)壓放在較小圓盤(pán)之上；例

n=3時(shí)圓盤(pán)移動(dòng)的過(guò)程如下圖所示：64ppt課件abc32111213121棧與遞歸YXZ65ppt課件棧與遞歸首先給出求解Hanoi塔問(wèn)題

的遞歸描述（定義）

基本項(xiàng)：n=1時(shí)，將n號(hào)圓盤(pán)從X移至Z；遞歸項(xiàng)：n>1時(shí)，將X上1——n-1號(hào)圓盤(pán)移至Y；將X上的n號(hào)圓盤(pán)從X移至Z;將Y上1——n-1號(hào)圓盤(pán)從Y移至Z;

將規(guī)模為n的問(wèn)題的求解歸結(jié)為規(guī)模為n-1的問(wèn)題的求解有了問(wèn)題的遞歸定義，很容易寫(xiě)出對(duì)應(yīng)的遞歸算法：66ppt課件voidhanoi(intn,charx,chary,charz)//將塔座x上按直徑由小到大且自上而下編號(hào)為1至n的n個(gè)圓盤(pán)按規(guī)則搬到塔座z上，y可用作輔助塔座。{

if(n==1)

move(x,1,z);//將編號(hào)為1的圓盤(pán)從x移動(dòng)z

else{

hanoi(n-1,x,z,y);//將x上編號(hào)為1至n-1的圓盤(pán)移到y(tǒng),z作輔助塔

move(x,n,z);//將編號(hào)為n的圓盤(pán)從x移到z

hanoi(n-1,y,x,z)；

//將y上編號(hào)為1至n-1的圓盤(pán)移到z，x作輔助塔

}

}

67ppt課件棧與遞歸3遞歸函數(shù)的實(shí)現(xiàn)先看一般函數(shù)的調(diào)用機(jī)制如何實(shí)現(xiàn)的。

A(){…B();…}C(){……}B(){…C();…}調(diào)用調(diào)用返回返回函數(shù)調(diào)用順序ABC函數(shù)返回順序CBA后調(diào)用的函數(shù)先返回

函數(shù)調(diào)用機(jī)制可通過(guò)棧來(lái)實(shí)現(xiàn)計(jì)算機(jī)正是利用棧來(lái)實(shí)現(xiàn)函數(shù)的調(diào)用和返回的68ppt課件棧與遞歸我們看一下n=3階乘函數(shù)fact(n)的執(zhí)行過(guò)程Main(){intn=3,y;Ly=fact(n);}調(diào)用調(diào)用調(diào)用intfact(n){

If（n=1）return（1）；ElseL1return（n*fact(n-1)）；}//factn=3intfact(intn){

If（n=1）return（1）；ElseL1return（n*fact(n-1)）；}//factn=2intfact(intn){

If（n=1）return（1）；ElseL1return（n*fact(n-1)）；}//factn=1L3L11L12返回1返回2返回61n*fact(n-1)n*fact(n-1)fact(n)返回地址實(shí)參

注意遞歸調(diào)用中棧的變化69ppt課件2、隊(duì)列的特點(diǎn)：由于限制了插入、刪除分別在兩端進(jìn)行，那么元素的操作順序有“先進(jìn)先出”或“后進(jìn)后出”的特點(diǎn)（FirstInFirstOut--FIFOLastInLastOut--LILO）1、隊(duì)列（Queue)：是一種特殊的線(xiàn)性表(數(shù)據(jù)元之間的關(guān)系是線(xiàn)性關(guān)系.其插入、刪除分別在表的兩端進(jìn)行，一端只能插入、另一端只能刪除。)隊(duì)首（front)：進(jìn)行刪除的一端；隊(duì)尾（rear)：進(jìn)行插入的一端；入隊(duì)：在隊(duì)尾插入一個(gè)元素；出隊(duì)：在隊(duì)首刪除一個(gè)元素；§3.4隊(duì)列3.4.1抽象數(shù)據(jù)類(lèi)型隊(duì)列的定義70ppt課件

a1a2a3an入隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)列隊(duì)列的示意圖隊(duì)列的特點(diǎn)先進(jìn)先出第一個(gè)入隊(duì)的元素在隊(duì)頭，

最后一個(gè)入隊(duì)的元素在隊(duì)尾，第一個(gè)出隊(duì)的元素為隊(duì)頭元素，最后一個(gè)出隊(duì)的元素為隊(duì)尾元素隊(duì)列類(lèi)似于日常的排隊(duì)，新來(lái)的人站在隊(duì)尾，隊(duì)頭的人進(jìn)行事務(wù)處理后離隊(duì)。隊(duì)列通常設(shè)置兩個(gè)變量分別指示隊(duì)頭元素位置和隊(duì)尾元素的位置，這兩個(gè)變量分別稱(chēng)為隊(duì)頭指針、隊(duì)尾指針；71ppt課件2.隊(duì)列的基本操作1）初始化操作InitQueue(&Q)

功能：構(gòu)造一個(gè)空隊(duì)列Q；

2）銷(xiāo)毀操作DestroyQueue(&Q)

功能：銷(xiāo)毀已存在隊(duì)列Q；

3）置空操作ClearQueue(&Q)功能：將隊(duì)列Q置為空隊(duì)列；4）判空操作QueueEmpty(Q)功能：若隊(duì)列Q為空，則返回True，否則返回False；72ppt課件5）取隊(duì)頭元素操作GetHead(Q,&e)

功能：取隊(duì)頭元素，并用e返回；

6）入隊(duì)操作EnQueue(&Q,e)

功能：將元素e插入Q的隊(duì)尾；

7）出隊(duì)操作DeQueue(&Q,&e)

功能：若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用e返回其值，并返回OK，否則返回ERROR；73ppt課件隊(duì)列的抽象數(shù)據(jù)類(lèi)型定義：

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ì)列尾

74ppt課件基本操作：

InitQueue(&Q) DestroyQueue(&Q) ClearQueue(&Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q,&e) EnQueue(&Q,e) DeQueue(&Q,&e) QueueTraverse(Q,visit())}ADTQueue75ppt課件3.隊(duì)列ADT應(yīng)用舉例打印機(jī)隊(duì)列管理：在一臺(tái)打印機(jī)共享使用時(shí)，任何時(shí)刻它只能處理一個(gè)用戶(hù)的打印請(qǐng)求。打印任務(wù)的組織就用一個(gè)隊(duì)列來(lái)組織（先請(qǐng)求的，先處理）。當(dāng)用戶(hù)發(fā)出打印請(qǐng)求時(shí)，把打印任務(wù)入隊(duì)；當(dāng)打印機(jī)空閑時(shí)，從打印隊(duì)列中出隊(duì)一個(gè)任務(wù)；當(dāng)打印機(jī)阻塞時(shí),系統(tǒng)管理員可以清空隊(duì)列.76ppt課件1、存儲(chǔ)方式：同一般線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)完全相同。但是由于在兩端操作，設(shè)兩個(gè)指示器，(rear和front）分別指示隊(duì)列的尾和首。特別約定:頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一位置！空隊(duì)列：rear=front=0入隊(duì)：rear=rear+1出隊(duì)：front=front+1隊(duì)列空：front=rear3.4.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)77ppt課件特點(diǎn):簡(jiǎn)單,方便,但是易產(chǎn)生假溢出.78ppt課件只是稱(chēng)為指針，實(shí)現(xiàn)時(shí)不一定用指針變量79ppt課件2.隊(duì)列的簡(jiǎn)單操作的實(shí)現(xiàn)(1）初始化Q.front=Q.rear=0;(2）入隊(duì)Q.base[Q.rear]＝e;Q.rear++;(3）出隊(duì)Q.front++;(4）判空Q.front==Q.rear;(5）求隊(duì)長(zhǎng)Q.rear-Q.front80ppt課件思考：順序隊(duì)列存在的問(wèn)題及解決方案

可以看出：當(dāng)入隊(duì)一個(gè)元素時(shí)，可能會(huì)出現(xiàn)假溢出現(xiàn)象.即：空間并沒(méi)有使用完，但不能入隊(duì)！解決的辦法：(1）平移，一旦發(fā)生假溢出，把隊(duì)列中所有元素移到隊(duì)列開(kāi)頭．效率低．

(2）使用動(dòng)態(tài)數(shù)組，當(dāng)產(chǎn)生假溢出或真溢出時(shí)，都重新分配一個(gè)更大的空間．（不可取）(3）使用環(huán)數(shù)組，即將順序存儲(chǔ)的空間視為一個(gè)環(huán)空間。81ppt課件3.4.3循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)

方式：將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，如圖所示，稱(chēng)之為循環(huán)隊(duì)列.指針和隊(duì)列元素之間的關(guān)系不變這種循環(huán)的圈只是一種邏輯上的圈,在物理上還是一組連續(xù)的存儲(chǔ)單元,仍可利用數(shù)組實(shí)現(xiàn).82ppt課件1.存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)

循環(huán)隊(duì)列可充分利用空間，但仍存在問(wèn)題：我們知道：隊(duì)列為空時(shí)front=rear右圖中，繼續(xù)入隊(duì)a7,a8，則front=rear即：隊(duì)列為空或隊(duì)列為滿(mǎn)時(shí)，都是front=rear，如何區(qū)分？83ppt課件兩種方法1.設(shè)置標(biāo)志位以區(qū)別隊(duì)列是“空”還是“滿(mǎn)”因出隊(duì)而相等，則為空；因入隊(duì)而相等，則為滿(mǎn)；2.少用一個(gè)元素的空間，約定rear+1=front時(shí)，就認(rèn)為隊(duì)滿(mǎn)．84ppt課件2.循環(huán)隊(duì)列存儲(chǔ)結(jié)構(gòu)及操作實(shí)現(xiàn)

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

typedefstruct{

QElemType*base;//初始化時(shí)動(dòng)態(tài)分配//存儲(chǔ)空間的基址

intfront;//隊(duì)頭指針，指向隊(duì)頭元素

intrear;//隊(duì)尾指針，指向隊(duì)尾元素的下//一個(gè)位置}SqQueue;85ppt課件

1）初始化操作InitQueue_Sq(SqQueue&Q)

參數(shù)：Q是存放隊(duì)列的結(jié)構(gòu)變量；功能：建一個(gè)空隊(duì)列Q；

循環(huán)隊(duì)列的基本操作算法Q.frontQ.rear540312建一個(gè)空隊(duì)列Q86ppt課件StatusInitQueue_Sq(SqQueue&Q){

//構(gòu)造一個(gè)空隊(duì)列QQ.base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!Q.base)exit(OVERFLOW);

//存儲(chǔ)分配失敗

Q.front=Q.rear=0;(什么意思？)

ReturnOK;

}//InitQueue_Sq算法：87ppt課件2)入隊(duì)操作EnQueue_Sq(SqQueue&Q,QElemTypee)

功能：將元素e插入隊(duì)尾；入隊(duì)操作主要步驟：1）Q是否已滿(mǎn)，若滿(mǎn)，返回ERROR；否則轉(zhuǎn)2）；2）將元素e寫(xiě)入隊(duì)尾；3）修改隊(duì)尾指針，使隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置；Q.frontQ.rear540312J1J3J2eQ.frontQ.rear540312J1J3J2元素e入隊(duì)前元素e入隊(duì)后88ppt課件StatusEnQueue_Sq(SqQueue&Q,QElemTypee)

//將元素e插入隊(duì)尾

if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;

Q.base[Q.rear]=e;//將元素e插入隊(duì)尾Q.rear=(Q.rear+1)%MAXSIZE;

//修改隊(duì)尾指針

returnOK;}//EnQueue_Sq入隊(duì)操作算法

89ppt課件3)出隊(duì)操作DeQueue_Sq(SqQueue&Q,QElemType&e)功能：刪除隊(duì)頭元素，用e返回其值;出隊(duì)操作主要步驟：1）Q是否為空，若空，返回ERROR；否則轉(zhuǎn)2）；2）將隊(duì)頭元素賦值給e；3）修改隊(duì)頭指針，刪除隊(duì)頭元素；Q.frontQ.rear540312J1J3J2Q.frontQ.rear540312J1J3J2出隊(duì)操作前出隊(duì)操作后eJ190ppt課件StatusDeQueue_Sq(SqQueue&Q,QElemType&e)

//刪除隊(duì)頭元素，用e返回其值,并返回OK；否

//則返回ERROR

if((Q.rear==Q.front)returnERROR;

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;//修改隊(duì)頭指針

returnOK;

}//EnQueue_Sq出隊(duì)操作算法

91ppt課件§3.4.4鏈?zhǔn)疥?duì)列的表示和實(shí)現(xiàn)1、存儲(chǔ)方式：同一般線(xiàn)性表的單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)完全相同。但是由于插入、刪除在兩端進(jìn)行，需要兩個(gè)指針front、rear分別指向隊(duì)列的兩端。有兩種不同的鏈法：哪個(gè)好?92ppt課件入隊(duì)都很容易，但是出隊(duì)差別很大！!

應(yīng)該用第1種鏈法。為了處理空隊(duì)列，可以加上頭結(jié)點(diǎn)。2、特點(diǎn)：沒(méi)有假溢出，提高了空間利用率。只有系統(tǒng)沒(méi)有空間了，才會(huì)溢出；93ppt課件2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。頭結(jié)點(diǎn)^…...front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾94ppt課件frontrearx入隊(duì)^xfrontreary入隊(duì)x^yfrontrearx出隊(duì)x^yfrontrear空隊(duì)^frontreary出隊(duì)^95ppt課