1第三章棧和隊列2【課前思考】【課前思考】1.什么是線性結構？什么是線性結構？簡單地說，線性結構是一個數(shù)據(jù)元素的序列。2.你見過餐館中一疊一疊的盤子嗎？如果它們是按你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,n 的次序往上疊的，那么使用時候的次序應的次序往上疊的，那么使用時候的次序應是什么樣的？是什么樣的？必然是依從上往下的次序，即n,2,1。它們遵循的是后進先出的規(guī)律，這正是本章要討論的棧的結構特點。3.在日常生活中，為了維持正常的社會秩序而出現(xiàn)在日常生活中，為了維持正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？的常見現(xiàn)象是什么？是排隊。在計算機程序中，模擬排隊的數(shù)據(jù)結構是隊列。3【學習目標】【學習目標】1.掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應的應用問題中正確選用它們。2.熟練掌握棧類型的兩種實現(xiàn)方法。3.熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。4.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。4 棧和隊列是在程序設計中被廣泛使用的兩種線性數(shù)據(jù)結構，因此本章的學習重點在于掌握這兩種結構的特點，以便能在應用問題中正確使用?！局R點】【知識點】順序棧、鏈棧、循環(huán)隊列、鏈隊列【重點和難點】【重點和難點】5【學習指南】【學習指南】在這一章中，主要是學習如何在求解應用問題中適當?shù)貞脳：完犃?，棧和隊列在兩種存儲結構中的實現(xiàn)都不難，但應該對它們了如指掌，特別要注意它們的基本操作實現(xiàn)時的一些特殊情況，如棧滿和棧空、隊滿和隊空的條件以及它們的描述方法。本章要求必須完成的算法設計題為：3.15，3.17，3.19，3.22，3.27,3.28，3.30，3.31，3.32。其中前4個主要是練習棧的應用，后4個主要是有關隊列的實現(xiàn)方法的練習。6通常稱，棧和隊列是限定插入和刪除插入和刪除只能只能在表的“端點端點”進行的線性表。線性表線性表 棧棧 隊列隊列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棧和隊列是兩種常用的數(shù)據(jù)類型棧和隊列是兩種常用的數(shù)據(jù)類型7 目目 錄錄83.1 棧棧一、棧的定義一、棧的定義 棧棧(stack)(stack)作為一種限定性線性表，是將線性表的插入插入和刪除刪除運算限制為僅在表的一端僅在表的一端進行。通常將表中允許進行插入、刪除操作的一端稱為棧頂棧頂(Top)(Top)，因此棧頂?shù)漠斍拔恢檬莿討B(tài)變化的，它由一個稱為棧頂指針的位置指示器指示。同時表的另一端為固定的一端，被稱為棧底棧底(Bottom)(Bottom)。當棧中沒有元素時稱為空棧。棧的插入操作被形象地稱為進?；蛉霔?，刪除操作稱為出?；蛲藯?。插入：最先放入棧中元素在棧底，最后放入的元素在棧頂；刪除：最后放入的元素最先刪除，最先放入的元素最后刪除。棧是一種后進先出(Last In First OutLast In First Out)的線性表，簡稱為LIFO表。9ana2a1進棧出棧棧頂棧底進棧出棧(a)棧的示意圖(b)鐵路調(diào)序棧的表示圖圖3.1 棧棧ana2a1進棧出棧棧頂棧底進棧出棧(a)棧的示意圖(b)鐵路調(diào)序棧的表示10 例：設一個棧的輸入序列為例：設一個棧的輸入序列為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是不可是不可能的能的,因為因為D先出來先出來,說明說明A,B,C,D均在棧中均在棧中,按照入棧按照入棧順序順序,在棧中順序應為在棧中順序應為D,C,B,A,出棧的順序只能是出棧的順序只能是D,C,B,A。所以本題答案為。所以本題答案為D。11二、棧的主要操作二、棧的主要操作 1.初始化棧：初始化棧：InitStack(&S)將棧S置為一個空棧(不含任何元素)。2.進棧：進棧：PUSH(&S,X)將元素X插入到棧S中，也稱為“入棧”、“插入”、“壓入”。3.出棧：出棧：POP(&S，&e)刪除棧S中的棧頂元素，也稱為”退?！薄ⅰ皠h除”、“彈出”。4.取棧頂元素：取棧頂元素：GETTOP(S，&e)取棧S中棧頂元素。5.判棧空：判?？眨篍MPTY(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ù)關系數(shù)據(jù)關系：R1=|ai-1,ai D,i=1,2,n 基本操作：基本操作：InitStack(&S)操作前提：S為未初始化的棧。操作結果：將S初始化為空棧。ClearStack(&S)操作前提：棧S已經(jīng)存在。操作結果：將棧S置成空棧。StackEmpty(S)操作前提：棧S已經(jīng)存在。操作結果：若棧S為空，則返回TRUE,否則FALSE。13 StackLength(S)操作前提：棧S已經(jīng)存在。操作結果：返回S的元素個數(shù)即棧的長度。IsFull(S)操作前提：棧S已經(jīng)存在。操作結果：判棧滿函數(shù)，若S棧已滿，則函數(shù)值為TRUE，否則為FALSE。StackTraverse(S,visit()操作前提：棧S已經(jīng)存在且非空。操作結果：從棧底到棧頂依次對S底每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失效。14 Push(&S,e)操作前提：棧S已經(jīng)存在。操作結果：在S的頂部插入(亦稱壓入)元素e；若S棧未滿，將e插入棧頂位置，若棧已滿，則返回FALSE，表示操作失敗，否則返回TRUE。Pop(&S,&e)操作前提：棧S已經(jīng)存在。操作結果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值；若棧為空，返回值為FALSE，表示操作失敗，否則返回TRUE。GetTop(S,&e)操作前提：棧S已經(jīng)存在。操作結果：取棧S的頂部元素。與Pop(&S,&e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢?。ADT Stack15 1.順序棧順序棧 順序棧是用順序存儲結構實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時由于棧的操作的特殊性，還必須附設一個位置指針位置指針toptop（棧頂指針）來動態(tài)地指示棧頂元素動態(tài)地指示棧頂元素在順序棧中的位位置置。通常以top=0或 top=-1表示空棧。順序棧的存儲結構可以用C語言中的一維數(shù)組來表示。棧的順序存儲結構定義如下：四、四、棧的表示和實現(xiàn)棧的表示和實現(xiàn) 16#define STACK_INIT_SIZE 100/存儲空間初始分配量#define STACKINCREMENT 10 /存儲空間分配增量typedef struct SElemType*base;/在棧構造前和銷毀后base值為NULL SElemType*top;/棧頂指針 int stacksize;SqStack;/當前已分配存儲空間或簡單定義如下：#define M 100 int sM;int top;17圖3.2 順序棧中的進棧和出棧 Top指向棧頂元素指向棧頂元素初態(tài)：初態(tài)：top=-1;空棧，棧中無元素，進棧：進棧：top=top+1;stop=x;退棧：退棧：取stop;top=top-1;棧滿：棧滿：top=M-1;棧溢出（上溢），不能再進棧（錯誤狀態(tài)）top=-1時不能退棧，下溢（正常狀態(tài)，常作控制條件）18（1 1）構造空順序棧算法）構造空順序棧算法:初始化棧初始化棧Status InitStack(SqStack&S)/構造一個空棧構造一個空棧 S SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/為棧分配存儲空間失敗為棧分配存儲空間失敗S.top=S.base;/令棧頂指針令棧頂指針 =棧底指針棧底指針/設置棧的當前可使用的最大容量設置棧的當前可使用的最大容量S.stacksize=STACK_INIT_SIZE;return OK;/InitStack/InitStack2.2.順序?；静僮鞯膶崿F(xiàn)如下順序?；静僮鞯膶崿F(xiàn)如下:19程序描述：程序描述：/This program is to initialize a stack#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 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(ERROR);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 返回棧返回棧 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）將元素壓入順序棧算法（將元素壓入順序棧算法（進棧）進棧）Status Push(SqStack&S,SElemType e)/將元素將元素 e 插入到棧插入到棧 S 中，成為新的棧頂元素中，成為新的棧頂元素 if(S.top-S.base S.stacksize)/如果棧滿，則追加存儲空間如果棧滿，則追加存儲空間 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.stacksize;/修改棧頂指針修改棧頂指針 S.stacksize+=STACKINCREMENT;/S.stacksize+=STACKINCREMENT;/修改當前棧的存儲空間修改當前棧的存儲空間 /if /if 結束結束 *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；如果棧；如果棧 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 為空，則返回為空，則返回 1else return 0;/如果棧如果棧 S 為空，則返回為空，則返回 0/Empty end253棧的共享棧的共享有時，一個程序設計中，需要使用多個同一類型的棧,這時候，可能會產(chǎn)生一個?？臻g過小，容量發(fā)生溢出，而另一個棧空間過大，造成大量存儲單元浪費的現(xiàn)象。為了充分利用各個棧的存儲空間，這時可以采用多個棧共享存儲單元，即給多個棧分配一個足夠大的存儲空間，讓多個棧實現(xiàn)存儲空間優(yōu)勢互補。棧 1 頂 棧 2 頂 棧 1 底 棧 2 底 圖 3-3 兩個棧共享存儲單元示意圖 棧空：?？眨簍op1=0,top2=M-1;top1=0,top2=M-1;棧滿：棧滿：top1+1=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 of DuSqStack S2 int flag;DuSqStack;/或：或：#define MAXSIZE 100Struct duseqstack elemtype datamaxsize;int top2;/兩個棧的棧頂指針兩個棧的棧頂指針 int flag;27（1）兩個棧共享存儲單元的進棧算法）兩個棧共享存儲單元的進棧算法Status DuSqStackPush(DuSqStack&S,SElemType x)/棧棧 S S 為共享順序棧類型為共享順序棧類型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 數(shù)組域；數(shù)組域；/此算法將元素此算法將元素 x x 放入棧放入棧 S S 中；如果兩個棧滿，則返回中；如果兩個棧滿，則返回 ERRORERROR if(S.top1+1)=(S.top2)return ERROR;/如果兩個棧滿，則返回如果兩個棧滿，則返回 ERRORERROR else /如果棧未滿，則進行入棧操作如果棧未滿，則進行入棧操作 if(S.flag!=1)&(S.flag!=2)return ERROR;/如果如果 flag flag 不為不為 1,21,2，則返回，則返回 ERRORERROR else /如果如果 flag flag 為為 1 1 或或 2 2，則入棧，則入棧 switch(S.flag)case 1:/標志位標志位 flag flag 為為 1 1 28 S.dataS.top1=x;/元素元素 x x 入棧入棧 S1S1 S.top1+;/修改棧修改棧 S1 S1 的棧頂指針的棧頂指針 break;case 2:/標志位標志位 flag flag 為為 2 2 S.dataS.top2=x;/元素元素 x x 入棧入棧 S2S2 S.top2-;/修改棧修改棧 S2 S2 的棧頂指針的棧頂指針 break;/switch/switch 結束結束 return OK;/else/else 結束結束 /else/else 結束結束/DuSqStackPush/DuSqStackPush29（2）兩個棧共享存儲單元的退棧算法）兩個棧共享存儲單元的退棧算法Status DuSqStackPop(DuSqStack&S,SElemType&x)/棧棧 S S 為共享順序棧類型為共享順序棧類型 DuSqStackDuSqStack，含，含 top1top1、top2 top2 和和 data data 數(shù)組域數(shù)組域/此算法刪除棧此算法刪除棧 S S 中棧頂元素，并用中棧頂元素，并用 x x 返回其值；如果?？眨祷仄渲?；如果?？?，則返回則返回 ERRORERRORif(S.flag!=1)&(S.flag!=2)return ERROR;/如果如果 flag1,2flag1,2，則返回，則返回 ERRORERRORelelse /如果如果 flag flag 為為 1 1 或或 2 2，則出棧，則出棧switch(S.flag)case 1:/標志位標志位 flag flag 為為 1 1 if(S.top1 0)/如果棧如果棧 S1 S1 不空，則對不空，則對 S1 S1 進行操作進行操作S.top1-;/修改棧修改棧 S1 S1 的棧頂指針的棧頂指針x=S.dataS.top1;/元素元素 x x 出棧出棧 /if/if 結束結束 30 else return ERROR;/如果棧如果棧 S1 S1 為空，則返回為空，則返回 ERRORERROR break;case 2:/標志位標志位 flag flag 為為 1 1 if(S.top2next=NULL;（b）進棧運算）進棧運算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）退棧運算）退棧運算Status 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);/釋放棧頂元素所占的空間釋放棧頂元素所占的空間 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=top-next-data;return OK;return OK;/else /else 結束結束/GetTop_L/GetTop_L35（5）判?？眨┡袟？読nt empty(LinkStack*top)if(top-next=NULL)return(1);else return(0);36課課 前前 復復 習習設n 個元素的進棧序列是P1，P2，P3，Pn，其輸出序列是1,2，3，n，若P1=3，則P2的值()。A、可能是2B、一定是2C、不可能是1D、一定是1 37 一、一、數(shù)制轉換數(shù)制轉換 假設要將十進制數(shù)N轉換為d進制數(shù)，一個簡單的轉換算法是重復下述兩步，直到N等于零：X=N mod d (其中mod為求余運算)N=N div d (其中div為整除運算)計算過程從低位到高位，打印輸出從高位到低位3.2 3.2 棧的應用舉例棧的應用舉例 棧在日常生活中和計算機程序設計中有著許多應用，下面僅介紹棧在計算機中的應用。38void Conversion(int N)/*對于任意的一個非負十進制數(shù)N，打印出與其等值的8進制數(shù)*/Stack S;int x;/*S為順序?；蜴湕?/InitStack(&S);while(N0)x=N%8;Push(&S,x);/*將轉換后的數(shù)字壓入棧S*/N=N/8;while(！StackEmpty(S)Pop(&S,&x);printf(%d,x);算法算法3.139二、括號匹配問題二、括號匹配問題 假設表達式中允許包含三種括號假設表達式中允許包含三種括號:圓括號、圓括號、方括號和大括號。編寫一個算法判斷表達式中的方括號和大括號。編寫一個算法判斷表達式中的括號是否正確配對。括號是否正確配對。解解:設置一個括號棧設置一個括號棧,掃描表達式：遇到左括號掃描表達式：遇到左括號(包括包括(、和和)時進棧時進棧,遇到右括號時遇到右括號時,若棧是相匹若棧是相匹配的左括號配的左括號,則出棧則出棧,否則否則,返回返回0。若表達式掃描結束若表達式掃描結束,棧為空棧為空,返回返回1表示括號正表示括號正確匹配確匹配,否則返回否則返回0。40 int correct(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ū)。算法思想：設輸入緩沖區(qū)為一個棧結構，每當從終端接收一個字符后先作如下判別：若它既不是退格符（#）也不是退行符（）,則將該字符入棧；若是退格符（#），則從棧頂刪去一個字符；若是退行符（），則將棧清空。算法描述如下：算法描述如下：43void LineEdit()InitStack(s);ch=getchar();While(ch!=EOF)/EOF為全文結束符 while(ch!=EOF&ch!=“n”)switch(ch)case“#”:pop(s,c);break;/當棧非空時退棧 case“”:clearstack(s);break;/重置S為空棧 default:push(s,c);break;/有效字符進棧，但未考慮棧滿 ch=getchar();clearstack(s);if(ch!=EOF)ch=getchar();destroystack(s);44五、五、表達式求值表達式求值 表達式求值是高級語言編譯中的一個基本問題，是棧的典型應用實例。任何一個表達式都是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。操作數(shù)操作數(shù)既可以是常數(shù)，也可以是被說明為變量或常量的標識符；運算符運算符可以分為算術運算符、關系運算符和邏輯運算符三類；基基本界限符本界限符有左右括號和表達式結束符等。451.1.無括號算術表達式求值無括號算術表達式求值 表達式計算表達式計算 程序設計語言中都有計算表達式的問題，這是語言編譯中的典型問題。(1)表達式形式：由運算對象、運算符及必要的表達式括號組成；(2)表達式運算：運算時要有一個正確的運算形式順序。由于某些運算符可能具有比別的運算符更高的優(yōu)先級，因此表達式不可能嚴格的從左到右，見圖3.5。46圖3.5 表達式運算及運算符優(yōu)先級 47圖3.6 無括號算術表達式的處理過程 置空棧OVS、OPTR讀字符WW是操作符OPTR?？誛優(yōu)先級OPTR棧頂優(yōu)先級取OVS頂、次頂和OPTR頂，形成運算結果T(i),然后退OVS頂、次頂和OPTR頂，將T(i)置入OVS棧頂進OVS進OPTR棧W#結束NYYYNYNN48 2.2.算術表達式處理規(guī)則算術表達式處理規(guī)則 (1)規(guī)定優(yōu)先級表。(2)設置兩個棧：OVS(運算數(shù)棧)和OPTR(運算符棧)。(3)自左向右掃描，遇操作數(shù)進OVS，遇操作符則與OPTR棧頂優(yōu)先數(shù)比較：當前操作符OPTR棧頂,當前操作符進OPTR棧；當前操作符OPTR棧頂，OVS棧頂、次頂和OPTR棧頂，退棧形成運算T(i)，T(i)進OVS棧。例：實現(xiàn)A/BC+D*E的運算過程時棧區(qū)變化情況如圖3.7所示。49圖3.7 A/BC+D*E運算過程的棧區(qū)變化情況示意圖 CBAOVS/OPTROPTR生成BC，運算結果T(1)T(1)AOVS/OPTROPTR/生成A/T(1),運算結果T(2)T(2)/OPTR為空，進棧DT(2)右邊界#OPTR*生成D*E，運算結果T(3)T(3)T(2)生成T(3)T(2)，得到T(4)T(4)E*右邊界#OPTR+*50 3.3.帶括號算術表達式帶括號算術表達式 假設操作數(shù)是整型常數(shù)，運算符只含加、減、乘、除等四種運算符，界限符有左右括號和表達式起始、結束符“”，如：（7+15）*（23-28/4）。引入表達式起始、結束符是為了方便。要對一個簡單的算術表達式求值，首先要了解算術四則運算的規(guī)則，即：(1)從左算到右；(2)先乘除，后加減；(3)先括號內(nèi)，后括號外。51 運算符和界限符可統(tǒng)稱為算符，它們構成的集合命名為OPTR。根據(jù)上述三條運算規(guī)則，在運算過程中，任意兩個前后相繼出現(xiàn)的算符1和2之間的優(yōu)先關系必為下面三種關系之一：12，1的優(yōu)先權高于2。52表表 3-1 3-1 算符之間的優(yōu)先關系算符之間的優(yōu)先關系 53 實現(xiàn)算符優(yōu)先算法時需要使用兩個工作棧：一個稱作optr，用以存放運算符；另一個稱作opnd，用以存放操作數(shù)或運算的中間結果。算法的基本過程如下：首先初始化操作數(shù)棧opnd和運算符棧optr，并將表達式起始符“”壓入運算符棧；依次讀入表達式中的每個字符，若是操作數(shù)則直接進入操作數(shù)棧opnd，若是運算符，則與運算符棧optr的棧頂運算符進行優(yōu)先權比較，并做如下處理：54 (1)若棧頂運算符的優(yōu)先級低于剛讀入的運算符，則讓剛讀入的運算符進optr棧；(2)若棧頂運算符的優(yōu)先級高于剛讀入的運算符，則將棧頂運算符退棧，送入，同時將操作數(shù)棧opnd退棧兩次，得到兩個操作數(shù)a、b，對a、b進行運算后，將運算結果作為中間結果推入opnd棧；(3)若棧頂運算符的優(yōu)先級與剛讀入的運算符的優(yōu)先級相同，說明左右括號相遇，只需將棧頂運算符（左括號）退棧即可。55算法具體描述如下：算法具體描述如下：int ExpEvaluation()/*讀入一個簡單算術表達式并計算其值。operator和operand分別為運算符棧和運算數(shù)棧，OPS為運算符集合*/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);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進行op運算*/Push(&opnd,v);break;return(GetTop(opnd);例求表達式1+2*3-4/2的值，棧的變化如下。58步驟 操作數(shù)棧 運算符棧 說明 開始兩棧均為空111進入操作數(shù)棧+進入運算符棧2進入操作數(shù)棧*進入運算符棧3進入操作數(shù)棧退棧2*3進入操作數(shù)棧退棧1+6進入操作數(shù)棧234567891+12+12+1117+*236+*+59步驟 操作數(shù)棧 運算符棧 說明 107-進入運算符棧4進入操作數(shù)棧/進入運算符棧2進入操作數(shù)棧退棧4/2進入操作數(shù)棧退棧7-2進入操作數(shù)棧111213141516177 4-7 4-/7 4 2-/77 2-560當然，算術表達式除了簡單求值外，還會涉及到算術表達式的兩種表示方法，即中綴表示法和后綴表示法。中綴表達式求值較麻煩（須考慮運算符的優(yōu)先級，甚至還要考慮圓括號），而后綴表達式求值較方便（無須考慮運算符的優(yōu)先級及圓括號）。下面將介紹算術表達式的中綴表示和后綴表示及它們的求值規(guī)律，例如，對于下列各中綴表達式：（1）3/5+8（2）18-9*(4+3)（3）(25+x)*(a*(a+b)+b)對應的后綴表達式為：(1)3 5 /8 +(2)18 9 4 3 +*-(3)25 x +a a b +*b +*614.4.中綴表達式變成等價的后綴表達式中綴表達式變成等價的后綴表達式 將中綴表達式變成等價的后綴表達式，表達式中操作數(shù)次序不變，運算符次序發(fā)生變化，同時去掉了圓括號。轉換規(guī)則是：設立一個棧，存放運算符，首先棧為空，編譯程序從左到右掃描中綴表達式，若遇到操作數(shù)，直接輸出，并輸出一個空格作為兩個操作數(shù)的分隔符；若遇到運算符，則必須與棧頂比較，運算符級別比棧頂級別高則進棧，否則退出棧頂元素并輸出，然后輸出一個空格作分隔符；若遇到左括號，進棧；若遇到右括號，則一直退棧輸出，直到退到左括號止。當棧變成空時，輸出的結果即為后綴表達式。將中綴表達式(1+2)*(8-2)/(7-4)變成等價的后綴表達式?，F(xiàn)在用棧來實現(xiàn)該運算，棧的變化及輸出結果如下62步驟棧中元素 輸出結果 說明1(（進棧2(1輸出13(+1+進棧4(+1 2輸出25 1 2 +退棧輸出，退棧到（止6*1 2 +*進棧7*(1 2 +（進棧8*(1 2 +（進棧9*(1 2 +8輸出810*(-1 2 +8 -進棧6311*(-1 2 +8 2輸出212*(1 2 +8 2 -退棧輸出，退棧到（止13*(/1 2 +8 2 -/進棧14*(/(1 2 +8 2 -（進棧15*(/(1 2 +8 2 -7輸出716*(/(-1 2 +8 2 -7-進棧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 -/*退棧并輸出步驟 棧中元素 輸出結果 說明645.5.后綴表達式的求值后綴表達式的求值 將中綴表達式轉換成等價的后綴表達式后，求值時，不需要再考慮運算符的優(yōu)先級，只需從左到右掃描一遍后綴表達式即可。具體求值步驟為：設置一個棧，開始時，棧為空，然后從左到右掃描后綴表達式，若遇操作數(shù)，則進棧；若遇運算符，則從棧中退出兩個元素，先退出的放到運算符的右邊，后退出的放到運算符左邊，運算后的結果再進棧，直到后綴表達式掃描完畢。此時，棧中僅有一個元素，即為運算的結果。例，求后綴表達式：1 2 +8 2 -7 4 -/*的值，棧的變化情如下：65步驟棧中元素 說明111進棧21 22進棧3 遇+號退棧2和1431+2=3的結果3進棧53 88進棧63 8 22進棧73遇-號退棧2和883 68-2=6的結果6進棧93 6 77進棧103 6 7 44進棧66步驟棧中元素 說明113 6遇-號退棧4和7123 6 37-4=3的結果3進棧133遇/號退棧3和6143 26/3=2的結果2進棧15 遇*號退棧2和31663*2=6進棧176掃描完畢，運算結束 從上可知，最后求得的后綴表達式之值為6，與用中綴表達式求得的結果一致，但后綴式求值要簡單得多。67五、五、求解迷宮問題求解迷宮問題 求迷宮問題就是求出從入口到出口的路徑。在求迷宮問題就是求出從入口到出口的路徑。在求解時求解時,通常用的是通常用的是“窮舉求解窮舉求解”的方法的方法,即從入即從入口出發(fā)口出發(fā),順某一方向向前試探順某一方向向前試探,若能走通若能走通,則繼續(xù)往則繼續(xù)往前走；否則沿原路退回前走；否則沿原路退回,換一個方向再繼續(xù)試探換一個方向再繼續(xù)試探,直至所有可能的通路都試探完為止。為了保證在直至所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回任何位置上都能沿原路退回(稱為回溯稱為回溯),),需要用一需要用一個后進先出的棧來保存從入口到當前位置的路徑。個后進先出的棧來保存從入口到當前位置的路徑。首先用如圖首先用如圖3.33.3所示的方塊圖表示迷宮。對所示的方塊圖表示迷宮。對于圖中的每個方塊于圖中的每個方塊,用空白表示通道用空白表示通道,用陰影表示用陰影表示墻。所求路徑必須是簡單路徑墻。所求路徑必須是簡單路徑,即在求得的路徑上即在求得的路徑上不能重復出現(xiàn)同一通道塊。不能重復出現(xiàn)同一通道塊。6869 為了表示迷宮為了表示迷宮,設置一個數(shù)組設置一個數(shù)組mg,其中每個元素表示其中每個元素表示一個方塊的狀態(tài)一個方塊的狀態(tài),為為0時表示對應方塊是通道時表示對應方塊是通道,為為1時表示時表示對應方塊為墻對應方塊為墻,如圖如圖3.3所示的迷宮所示的迷宮,對應的迷宮數(shù)組對應的迷宮數(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;70while(while(棧不空棧不空)若當前位置可通若當前位置可通，則則 將當前位置插入棧頂；將當前位置插入棧頂；/納入路徑納入路徑 若該位置是出口位置，則算法結束；若該位置是出口位置，則算法結束；/此時棧中存放的是一條從入口位置到出口位置的路徑此時棧中存放的是一條從入口位置到出口位置的路徑否則切換當前位置的北鄰方塊為新的當前位置；否則切換當前位置的北鄰方塊為新的當前位置；否則否則 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索，則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；則設定新的當前位置為沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，若棧不空但棧頂位置的四周均不可通，則則 刪去棧頂位置；刪去棧頂位置；/從路徑中刪去該通道塊從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至棧空；直至找到一個可通的相鄰塊或出棧至棧空；算法描述：算法描述：71void mgpath()/*路徑為路徑為:(1,1)-(M-2,N-2)*/int i,j,di,find,k;top+;/*初始方塊進棧初始方塊進棧*/Stacktop.i=1;Stacktop.j=1;Stacktop.di=-1;mg11=-1;while(top-1)/*棧不空時循環(huán)棧不空時循環(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)問題的求解方法是遞歸的問題的求解方法是遞歸的 有些問題的解法是遞歸的有些問題的解法是遞歸的,典型的有典型的有Hanoi問題求問題求解解,該問題描述是：設有該問題描述是：設有3個分別命名為個分別命名為X,Y和和Z的塔座的塔座,在塔座在塔座X上有上有n個直徑各不相同個直徑各不相同,從小到大依次編號為從小到大依次編號為1,2,n的盤片的盤片,現(xiàn)要求將現(xiàn)要求將X塔座上的塔座上的n個盤片移到塔座個盤片移到塔座Z上并仍按同樣順序疊放上并仍按同樣順序疊放,盤片移動時必須遵守以下規(guī)盤片移動時必須遵守以下規(guī)則：每次只能移動一個盤片；盤片可以插在則：每次只能移動一個盤片；盤片可以插在X,Y和和Z中任一塔座；任何時候都不能將一個較大的盤片放在中任一塔座；任何時候都不能將一個較大的盤片放在較小的盤片上。設計遞歸求解算法較小的盤片上。設計遞歸求解算法,并將其轉換為非并將其轉換為非遞歸算法。遞歸算法。設設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ù)運行示意圖 813 3、遞歸模型遞歸模型 遞歸模型是遞歸算法的抽象遞歸模型是遞歸算法的抽象,它反映一個遞歸問題它反映一個遞歸問題的遞歸結構的遞歸結構,例如例如,前面的遞歸算法對應的遞歸模型如下：前面的遞歸算法對應的遞歸模型如下：fun(1)=1 (1)fun(n)=n*fun(n-1)n1 (2)其中其中,第一個式子給出了遞歸的終止條件第一個式子給出了遞歸的終止條件,第二個式第二個式子給出了子給出了fun(n)的值與的值與fun(n-1)的值之間的關系的值之間的關系,我們把我們把第一個式子稱為第一個式子稱為遞歸出口遞歸出口,把第二個式子稱為把第二個式子稱為遞歸體遞歸體。82 實際上實際上,遞歸思路是把一個不能或不好直接求解的遞歸思路是把一個不能或不好直接求解的“大問題大問題”轉化成一個或幾個轉化成一個或幾個“小問題小問題”來解決來解決,再把再把這些這些“小問題小問題”進一步分解成進一步分解成更小的更小的“小問題小問題”來解來解決決,如此分解如此分解,直至每個直至每個“小問題小問題”都可以直接解決都可以直接解決(此此時分解到遞歸出口時分解到遞歸出口)。但遞歸分解不是隨意的分解。但遞歸分解不是隨意的分解,遞歸遞歸分解要保證分解要保證“大問題大問題”與與“小問題小問題”相似相似,即即求解過程求解過程與環(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 求解求解fun(5)的過程如下：的過程如下：5!844 4 遞歸問題的優(yōu)點遞歸問題的優(yōu)點 通過上面的例子可看出，遞歸既是強有力的數(shù)學方法，也是程序設計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結構清晰，程序的正確性容易證明。5 5、消除遞歸的原因、消除遞歸的原因 其一：有利于提高算法時空性能，因為遞歸執(zhí)行時需要系統(tǒng)提供隱式棧實現(xiàn)遞歸，效率低且費時。其二：無應用遞歸語句的語言設施環(huán)境條件，有些計算機語言不支持遞歸功能，如FORTRAN語言中無遞歸機制。其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時不合適，也存在一個把遞歸算法轉化為非遞歸算法的需求。853.4 3.4 隊列隊列 a1 a2 .an 入隊 隊頭 隊尾 出隊 圖 3-13 隊列示意圖 隊列簡稱隊隊列簡稱隊,它也是一種運算受限的線性表它也是一種運算受限的線性表,其限其限制僅允許在表的一端進行插入制僅允許在表的一端進行插入,而在表的另一端進行而在表的另一端進行刪除。刪除。我們把進行插入的一端稱做我們把進行插入的一端稱做隊尾隊尾(rear),進行刪除進行刪除的一端稱做的一端稱做隊首隊首(front)。向隊列中插入新元素稱為向隊列中插入新元素稱為進隊進隊或或入隊入隊,新元素進隊新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為后就成為新的隊尾元素；從隊列中刪除元素稱為出隊出隊或或離隊離隊,元素出隊后元素出隊后,其后繼元素就成為隊首元素。其后繼元素就成為隊首元素。86 二、隊列的基本運算二、隊列的基本運算 1.初始化操作：InitQueue(&Q)。設置一個空隊列。2.判空操作：QueueEmpty(Q)。若隊列為空，則返回TRUE，否則返回FALSE。3.進隊操作：EnQueue(&Q，x)。在隊列Q的隊尾插入x。操作成功，返回值為TRUE，否則返回值為FALSE。4.出隊操作：DeQueue(&Q,&x)。使隊列Q的隊頭元素出隊，并用x帶回其值。操作成功，返回值為RUE，否則返回值為FALSE。87 5.取隊頭元素操作：GetHead（Q,&x）。用x取得隊元素的值。操作成功，返回值為TRUE，否則返回值為FALSE。6.隊列置空操作：ClearQueue(&Q)。將隊列Q置為空隊列。7.隊列銷毀操作DestroyQueue(&Q)。釋放隊列的空間。8.求隊列長度操作：QueueLength(Q)。返回隊列Q的元素個數(shù)，即隊列Q的長度。88三、三、隊列的抽象數(shù)據(jù)類型描述隊列的抽象數(shù)據(jù)類型描述 隊列的抽象數(shù)據(jù)類型可描述為：隊列的抽象數(shù)據(jù)類型可描述為：ADT QUEUEADT QUEUE 數(shù)據(jù)元素數(shù)據(jù)元素：D=ai|ai ElemSet，i=1,2,n,n 0 數(shù)據(jù)關系數(shù)據(jù)關系：R1=|ai-1,ai D,i=1,2,n 基本操作：基本操作：InitQueue(&Q)：初始化操作。設置一個空隊列。QueueEmpty(Q)：判空操作。若隊列為空，則返回TRUE，否則返回FALSE。EnQueue(&Q，x)：進隊操作。在隊列Q的隊尾插入x。操作成功，返回值為TRUE，否則返回值為FALSE。89DeQueue(&Q,&x)：出隊操作。使隊列Q的隊頭元素出隊，并用x帶回其值。操作成功，返回值為RUE，否則返回值為FALSE。GetHead（Q,&x）：取隊頭元素操作。用x取得隊元素的值。操作成功，返回值為TRUE，否則返回值為FALSE。ClearQueue(&Q)：隊列置空操作。將隊列Q置為空隊列。DestroyQueue(&Q)：隊列銷毀操作。釋放隊列的空間。QueueLength(Q)。返回隊列Q的元素個數(shù)，即隊列Q的長度。ADT Queue 90四、隊列的表示和實現(xiàn)四、隊列的表示和實現(xiàn) 1.鏈隊列鏈隊列 圖3.14 鏈隊列(b)非空的鏈隊列a1anrearfront(a)空的鏈隊列隊尾指針rear隊頭指針front隊列的鏈式存儲，稱為鏈隊列。一個鏈隊列顯然需要兩個分別指示隊頭（頭指針）和隊尾（尾指針）指針才能唯一確定。91與前面介紹的單鏈表類似，但為了使頭指針，尾指針統(tǒng)一起來，鏈隊列可以定義如下：typedef struct QNode QElemType data;/*數(shù)據(jù)域*/struct QNode *next;/*指針域*/Qnode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;rear 頭 front an 頭 front a1 a2 rear（a）空鏈隊列 (b)非空鏈隊 92 鏈隊列的基本操作鏈隊列的基本操作（1）初始化操作。int InitQueue(LinkQueue&Q)/*將Q初始化為一個空的鏈隊列*/Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q-front-next=NULL;return OK;93（2）入隊操作。Status EnQueue(LinkQueue&Q,QElemType e)/*將數(shù)據(jù)元素x插入到隊列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）出隊操作。int DeQueue(LinkQueue&Q,QElemType&e)/*將隊列Q的隊頭元素出隊，并存放到x所指的存儲空間中*/QueuePtr p;if(Q-front=Q-rear)return ERROR;p=Q-front-next;e=p-data;Q-front-next=p-next;/*隊頭元素p出隊*/if(Q-rear=p)/*如果隊中只有一個元素p，則p出隊后成為空隊*/Q-rear=Q-front;free(p);/*釋放存儲空間*/return OK;952.循環(huán)隊列循環(huán)隊列:隊列的順序表示和實現(xiàn)隊列的順序表示和實現(xiàn) 圖3.15 隊列的基本操作 Queue6543210rearfront(1)空隊列543210rearfrontcbad(2)a、b、c、d依 次 入隊543210rearfrontd(3)a、b、c出 隊543210rearfrontdef(4)e、f入 隊用一組連續(xù)的存儲單元依次存放隊列的元素，并設兩個指針front、rear分別指示隊頭和隊尾元素的位置。front：指向?qū)嶋H的隊頭；rear：指向?qū)嶋H隊尾的下一位置。初態(tài)：frontrear0；隊空：frontrear;隊滿：rearM;入隊：qrear=x;rear rear+1;出隊：x=qfront;front=front+1;96圖3.16 循環(huán)隊列 012354rearfront(a)空隊列012354e6e7e8e3e4e5012354(b)隊列滿(b)一般情況frontreare3e4e5frontrear假溢出的解決方法假溢出的解決方法：（1）將隊中元素向隊頭移動；（2）采用循環(huán)隊列：q0接在QM-1之后初態(tài)：frontrear0或M-1；隊空：frontrear;入隊：qrear=x；rear(rear+1)%M;出隊：x=qfront;front=(front+1)%M;隊滿：留一個空間不用(rear+1)%M=front;或另設一個標志以區(qū)分隊空和隊滿。97循環(huán)隊列的類型定義：define MAXSIZE 100 /*隊列的最大長度*/typedef struct QElemType elementMAXSIZE;/*隊列的元素空間*/int front;/*頭指針指示器*/int rear;/*尾指針指示器*/SeqQueue;98循環(huán)隊列的基本操作：循環(huán)隊列的基本操作：（1）初始化操作。void InitQueue（SeqQueue&Q）/*將*Q初始化為一個空的循環(huán)隊列*/Q-front=Q-rear=0;99（2）入隊操作。int EnterQueue(SeqQueue*Q,QueueElementType x)/*將元素x入隊*/if(Q-rear+1)%MAXSIZE=Q-front)/*隊列已經(jīng)滿了*/return ERROR;Q-elementQ-rear=x;Q-rear=(Q-rear+