1第三章棧和隊(duì)列2棧的定義、表示及實(shí)現(xiàn)；棧的應(yīng)用（表達(dá)式求值、遞歸）；隊(duì)列的定義、表示及實(shí)現(xiàn)棧和隊(duì)列的特點(diǎn)；在兩種存儲結(jié)構(gòu)上棧的基本操作的實(shí)現(xiàn)；循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算；遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算。

※

教學(xué)內(nèi)容：※教學(xué)重點(diǎn)：

※教學(xué)難點(diǎn)：

3

棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)”進(jìn)行的線性表。

線性表?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ì)列是兩種常用的數(shù)據(jù)類型43.1棧的類型定義3.3棧的應(yīng)用舉例3.2棧類型的實(shí)現(xiàn)3.4隊(duì)列的類型定義3.5隊(duì)列類型的實(shí)現(xiàn)5一、棧(stack)的定義

限定僅在表尾進(jìn)行插入或刪除操作的線性表。其中允許進(jìn)行插入和刪除的一端（表尾）稱為棧頂；另一端（表頭）稱為棧底。當(dāng)表中沒有元素時(shí)，稱為空棧。3.1棧的類型定義6

假設(shè)棧

S=(a1,a2,…,an)棧底元素棧頂元素進(jìn)棧次序：

a1,a2,…,an退棧次序：an,an-1,…,a2,a1a1a2an棧頂棧底進(jìn)棧退棧棧是按照“后進(jìn)先出”原則處理數(shù)據(jù)元素的，棧也稱為“后進(jìn)先出”表。簡稱LIFO表。棧頂棧頂7二、棧的抽象數(shù)據(jù)類型的類型定義

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端為棧底。

基本操作：

}ADTStack8InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())9

InitStack(&S)初始化操作

操作結(jié)果：

DestroyStack(&S)

初始條件：

操作結(jié)果：棧S已存在。

棧S被銷毀。構(gòu)造一個(gè)空棧S。10

StackEmpty(S)判定S是否為空棧

初始條件：

操作結(jié)果：

StackLength(S)求棧的長度初始條件：

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

棧S已存在。

若棧S為空棧，則返回TRUE，

否則FALSE。11GetTop(S,&e)取棧頂元素

初始條件：

操作結(jié)果：a1a2an……棧S已存在且非空。

用e返回S的棧頂元素。12ClearStack(&S)棧置空操作

初始條件：

操作結(jié)果：棧S已存在。

將S清為空棧。13Push(&S,e)入棧操作

初始條件：

操作結(jié)果：a1a2ane……棧S已存在。

插入元素e為新的棧頂元素。top14Pop(&S,&e)出棧操作

初始條件：

操作結(jié)果：a1a2anan-1

……棧S已存在且非空。

刪除

S的棧頂元素，并用e返回其值。top15

例

3-1

有三個(gè)元素的進(jìn)棧順序?yàn)?、2、3。舉出此三個(gè)元素可能的出棧序列，并寫出相應(yīng)的進(jìn)棧和出棧操作序列（假設(shè)以s和x分別表示進(jìn)棧和出棧操作）。

出棧序列

1、2、31、3、22、1、32、3、13、2、1操作序列sxsxsxsxssxxssxxsxssxsxxsssxxx16利用一組地址連續(xù)的存貯單元（數(shù)組）依次存放從棧底到棧頂?shù)娜舾蓴?shù)據(jù)元素，數(shù)組的上界maxsize表示棧的最大容量；附設(shè)棧頂指針Top來指示棧頂元素在數(shù)組中的位置。一個(gè)棧的棧底位置是固定的,棧頂位置隨著進(jìn)棧和出棧操作而變化。一、棧的順序存儲結(jié)構(gòu)3.2棧類型的實(shí)現(xiàn)17ABCDTop=5Top=-1(空棧,再出棧產(chǎn)生“下溢”)(棧滿,再入棧產(chǎn)生“上溢”)ABCABTop=2Top=1Top=-1(空棧)(A.B.C入棧后棧的狀態(tài))(C出棧后的)EF18C語言描述：類似于線性表的順序存貯結(jié)構(gòu)

#defineMAXSIZEn

/*n為棧中數(shù)據(jù)元素個(gè)數(shù)的最大可能值*/

typedefstruct{}sqstack;

棧的順序存儲結(jié)構(gòu)方法一elemtypestack[MAXSIZE];inttop;

19voidInitstack(sqstack&s){

}初始化棧算法s.top=-1;//設(shè)置棧頂指針top，表示?？?0statuspush(sqstack&s,elemtypex){if(s.top>=MAXSIZE-1)returnERROR;//棧滿，上溢

else{s.top++;

s.stack[top]=x;returnOK;}}//push進(jìn)棧算法21出棧算法status

pop(sqstack&s,elemtype&e)

{if(s.top<0)returnERROR;//?？?，下溢

else{e=s.stack[top];s.top--;returnOK;}}//pop22取棧頂元素算法status

gettop(sqstacks,elemtype&e)

{if(s.top<0)returnNULL;//棧空，返回空值

else{e=s.stack[top];returnOK;}}//gettop23判棧空算法statusempty(sqstacks)

{if(s.

top<0)returnTRUE;//棧空，返回TRUEelse{returnFALSE;}}//empty24

在實(shí)現(xiàn)上述這些操作時(shí)，可以不把棧S定義為結(jié)構(gòu)體類型（sqstacks)

而是定義為指向結(jié)構(gòu)體的指針類型:這樣在編程時(shí)，只需將

s.top改為s

top

s.stack[]改為s

stack[]即可。Sqstack*s;

25#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

*top;//指向棧頂?shù)南乱粋€(gè)位置

int

stacksize;

}

SqStack;

類似于線性表的順序映象實(shí)現(xiàn)，指向表尾的指針可以作為棧頂指針。棧頂指針指向最后一個(gè)元素的下一個(gè)位置。棧的順序存儲結(jié)構(gòu)方法二26

StatusInitStack(SqStack&S){//構(gòu)造一個(gè)空棧SS.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));

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

}S.top=S.base;S.stacksize=STACK_INIT_SIZE;

returnOK;27

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間

S.base=(ElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(ElemType));

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

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

}

*S.top++=e;//先賦值，top后加1

returnOK}入棧28StatusPop(SqStack&S,SElemType&e){

//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERROR

if

(S.top==S.base)

returnERROR;

e=*--S.top;//先top減1，后取值給ereturnOK;}出棧29順序棧判滿、判空條件

順序棧空時(shí)：注意:

非空棧中的棧頂指針始終在棧頂元素的下一個(gè)位置上。順序棧滿時(shí)：S.top-S.base>=S.stacksizeS.top=S.base30

如果在一個(gè)程序中需要使用多個(gè)棧，為了充分利用各個(gè)棧的空間，不產(chǎn)生?？臻g過大造成系統(tǒng)空間緊張的問題，又要保證各個(gè)棧都能足夠大以保存入棧的元素，不產(chǎn)生“上溢”現(xiàn)象，最好能采用多個(gè)棧共享空間的方法，即給多個(gè)棧分配一個(gè)足夠大的數(shù)組空間，利用棧的動態(tài)特性，使其存儲空間互相補(bǔ)充。為說明簡單，假定在程序中同時(shí)使用兩個(gè)棧。給它們分配一個(gè)長度為m的數(shù)組空間，這時(shí)可將這兩個(gè)棧的棧底設(shè)在數(shù)組的兩端，讓它們的棧頂向數(shù)組中間增長。這樣當(dāng)一個(gè)棧中元素較多時(shí)，就可以越過數(shù)組的中點(diǎn)，延伸到另一個(gè)棧的部分空間中去，當(dāng)然前提是另一個(gè)棧中當(dāng)前的元素不多。只有當(dāng)兩個(gè)棧的棧頂相迂時(shí)，才會發(fā)生“上溢”。顯然，這比兩個(gè)各有m/2存儲空間的棧產(chǎn)生“上溢”的概率要小。31棧的順序存儲結(jié)構(gòu)方法三（多個(gè)棧共享空間）0m-1Top1(棧1頂)Top2(棧2頂)這種棧的數(shù)據(jù)結(jié)構(gòu)可定義為：typedefstruct{elemtypestack[m];

inttop1,top2;

}dustack;

棧1底棧2底32top2=mtop1=-1棧1棧1棧2棧2(a)棧1和棧2均為空棧時(shí)(b)棧1和棧2均有若干元素進(jìn)棧時(shí)(c)棧滿時(shí)top1top2top2top1兩個(gè)棧共享一段存貯空間33

例子：有兩個(gè)棧S1和S2共享存儲空間c[1,m0],其中一個(gè)棧底設(shè)在c[1]處，另一個(gè)棧底設(shè)在c[m0]處，分別編寫S1和S2的進(jìn)棧push(i,x)、退棧pop(i)和設(shè)置?？誷etnull(i)的函數(shù)，其中，i=1，2。注意：僅當(dāng)整個(gè)空間c[1,m0]占滿時(shí)才產(chǎn)生上溢。34a1a2……an……bm……b2b1C的元素序號

12……n……m0-1m0

棧1底

棧1頂棧2頂棧2底

top1top2

該共享?xiàng)５慕Y(jié)構(gòu)如圖所示，兩棧的最多元素個(gè)數(shù)為m0，top1是棧1的棧頂指針，top2是棧2的棧頂指針，當(dāng)top2=top1+1時(shí)出現(xiàn)上溢；當(dāng)top1=0時(shí)棧1出現(xiàn)下溢，當(dāng)top2=m0+1時(shí)棧2出現(xiàn)下溢。35根據(jù)上述原理得到入棧函數(shù)如下：voidpush(inti,intx){}if(top1==top2-1)printf(“上溢!\n”);elseif(i==1);//對第一個(gè)棧進(jìn)行入棧操作

{top1++;c[top1]=x;}else//對第二個(gè)棧進(jìn)行入棧操作

{top2--;c[top2]=x;}36voidpop(inti){if(i==1);//對第一個(gè)棧進(jìn)行出棧操作

if(top1==0)printf(“棧1下溢!\n”）;else{x=c[top1];top1--;}else//對第二個(gè)棧進(jìn)行出棧操作

if(top2==m0+1)printf(“棧2下溢!\n”）

else{x=c[top2];top2++;}}出棧函數(shù)如下：37voidsetnull(inti){if(i==1);top1=0;elsetop2=m0+1;}判棧空函數(shù)如下：38

當(dāng)最大需要容量事先不能估計(jì)時(shí),采用鏈?zhǔn)酱尜A結(jié)構(gòu)是有效的方法,鏈棧的操作只能在棧頂處進(jìn)行。二、棧的鏈?zhǔn)酱尜A結(jié)構(gòu)a5a4a3a2a1^棧底棧頂topdatanexttypedefstructsnode{elemtypedata;

structsnode*next;}*linkstack;39statuspush(linkstacktop,elemtypex){}//push鏈?zhǔn)竭M(jìn)棧操作t=(linkstack)malloc(sizeof(snode));if(t==NULL)returnERROR;//內(nèi)存無可用空間,棧上溢

else{t->data=x;t->next=top;top=t;returnOK;}40status

pop(linkstacktop,elemtype&e){}//pop鏈?zhǔn)匠鰲２僮鱭if(top==NULL)//?？?，棧溢出（下溢）

returnNULL;else{p=top;top=top->next;e=p->data;free(p);returnOK;}41

對于鏈棧，不會產(chǎn)生單個(gè)棧滿而其余?？盏那樾?，只有當(dāng)系統(tǒng)空間全部用完，malloc過程無法實(shí)現(xiàn)時(shí)才會發(fā)生上溢，因此多個(gè)鏈棧共享空間也就是自然的事了?？梢?，對棧這樣一種元素多變的數(shù)據(jù)結(jié)構(gòu)來說，鏈?zhǔn)酱鎯Y(jié)構(gòu)似乎更適宜些。此外初始化棧、棧判空操作也很容易實(shí)現(xiàn)。423.3棧的應(yīng)用舉例例一、數(shù)制轉(zhuǎn)換例二、括號匹配的檢驗(yàn)例三、行編輯程序問題例四、迷宮求解例五、表達(dá)式求值例六、實(shí)現(xiàn)遞歸43

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

算法基于原理：

N=(Ndivd)×d+Nmodd

44例如：

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

NNdiv8Nmod8

210

2125

202計(jì)算順序輸出順序45void

conversion(){}

//conversionInitStack(S);

scanf("%d",N);while(N){//N不等于0時(shí)循環(huán)

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

}while(!StackEmpty(S)){

Pop(S,e);

printf("%d",e);

}46#definestacksize100;typedefstruct{intbase[stacksize];inttop;}stack;

數(shù)制轉(zhuǎn)換的完整程序47intpush(stack*s,inte){

if(s->top>=stacksize)return0;s->base[s->top]=e;s->top++;return1;}intpop(stack*s,int*e){

if(s->top==0)return0;*e=s->base[--s->top];return1;}//top指向棧頂元素的下一個(gè)位置48main(){stacks1;intm,e,n;s1.top=0;m=1348;n=8;while(m){push(&s1,m%n);m=m/n;}while(s1.top!=0){pop(&s1,&e);printf("%d",e);}}49例二、括號匹配的檢驗(yàn)假設(shè)在表達(dá)式中,

（［］（））或［（［］［］）］則檢驗(yàn)括號是否匹配的方法可用“期待的急迫程度”這個(gè)概念來描述。

等為正確的格式，［（］）或（［（））或（（）］)

均為不正確的格式。50分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號序列：

[([][])]12345678到來的是“不速之客”；直到結(jié)束，也沒有到來所“期待”的括弧。51算法的設(shè)計(jì)思想：1)凡出現(xiàn)左括弧，則2)凡出現(xiàn)右括弧，3)表達(dá)式檢驗(yàn)結(jié)束時(shí)，

若?？眨瑒t表明表達(dá)式中匹配正確，

否則表明“左括弧”有余。進(jìn)棧；“右括弧”多余，首先檢查棧是否空若?？眨瑒t表明該

否則和棧頂元素比較，

若相匹配，則“左括弧出?！?/p>

，

否則表明不匹配。52Statusmatching(string&exp){//只有圓括號，調(diào)用基本操作}//matchingintstate=1;i=1;

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

switch(exp[i])

{

case

“(”:{Push(S,exp[i]);i++;break;}

case”)”:{

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

elsestate=0;break;}//表示不匹配

default：{

state=0;break;}}if(StackEmpty(S)&&state)return

OK;

else

returnERROR53例三、行編輯程序問題

一個(gè)簡單的行編輯程序的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)，并存入用戶的數(shù)據(jù)區(qū)。如何實(shí)現(xiàn)？“每接受一個(gè)字符即存入存儲器”?

由于用戶在終端上進(jìn)行輸入時(shí)，不能保證不出差錯(cuò)，因此，若在編輯程序中，“每接收一個(gè)字符即存入用戶數(shù)據(jù)區(qū)”的做法顯然不是最恰當(dāng)?shù)摹?4

實(shí)現(xiàn)：設(shè)立一個(gè)輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符（前一個(gè)字符無效），“@”為退行符。合理的作法是：

在用戶輸入一行的過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。55假設(shè)從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);則實(shí)際有效的是下列兩行：

while(*s)

putchar(*s++);56

為此，可設(shè)這個(gè)輸入緩沖區(qū)為一個(gè)棧結(jié)構(gòu)，每當(dāng)從終端接收了一個(gè)字符之后先作如下判別：

如果它既不是退格符也不是退行符，則將該字符壓入棧頂；如果是一個(gè)退格符，則從棧頂刪去一個(gè)字符；如果是一個(gè)退行符，則將字符棧清為空棧。可用下述算法來描述：57voidLineEdit(){InitStack(S);//構(gòu)造空棧

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

while(ch!=EOF)//EOF是全文結(jié)束符

{while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,ch);break;case‘@’:ClearStack(S);break;

//重置S為空棧

default:Push(S,ch);break;}ch=getchar();

//從終端接收下一個(gè)字符

}

將從棧底至棧頂?shù)臈?nèi)字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；

ClearStack(S);//重置S為空棧

if(ch!=EOF)ch=getchar();}DestroyStack(S);//棧S被銷毀

}//LineEdit58通常用的是“窮舉求解”的方法#############################################Q###########例四、迷宮求解→→↓↓→→↑→←↑←↓$$$$$$$$↓→→↓→→↓↓→→→→←從點(diǎn)的東向開始按順時(shí)針旋轉(zhuǎn)入口59求迷宮路徑算法的基本思想是：若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn);若當(dāng)前位置“不可通”，則后退，換方向繼續(xù)探索;若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。迷宮圖60設(shè)定當(dāng)前位置的初值為入口位置；

do｛若當(dāng)前位置可通，則｛將當(dāng)前位置插入棧頂；若該位置是出口位置，則算法結(jié)束；

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

新的當(dāng)前位置；

｝

否則{

｝｝while(棧不空）；求迷宮中一條從入口到出口的路徑的算法：

A:…

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

{則設(shè)定新的當(dāng)前位置為:沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；}若棧不空但棧頂位置的四周均不可通，

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

若棧不空，則重新測試新的棧頂位置，直至找到一個(gè)可通的相鄰塊或出棧至棧空；｝

若?？?，則表明迷宮沒有通路。62

表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)基本問題，它的實(shí)現(xiàn)是棧應(yīng)用的又一個(gè)典型例子。這里介紹一種簡單直觀，廣為使用的算法，叫“算符優(yōu)先法”。它是根據(jù)運(yùn)算優(yōu)先關(guān)系的規(guī)定來實(shí)現(xiàn)對表達(dá)式的編譯或解釋執(zhí)行的。例如：要對算術(shù)表達(dá)式4+2*3-10/5求值。算術(shù)四則運(yùn)算規(guī)則：⑴先括號內(nèi)，后括號外；⑵先乘除，后加減；⑶同級運(yùn)算從左算到右?！八惴麅?yōu)先法”就是根據(jù)這個(gè)運(yùn)算優(yōu)先關(guān)系的規(guī)定來實(shí)現(xiàn)對表達(dá)式的編譯或解釋執(zhí)行的。例五、表達(dá)式求值63表達(dá)式操作數(shù)(operand)：常數(shù)、變量或常量標(biāo)識符運(yùn)算符(operator)：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符等界限符(delimiter)：（、）、表達(dá)式結(jié)束符等

為了敘述的簡潔，我們僅討論簡單算術(shù)表達(dá)式的求值問題，這種表達(dá)式僅包含加、減、乘、除、括號等四種運(yùn)算。不難將它推廣到更一般的表達(dá)式上。64

我們把運(yùn)算符和界限符統(tǒng)稱為算符，它們構(gòu)成的集合命名為op，在運(yùn)算的每一步中，任意兩個(gè)相繼出現(xiàn)的運(yùn)算符θ1和θ2之間的優(yōu)先關(guān)系至多是下面三種關(guān)系之一：

θ1<θ2:θ1的優(yōu)先權(quán)低于θ2；

θ1=θ2:θ1的優(yōu)先權(quán)等于θ2；

θ1>θ2:θ1的優(yōu)先權(quán)高于θ2；下表定義了算符之間的這種優(yōu)先關(guān)系。65算符優(yōu)先關(guān)系表

+-*/

（）#>><<<>>>><<<>>>>>><>>>>>><>><<<<<=>>>>>><<<<<=+-*/()#θ1θ266

為實(shí)現(xiàn)算符優(yōu)先算法可使用兩個(gè)工作棧：

OPTR棧：用以寄存運(yùn)算符；

OPND棧：用以寄存操作數(shù)或運(yùn)算結(jié)果；算法基本思想：⑴首先置操作數(shù)棧為空棧，表達(dá)式起始符“#”為運(yùn)算符棧的棧底元素；⑵依次讀入表達(dá)式中的每個(gè)字符，若是操作數(shù)，則進(jìn)OPND棧；若是運(yùn)算符，則和OPTR棧的棧頂運(yùn)算符比較優(yōu)先數(shù)后作相應(yīng)操作，直至整個(gè)表達(dá)式求值完畢（即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為“#”)。67OperandTypeEvaluateExpression()//求算術(shù)表達(dá)式的值

{InitStack(OPTR);Push(OPTR,’#’);//初始化運(yùn)算符棧

InitStack(OPND);c=getchar();//初始化操作數(shù)棧

while(c!=‘#’||GetTop(OPTR))!=‘#’){if(!In(c,OP)//讀入的c不是運(yùn)算符

{Push((OPND,c);c=getchar();}//操作數(shù)進(jìn)棧

elseswitch(Precede(GetTop(OPTR),c){case‘<’:Push(OPTR,c);c=getchar();break;//棧頂元素優(yōu)先權(quán)低，運(yùn)算符進(jìn)棧

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

case‘>’:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;//退棧并將運(yùn)算結(jié)果入棧

}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression

68

表達(dá)式::=(操作數(shù))+(運(yùn)算符)+(操作數(shù))

操作數(shù)::=簡單變量|表達(dá)式簡單變量::=標(biāo)識符|無符號整數(shù)二元運(yùn)算符的表達(dá)式的三種標(biāo)識方法69

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

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

70例如:Exp=a

b

+

(c

d/e)

f前綴式:

中綴式:

后綴式:

結(jié)論:1）操作數(shù)之間的相對次序不變;2）運(yùn)算符的相對次序不同;3）中綴式丟失了括弧信息，致使運(yùn)算的次序不確定;

+

ab

c/defa

b

+

c

d/e

fab

cde/

f

+715)后綴式的運(yùn)算規(guī)則為:

每個(gè)運(yùn)算符和在它之前出現(xiàn)

且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式;

運(yùn)算符在表達(dá)式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序。4)前綴式的運(yùn)算規(guī)則為:

連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式;72如何從后綴式求值？先找運(yùn)算符，再找操作數(shù)例如：

ab

cde/

f

+a

bd/ec-d/e(c-d/e)

f73如何從原表達(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

c

d/e

f后綴式:

abc

+de/f

74從原表達(dá)式求得后綴式的規(guī)律為：1)設(shè)立運(yùn)算符棧；2)設(shè)表達(dá)式的結(jié)束符為“#”，

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

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

//s是運(yùn)算符棧，s棧底預(yù)設(shè)‘#’，OP是運(yùn)算符集合

{}//CrtExptreeInitStack(S);Push(S,

#

);p=exp;ch=*p;

while(!StackEmpty(S)){if(!IN(ch,OP))//若ch是操作數(shù)

Pass(Suffix,ch);else{A:}//若ch是運(yùn)算符

if(ch!=

#

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

}//while……77A:switch(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;

}//switch若ch的優(yōu)先級比c低，為真781)設(shè)立操作數(shù)棧S；2)設(shè)表達(dá)式的結(jié)束符為“#”；3)讀入表達(dá)式一個(gè)字符,若當(dāng)前字符是操作數(shù)，則壓入棧中,轉(zhuǎn)4)。求后綴式的值：79若當(dāng)前字符是運(yùn)算符optr，從棧中彈出2個(gè)數(shù),將運(yùn)算結(jié)果再壓入棧,即:x2=POP(S)；x1=POP(S)；

PUSH(S,(x1optrx2));讀下一字符，重復(fù)3）和4）直至讀到結(jié)束符#；

棧頂,x=POP(S)即后綴式相應(yīng)的表達(dá)式的值。80intcal(charsuffix-exp[])//求后綴式表達(dá)式的值

//s是運(yùn)算數(shù)棧，OP是運(yùn)算符集合

{

}//calInitStack(S);i=0;ch=suffix-exp[0];while(ch<>’#’){if(!IN(ch,OP))//若ch是操作數(shù)

Push(S,ch);else//若ch是運(yùn)算符

{x2=POP(S)；x1=POP(S)；//取出兩個(gè)操作數(shù)

PUSH(S,(x1chx2));}i++;ch=suffix-exp[i];}//while81例六、實(shí)現(xiàn)遞歸將所有的實(shí)在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(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ù)：82保存被調(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ù)：83多個(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ū)函數(shù)a的數(shù)據(jù)區(qū)84

函數(shù)之間的信息傳遞和控制轉(zhuǎn)移必須通過“棧”來實(shí)現(xiàn)，系統(tǒng)將整個(gè)程序運(yùn)行時(shí)所需要的數(shù)據(jù)空間安排在一個(gè)棧內(nèi)，每當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，就為它在棧頂分配一個(gè)存儲區(qū)，每當(dāng)從一個(gè)函數(shù)退出時(shí)，就釋放它的存儲區(qū)。所以當(dāng)前運(yùn)行的函數(shù)的數(shù)據(jù)區(qū)必在棧頂。一個(gè)遞歸函數(shù)的運(yùn)行過程類似于多個(gè)函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)與被調(diào)用函數(shù)是同一個(gè)函數(shù)。注意：遞歸函數(shù)運(yùn)行的“層次”。主函數(shù)是第0層，從主函數(shù)調(diào)用遞歸函數(shù)為進(jìn)入第1層。每進(jìn)入一層遞歸，就產(chǎn)生一個(gè)新的工作記錄（包括上一層的返回地址、實(shí)在參數(shù)、局部量）壓入棧頂。每退出一層遞歸，就從棧頂彈出一個(gè)工作記錄。85例3-2n階Hanoi問題。假設(shè)有三個(gè)分別命名為X、Y和Z的塔座，在塔座X上插有n個(gè)直徑大小各不相同、依小到大編號為1，2，…,n的圓盤?，F(xiàn)要求將X軸上的n個(gè)圓盤移至塔座Z上，并仍按同樣順序疊排。12..n-1nXYZ12..nXYZ86圓盤移動時(shí)必須遵循下列規(guī)則：1)每次只能移動一個(gè)圓盤；

2)圓盤可以插在X、Y和Z中的任一塔座上；

3)任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。XYZ87如何實(shí)現(xiàn)圓盤的移動操作？當(dāng)n=1時(shí)，從塔座X

Z;XYZ

而如何將n-1個(gè)圓盤從一個(gè)塔座移至另一個(gè)塔座的問題是一個(gè)和原問題具有相同特征屬性的問題，只是問題的規(guī)模小1，因此可以用同樣的方法求解。XYZ

當(dāng)n>1時(shí)，利用塔座Y作輔助塔座，若能設(shè)法將壓在編號為n的圓盤之上的n-1個(gè)圓盤從塔座X

Y上，則可先將編號為n的圓盤從塔座X

Z，然后再將塔座Y上的n-1個(gè)圓盤移至塔座Z上。88voidhanoi(intn,charx,chary,charz)//

將塔座x上按直徑由小到大且至上而下編號為1至n//

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

1{2if(n==1)3move(x,1,z);//

將編號為１的圓盤從x移到z4else{5hanoi(n-1,x,z,y);//

將x上編號為１至n-1的

//圓盤移到y(tǒng),z作輔助塔

6move(x,n,z);//

將編號為n的圓盤從x移到z7hanoi(n-1,y,x,z);//

將y上編號為１至n-1的

//圓盤移到z,x作輔助塔8}9}8903abc返址nxyz52acb51abc71cabvoidhanoi(intn,charx,chary,charz){1if(n==1)2move(x,1,z);3else4

{hanoi(n-1,x,z,y);5move(x,n,z);6hanoi(n-1,y,x,z);7}8}

語句標(biāo)號90過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程3棧的應(yīng)用91地圖四染色問題“四染色”定理是計(jì)算機(jī)科學(xué)中著名的定理之一。使地圖中相鄰的國家或行政區(qū)域不重色，最少可用四種顏色對地圖著色。證明此定理的結(jié)論，利用棧采用回溯法對地圖著色。思想：對每個(gè)行政區(qū)編號：1-7

對顏色編號；a、b、c、d；從第一號行政區(qū)開始逐一染色，每一個(gè)區(qū)域逐次用四種顏色進(jìn)行試探，若所取顏色與周圍不重，則用棧記下來該區(qū)域的色數(shù)，否則依次用下一色數(shù)進(jìn)行試探。若出現(xiàn)a-d均與周圍發(fā)生重色，則需退?；厮?，修改當(dāng)前棧頂?shù)纳珨?shù)。92(1)(2)(4)(5)(6)(7)(3)R[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#

紫色

2#黃色3#

紅色4#

藍(lán)色地圖四染色舉例S[K]93Voidmapcolor(intR[][],intn,ints[]){s[1]=1;//1號區(qū)域染1色

a=2;J=1;//a為區(qū)域號，J為染色號

while(a<=n)

{while((J<=4)&&(a<=n)){k=1;//k表示已經(jīng)著色的區(qū)域號

while((k<a)&&(s[k]

R[a-1][k-1]!=J))k=k+1;

//若不相鄰，或若相鄰且不重色，對下一個(gè)區(qū)域判斷。

IF(k<a)J=J+1；//相鄰且重色

ELSE{s[a]=J;a=a+1;J=1;}//相鄰且不重色

}IF(J>4){a=a-1;J=s[a]+1}}}94

設(shè)n皇后問題的解為(x1,x2,x3,…,xn),

約束條件為：其中任意兩個(gè)xi

和xj不能位于棋盤的同行、同列及同對角線。如何表示棋盤中放置的棋子？

由于每行、列及對角線上只能有一個(gè)棋子，因而對每列來說，只需記錄該列中棋子所在的行號，故用一維數(shù)組即可?；屎髥栴}求解95

設(shè)四皇后問題的解為(x1,x2,x3,x4),

其中：xi(i=1,2,3,4)Si={1,2,3,4}約束條件為：其中任意兩個(gè)xi

和xj不能位于棋盤的同行、同列及同對角線。

按回溯法的定義，皇后問題求解過程為：解的初始值為空；首先添加x1=1,之后添加滿足條件的x2=3，由于對所有的x3

{1,2,3,4}都不能找到滿足約束條件的部分解(x1,x2,x3),

則回溯到部分解(x1),

重新添加滿足約束條件的x2=4,依次類推(按行存列號)。按四皇后問題求解舉例96????????????????????????????????????????????????????????????????????????97void

queen(inti,intn)

{//進(jìn)入本函數(shù)時(shí)，在n×n棋盤前i-1行已放置了互不攻

//擊的i-1個(gè)棋子?，F(xiàn)從第i行起繼續(xù)為后續(xù)棋子選擇

//滿足約束條件的位置。當(dāng)求得(i>n)的一個(gè)合法布局

//時(shí)，輸出之。

if(i>n)輸出棋盤的當(dāng)前布局;

elsefor(j=1;j<=n;++j)

{

在第i行第j列放置一個(gè)棋子;

if(當(dāng)前布局合法)queen(i+1,n);

移去第i行第j列的棋子;

}}//trial98#include<stdio.h>#definen8//n為皇后個(gè)數(shù)，m為擺法計(jì)數(shù)intm=0,a[n];

//a[i]存放第i個(gè)皇后放置的行號,int

ok(inti,intj)

//檢查(i,j)上能否放棋子{

j1=j;i1=i;ok1=1;//檢查第i行上能否放棋子

while((j1>1)&&ok1){j1--;ok1=a[j1]!=i;}

j1=j;i1=i;//檢查對角線上能否放棋子

while((j1>1)&&(i1>1)&&ok1){j1--;i1--;ok1=a[j1]!=i1;}j1=j;i1=i;//檢查另一對角線上能否放棋子

while((j1>1)&&(i1<n)&&ok1){j1--;i1++;ok1=a[j1]!=i1;}returnok1}99Voidqueen(intj)

//從第j列開始逐個(gè)試探{

if(j>n)

{m++;

printf("m=%d",m);

for(i=1;i<=n;i++)printf("%d",a[i]);

printf(“\n”);

}

elsefor(i=1;i<=n;i++)if(ok(i,j))//檢查(i,j)上能否放棋子

{a[j]=i;//在(i,j)上放一個(gè)棋子

queen(j+1);}}main(){queen(1);}100隊(duì)列是只允許在表的一端進(jìn)行插入,在另一端刪除元素的線性表；允許插入的一端稱為隊(duì)尾(rear);允許刪除的一端稱為隊(duì)頭(front)；假設(shè)隊(duì)列為Q=(a1,a2,…,an),則a1是隊(duì)頭元素，an是隊(duì)尾元素；隊(duì)列中的元素是按照a1,a2,…,an的順序進(jìn)入的，退出隊(duì)列也只能按照這個(gè)次序依次退出；當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列；隊(duì)列是一種“先進(jìn)先出”的線性表，簡稱FIFO表。3.4隊(duì)列的類型定義一、隊(duì)列的定義101a1

a2

a3…an出隊(duì)列

入隊(duì)列隊(duì)頭隊(duì)尾隊(duì)列示意圖102

ADTQueue{

數(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ì)列尾基本操作:}ADTQueue二、隊(duì)列的抽象數(shù)據(jù)類型的類型定義103隊(duì)列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())104InitQueue(&Q)

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

DestroyQueue(&Q)

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

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

不再存在。

105

QueueEmpty(Q)

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

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

TRUE，否則返回FALSE。106

QueueLength(Q)

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

操作結(jié)果：返回Q的元素個(gè)數(shù)，

即隊(duì)列的長度。107

GetHead(Q,&e)

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

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

ClearQueue(&Q)

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

操作結(jié)果：將Q清為空隊(duì)列。109

EnQueue(&Q,e)

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

操作結(jié)果：插入元素e為Q的新的

隊(duì)尾元素。a1a2ane……110

DeQueue(&Q,&e)

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

操作結(jié)果：刪除Q的隊(duì)頭元素，

并用e返回其值。a1a2an……

111QueueTravers(Q,visit())

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

操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對Q

的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)

visit()。一旦Visit()失敗，則操作失敗。1123.5隊(duì)列類型的實(shí)現(xiàn)鏈隊(duì)列——鏈?zhǔn)接诚笱h(huán)隊(duì)列——順序映象1131、隊(duì)列的順序存貯結(jié)構(gòu)

隊(duì)列的順序存儲結(jié)構(gòu)稱為順序隊(duì)列，采用一維數(shù)組來存儲隊(duì)列中的每一元素，數(shù)組的上界表示隊(duì)列的最大容量。另設(shè)兩個(gè)指針front

和rear

，分別指示隊(duì)頭元素和隊(duì)尾元素在隊(duì)列中的位置。約定：

隊(duì)頭指針front總是指向隊(duì)頭元素在隊(duì)列中的當(dāng)前位置；隊(duì)尾指針rear總是指示隊(duì)尾元素的下一個(gè)位置；114C語言描述：

#defineMAXQSIZEntypedefstruct{elemtypequeue[MAXQSIZE];//靜態(tài)分配

intfront,rear;}sequeuetp;

ABCDEfrontrear（1）一般的隊(duì)列115C語言描述：

#defineMAXQSIZEntypedefstruct{elemtype*queue;//動態(tài)分配

intfront,rear;}sequeuetp;116例：順序隊(duì)列Q的C語言描述是：

#defineMAXQSIZE8typedefstruct{charqueue[MAXQSIZE];intfront,rear;}sequeuetp;sequeuetpQ;

117(a)隊(duì)列的初始狀態(tài)(空隊(duì)列):01234567Q.frontQ.rear

狀態(tài)特征：Q.front=Q.rear=0118初始化算法voidinitqueue(sequeuetpQ){Q.front=0;Q.rear=0;//設(shè)置隊(duì)頭指針和隊(duì)尾指針均指向

//數(shù)組下界

}119

(b)

元素入隊(duì)列后，隊(duì)列的狀態(tài):

Q.frontQ.rear

入列操作:

Q.queue[Q.rear]=‘A’;Q.rear++;Q.queue[Q.rear]=‘B’;Q.rear++;Q.queue[Q.rear]=‘C’;Q.rear++;Q.queue[Q.rear]=‘D’;Q.rear++;Q.queue[Q.rear]=‘E’;Q.rear++;ABCDE120

(c)

元素A,B,C出列后的狀態(tài):Q.frontQ.rear

出列操作:

ch=Q.queue[Q.front];Q.front++;ch=Q.queue[Q.front];Q.front++;ch=Q.queue[Q.fr