《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第3章PPT課件》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第3章PPT課件（110頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、1第三章棧和隊(duì)列2【課前思考】【課前思考】1.什么是線性結(jié)構(gòu)？什么是線性結(jié)構(gòu)？簡單地說，線性結(jié)構(gòu)是一個數(shù)據(jù)元素的序列。2.你見過餐館中一疊一疊的盤子嗎？如果它們是按你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,n 的次序往上疊的，那么使用時候的次序應(yīng)的次序往上疊的，那么使用時候的次序應(yīng)是什么樣的？是什么樣的？必然是依從上往下的次序，即n,2,1。它們遵循的是后進(jìn)先出的規(guī)律，這正是本章要討論的棧的結(jié)構(gòu)特點(diǎn)。3.在日常生活中，為了維持正常的社會秩序而出現(xiàn)在日常生活中，為了維持正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？的常見現(xiàn)象是什么？是排隊(duì)。在計(jì)算機(jī)程序中，模擬排隊(duì)的數(shù)據(jù)結(jié)構(gòu)是隊(duì)列。3【學(xué)習(xí)目標(biāo)】

2、【學(xué)習(xí)目標(biāo)】1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法。3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。4.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。4 棧和隊(duì)列是在程序設(shè)計(jì)中被廣泛使用的兩種線性數(shù)據(jù)結(jié)構(gòu)，因此本章的學(xué)習(xí)重點(diǎn)在于掌握這兩種結(jié)構(gòu)的特點(diǎn)，以便能在應(yīng)用問題中正確使用。【知識點(diǎn)】【知識點(diǎn)】順序棧、鏈棧、循環(huán)隊(duì)列、鏈隊(duì)列【重點(diǎn)和難點(diǎn)】【重點(diǎn)和難點(diǎn)】5【學(xué)習(xí)指南】【學(xué)習(xí)指南】在這一章中，主要是學(xué)習(xí)如何在求解應(yīng)用問題中適當(dāng)?shù)貞?yīng)用棧和隊(duì)列，棧和隊(duì)列在兩種存儲結(jié)構(gòu)中的實(shí)現(xiàn)都不難，但應(yīng)該對它們了如指掌，特別要注意它們的基本操作實(shí)現(xiàn)時

3、的一些特殊情況，如棧滿和?？铡㈥?duì)滿和隊(duì)空的條件以及它們的描述方法。本章要求必須完成的算法設(shè)計(jì)題為：3.15，3.17，3.19，3.22，3.27,3.28，3.30，3.31，3.32。其中前4個主要是練習(xí)棧的應(yīng)用，后4個主要是有關(guān)隊(duì)列的實(shí)現(xiàn)方法的練習(xí)。6通常稱，棧和隊(duì)列是限定插入和刪除插入和刪除只能只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。線性表線性表 棧棧 隊(duì)列隊(duì)列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in棧和隊(duì)列是兩種常用的數(shù)據(jù)類型棧和隊(duì)列是兩種常用的數(shù)據(jù)類型7 目

4、目 錄錄83.1 棧棧一、棧的定義一、棧的定義 棧棧(stack)(stack)作為一種限定性線性表，是將線性表的插入插入和刪除刪除運(yùn)算限制為僅在表的一端僅在表的一端進(jìn)行。通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂棧頂(Top)(Top)，因此棧頂?shù)漠?dāng)前位置是動態(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端為固定的一端，被稱為棧底棧底(Bottom)(Bottom)。當(dāng)棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進(jìn)棧或入棧，刪除操作稱為出棧或退棧。插入：最先放入棧中元素在棧底，最后放入的元素在棧頂；刪除：最后放入的元素最先刪除，最先放入的元素最后刪除。棧是一種后進(jìn)先出(

5、Last In First OutLast In First Out)的線性表，簡稱為LIFO表。9ana2a1進(jìn)棧出棧棧頂棧底進(jìn)棧出棧(a)棧的示意圖(b)鐵路調(diào)序棧的表示圖圖3.1 棧棧ana2a1進(jìn)棧出棧棧頂棧底進(jìn)棧出棧(a)棧的示意圖(b)鐵路調(diào)序棧的表示10 例：設(shè)一個棧的輸入序列為例：設(shè)一個棧的輸入序列為A,B,C,D,則借助一則借助一個棧所得到的輸出序列不可能是個棧所得到的輸出序列不可能是 。(A)A,B,C,D(B)D,C,B,A (C)A,C,D,B(D)D,A,B,C 答答:可以簡單地推算可以簡單地推算,得容易得出得容易得出D,A,B,C是不可是不可能的能的,因?yàn)橐驗(yàn)镈先出

6、來先出來,說明說明A,B,C,D均在棧中均在棧中,按照入棧按照入棧順序順序,在棧中順序應(yīng)為在棧中順序應(yīng)為D,C,B,A,出棧的順序只能是出棧的順序只能是D,C,B,A。所以本題答案為。所以本題答案為D。11二、棧的主要操作二、棧的主要操作 1.初始化棧：初始化棧：InitStack(&S)將棧S置為一個空棧(不含任何元素)。2.進(jìn)棧：進(jìn)棧：PUSH(&S,X)將元素X插入到棧S中，也稱為“入?！薄ⅰ安迦搿?、“壓入”。3.出棧：出棧：POP(&S，&e)刪除棧S中的棧頂元素，也稱為”退棧”、“刪除”、“彈出”。4.取棧頂元素：取棧頂元素：GETTOP(S，&e)取棧S中棧頂元素。5.判?？眨号袟?/p>

7、空：EMPTY(S)判斷棧S是否為空，若為空，返回值為1，否則返回值為0。12三、棧的抽象數(shù)據(jù)類型描述三、棧的抽象數(shù)據(jù)類型描述 ADT Stack 數(shù)據(jù)對象數(shù)據(jù)對象：D=ai|ai ElemSet，i=1,2,n,n 0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1=|ai-1,ai D,i=1,2,n 基本操作：基本操作：InitStack(&S)操作前提：S為未初始化的棧。操作結(jié)果：將S初始化為空棧。ClearStack(&S)操作前提：棧S已經(jīng)存在。操作結(jié)果：將棧S置成空棧。StackEmpty(S)操作前提：棧S已經(jīng)存在。操作結(jié)果：若棧S為空，則返回TRUE,否則FALSE。13 StackLength(S

8、)操作前提：棧S已經(jīng)存在。操作結(jié)果：返回S的元素個數(shù)即棧的長度。IsFull(S)操作前提：棧S已經(jīng)存在。操作結(jié)果：判棧滿函數(shù)，若S棧已滿，則函數(shù)值為TRUE，否則為FALSE。StackTraverse(S,visit()操作前提：棧S已經(jīng)存在且非空。操作結(jié)果：從棧底到棧頂依次對S底每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失效。14 Push(&S,e)操作前提：棧S已經(jīng)存在。操作結(jié)果：在S的頂部插入(亦稱壓入)元素e；若S棧未滿，將e插入棧頂位置，若棧已滿，則返回FALSE，表示操作失敗，否則返回TRUE。Pop(&S,&e)操作前提：棧S已經(jīng)存在。操作結(jié)果：刪除(亦

9、稱彈出)棧S的頂部元素，并用e帶回該值；若棧為空，返回值為FALSE，表示操作失敗，否則返回TRUE。GetTop(S,&e)操作前提：棧S已經(jīng)存在。操作結(jié)果：取棧S的頂部元素。與Pop(&S,&e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢?。ADT Stack15 1.順序棧順序棧 順序棧是用順序存儲結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設(shè)一個位置指針位置指針toptop（棧頂指針）來動態(tài)地指示棧頂元素動態(tài)地指示棧頂元素在順序棧中的位位置置。通常以top=0或 top=-1表示空棧。

10、順序棧的存儲結(jié)構(gòu)可以用C語言中的一維數(shù)組來表示。棧的順序存儲結(jié)構(gòu)定義如下：四、四、棧的表示和實(shí)現(xiàn)棧的表示和實(shí)現(xiàn) 16#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10 /存儲空間分配增量typedef struct SElemType*base;/在棧構(gòu)造前和銷毀后base值為NULL SElemType*top;/棧頂指針 int stacksize;SqStack;/當(dāng)前已分配存儲空間或簡單定義如下：#define M 100 int sM;int top;17圖3.2 順序棧中的進(jìn)棧和出棧 Top指向棧頂元素指向棧

11、頂元素初態(tài)：初態(tài)：top=-1;空棧，棧中無元素，進(jìn)棧：進(jìn)棧：top=top+1;stop=x;退棧：退棧：取stop;top=top-1;棧滿：棧滿：top=M-1;棧溢出（上溢），不能再進(jìn)棧（錯誤狀態(tài)）top=-1時不能退棧，下溢（正常狀態(tài)，常作控制條件）18（1 1）構(gòu)造空順序棧算法）構(gòu)造空順序棧算法:初始化棧初始化棧Status InitStack(SqStack&S)/構(gòu)造一個空棧構(gòu)造一個空棧 S SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/為棧分配存儲

12、空間失敗為棧分配存儲空間失敗S.top=S.base;/令棧頂指針令棧頂指針 =棧底指針棧底指針/設(shè)置棧的當(dāng)前可使用的最大容量設(shè)置棧的當(dāng)前可使用的最大容量S.stacksize=STACK_INIT_SIZE;return OK;/InitStack/InitStack2.2.順序?；静僮鞯膶?shí)現(xiàn)如下順序?；静僮鞯膶?shí)現(xiàn)如下:19程序描述：程序描述：/This program is to initialize a stack#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK

13、 1#define ERROR 0 typedef int SElemType;typedef struct/define structure SqStack()SElemType*base;SElemType*top;int stacksize;SqStack;20 int InitStack(SqStack&S)/InitStack()sub-function S.base=(SElemType)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)printf(“Allocate space failure!n“);return(ERRO

14、R);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);/InitStack()end void main()/main()function SqStack S;if(InitStack(S)printf(Success!The stack has been created!n“);printf(.OK!n“);getch();21（2）取順序棧的棧頂元素取順序棧的棧頂元素 Status GetTop(SqStack S,SElemType&e)/如果棧如果棧 S 空，返回空，返回 ERROR；如果棧；如果棧 S 不空，用不空，用 e 返回

15、棧返回棧 S 的棧的棧頂元素，并返回頂元素，并返回 OK。if(S.top=S.base)return ERROR;/如果棧如果棧 S 為空，則返回為空，則返回 ERROR e=*(S.top-1);/將棧頂指針減將棧頂指針減 1 后所指向的單元內(nèi)的值賦給后所指向的單元內(nèi)的值賦給 e return OK;/GetTop/GetTop22（3）將元素壓入順序棧算法（將元素壓入順序棧算法（進(jìn)棧）進(jìn)棧）Status Push(SqStack&S,SElemType e)/將元素將元素 e 插入到棧插入到棧 S 中，成為新的棧頂元素中，成為新的棧頂元素 if(S.top-S.base S.stacks

16、ize)/如果棧滿，則追加存儲空間如果棧滿，則追加存儲空間 S.base=(SElemType S.base=(SElemType*)realloc(S.base,)realloc(S.base,(S.stacksixe+STACKINCREMENT(S.stacksixe+STACKINCREMENT*sizeof(SElemType);sizeof(SElemType);if(!S.base)exit(OVERFLOW);/if(!S.base)exit(OVERFLOW);/追加存儲空間失敗追加存儲空間失敗 S.top=S.base+S.stacksize;/S.top=S.base+S

17、.stacksize;/修改棧頂指針修改棧頂指針 S.stacksize+=STACKINCREMENT;/S.stacksize+=STACKINCREMENT;/修改當(dāng)前棧的存儲空間修改當(dāng)前棧的存儲空間 /if /if 結(jié)束結(jié)束 *S.top+=e;/S.top+=e;/先將先將 e e 送入棧頂，然后將棧頂指針加送入棧頂，然后將棧頂指針加 1 1 return OK;return OK;/Push/Push23（4）將元素彈出順序棧算法（將元素彈出順序棧算法（退棧）退棧）Status Pop(SqStack&S,SElemType&e)/如果棧如果棧 S 空，返回空，返回 ERROR；如

18、果棧；如果棧 S 不空，刪除不空，刪除 S 棧頂元素，棧頂元素，用用 e 返回其值，并返回返回其值，并返回 OK。if(S.top=S.base)return ERROR;/如果棧如果棧 S 為空，則返回為空，則返回 ERROR e=*-S.top;/先令先令 top 減減 1，再將，再將 top 所指單元值賦給所指單元值賦給 e return OK;/Pop/Pop24（5）判?？辗衽袟？辗?Int Empty(SqStack S)/如果棧如果棧 S 空，返回空，返回 1；如果棧；如果棧 S 不空，返回不空，返回 0。if(S.top=S.base)return 1;/如果棧如果棧 S 為空

19、，則返回為空，則返回 1else return 0;/如果棧如果棧 S 為空，則返回為空，則返回 0/Empty end253棧的共享?xiàng)５墓蚕碛袝r，一個程序設(shè)計(jì)中，需要使用多個同一類型的棧,這時候，可能會產(chǎn)生一個棧空間過小，容量發(fā)生溢出，而另一個?？臻g過大，造成大量存儲單元浪費(fèi)的現(xiàn)象。為了充分利用各個棧的存儲空間，這時可以采用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實(shí)現(xiàn)存儲空間優(yōu)勢互補(bǔ)。棧 1 頂 棧 2 頂 棧 1 底 棧 2 底 圖 3-3 兩個棧共享存儲單元示意圖 ?？眨簵？眨簍op1=0,top2=M-1;top1=0,top2=M-1;棧滿：棧滿：top1+1

20、=top2top1+1=top226兩個棧共享存儲單元可用如下兩個棧共享存儲單元可用如下C C語句描述：語句描述：#define MAXSIZE 100#define DUSTACKSIZE MAXSIZE typedef struct DuSqStack SElemType dataMAXSIZE;int top1;/top1 is the pointer of DuSqStack S1/top1 is the pointer of DuSqStack S1 int top2;/top2 is the pointer of DuSqStack S2/top2 is the pointer o

21、f DuSqStack S2 int flag;DuSqStack;/或：或：#define MAXSIZE 100Struct duseqstack elemtype datamaxsize;int top2;/兩個棧的棧頂指針兩個棧的棧頂指針 int flag;27（1）兩個棧共享存儲單元的進(jìn)棧算法）兩個棧共享存儲單元的進(jìn)棧算法Status DuSqStackPush(DuSqStack&S,SElemType x)/棧棧 S S 為共享順序棧類型為共享順序棧類型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 數(shù)組域；數(shù)組域；

22、/此算法將元素此算法將元素 x x 放入棧放入棧 S S 中；如果兩個棧滿，則返回中；如果兩個棧滿，則返回 ERRORERROR if(S.top1+1)=(S.top2)return ERROR;/如果兩個棧滿，則返回如果兩個棧滿，則返回 ERRORERROR else /如果棧未滿，則進(jìn)行入棧操作如果棧未滿，則進(jìn)行入棧操作 if(S.flag!=1)&(S.flag!=2)return ERROR;/如果如果 flag flag 不為不為 1,21,2，則返回，則返回 ERRORERROR else /如果如果 flag flag 為為 1 1 或或 2 2，則入棧，則入棧 switch(

23、S.flag)case 1:/標(biāo)志位標(biāo)志位 flag flag 為為 1 1 28 S.dataS.top1=x;/元素元素 x x 入棧入棧 S1S1 S.top1+;/修改棧修改棧 S1 S1 的棧頂指針的棧頂指針 break;case 2:/標(biāo)志位標(biāo)志位 flag flag 為為 2 2 S.dataS.top2=x;/元素元素 x x 入棧入棧 S2S2 S.top2-;/修改棧修改棧 S2 S2 的棧頂指針的棧頂指針 break;/switch/switch 結(jié)束結(jié)束 return OK;/else/else 結(jié)束結(jié)束 /else/else 結(jié)束結(jié)束/DuSqStackPush/Du

24、SqStackPush29（2）兩個棧共享存儲單元的退棧算法）兩個棧共享存儲單元的退棧算法Status DuSqStackPop(DuSqStack&S,SElemType&x)/棧棧 S S 為共享順序棧類型為共享順序棧類型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 數(shù)組域數(shù)組域/此算法刪除棧此算法刪除棧 S S 中棧頂元素，并用中棧頂元素，并用 x x 返回其值；如果?？?，返回其值；如果?？眨瑒t返回則返回 ERRORERRORif(S.flag!=1)&(S.flag!=2)return ERROR;/如果如果 flag1

25、,2flag1,2，則返回，則返回 ERRORERRORelelse /如果如果 flag flag 為為 1 1 或或 2 2，則出棧，則出棧switch(S.flag)case 1:/標(biāo)志位標(biāo)志位 flag flag 為為 1 1 if(S.top1 0)/如果棧如果棧 S1 S1 不空，則對不空，則對 S1 S1 進(jìn)行操作進(jìn)行操作S.top1-;/修改棧修改棧 S1 S1 的棧頂指針的棧頂指針x=S.dataS.top1;/元素元素 x x 出棧出棧 /if/if 結(jié)束結(jié)束 30 else return ERROR;/如果棧如果棧 S1 S1 為空，則返回為空，則返回 ERRORERRO

26、R break;case 2:/標(biāo)志位標(biāo)志位 flag flag 為為 1 1 if(S.top2next=NULL;（b）進(jìn)棧運(yùn)算）進(jìn)棧運(yùn)算Status Push_L(LinkStack⊤SElemType e)/將元素將元素 e 插入到棧插入到棧 S 中，成為新的棧頂元素中，成為新的棧頂元素 q=(LinkStack)malloc(sizeof(SNode);if(!q)exit(OVERFLOW);/存儲分配失敗存儲分配失敗 q-data=e;q-next=top-next;top-next=q;return OK;/Push_L/Push_L33（c）退棧運(yùn)算）退棧運(yùn)算Stat

27、us Pop_L(LinkStack&top,SElemType&e)/如果棧如果棧 S 空，返回空，返回 ERROR；如果棧；如果棧 S 不空，刪除不空，刪除 S 的棧頂元素，的棧頂元素，用用 e 返回其值，并返回返回其值，并返回 OK。if(!top-next)return ERROR;/如果棧如果棧 S 為空，則返回為空，則返回 ERROR e=top-next-data;/取出棧頂元素的值取出棧頂元素的值 q=top-next;/q 指向棧頂元素指向棧頂元素 top-next=q-next;/top-next=q-next;/刪除棧頂元素刪除棧頂元素 free(q);/free(q);

28、/釋放棧頂元素所占的空間釋放棧頂元素所占的空間 return OK;return OK;/Pop_L/Pop_L34（d）取棧頂元素）取棧頂元素Status GetTop_L(LinkStack top,SElemType&e)/如果棧如果棧 S 空，返回空，返回 ERROR；如果棧；如果棧 S 不空，用不空，用 e 返回棧返回棧 S 的的棧頂元素，并返回棧頂元素，并返回 OK。if(!top-next)return ERROR;/如果棧如果棧 S 為空，則返回為空，則返回 ERROR else /如果棧如果棧 S 不空，則返回棧頂元素不空，則返回棧頂元素 e=top-next-data;e=

29、top-next-data;return OK;return OK;/else /else 結(jié)束結(jié)束/GetTop_L/GetTop_L35（5）判?？眨┡袟？読nt empty(LinkStack*top)if(top-next=NULL)return(1);else return(0);36課課 前前 復(fù)復(fù) 習(xí)習(xí)設(shè)n 個元素的進(jìn)棧序列是P1，P2，P3，Pn，其輸出序列是1,2，3，n，若P1=3，則P2的值()。A、可能是2B、一定是2C、不可能是1D、一定是1 37 一、一、數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)，一個簡單的轉(zhuǎn)換算法是重復(fù)下述兩步，直到N等于零：X=N mo

30、d d (其中mod為求余運(yùn)算)N=N div d (其中div為整除運(yùn)算)計(jì)算過程從低位到高位，打印輸出從高位到低位3.2 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 棧在日常生活中和計(jì)算機(jī)程序設(shè)計(jì)中有著許多應(yīng)用，下面僅介紹棧在計(jì)算機(jī)中的應(yīng)用。38void Conversion(int N)/*對于任意的一個非負(fù)十進(jìn)制數(shù)N，打印出與其等值的8進(jìn)制數(shù)*/Stack S;int x;/*S為順序?；蜴湕?/InitStack(&S);while(N0)x=N%8;Push(&S,x);/*將轉(zhuǎn)換后的數(shù)字壓入棧S*/N=N/8;while(！StackEmpty(S)Pop(&S,&x);printf(%d

31、,x);算法算法3.139二、括號匹配問題二、括號匹配問題 假設(shè)表達(dá)式中允許包含三種括號假設(shè)表達(dá)式中允許包含三種括號:圓括號、圓括號、方括號和大括號。編寫一個算法判斷表達(dá)式中的方括號和大括號。編寫一個算法判斷表達(dá)式中的括號是否正確配對。括號是否正確配對。解解:設(shè)置一個括號棧設(shè)置一個括號棧,掃描表達(dá)式：遇到左括號掃描表達(dá)式：遇到左括號(包括包括(、和和)時進(jìn)棧時進(jìn)棧,遇到右括號時遇到右括號時,若棧是相匹若棧是相匹配的左括號配的左括號,則出棧則出棧,否則否則,返回返回0。若表達(dá)式掃描結(jié)束若表達(dá)式掃描結(jié)束,棧為空棧為空,返回返回1表示括號正表示括號正確匹配確匹配,否則返回否則返回0。40 int c

32、orrect(char exp,int n)char stMaxSize;int top=-1,i=0,tag=1;while(i-1)tag=0;/*若棧不空若棧不空,則不配對則不配對*/return(tag);42三、行編輯程序三、行編輯程序功能：接收用戶從終端輸入的數(shù)據(jù)或程序，并存入用戶的數(shù)據(jù)區(qū)。算法思想：設(shè)輸入緩沖區(qū)為一個棧結(jié)構(gòu)，每當(dāng)從終端接收一個字符后先作如下判別：若它既不是退格符（#）也不是退行符（）,則將該字符入棧；若是退格符（#），則從棧頂刪去一個字符；若是退行符（），則將棧清空。算法描述如下：算法描述如下：43void LineEdit()InitStack(s);ch=ge

33、tchar();While(ch!=EOF)/EOF為全文結(jié)束符 while(ch!=EOF&ch!=“n”)switch(ch)case“#”:pop(s,c);break;/當(dāng)棧非空時退棧 case“”:clearstack(s);break;/重置S為空棧 default:push(s,c);break;/有效字符進(jìn)棧，但未考慮棧滿 ch=getchar();clearstack(s);if(ch!=EOF)ch=getchar();destroystack(s);44五、五、表達(dá)式求值表達(dá)式求值 表達(dá)式求值是高級語言編譯中的一個基本問題，是棧的典型應(yīng)用實(shí)例。任何一個表達(dá)式都是由操作數(shù)(

34、operand)、運(yùn)算符(operator)和界限符(delimiter)組成的。操作數(shù)操作數(shù)既可以是常數(shù)，也可以是被說明為變量或常量的標(biāo)識符；運(yùn)算符運(yùn)算符可以分為算術(shù)運(yùn)算符、關(guān)系運(yùn)算符和邏輯運(yùn)算符三類；基基本界限符本界限符有左右括號和表達(dá)式結(jié)束符等。451.1.無括號算術(shù)表達(dá)式求值無括號算術(shù)表達(dá)式求值 表達(dá)式計(jì)算表達(dá)式計(jì)算 程序設(shè)計(jì)語言中都有計(jì)算表達(dá)式的問題，這是語言編譯中的典型問題。(1)表達(dá)式形式：由運(yùn)算對象、運(yùn)算符及必要的表達(dá)式括號組成；(2)表達(dá)式運(yùn)算：運(yùn)算時要有一個正確的運(yùn)算形式順序。由于某些運(yùn)算符可能具有比別的運(yùn)算符更高的優(yōu)先級，因此表達(dá)式不可能嚴(yán)格的從左到右，見圖3.5。46圖

35、3.5 表達(dá)式運(yùn)算及運(yùn)算符優(yōu)先級 47圖3.6 無括號算術(shù)表達(dá)式的處理過程 置空棧OVS、OPTR讀字符WW是操作符OPTR棧空W優(yōu)先級OPTR棧頂優(yōu)先級取OVS頂、次頂和OPTR頂，形成運(yùn)算結(jié)果T(i),然后退OVS頂、次頂和OPTR頂，將T(i)置入OVS棧頂進(jìn)OVS進(jìn)OPTR棧W#結(jié)束NYYYNYNN48 2.2.算術(shù)表達(dá)式處理規(guī)則算術(shù)表達(dá)式處理規(guī)則 (1)規(guī)定優(yōu)先級表。(2)設(shè)置兩個棧：OVS(運(yùn)算數(shù)棧)和OPTR(運(yùn)算符棧)。(3)自左向右掃描，遇操作數(shù)進(jìn)OVS，遇操作符則與OPTR棧頂優(yōu)先數(shù)比較：當(dāng)前操作符OPTR棧頂,當(dāng)前操作符進(jìn)OPTR棧；當(dāng)前操作符OPTR棧頂，OVS棧頂、次

36、頂和OPTR棧頂，退棧形成運(yùn)算T(i)，T(i)進(jìn)OVS棧。例：實(shí)現(xiàn)A/BC+D*E的運(yùn)算過程時棧區(qū)變化情況如圖3.7所示。49圖3.7 A/BC+D*E運(yùn)算過程的棧區(qū)變化情況示意圖 CBAOVS/OPTROPTR生成BC，運(yùn)算結(jié)果T(1)T(1)AOVS/OPTROPTR/生成A/T(1),運(yùn)算結(jié)果T(2)T(2)/OPTR為空，進(jìn)棧DT(2)右邊界#OPTR*生成D*E，運(yùn)算結(jié)果T(3)T(3)T(2)生成T(3)T(2)，得到T(4)T(4)E*右邊界#OPTR+*50 3.3.帶括號算術(shù)表達(dá)式帶括號算術(shù)表達(dá)式 假設(shè)操作數(shù)是整型常數(shù)，運(yùn)算符只含加、減、乘、除等四種運(yùn)算符，界限符有左右括號

37、和表達(dá)式起始、結(jié)束符“”，如：（7+15）*（23-28/4）。引入表達(dá)式起始、結(jié)束符是為了方便。要對一個簡單的算術(shù)表達(dá)式求值，首先要了解算術(shù)四則運(yùn)算的規(guī)則，即：(1)從左算到右；(2)先乘除，后加減；(3)先括號內(nèi)，后括號外。51 運(yùn)算符和界限符可統(tǒng)稱為算符，它們構(gòu)成的集合命名為OPTR。根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算過程中，任意兩個前后相繼出現(xiàn)的算符1和2之間的優(yōu)先關(guān)系必為下面三種關(guān)系之一：12，1的優(yōu)先權(quán)高于2。52表表 3-1 3-1 算符之間的優(yōu)先關(guān)系算符之間的優(yōu)先關(guān)系 53 實(shí)現(xiàn)算符優(yōu)先算法時需要使用兩個工作棧：一個稱作optr，用以存放運(yùn)算符；另一個稱作opnd，用以存放操作數(shù)或運(yùn)

38、算的中間結(jié)果。算法的基本過程如下：首先初始化操作數(shù)棧opnd和運(yùn)算符棧optr，并將表達(dá)式起始符“”壓入運(yùn)算符棧；依次讀入表達(dá)式中的每個字符，若是操作數(shù)則直接進(jìn)入操作數(shù)棧opnd，若是運(yùn)算符，則與運(yùn)算符棧optr的棧頂運(yùn)算符進(jìn)行優(yōu)先權(quán)比較，并做如下處理：54 (1)若棧頂運(yùn)算符的優(yōu)先級低于剛讀入的運(yùn)算符，則讓剛讀入的運(yùn)算符進(jìn)optr棧；(2)若棧頂運(yùn)算符的優(yōu)先級高于剛讀入的運(yùn)算符，則將棧頂運(yùn)算符退棧，送入，同時將操作數(shù)棧opnd退棧兩次，得到兩個操作數(shù)a、b，對a、b進(jìn)行運(yùn)算后，將運(yùn)算結(jié)果作為中間結(jié)果推入opnd棧；(3)若棧頂運(yùn)算符的優(yōu)先級與剛讀入的運(yùn)算符的優(yōu)先級相同，說明左右括號相遇，只需

39、將棧頂運(yùn)算符（左括號）退棧即可。55算法具體描述如下：算法具體描述如下：int ExpEvaluation()/*讀入一個簡單算術(shù)表達(dá)式并計(jì)算其值。operator和operand分別為運(yùn)算符棧和運(yùn)算數(shù)棧，OPS為運(yùn)算符集合*/InitStack(&opnd);InitStack(&optr);Push(&optr,);printf(nnPlease input an expression(Ending with):);c=getchar();while(c!=|GetTop(optr)!=)/*GetTop()通過函數(shù)值返回棧頂元素*/56 if(!In(c,OP)Push(&opnd,c)

40、;c=getchar();else switch(Precede(GetTop(optr),c)case:Pop(&optr,&theta);57 Pop(&opnd,&b);Pop(&opnd,&a);v=Execute(a,theta,b);/*對a和b進(jìn)行op運(yùn)算*/Push(&opnd,v);break;return(GetTop(opnd);例求表達(dá)式1+2*3-4/2的值，棧的變化如下。58步驟 操作數(shù)棧 運(yùn)算符棧 說明 開始兩棧均為空111進(jìn)入操作數(shù)棧+進(jìn)入運(yùn)算符棧2進(jìn)入操作數(shù)棧*進(jìn)入運(yùn)算符棧3進(jìn)入操作數(shù)棧退棧2*3進(jìn)入操作數(shù)棧退棧1+6進(jìn)入操作數(shù)棧234567891+12+12

41、+1117+*236+*+59步驟 操作數(shù)棧 運(yùn)算符棧 說明 107-進(jìn)入運(yùn)算符棧4進(jìn)入操作數(shù)棧/進(jìn)入運(yùn)算符棧2進(jìn)入操作數(shù)棧退棧4/2進(jìn)入操作數(shù)棧退棧7-2進(jìn)入操作數(shù)棧111213141516177 4-7 4-/7 4 2-/77 2-560當(dāng)然，算術(shù)表達(dá)式除了簡單求值外，還會涉及到算術(shù)表達(dá)式的兩種表示方法，即中綴表示法和后綴表示法。中綴表達(dá)式求值較麻煩（須考慮運(yùn)算符的優(yōu)先級，甚至還要考慮圓括號），而后綴表達(dá)式求值較方便（無須考慮運(yùn)算符的優(yōu)先級及圓括號）。下面將介紹算術(shù)表達(dá)式的中綴表示和后綴表示及它們的求值規(guī)律，例如，對于下列各中綴表達(dá)式：（1）3/5+8（2）18-9*(4+3)（3）(2

42、5+x)*(a*(a+b)+b)對應(yīng)的后綴表達(dá)式為：(1)3 5 /8 +(2)18 9 4 3 +*-(3)25 x +a a b +*b +*614.4.中綴表達(dá)式變成等價的后綴表達(dá)式中綴表達(dá)式變成等價的后綴表達(dá)式 將中綴表達(dá)式變成等價的后綴表達(dá)式，表達(dá)式中操作數(shù)次序不變，運(yùn)算符次序發(fā)生變化，同時去掉了圓括號。轉(zhuǎn)換規(guī)則是：設(shè)立一個棧，存放運(yùn)算符，首先棧為空，編譯程序從左到右掃描中綴表達(dá)式，若遇到操作數(shù)，直接輸出，并輸出一個空格作為兩個操作數(shù)的分隔符；若遇到運(yùn)算符，則必須與棧頂比較，運(yùn)算符級別比棧頂級別高則進(jìn)棧，否則退出棧頂元素并輸出，然后輸出一個空格作分隔符；若遇到左括號，進(jìn)棧；若遇到右括

43、號，則一直退棧輸出，直到退到左括號止。當(dāng)棧變成空時，輸出的結(jié)果即為后綴表達(dá)式。將中綴表達(dá)式(1+2)*(8-2)/(7-4)變成等價的后綴表達(dá)式。現(xiàn)在用棧來實(shí)現(xiàn)該運(yùn)算，棧的變化及輸出結(jié)果如下62步驟棧中元素 輸出結(jié)果 說明1(（進(jìn)棧2(1輸出13(+1+進(jìn)棧4(+1 2輸出25 1 2 +退棧輸出，退棧到（止6*1 2 +*進(jìn)棧7*(1 2 +（進(jìn)棧8*(1 2 +（進(jìn)棧9*(1 2 +8輸出810*(-1 2 +8 -進(jìn)棧6311*(-1 2 +8 2輸出212*(1 2 +8 2 -退棧輸出，退棧到（止13*(/1 2 +8 2 -/進(jìn)棧14*(/(1 2 +8 2 -（進(jìn)棧15*(/(1

44、 2 +8 2 -7輸出716*(/(-1 2 +8 2 -7-進(jìn)棧17*(/(-1 2 +8 2 -7 4輸出418*(/1 2 +8 2 -7 4 -退棧輸出，退棧到（止19*1 2 +8 2 -7 4 -/退棧輸出，退棧到（止20 1 2 +8 2 -7 4 -/*退棧并輸出步驟 棧中元素 輸出結(jié)果 說明645.5.后綴表達(dá)式的求值后綴表達(dá)式的求值 將中綴表達(dá)式轉(zhuǎn)換成等價的后綴表達(dá)式后，求值時，不需要再考慮運(yùn)算符的優(yōu)先級，只需從左到右掃描一遍后綴表達(dá)式即可。具體求值步驟為：設(shè)置一個棧，開始時，棧為空，然后從左到右掃描后綴表達(dá)式，若遇操作數(shù)，則進(jìn)棧；若遇運(yùn)算符，則從棧中退出兩個元素，先退出

45、的放到運(yùn)算符的右邊，后退出的放到運(yùn)算符左邊，運(yùn)算后的結(jié)果再進(jìn)棧，直到后綴表達(dá)式掃描完畢。此時，棧中僅有一個元素，即為運(yùn)算的結(jié)果。例，求后綴表達(dá)式：1 2 +8 2 -7 4 -/*的值，棧的變化情如下：65步驟棧中元素 說明111進(jìn)棧21 22進(jìn)棧3 遇+號退棧2和1431+2=3的結(jié)果3進(jìn)棧53 88進(jìn)棧63 8 22進(jìn)棧73遇-號退棧2和883 68-2=6的結(jié)果6進(jìn)棧93 6 77進(jìn)棧103 6 7 44進(jìn)棧66步驟棧中元素 說明113 6遇-號退棧4和7123 6 37-4=3的結(jié)果3進(jìn)棧133遇/號退棧3和6143 26/3=2的結(jié)果2進(jìn)棧15 遇*號退棧2和31663*2=6進(jìn)棧1

46、76掃描完畢，運(yùn)算結(jié)束 從上可知，最后求得的后綴表達(dá)式之值為6，與用中綴表達(dá)式求得的結(jié)果一致，但后綴式求值要簡單得多。67五、五、求解迷宮問題求解迷宮問題 求迷宮問題就是求出從入口到出口的路徑。在求迷宮問題就是求出從入口到出口的路徑。在求解時求解時,通常用的是通常用的是“窮舉求解窮舉求解”的方法的方法,即從入即從入口出發(fā)口出發(fā),順某一方向向前試探順某一方向向前試探,若能走通若能走通,則繼續(xù)往則繼續(xù)往前走；否則沿原路退回前走；否則沿原路退回,換一個方向再繼續(xù)試探換一個方向再繼續(xù)試探,直至所有可能的通路都試探完為止。為了保證在直至所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回任何位

47、置上都能沿原路退回(稱為回溯稱為回溯),),需要用一需要用一個后進(jìn)先出的棧來保存從入口到當(dāng)前位置的路徑。個后進(jìn)先出的棧來保存從入口到當(dāng)前位置的路徑。首先用如圖首先用如圖3.33.3所示的方塊圖表示迷宮。對所示的方塊圖表示迷宮。對于圖中的每個方塊于圖中的每個方塊,用空白表示通道用空白表示通道,用陰影表示用陰影表示墻。所求路徑必須是簡單路徑墻。所求路徑必須是簡單路徑,即在求得的路徑上即在求得的路徑上不能重復(fù)出現(xiàn)同一通道塊。不能重復(fù)出現(xiàn)同一通道塊。6869 為了表示迷宮為了表示迷宮,設(shè)置一個數(shù)組設(shè)置一個數(shù)組mg,其中每個元素表示其中每個元素表示一個方塊的狀態(tài)一個方塊的狀態(tài),為為0時表示對應(yīng)方塊是通道

48、時表示對應(yīng)方塊是通道,為為1時表示時表示對應(yīng)方塊為墻對應(yīng)方塊為墻,如圖如圖3.3所示的迷宮所示的迷宮,對應(yīng)的迷宮數(shù)組對應(yīng)的迷宮數(shù)組mg如下如下:int mgM+1N+1=/*M=10,N=10*/1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;70

49、while(while(棧不空棧不空)若當(dāng)前位置可通若當(dāng)前位置可通，則則 將當(dāng)前位置插入棧頂；將當(dāng)前位置插入棧頂；/納入路徑納入路徑 若該位置是出口位置，則算法結(jié)束；若該位置是出口位置，則算法結(jié)束；/此時棧中存放的是一條從入口位置到出口位置的路徑此時棧中存放的是一條從入口位置到出口位置的路徑否則切換當(dāng)前位置的北鄰方塊為新的當(dāng)前位置；否則切換當(dāng)前位置的北鄰方塊為新的當(dāng)前位置；否則否則 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不

50、空但棧頂位置的四周均不可通，若棧不空但棧頂位置的四周均不可通，則則 刪去棧頂位置；刪去棧頂位置；/從路徑中刪去該通道塊從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至?？眨恢敝琳业揭粋€可通的相鄰塊或出棧至?？?；算法描述：算法描述：71void mgpath()/*路徑為路徑為:(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+;/*初始方塊進(jìn)棧初始方塊進(jìn)棧*/Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while(top-1)/*棧不空時循環(huán)

51、棧不空時循環(huán)*/i=Stacktop.i;j=Stacktop.j;di=Stacktop.di;if(i=M-2&j=N-2)/*找到了出口找到了出口,輸出路徑輸出路徑*/printf(迷宮路徑如下迷宮路徑如下:n);for(k=0;k=top;k+)printf(t(%d,%d),Stackk.i,Stackk.j);if(k+1)%5=0)printf(n);printf(n);return;72 find=0;while(didata+Sum(head-next);793)問題的求解方法是遞歸的問題的求解方法是遞歸的 有些問題的解法是遞歸的有些問題的解法是遞歸的,典型的有典型的有Han

52、oi問題求問題求解解,該問題描述是：設(shè)有該問題描述是：設(shè)有3個分別命名為個分別命名為X,Y和和Z的塔座的塔座,在塔座在塔座X上有上有n個直徑各不相同個直徑各不相同,從小到大依次編號為從小到大依次編號為1,2,n的盤片的盤片,現(xiàn)要求將現(xiàn)要求將X塔座上的塔座上的n個盤片移到塔座個盤片移到塔座Z上并仍按同樣順序疊放上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在則：每次只能移動一個盤片；盤片可以插在X,Y和和Z中任一塔座；任何時候都不能將一個較大的盤片放在中任一塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設(shè)計(jì)遞歸求解算法較小的盤片

53、上。設(shè)計(jì)遞歸求解算法,并將其轉(zhuǎn)換為非并將其轉(zhuǎn)換為非遞歸算法。遞歸算法。設(shè)設(shè)Hanoi(n,x,y,z)表示將表示將n個盤片從個盤片從x通過通過y移動到移動到z上上,遞歸分解的過程是：遞歸分解的過程是：80Hanoi(n,a,b,c)Hanoi(n-1,a,c,b)；move(n,a,c):將第將第n個圓盤從個圓盤從a移到移到c；Hanoi(n-1,b,a,c)321a321abc321abc321abc321abcbc321abc321abc321abc圖 Hanoi塔的遞歸函數(shù)運(yùn)行示意圖 813 3、遞歸模型遞歸模型 遞歸模型是遞歸算法的抽象遞歸模型是遞歸算法的抽象,它反映一個遞歸問題它反映

54、一個遞歸問題的遞歸結(jié)構(gòu)的遞歸結(jié)構(gòu),例如例如,前面的遞歸算法對應(yīng)的遞歸模型如下：前面的遞歸算法對應(yīng)的遞歸模型如下：fun(1)=1 (1)fun(n)=n*fun(n-1)n1 (2)其中其中,第一個式子給出了遞歸的終止條件第一個式子給出了遞歸的終止條件,第二個式第二個式子給出了子給出了fun(n)的值與的值與fun(n-1)的值之間的關(guān)系的值之間的關(guān)系,我們把我們把第一個式子稱為第一個式子稱為遞歸出口遞歸出口,把第二個式子稱為把第二個式子稱為遞歸體遞歸體。82 實(shí)際上實(shí)際上,遞歸思路是把一個不能或不好直接求解的遞歸思路是把一個不能或不好直接求解的“大問題大問題”轉(zhuǎn)化成一個或幾個轉(zhuǎn)化成一個或幾個

55、“小問題小問題”來解決來解決,再把再把這些這些“小問題小問題”進(jìn)一步分解成進(jìn)一步分解成更小的更小的“小問題小問題”來解來解決決,如此分解如此分解,直至每個直至每個“小問題小問題”都可以直接解決都可以直接解決(此此時分解到遞歸出口時分解到遞歸出口)。但遞歸分解不是隨意的分解。但遞歸分解不是隨意的分解,遞歸遞歸分解要保證分解要保證“大問題大問題”與與“小問題小問題”相似相似,即即求解過程求解過程與環(huán)境都相似與環(huán)境都相似。83 fun(5)d1:fun(4)d2:fun(3)d3:fun(2)d4:fun(1)返回 1 fun(2)=2 fun(3)=6 fun(4)=24 fun(5)=120 求

56、解求解fun(5)的過程如下：的過程如下：5!844 4 遞歸問題的優(yōu)點(diǎn)遞歸問題的優(yōu)點(diǎn) 通過上面的例子可看出，遞歸既是強(qiáng)有力的數(shù)學(xué)方法，也是程序設(shè)計(jì)中一個很有用的工具。其特點(diǎn)是對遞歸問題描述簡捷，結(jié)構(gòu)清晰，程序的正確性容易證明。5 5、消除遞歸的原因、消除遞歸的原因 其一：有利于提高算法時空性能，因?yàn)檫f歸執(zhí)行時需要系統(tǒng)提供隱式棧實(shí)現(xiàn)遞歸，效率低且費(fèi)時。其二：無應(yīng)用遞歸語句的語言設(shè)施環(huán)境條件，有些計(jì)算機(jī)語言不支持遞歸功能，如FORTRAN語言中無遞歸機(jī)制。其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時不合適，也存在一個把遞歸算法轉(zhuǎn)化為非遞歸算法的需求。853.4 3.4 隊(duì)列隊(duì)列 a1 a2 .

57、an 入隊(duì) 隊(duì)頭 隊(duì)尾 出隊(duì) 圖 3-13 隊(duì)列示意圖 隊(duì)列簡稱隊(duì)隊(duì)列簡稱隊(duì),它也是一種運(yùn)算受限的線性表它也是一種運(yùn)算受限的線性表,其限其限制僅允許在表的一端進(jìn)行插入制僅允許在表的一端進(jìn)行插入,而在表的另一端進(jìn)行而在表的另一端進(jìn)行刪除。刪除。我們把進(jìn)行插入的一端稱做我們把進(jìn)行插入的一端稱做隊(duì)尾隊(duì)尾(rear),進(jìn)行刪除進(jìn)行刪除的一端稱做的一端稱做隊(duì)首隊(duì)首(front)。向隊(duì)列中插入新元素稱為向隊(duì)列中插入新元素稱為進(jìn)隊(duì)進(jìn)隊(duì)或或入隊(duì)入隊(duì),新元素進(jìn)隊(duì)新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱為出隊(duì)出隊(duì)或或離隊(duì)離隊(duì),元素出隊(duì)后元素出隊(duì)后,其后繼元素就成

58、為隊(duì)首元素。其后繼元素就成為隊(duì)首元素。86 二、隊(duì)列的基本運(yùn)算二、隊(duì)列的基本運(yùn)算 1.初始化操作：InitQueue(&Q)。設(shè)置一個空隊(duì)列。2.判空操作：QueueEmpty(Q)。若隊(duì)列為空，則返回TRUE，否則返回FALSE。3.進(jìn)隊(duì)操作：EnQueue(&Q，x)。在隊(duì)列Q的隊(duì)尾插入x。操作成功，返回值為TRUE，否則返回值為FALSE。4.出隊(duì)操作：DeQueue(&Q,&x)。使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用x帶回其值。操作成功，返回值為RUE，否則返回值為FALSE。87 5.取隊(duì)頭元素操作：GetHead（Q,&x）。用x取得隊(duì)元素的值。操作成功，返回值為TRUE，否則返回值為FA

59、LSE。6.隊(duì)列置空操作：ClearQueue(&Q)。將隊(duì)列Q置為空隊(duì)列。7.隊(duì)列銷毀操作DestroyQueue(&Q)。釋放隊(duì)列的空間。8.求隊(duì)列長度操作：QueueLength(Q)。返回隊(duì)列Q的元素個數(shù)，即隊(duì)列Q的長度。88三、三、隊(duì)列的抽象數(shù)據(jù)類型描述隊(duì)列的抽象數(shù)據(jù)類型描述 隊(duì)列的抽象數(shù)據(jù)類型可描述為：隊(duì)列的抽象數(shù)據(jù)類型可描述為：ADT QUEUEADT QUEUE 數(shù)據(jù)元素?cái)?shù)據(jù)元素：D=ai|ai ElemSet，i=1,2,n,n 0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系：R1=|ai-1,ai D,i=1,2,n 基本操作：基本操作：InitQueue(&Q)：初始化操作。設(shè)置一個空隊(duì)列。Que

60、ueEmpty(Q)：判空操作。若隊(duì)列為空，則返回TRUE，否則返回FALSE。EnQueue(&Q，x)：進(jìn)隊(duì)操作。在隊(duì)列Q的隊(duì)尾插入x。操作成功，返回值為TRUE，否則返回值為FALSE。89DeQueue(&Q,&x)：出隊(duì)操作。使隊(duì)列Q的隊(duì)頭元素出隊(duì)，并用x帶回其值。操作成功，返回值為RUE，否則返回值為FALSE。GetHead（Q,&x）：取隊(duì)頭元素操作。用x取得隊(duì)元素的值。操作成功，返回值為TRUE，否則返回值為FALSE。ClearQueue(&Q)：隊(duì)列置空操作。將隊(duì)列Q置為空隊(duì)列。DestroyQueue(&Q)：隊(duì)列銷毀操作。釋放隊(duì)列的空間。QueueLength(Q)。

61、返回隊(duì)列Q的元素個數(shù)，即隊(duì)列Q的長度。ADT Queue 90四、隊(duì)列的表示和實(shí)現(xiàn)四、隊(duì)列的表示和實(shí)現(xiàn) 1.鏈隊(duì)列鏈隊(duì)列 圖3.14 鏈隊(duì)列(b)非空的鏈隊(duì)列a1anrearfront(a)空的鏈隊(duì)列隊(duì)尾指針rear隊(duì)頭指針front隊(duì)列的鏈?zhǔn)酱鎯ΓQ為鏈隊(duì)列。一個鏈隊(duì)列顯然需要兩個分別指示隊(duì)頭（頭指針）和隊(duì)尾（尾指針）指針才能唯一確定。91與前面介紹的單鏈表類似，但為了使頭指針，尾指針統(tǒng)一起來，鏈隊(duì)列可以定義如下：typedef struct QNode QElemType data;/*數(shù)據(jù)域*/struct QNode *next;/*指針域*/Qnode,*QueuePtr;typed

62、ef struct QueuePtr front;QueuePtr rear;LinkQueue;rear 頭 front an 頭 front a1 a2 rear（a）空鏈隊(duì)列 (b)非空鏈隊(duì) 92 鏈隊(duì)列的基本操作鏈隊(duì)列的基本操作（1）初始化操作。int InitQueue(LinkQueue&Q)/*將Q初始化為一個空的鏈隊(duì)列*/Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q-front-next=NULL;return OK;93（2）入隊(duì)操作。Status EnQueue(Link

63、Queue&Q,QElemType e)/*將數(shù)據(jù)元素x插入到隊(duì)列Q中*/QueuePtr p;p=(QueuePtr*)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q-rear-next=p;Q-rear=p;return OK;94（3）出隊(duì)操作。int DeQueue(LinkQueue&Q,QElemType&e)/*將隊(duì)列Q的隊(duì)頭元素出隊(duì)，并存放到x所指的存儲空間中*/QueuePtr p;if(Q-front=Q-rear)return ERROR;p=Q-front-next;e=p-data;Q-

64、front-next=p-next;/*隊(duì)頭元素p出隊(duì)*/if(Q-rear=p)/*如果隊(duì)中只有一個元素p，則p出隊(duì)后成為空隊(duì)*/Q-rear=Q-front;free(p);/*釋放存儲空間*/return OK;952.循環(huán)隊(duì)列循環(huán)隊(duì)列:隊(duì)列的順序表示和實(shí)現(xiàn)隊(duì)列的順序表示和實(shí)現(xiàn) 圖3.15 隊(duì)列的基本操作 Queue6543210rearfront(1)空隊(duì)列543210rearfrontcbad(2)a、b、c、d依 次 入隊(duì)543210rearfrontd(3)a、b、c出 隊(duì)543210rearfrontdef(4)e、f入 隊(duì)用一組連續(xù)的存儲單元依次存放隊(duì)列的元素，并設(shè)兩個指針f

65、ront、rear分別指示隊(duì)頭和隊(duì)尾元素的位置。front：指向?qū)嶋H的隊(duì)頭；rear：指向?qū)嶋H隊(duì)尾的下一位置。初態(tài)：frontrear0；隊(duì)空：frontrear;隊(duì)滿：rearM;入隊(duì)：qrear=x;rear rear+1;出隊(duì)：x=qfront;front=front+1;96圖3.16 循環(huán)隊(duì)列 012354rearfront(a)空隊(duì)列012354e6e7e8e3e4e5012354(b)隊(duì)列滿(b)一般情況frontreare3e4e5frontrear假溢出的解決方法假溢出的解決方法：（1）將隊(duì)中元素向隊(duì)頭移動；（2）采用循環(huán)隊(duì)列：q0接在QM-1之后初態(tài)：frontrear0或

66、M-1；隊(duì)空：frontrear;入隊(duì)：qrear=x；rear(rear+1)%M;出隊(duì)：x=qfront;front=(front+1)%M;隊(duì)滿：留一個空間不用(rear+1)%M=front;或另設(shè)一個標(biāo)志以區(qū)分隊(duì)空和隊(duì)滿。97循環(huán)隊(duì)列的類型定義：define MAXSIZE 100 /*隊(duì)列的最大長度*/typedef struct QElemType elementMAXSIZE;/*隊(duì)列的元素空間*/int front;/*頭指針指示器*/int rear;/*尾指針指示器*/SeqQueue;98循環(huán)隊(duì)列的基本操作：循環(huán)隊(duì)列的基本操作：（1）初始化操作。void InitQueue（SeqQueue&Q）/*將*Q初始化為一個空的循環(huán)隊(duì)列*/Q-front=Q-rear=0;99（2）入隊(duì)操作。int EnterQueue(SeqQueue*Q,QueueElementType x)/*將元素x入隊(duì)*/if(Q-rear+1)%MAXSIZE=Q-front)/*隊(duì)列已經(jīng)滿了*/return ERROR;Q-elementQ-rear=x;Q-rear=(Q-rear+