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

第三章棧和隊列

第三章棧和隊列

3.1棧

3.2棧的應(yīng)用舉例

3.3棧與遞歸

3.4隊列

3.5隊列的應(yīng)用3.1棧3.1.1棧的概念

3.1.2棧的順序存儲和實現(xiàn)

3.1.3棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)

3.1.1棧的概念棧是限定僅能在表尾一端進(jìn)行插入、刪除操作的線性表；（a1,a2,...ai,…,an-1,an

）插入刪除ana2a1棧的特點后進(jìn)先出又稱為后進(jìn)先出表（LIFO表Last_inFirst_out)出棧進(jìn)棧棧頂棧底ana2a13.1.1棧的概念棧的應(yīng)用火車調(diào)度123基本操作初始化操作InitStack(&S)

功能：構(gòu)造一個空棧S。銷毀棧操作DestroyStack(&S)

功能：銷毀一個已存在的棧。置空棧操作ClearStack(&S)

功能：將棧S置為空棧。判空操作StackEmpty(S)

功能：若棧S為空，則返回True，否則，棧不空返回False。ana2a1棧頂棧底

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

功能：取棧頂元素，并用e返回。

進(jìn)棧操作Push(&S,e)

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

退棧操作Pop(&S,&e)

功能：棧頂元素退棧，并用e返回。ana2a1棧頂棧底3.1.2棧的順序存儲和實現(xiàn)出棧進(jìn)棧棧頂棧底ana2a1

順序棧的類型定義#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{

ElemType*base;//動態(tài)數(shù)組基址

intstacksize;//?？臻g大小

}SqStack;SqStackS;ElemType*top//棧頂指針出棧進(jìn)棧棧頂棧底ana2a1S.stacksizeS.topS.base

an

an-1a2a110099 n-110topbaseaabcdab空棧

a進(jìn)棧

b,c,d進(jìn)棧d,c出棧topbasetopbasetopbase

順序棧的基本操作算法

約定：棧頂指針示棧頂元素的下一個位置

初始化操作InitStack(&S)功能：建空棧S.stacksizeS.topS.base100

99 n-110StatusInitList_Sq(SqStack&S){//建立空順序棧S

S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

//為順序棧動態(tài)分配存儲空間

if(!S.base)exit(OVERFLOW);//分配失敗

S.top=S.base;//棧頂指針初始化

S.stacksize=STACK_INIT_SIZE;returnOK;}//InitList_Sq

算法時間復(fù)雜度：O(1)S.stacksizeS.topS.base

an

an-1a2a110099 n-1100

銷毀棧操作DestroyStack(&S)

功能：銷毀一個已存在的棧NULLNULLStatusDestroyStack(SqStack&S){//銷毀一個已存在的棧

free(S.base);

//釋放棧空間

S.base=S.top=NULL;

S.stacksize=0;

returnOK;}//DestroyStack

置空操作ClearStack(&S)功能：將已存在的棧S，置成空棧99 n-110S.stacksizeS.topS.base

an

an-1a2a110099 n-110S.stacksizeS.topS.base

an

an-1a2a1100置空StatusDestroyStack(SqStack&S){//銷毀一個已存在的棧

S.top=NULL;

//釋放?？臻g

returnOK;}//DestroyStack

進(jìn)棧操作

Push(&S,e)

e進(jìn)棧前e進(jìn)棧后功能：將元素e壓入棧頂S

an

an-1a2a1100

99 n-110S

ean

an-1a2a1100

99 n-110*S.top=e;S.top++;StatusPush(SqStack&S,ElemTypee){

//將元素e插入棧頂

*S.top=e;S.top++;

//元素e插入棧頂，修改棧頂指針

returnOK;

}//Pushif(S.top-S.base==S.stacksize)//棧滿

{newbase=(ElemType*)realloc(S.base,

(S.stacksize+STACKINCREMENT)*sizeof(ElemType));

if(!newbase)exit(OVERFLOW);S.base=newbase;S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}//if

出棧操作

Pop(&S,&e)功能：棧頂元素退棧，并用e返回。出棧操作前出棧操作后eanS

an

an-1a2a110099 n-110S

an

an-1a2a110099 n-110--S.top;e=*S.top;StatusPop(SqStack&S,ElemType&e){//刪除棧頂元素，并用e返回其值

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

--S.top;e=*S.top;

//讀取棧頂元素，修改棧頂指針

returnOK;

}//PopS

an

an-1a2a110099 n-1103.1.3棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)Sanan-1a1棧底棧頂typedefstructLNode{

ElemTypedata;

StructSNode*next;

}SNode,*SLinkList;SLinkListS；

//S棧頂指針3.1.3棧的鏈?zhǔn)酱鎯蛯崿F(xiàn)出棧e棧頂Sanan-1a1棧底e入棧棧頂Sanan-1a1棧底順序棧和鏈?zhǔn)綏５谋容^棧的特點：后進(jìn)先出時間效率所有操作都時間復(fù)雜度都是O(1)順序棧和鏈?zhǔn)綏Ｔ跁r間效率上難分伯仲空間效率順序棧須說明一個固定的長度鏈?zhǔn)綏５拈L度可變，但增加結(jié)構(gòu)性開銷

3.2棧的應(yīng)用舉例迷宮求解——搜索(深度優(yōu)先)行編輯程序表達(dá)式括號匹配的檢驗表達(dá)式求值實現(xiàn)遞歸其它退棧進(jìn)棧棧頂棧底ana2a1

數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)到八進(jìn)制數(shù)的轉(zhuǎn)換算法基于下面整數(shù)性質(zhì)

N=(Ndivd)×d+

Nmodd43=5×8+3

例(1348)10=(2504)8

，其運算過程如下:=2×83+5×82+0×8+4

=(2504)8

=(21×8+0)×8+4

=(2×8+5)×8+0)×8+4

=168×8+41348=(1348div8)×8+1348mod8

voidconversion(){//輸入一個非負(fù)十進(jìn)制數(shù)，輸出八進(jìn)制數(shù)

InitStack(S);//建空棧

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

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

Push(S,N%8);//余數(shù)進(jìn)棧

N=N/8;//整除運算,N=商

}

while(!StackEmpty){//輸出棧中的八制數(shù)位

Pop(S,e);Printf(“%d”,e);

}

DestroyStack(S);//釋放棧空間

}//conversion

迷宮問題輸入數(shù)據(jù)：迷宮結(jié)果數(shù)據(jù)：從入口到出口的一條路徑入口出口1234入口出口1234迷宮問題迷宮問題求解迷宮問題的基本步驟若當(dāng)前位置“可通”,則納入路徑,繼續(xù)探索；若當(dāng)前位置“不可通”,換個方向繼續(xù)探索；若四周“均已探索”，則后退一步,換個方向繼續(xù)探索;入口出口1234括號匹配問題在表達(dá)式中，正確的格式（［］（））［（［］［］）］在表達(dá)式中,不正確的格式：［（］）（））（（）main(){…x=2;y=3;

z=x*x+y*y;}表達(dá)式求值-算符優(yōu)先算法表達(dá)式的構(gòu)成

表達(dá)式::=操作數(shù)+運算符+界符5+6(1+2)–4212355+6(1+2)–42表達(dá)式的求值

(數(shù)學(xué)上)4=5+63-42=5+18-42=23-42=23-8=151）確定表達(dá)式中算符運算順序

2）按照算符的運算順序進(jìn)行計算算符優(yōu)先關(guān)系表(1、2是相鄰算符,1

左,2右)

1、2的優(yōu)先關(guān)系有：1<2

1=2

1>22

1

+-*/()#>><<<>>>

><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=+-*/()##5+6(1+2)-42#表達(dá)式求值基本思路+(

從左向右掃描表達(dá)式:#5+6(1+2)-42

?

遇操作數(shù)——保存

?

遇運算符j

——與左運算符i比較

–若i<j

則保存

–若i>j

則i可進(jìn)行運算；

–若i=j

需要消去括號；5612+<<<#<>后保存運算符優(yōu)先級高OPTR棧#OPND棧5+6×(1+25

讀入表達(dá)式：+6×(1+2)-4#1+2=36×3=185+18=2323-8=15表達(dá)式求值示意圖（算符優(yōu)先算法）1823-15×24×2=84×832

算符優(yōu)先算法OperandTypeEvaluateExpression(){//算術(shù)表達(dá)式求值的算符優(yōu)先算法。設(shè)OPTR和OPND分別為運算符棧和操作數(shù)棧，OP為運算符集合。

InitStack(OPTR);Push(OPTR,#);InitStack(OPND);c=getchar();//讀入算術(shù)表達(dá)式

while(c!=‘#’||GetTop(OPTR)!=‘#’){if(!In(c,OP))//若為操作數(shù)進(jìn)棧OPND{Push(OPND,c);c=getchar()}else{//若為運算符

switch(Precede(GetTop(OPTR),c)){case<://運算符進(jìn)棧并接收下一字符

Push(OPTR,c);c=getchar();break;case=://脫括號并接收下一字符

Pop(OPTR,x);c=getchar();break;case>:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch}//if}//whilereturnGetTop(OPND);}//EvaluateExpression

中綴表達(dá)式5+6(1+2)–425612++42

-1234

后綴表達(dá)式

前綴表達(dá)式-+56+12421234

表達(dá)式的三種表達(dá)方式55例求解n!的遞歸函數(shù)

intfact(intn){if(n==1)return1;elsereturn(n*fact(n-1));}3.3棧與遞歸A(){…A();…}遞歸函數(shù)遞歸函數(shù)的執(zhí)行過程中棧的作用函數(shù)的調(diào)用數(shù)據(jù)傳遞控制轉(zhuǎn)移main(){intn=3;f(n);}intf(intn){r=1;for(i=1;i<=n;i++)

r=r*i;return(r);}調(diào)用返回遞歸函數(shù)的執(zhí)行過程中棧的作用主調(diào)函數(shù)時涉及的數(shù)據(jù)函數(shù)實參返回地址被調(diào)函數(shù)涉及的數(shù)據(jù)函數(shù)形參局部變量函數(shù)返回值函數(shù)數(shù)據(jù)區(qū)參數(shù)返回地址等局部變量遞歸函數(shù)的執(zhí)行過程中棧的作用(被調(diào))函數(shù)數(shù)據(jù)區(qū)的分配對于非遞歸函數(shù)，數(shù)據(jù)區(qū)的分配可以在程序運行前進(jìn)行，直到整個程序運行結(jié)束才釋放，這種分配稱為靜態(tài)分配。內(nèi)存代碼區(qū)域全程/靜態(tài)區(qū)域動態(tài)區(qū)域intf(intn){r=1;for(i=1;i<=n;i++)

r=r*i;return(r);}main(){intn=3;f(n);}main(){intn=3;fact(n);}intfact(intn){if(n==1)return(1);

elsereturn(n*fact(n-1));}調(diào)用n=3返回intfact(intn){if(n==1)return(1);

elsereturn(n*fact(n-1));}調(diào)用n=2返回參數(shù)返回地址等局部變量遞歸函數(shù)的執(zhí)行過程中棧的作用函數(shù)數(shù)據(jù)區(qū)的分配對于遞歸函數(shù)，必須每調(diào)用一次就分配一塊新的數(shù)據(jù)區(qū)，以存放當(dāng)前函數(shù)所使用的數(shù)據(jù)，當(dāng)函數(shù)結(jié)束返回時隨即釋放。即所謂的動態(tài)分配。代碼區(qū)域全程/靜態(tài)區(qū)域動態(tài)區(qū)域內(nèi)存

函數(shù)返回順序main()fac