第三章棧和隊(duì)列

第三章棧和隊(duì)列13.1棧的類型定義3.2棧的應(yīng)用舉例3.3棧類型的實(shí)現(xiàn)3.4隊(duì)列的類型定義3.5隊(duì)列類型的實(shí)現(xiàn)2通常稱，棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。線性表?xiàng)ｊ?duì)列ListInsert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1ListDelete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊(duì)列是兩種常用的數(shù)據(jù)類型33.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端為棧底。基本操作：

}ADTStack4InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())5

InitStack(&S)

操作結(jié)果：構(gòu)造一個(gè)空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結(jié)果：棧S被銷毀。6

StackEmpty(S)

初始條件：棧S已存在。

操作結(jié)果：若棧S為空棧，

則返回TRUE，否則FALE。7

StackLength(S)

初始條件：棧S已存在。

操作結(jié)果：返回S的元素個(gè)數(shù)， 即棧的長度。8

GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：用e返回S的棧頂元素。a1a2an……9

ClearStack(&S)

初始條件：棧S已存在。

操作結(jié)果：將S清為空棧。10Push(&S,e)

初始條件：棧S已存在。

操作結(jié)果：插入元素e為新的棧 頂元素。a1a2ane……11Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結(jié)果：刪除S的棧頂元素， 并用e返回其值。a1a2anan-1

……123.2棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)例三、行編輯程序問題例四、表達(dá)式求值例五、實(shí)現(xiàn)遞歸13

例一、數(shù)制轉(zhuǎn)換

算法基于原理：

N=(Ndivd)×d+Nmodd

14例如：（1348)10=(2504)8，其運(yùn)算過程如下：

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序15voidconversion(){InitStack(S);

scanf("%d",N);

while(N){

Push(S,N%8);N=N/8;

}

while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}}//conversion16例二、括號(hào)匹配的檢驗(yàn)則檢驗(yàn)括號(hào)是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。假設(shè)在表達(dá)式中（［］（））或［（［］［］）］等為正確的格式。例如：考慮下列括號(hào)序列：[([][])]1234567817分析可能出現(xiàn)的不匹配的情況:到來的右括弧非是所“期待”的;到來的是“不速之客”;直到結(jié)束，也沒有到來所“期待”的括弧;［（］）或(()])或（［（））均為不正確的格式。18算法的設(shè)計(jì)思想：1）凡出現(xiàn)左括弧，則進(jìn)棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空若?？?，則表明該“右括弧”多余否則和棧頂元素比較，若相匹配，則“左括弧出?！狈駝t表明不匹配3）表達(dá)式檢驗(yàn)結(jié)束時(shí)，若?？?，則表明表達(dá)式中匹配正確否則表明“左括弧”有余19Statusmatching(string&exp){

intstate=1;

while(i<=Length(exp)&&state){

switchofexp[i]{

case

左括弧:{Push(S,exp[i]);i++;break;}

case”)”:{

if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}

else{state=0;}

break;}……}

if(StackEmpty(S)&&state)returnOK;…...20例三、行編輯程序問題如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲(chǔ)器”?

并不恰當(dāng)！21設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū);并約定“#”為退格符，“@”為退行符。在用戶輸入一行的過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。合理的作法是：22假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)則實(shí)際有效的是：

while(*s)outcha@putchar(*s=#++);putchar(*s++);23

while(ch!=EOF&&ch!='\n'){

switch(ch){

case'#':Pop(S,c);break;

case'@':ClearStack(S);break;//重置S為空棧

default

:Push(S,ch);break;

}ch=getchar();//從終端接收下一個(gè)字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();while(ch!=EOF){//EOF為全文結(jié)束符將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū)；24限于二元運(yùn)算符的表達(dá)式定義:

表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))操作數(shù)::=簡單變量|表達(dá)式簡單變量::=標(biāo)識(shí)符|無符號(hào)整數(shù)例四、表達(dá)式求值25

表達(dá)式的三種標(biāo)識(shí)方法：設(shè)

Exp=S1+

OP

+S2則稱

OP

+S1+S2為前綴表示法

S1+

OP

+S2為中綴表示法

S1+S2+

OP為后綴表示法

26例如:Exp=ab

+

(cd/e)f前綴式:+

ab

c/def中綴式:ab

+

cd/ef后綴式:ab

cde/f

+結(jié)論:1）操作數(shù)之間的相對次序不變;2）運(yùn)算符的相對次序不同;3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;4)前綴式的運(yùn)算規(guī)則為:連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;5)后綴式的運(yùn)算規(guī)則為:

運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)運(yùn)算符和在它之前出現(xiàn)

且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;27如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：abcde/f+abd/ec-d/e(c-d/e)f28abc×d－ef/+×abbaa×bcdeedd/ed/ecc-d/effc-d/e（c-d/e）×f如何從后綴式求值？29如何從原表達(dá)式求得后綴式？

每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定，在后綴式中,優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符。分析“原表達(dá)式”和“后綴式”中的運(yùn)算符:原表達(dá)式:a+b

cd/e

f后綴式:abc+de/f

30a×b+(－c/d×e)f后綴式棧#×+(－/×ab×cde/－f#×+31從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立暫存運(yùn)算符的棧;2)設(shè)表達(dá)式的結(jié)束符為“#”,

預(yù)設(shè)運(yùn)算符棧的棧底為“#”3)若當(dāng)前字符是操作數(shù)，則直接發(fā)送給后綴式;324)若當(dāng)前運(yùn)算符的優(yōu)先數(shù)高于棧頂運(yùn)算符，則進(jìn)棧;5)否則，退出棧頂運(yùn)算符發(fā)送給后綴式;

6)“(”對它之前后的運(yùn)算符起隔離作用，“)”可視為自相應(yīng)左括弧開始的表達(dá)式的結(jié)束符。從原表達(dá)式求得后綴式的規(guī)律為：33voidtransform(charsuffix[],charexp[]){InitStack(S);Push(S,#);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))Pass(Suffix,ch);else{}

if(ch!=#){p++;ch=*p;}else{Pop(S,ch);Pass(Suffix,ch);}

}//while}//CrtExptree……34switch(ch){

case

(

:Push(S,ch);break;

case

)

:

Pop(S,c);

while(c!=

()

{Pass(Suffix,c);Pop(S,c)}

break;

defult:while(Gettop(S,c)&&(precede(c,ch)))

{Pass(Suffix,c);Pop(S,c);}

if(ch!=

#)Push(S,ch);

break;

}

//switch35例六、實(shí)現(xiàn)遞歸將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存;為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū);將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。當(dāng)在一個(gè)函數(shù)的運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行該被調(diào)用函數(shù)之前，

需先完成三項(xiàng)任務(wù)：36保存被調(diào)函數(shù)的計(jì)算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項(xiàng)任務(wù)：37多個(gè)函數(shù)嵌套調(diào)用的規(guī)則是:此時(shí)的內(nèi)存管理實(shí)行“棧式管理”后調(diào)用先返回！例如：voidmain(){voida(…){voidb(…){

………a(…);b(…);

……}//main}//a}//bMain的數(shù)據(jù)區(qū)函數(shù)a的數(shù)據(jù)區(qū)函數(shù)b的數(shù)據(jù)區(qū)38遞歸工作棧：遞歸過程執(zhí)行過程中占用的數(shù)據(jù)區(qū)。遞歸工作記錄：每一層的遞歸參數(shù)合成一個(gè)記錄。當(dāng)前活動(dòng)記錄：棧頂記錄指示當(dāng)前層的執(zhí)行情況。當(dāng)前環(huán)境指針：遞歸工作棧的棧頂指針。遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用。39voidhanoi(intn,charx,chary,charz){//將塔座x上按直徑由小到大且至上而下編號(hào)為1至n//的n個(gè)圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1if(n==1)2move(x,1,z);//將編號(hào)為１的圓盤從x移到z3else{4hanoi(n-1,x,z,y);//將x上編號(hào)為１至n-1的//圓盤移到y(tǒng),z作輔助塔5move(x,n,z);//將編號(hào)為n的圓盤從x移到z6hanoi(n-1,y,x,z);//將y上編號(hào)為１至n-1的//圓盤移到z,x作輔助塔7}8}P55403.2棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號(hào)匹配的檢驗(yàn)例三、行編輯程序問題例四、表達(dá)式求值例五、實(shí)現(xiàn)遞歸413.3 棧類型的實(shí)現(xiàn)順序棧鏈棧42//-----棧的順序存儲(chǔ)表示-----

#defineSTACK_INIT_SIZE100;

typedefstruct{

SElemType

*base;

SElemType

*top;

intstacksize;

}

SqStack;類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。43baseStacksizetopTop=base空棧atopbctop棧top44

StatusInitStack(SqStack&S,intmaxsize){

//構(gòu)造一個(gè)最大空間為maxsize的空順序棧SS.base=new

ElemType[maxsize];

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

S.top=S.base;S.stacksize=maxsize;

returnOK;}45

StatusPush(SqStack&S,SElemTypee){//若棧不滿，則將e插入棧頂if(S.top-S.base>=S.stacksize)

//棧滿

returnOVERFLOW;*S.top++=e;

returnOK;}46StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，//用e返回其值，并返回OK；//否則返回ERROR

if

(S.top

==

S.base)

returnERROR;

e=*--S.top;

returnOK;}47棧頂指針鏈?！腶1an注意:鏈棧中指針的方向an-1棧底元素48

習(xí)題設(shè)將整數(shù)1、2、3、4依次進(jìn)棧，但只要出棧時(shí)棧非空，則可將出棧操作按任何次序夾入其中，請回答下有問題：（1）若入棧出棧次序?yàn)閜ush(1)，pop()，push(2)，push(3)，pop()，pop()，push(4)，pop()，則出棧的數(shù)字序列為什么？（2）請分析1、2、3、4的24種排列中，哪些序列可以通過相應(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端為隊(duì)列頭，an端為隊(duì)列尾基本操作：3.4隊(duì)列的類型定義}

ADTQueue50隊(duì)列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)51InitQueue(&Q)

操作結(jié)果：構(gòu)造一個(gè)空隊(duì)列Q。

DestroyQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：隊(duì)列Q被銷毀，

不再存在。52QueueEmpty(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：若Q為空隊(duì)列，則 返回TRUE，否則 返回FALSE。53

QueueLength(Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：返回Q的元素個(gè)數(shù)， 即隊(duì)列的長度。54

GetHead(Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：用e返回Q的隊(duì) 頭元素。a1a2an……55

DeQueue(&Q,&e)

初始條件：Q為非空隊(duì)列。

操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。a1a2an……

56

EnQueue(&Q,e)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊(duì)尾元素。a1a2ane……57

ClearQueue(&Q)

初始條件：隊(duì)列Q已存在。

操作結(jié)果：將Q清為空隊(duì)列。583.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚笱h(huán)隊(duì)列——順序映象59

typedefstructQNode{//結(jié)點(diǎn)類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈隊(duì)列——鏈?zhǔn)接诚?0typedefstruct{

//鏈隊(duì)列類型

QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針}LinkQueue;a1∧an…Q.frontQ.frontQ.rear∧空隊(duì)列Q.rear隊(duì)頭元素61

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個(gè)空隊(duì)列Q

Q.front=Q.rear=

newQNode;

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

Q.front->next=NULL;

returnOK;}62

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e為Q的新的隊(duì)尾元素

p=newQNode;

if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;}Q.frontQ.rear∧epa1∧an…63

StatusDeQueue(LinkQueue&Q,QElemType&e){//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，//用e返回其值，并返回OK；否則返回ERROR

if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;

Q.front->next=p->next;delete(p);

returnOK;}if(Q.rear==p)Q.rear=Q.front;64Q.frontQ.reara1∧注意：出隊(duì)列操作的特殊情況∧if(Q.rear==p)Q.rear=Q.front;65#defineMAXQSIZE100//最大隊(duì)列長度typedefstruct{QElemType*base;//動(dòng)態(tài)分配存儲(chǔ)空間

intfront;//頭指針，若隊(duì)列不空，//指向隊(duì)列頭元素intrear;//尾指針，若隊(duì)列不空，指向//隊(duì)列尾元素的下一個(gè)位置

intqueuesize;}SqQueue;循環(huán)隊(duì)列——順序映象66注意：順序隊(duì)列的幾種情況：abcQ.frontQ.rear1、一般情況：100Q.frontQ.rear02、初始化：67abcQ.frontQ.rearabQ.front注意：順序隊(duì)列的幾種情況：3、特殊情況：cQ.reardQ.rearQ.frontdQ.rearQ.rear6