數(shù)據(jù)結構第三章課件

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

※

教學內(nèi)容：※教學重點：

※教學難點：

3

棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。

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

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

假設棧

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

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

ADTStack

{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關系：

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)初始化操作

操作結果：

DestroyStack(&S)

初始條件：

操作結果：棧S已存在。

棧S被銷毀。構造一個空棧S。10

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

初始條件：

操作結果：

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

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

棧S已存在。

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

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

初始條件：

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

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

初始條件：

操作結果：棧S已存在。

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

初始條件：

操作結果：a1a2ane……棧S已存在。

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

初始條件：

操作結果：a1a2anan-1

……棧S已存在且非空。

刪除

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

例

3-1

有三個元素的進棧順序為1、2、3。舉出此三個元素可能的出棧序列，并寫出相應的進棧和出棧操作序列（假設以s和x分別表示進棧和出棧操作）。

出棧序列

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

#defineMAXSIZEn

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

typedefstruct{}sqstack;

棧的順序存儲結構方法一elemtypestack[MAXSIZE];inttop;

19voidInitstack(sqstack&s){

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

else{s.top++;

s.stack[top]=x;returnOK;}}//push進棧算法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;//?？眨祷乜罩?/p>

else{e=s.stack[top];returnOK;}}//gettop23判?？账惴╯tatusempty(sqstacks)

{if(s.

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

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

而是定義為指向結構體的指針類型:這樣在編程時，只需將

s.top改為s

top

s.stack[]改為s

stack[]即可。Sqstack*s;

25#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedefstruct{

SElemType

*base;

SElemType

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

int

stacksize;

}

SqStack;

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

StatusInitStack(SqStack&S){//構造一個空棧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順序棧判滿、判空條件

順序棧空時：注意:

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

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

inttop1,top2;

}dustack;

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

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

12……n……m0-1m0

棧1底

棧1頂棧2頂棧2底

top1top2

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

{top1++;c[top1]=x;}else//對第二個棧進行入棧操作

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

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

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

當最大需要容量事先不能估計時,采用鏈式存貯結構是有效的方法,鏈棧的操作只能在棧頂處進行。二、棧的鏈式存貯結構a5a4a3a2a1^棧底棧頂topdatanexttypedefstructsnode{elemtypedata;

structsnode*next;}*linkstack;39statuspush(linkstacktop,elemtypex){}//push鏈式進棧操作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鏈式出棧操作qif(top==NULL)//?？眨瑮Ｒ绯觯ㄏ乱纾?/p>

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

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

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

算法基于原理：

N=(Ndivd)×d+Nmodd

44例如：

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

NNdiv8Nmod8

210

2125

202計算順序輸出順序45void

conversion(){}

//conversionInitStack(S);

scanf("%d",N);while(N){//N不等于0時循環(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指向棧頂元素的下一個位置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例二、括號匹配的檢驗假設在表達式中,

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

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

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

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

若?？眨瑒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例三、行編輯程序問題

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

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

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

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

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

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

while(*s)

putchar(*s++);56

為此，可設這個輸入緩沖區(qū)為一個棧結構，每當從終端接收了一個字符之后先作如下判別：

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

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

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

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

//重置S為空棧

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

//從終端接收下一個字符

}

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

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

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

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

do｛若當前位置可通，則｛將當前位置插入棧頂；若該位置是出口位置，則算法結束；

否則切換當前位置的東鄰方塊為

新的當前位置；

｝

否則{

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

A:…

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

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

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

若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至?？眨唬?/p>

若?？眨瑒t表明迷宮沒有通路。62

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

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

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

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

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

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

+-*/

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

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

OPTR棧：用以寄存運算符；

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

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

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

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

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

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

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}//whilereturnGetTop(OPND);}//EvaluateExpression

68

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

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

表達式的三種標識方法：設

Exp=S1+

OP

+S2則稱

OP

+S1+S2

為前綴表示法

S1+

OP

+S2

為中綴表示法

S1+S2+

OP

為后綴表示法

70例如:Exp=a

b

+

(c

d/e)

f前綴式:

中綴式:

后綴式:

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

+

ab

c/defa

b

+

c

d/e

fab

cde/

f

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

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

且緊靠它的兩個操作數(shù)構成一個最小表達式;

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

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

ab

cde/

f

+a

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

f73如何從原表達式求得后綴式？

每個運算符的運算次序要由它之后的一個運算符來定，在后綴式中，優(yōu)先數(shù)高的運算符領先于優(yōu)先數(shù)低的運算符。分析“原表達式”和“后綴式”中的運算符:原表達式:

a+b

c

d/e

f后綴式:

abc

+de/f

74從原表達式求得后綴式的規(guī)律為：1)設立運算符棧；2)設表達式的結束符為“#”，

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

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

//s是運算符棧，s棧底預設‘#’，OP是運算符集合

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

#

);p=exp;ch=*p;

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

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

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ù)棧S；2)設表達式的結束符為“#”；3)讀入表達式一個字符,若當前字符是操作數(shù)，則壓入棧中,轉(zhuǎn)4)。求后綴式的值：79若當前字符是運算符optr，從棧中彈出2個數(shù),將運算結果再壓入棧,即:x2=POP(S)；x1=POP(S)；

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

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

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

{

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

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

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

PUSH(S,(x1chx2));}i++;ch=suffix-exp[i];}//while81例六、實現(xiàn)遞歸將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。

當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，

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

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

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

Z;XYZ

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

當n>1時，利用塔座Y作輔助塔座，若能設法將壓在編號為n的圓盤之上的n-1個圓盤從塔座X

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

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

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

的n個圓盤按規(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}

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

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

紫色

2#黃色3#

紅色4#

藍色地圖四染色舉例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;

//若不相鄰，或若相鄰且不重色，對下一個區(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

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

約束條件為：其中任意兩個xi

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

由于每行、列及對角線上只能有一個棋子，因而對每列來說，只需記錄該列中棋子所在的行號，故用一維數(shù)組即可。皇后問題求解95

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

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

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

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

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

則回溯到部分解(x1),

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

queen(inti,intn)

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

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

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

//時，輸出之。

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

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

{

在第i行第j列放置一個棋子;

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

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

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

//a[i]存放第i個皇后放置的行號,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列開始逐個試探{

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)上放一個棋子

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

a2

a3…an出隊列

入隊列隊頭隊尾隊列示意圖102

ADTQueue{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定其中a1

端為隊列頭，an

端為隊列尾基本操作:}ADTQueue二、隊列的抽象數(shù)據(jù)類型的類型定義103隊列的基本操作：

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

操作結果：構造一個空隊列Q。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結果：隊列Q被銷毀，

不再存在。

105

QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結果：若Q為空隊列，則返回

TRUE，否則返回FALSE。106

QueueLength(Q)

初始條件：隊列Q已存在。

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

即隊列的長度。107

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結果：用e返回Q的隊頭元素。a1a2an……108

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結果：將Q清為空隊列。109

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結果：插入元素e為Q的新的

隊尾元素。a1a2ane……110

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結果：刪除Q的隊頭元素，

并用e返回其值。a1a2an……

111QueueTravers(Q,visit())

初始條件：Q為非空隊列。

操作結果：從隊頭到隊尾，依次對Q

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

visit()。一旦Visit()失敗，則操作失敗。1123.5隊列類型的實現(xiàn)鏈隊列——鏈式映象循環(huán)隊列——順序映象1131、隊列的順序存貯結構

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

和rear

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

隊頭指針front總是指向隊頭元素在隊列中的當前位置；隊尾指針rear總是指示隊尾元素的下一個位置；114C語言描述：

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

intfront,rear;}sequeuetp;

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

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

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

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

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

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

//數(shù)組下界

}119

(b)

元素入隊列后，隊列的狀態(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