數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列

1、第3章 棧和隊(duì)列3.1 棧3.2 棧的應(yīng)用舉例3.3 棧與遞歸的實(shí)現(xiàn)3.4 隊(duì)列13.1 棧3.1.1 抽象數(shù)據(jù)類型棧的定義 棧的定義棧(stack)，又稱堆棧，是限制線性表中元素的插入和刪除只能在線性表的同一端進(jìn)行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(Top)，另一端為固定的一端，稱為棧底(Bottom)。2根據(jù)棧的定義可知，最先放入棧中元素在棧底，最后放入的元素在棧頂，而刪除元素剛好相反，最后放入的元素最先刪除，最先放入的元素最后刪除。也就是說(shuō)，棧是一種后進(jìn)先出(Last In First Out)的線性表，簡(jiǎn)稱為L(zhǎng)IFO表。棧的插入操作被形象地稱為進(jìn)?；蛉霔?，刪

2、除操作稱為出?；蛲藯?。3例：入棧順序：123可能出棧順序：123，132，213，231，321不可能出棧順序：3124 棧的抽象數(shù)據(jù)類型ADT Stack isData：含有n個(gè)元素a1,a2,a3,an,按LIFO規(guī)則存放，每個(gè)元素的類型都為ElemType。Operation: /初始化棧svoid initStack(Stack& s); /清除棧s的所有元素，使之成為空棧void clearStack(Stack& s); /判斷棧s是否為空，若是則返回true，否則返回falsebool isEmpty(Stack& s); /若棧已滿則返回true，否則返回false，此操作為順

3、序棧所特有bool isFull(Stack& s);/返回棧頂元素，但不移動(dòng)棧頂指針ElemType peek(Stack& s); /元素e進(jìn)棧，即插入到棧頂void push(Stack& s,const ElemType& e); /刪除棧頂元素并返回之ElemType pop(Stack& s); end Stack53.1.2 棧的表示和實(shí)現(xiàn)3.1.2.1 順序棧-棧的順序存儲(chǔ)結(jié)構(gòu)和線性表類似，棧也有兩種存儲(chǔ)表示，其順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧。6順序棧類型定義：sqstack.h#include using namespace std;const int MAXSIZE=50;str

4、uct Elemint data;typedef Elem ElemType;struct SqStackElemType baseMAXSIZE;int top;7void initStack(SqStack& s);void clearStack(SqStack& s);bool isEmpty(SqStack& s);bool isFull(SqStack& s);ElemType peek(SqStack& s);void push(SqStack& s,const ElemType& e);ElemType pop(SqStack& s);8s.base 始終指向棧底s.base=N

5、ULL 表示棧結(jié)構(gòu)不存在s.top=0 表示?？誷.top 始終指向棧頂元素的下一個(gè)位置9順序棧基本操作的實(shí)現(xiàn)：sqstack.cpp#include sqstack.h 初始化棧void initStack(SqStack& s)s.top=0; 清空棧void clearStack(SqStack& s)s.top=0; 判?？誦ool isEmpty(SqStack& s)return s.top=0;10 判棧滿bool isFull(SqStack& s)return s.top=MAXSIZE; 讀取棧頂元素ElemType peek(SqStack& s)if(s.top=0)c

6、errStack is empty!endl;exit(1);return s.bases.top-1;11 入棧void push(SqStack& s,const ElemType& e)if(s.top=MAXSIZE)cerrStack overflow!endl;exit(1);s.bases.top=e;+s.top;12 出棧ElemType pop(SqStack& s)if(s.top=0)cerrStack is empty!endl;exit(1);-s.top;ElemType temp=s.bases.top;return temp;133.1.2.2 棧的鏈接存儲(chǔ)結(jié)

7、構(gòu)-鏈棧 （Linked-stack）棧的鏈?zhǔn)酱尜A結(jié)構(gòu)，也稱為鏈棧，它是一種限制運(yùn)算的鏈表，即規(guī)定鏈表中的插入和刪除運(yùn)算只能在鏈表開(kāi)頭進(jìn)行。鏈棧結(jié)構(gòu)見(jiàn)下圖注： 只能在鏈表頭部進(jìn)行操作 表示同線性表 頭指針-棧頂指針14鏈棧的結(jié)構(gòu)可用C+語(yǔ)言定義如下：struct LNode ElemType data; Lnode * next; ;LNode* top;153.2 棧的應(yīng)用舉例由于棧的操作具有后進(jìn)先出的固有特性，致使棧成為程序設(shè)計(jì)中的有用工具。凡應(yīng)用問(wèn)題求解的過(guò)程具有后進(jìn)先出的天然特性的話，則求解的算法中也必然需要利用棧。163.2.1 數(shù)制轉(zhuǎn)換假設(shè)要將十進(jìn)制數(shù)N轉(zhuǎn)換為d進(jìn)制數(shù)：（如8進(jìn)制）

8、轉(zhuǎn)換結(jié)果：2504 問(wèn)題很明確，就是要輸出計(jì)算過(guò)程中所得到的各個(gè)八進(jìn)制數(shù)位。然而這八進(jìn)制的各個(gè)數(shù)位產(chǎn)生的順序是從低位到高位的，而打印輸出的順序，一般來(lái)說(shuō)應(yīng)從高位到低位，這恰好和計(jì)算過(guò)程相反。因此，需要先保存在計(jì)算過(guò)程中得到的八進(jìn)制數(shù)的各位，然后逆序輸出，因?yàn)樗前春筮M(jìn)先出的規(guī)律進(jìn)行的，所以用棧最合適。17typedef int ElemType;void conversion(int n,int r)SqStack s;initStack(s);while(n)push(s,n%r);n=n/r;while(!isEmpty(s)coutpop(s);coutendl;183.2.2 括號(hào)匹配

9、問(wèn)題假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（ ）或（ （ ）或 ( ( ) ) ）均為錯(cuò)誤的匹配。現(xiàn)在的問(wèn)題是，要求檢驗(yàn)一個(gè)給定表達(dá)式中的括弧是否正確匹配？19檢驗(yàn)括號(hào)是否匹配的方法可用期待的急迫程度這個(gè)概念來(lái)描述。即后出現(xiàn)的左括弧，它等待與其匹配的右括弧出現(xiàn)的急迫心情要比先出現(xiàn)的左括弧高。20在檢驗(yàn)算法中可設(shè)置一個(gè)棧，每讀入一個(gè)括號(hào)：若是左括號(hào)，則直接入棧，等待相匹配的同類右括號(hào)；若讀入的是右括號(hào)，且與當(dāng)前棧頂?shù)淖罄ㄌ?hào)同類型，則二者匹配，將棧頂?shù)淖罄ㄌ?hào)出棧，否則屬于不合法的情況；如果輸入序列已讀盡，而棧中仍有等待匹配的左括號(hào)，不合法

10、；讀入了一個(gè)右括號(hào)，而棧中已無(wú)等待匹配的左括號(hào)，不合法。21typedef char ElemType;bool bracketsCheck(char* c)SqStack s;initStack(s);for(int i=0;ci!=0;+i)switch(ci)case :case (:push(s,ci);break;case :if(!isEmpty(s)&peek(s)=)pop(s);elsereturn false;break;22case ):if(!isEmpty(s)&peek(s)=()pop(s);elsereturn false;break; default: bre

11、ak;if(isEmpty(s)return true;elsereturn false;233.2.3 迷宮（Maze）求解一個(gè)迷宮包含有m行n列個(gè)小方格，每個(gè)方格用1表示可通行，用0表示墻壁，即不可通行，迷宮中通常有一個(gè)入口和一個(gè)出口。求解迷宮問(wèn)題是從入口點(diǎn)出發(fā)尋找一條通向出口點(diǎn)的路徑，并輸出這條路徑。24計(jì)算機(jī)解迷宮問(wèn)題時(shí)，通常用的是窮舉求解法：從入口出發(fā)，順某一方向向前搜索，若能走通，則繼續(xù)往前走，否則沿原路退回，換一個(gè)方向再繼續(xù)搜索，直至所有可能的通路都探索到為止。25在一個(gè)迷宮中，中間的每個(gè)方格位置都有四個(gè)可選擇的移動(dòng)方向，而在四個(gè)頂點(diǎn)只有兩個(gè)方向，并且每個(gè)頂點(diǎn)的兩個(gè)方向均有差別，

12、每條邊線上除頂點(diǎn)外的每個(gè)位置只有三個(gè)方向，并且也有差別。為了在求解迷宮的算法中避免判斷邊界條件和進(jìn)行不同處理的麻煩，使每個(gè)方格都能試著按四個(gè)方向移動(dòng)，可在迷宮的周?chē)偵线吙颍谶吙虻拿總€(gè)方格里填上0作為墻壁，如圖（b）所示。26當(dāng)從迷宮中的一個(gè)位置（稱之為當(dāng)前位置）前進(jìn)到下一個(gè)位置時(shí)，下一個(gè)位置相對(duì)于當(dāng)前位置的位移量（包括行位移量和列位移量）隨著前進(jìn)的方向的不同而不同，東、南、西、北（即右、下、左、上）各方向的位移量依次為（0,1）、（1,0）、（0,-1）和（-1,0）。27為了尋找從入口點(diǎn)到出口點(diǎn)的一條通路，首先從入口點(diǎn)出發(fā)，按照東南西北各方向的次序試探前進(jìn)，若向東可通行，同時(shí)沒(méi)有被訪問(wèn)過(guò)

13、，則向東前進(jìn)一個(gè)方格；否則表明向東沒(méi)有通向出口的路徑，接著向南方向試著前進(jìn)，若向南可通行同時(shí)沒(méi)有被訪問(wèn)過(guò)，應(yīng)向南前進(jìn)一步；否則依次向西和向北試探。若試探完當(dāng)前位置上的所有方向后都沒(méi)有通路，則應(yīng)退回一步，從到達(dá)當(dāng)前位置的下一個(gè)方向試探著前進(jìn)。因此每前進(jìn)一步都要記錄其上一步的坐標(biāo)位置以及前進(jìn)到此步的方向，以便退回之用。這正好需要用棧來(lái)解決。算法見(jiàn)教材P51。28sqstack.h#include using namespace std;const int MAXSIZE=100;struct PosType / 迷宮坐標(biāo)位置類型int x; / 行值int y; / 列值;29struct Ele

14、m / 棧的元素類型int ord; / 通道塊在路徑上的序號(hào)PosType seat; / 通道塊在迷宮中的坐標(biāo)位置int di; / 從此通道塊走向下一通道塊的方向(03表示東北);typedef Elem ElemType;struct SqStackElemType baseMAXSIZE;int top;30sqstack.cppvoid initStack(SqStack& s);void clearStack(SqStack& s);bool isEmpty(SqStack& s);bool isFull(SqStack& s);ElemType peek(SqStack& s)

15、;void push(SqStack& s,const ElemType& e);ElemType pop(SqStack& s);同前31main.cpp#include #include #include sqstack.h const int MAXLENGTH=25; / 設(shè)迷宮的最大行列為25typedef int MazeTypeMAXLENGTHMAXLENGTH; / 迷宮數(shù)組行列MazeType m; / 迷宮數(shù)組int curstep=1; / 當(dāng)前足跡,初值為1 / 定義墻元素值為0,可通過(guò)路徑為1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡32bool pass(PosType

16、 b) / 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，return true; /否則，return false 。if(mb.xb.y=1)return true;elsereturn false;void footPrint(PosType a) / 使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curstep)ma.xa.y=curstep;33 / 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置PosType nextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量/ 移動(dòng)方向,依次為東南西北c.x+=direcdi.x;c.y+=d

17、irecdi.y;return c;/ 使迷宮m的b點(diǎn)的序號(hào)變?yōu)?1(不能通過(guò)的路徑)void markPrint(PosType b) mb.xb.y=-1;34bool mazePath(PosType start,PosType end) /若迷宮maze中存在從入口start到出口end的通道，則求得一條存放在棧中(從棧底到棧頂)，并返回true；否則返回falseSqStack s;PosType curpos;ElemType e;initStack(s);curpos=start;35doif(pass(curpos) / 當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊footPrin

18、t(curpos); / 留下足跡e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;push(s,e); / 入棧當(dāng)前位置及狀態(tài)curstep+; / 足跡加1if(curpos.x=end.x&curpos.y=end.y) / 到達(dá)終點(diǎn)(出口)return true;curpos=nextPos(curpos,e.di);36else / 當(dāng)前位置不能通過(guò)if(!isEmpty(s)e=pop(s); / 退棧到前一位置curstep-;while(e.di=3&!isEmpty(s) / 前一位置處于最后一個(gè)方向(北)mar

19、kPrint(e.seat); / 留下不能通過(guò)的標(biāo)記(-1)e=pop(s); / 退回一步curstep-;if(e.di3) / 沒(méi)到最后一個(gè)方向(北)e.di+; / 換下一個(gè)方向探索push(s,e);curstep+;curpos=nextPos(e.seat,e.di); / 設(shè)定當(dāng)前位置是該新方向上的相鄰塊while(!isEmpty(s);return false;37void print(int x,int y) / 輸出迷宮的解for(int i=0;ix;i+)for(int j=0;jy;j+)coutsetw(3)mij;coutendl;38int main()P

20、osType begin,end;int x=8,y=10;begin.x=1;begin.y=1;end.x=6;end.y=8;ifstream infile;in(data.txt); /打開(kāi)文件for(int i=0;i8;i+)for(int j=0;jmij;in(); /關(guān)閉文件cout迷宮結(jié)構(gòu)如下:n;print(x,y);39if(mazePath(begin,end) / 求得一條通路cout此迷宮從入口到出口的一條路徑如下:n;print(x,y); / 輸出此通路elsecout此迷宮沒(méi)有從入口到出口的路徑n;403.2.4 表達(dá)式求值程序設(shè)計(jì)語(yǔ)言中都有計(jì)算表達(dá)式的問(wèn)題

21、，這是語(yǔ)言編譯中的典型問(wèn)題，是棧的典型應(yīng)用實(shí)例。413.2.4.1 算術(shù)表達(dá)式的兩種表示通常書(shū)寫(xiě)的算術(shù)表達(dá)式是由操作數(shù)（又叫運(yùn)算對(duì)象或運(yùn)算量）和運(yùn)算符以及改變運(yùn)算次序的圓括號(hào)連接而成。如16-9*(4+3)這種算術(shù)表達(dá)式稱為中綴表達(dá)式。在中綴表達(dá)式的計(jì)算過(guò)程中，即要考慮括號(hào)的作用，又要考慮運(yùn)算符的優(yōu)先級(jí)，還要考慮運(yùn)算符出現(xiàn)的先后次序，用計(jì)算機(jī)來(lái)處理非常困難。42波蘭科學(xué)家謝維奇提出了算術(shù)表達(dá)式的另一種表示，即后綴表示，又稱逆波蘭式，其定義是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象的后面。采用后綴表示的算術(shù)表達(dá)式稱為后綴表達(dá)式。如16 9 4 3 + * -在后綴表達(dá)式中，不存在括號(hào)，也不存在優(yōu)先級(jí)的差別，計(jì)算

22、過(guò)程完全按照運(yùn)算符出現(xiàn)的先后次序進(jìn)行，整個(gè)計(jì)算過(guò)程僅需一遍便可完成，顯然比中綴表達(dá)式的計(jì)算要簡(jiǎn)單得多。433.2.4.2 把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式設(shè)以字符作為結(jié)束的中綴表達(dá)式保存在s1字符串中，轉(zhuǎn)換后得到的后綴表達(dá)式擬存于s2字符串中。由中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的規(guī)則可知：轉(zhuǎn)換前后，表達(dá)式中的數(shù)值項(xiàng)的次序不變，而運(yùn)算符的次序發(fā)生了變化，由處在兩個(gè)運(yùn)算對(duì)象的中間變?yōu)樘幵趦蓚€(gè)運(yùn)算對(duì)象的后面，同時(shí)去掉了所有的括號(hào)。44為了使轉(zhuǎn)換正確，必須設(shè)定一個(gè)運(yùn)算符棧，并在棧底放入一個(gè)特殊運(yùn)算符，假定為字符，讓它具有最低的運(yùn)算符優(yōu)先級(jí)，假定數(shù)值為0。此棧用來(lái)保存掃描中中綴表達(dá)式得到的暫不能放入后綴表達(dá)式中的

23、運(yùn)算符，待它的兩個(gè)運(yùn)算符對(duì)象都放入到后綴表達(dá)式以后，再令其出棧并寫(xiě)入到后綴表達(dá)式中。45算法的基本思路：從頭到尾地掃描中綴表達(dá)式中的每個(gè)字符，不同的類型的字符按不同的情況處理。若遇到的是空格，則認(rèn)為是分隔符，不需要進(jìn)行處理；若遇到的是數(shù)字或小數(shù)點(diǎn)，則直接寫(xiě)入s2中，并在每個(gè)數(shù)值最后寫(xiě)入一個(gè)空格；若遇到的是左括號(hào)，則應(yīng)把它壓入到運(yùn)算符棧中，待以它開(kāi)始的括號(hào)內(nèi)的表達(dá)式轉(zhuǎn)換完畢后再出棧；若遇到的是右括號(hào)，則表明括號(hào)內(nèi)的中綴表達(dá)式已經(jīng)掃描完畢，把從棧頂直到保存著的對(duì)應(yīng)左括號(hào)之間的運(yùn)算符依次退棧并寫(xiě)入s2串中；46若遇到的是運(yùn)算符： a. 當(dāng)該運(yùn)算符的優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，表明該運(yùn)算符的后一個(gè)

24、運(yùn)算對(duì)象還沒(méi)有被放入到s2串中，應(yīng)把它暫存于運(yùn)算棧中； b. 當(dāng)該運(yùn)算符的優(yōu)先級(jí)小于棧頂運(yùn)算符的優(yōu)先級(jí)時(shí)，表明棧頂運(yùn)算符的兩個(gè)運(yùn)算對(duì)象已經(jīng)被保存到s2串中，應(yīng)將棧頂運(yùn)算符退棧并寫(xiě)入到s2串中，對(duì)于新的棧頂運(yùn)算符仍繼續(xù)進(jìn)行比較和處理，直到被處理的運(yùn)算符的優(yōu)先級(jí)大于棧頂運(yùn)算符的優(yōu)先級(jí)為止，然后令該運(yùn)算符進(jìn)棧即可。按照以上過(guò)程掃描到中綴表達(dá)式結(jié)束符時(shí)，把棧中剩余的運(yùn)算符依次退棧并寫(xiě)入到后綴表達(dá)式中，再向s2寫(xiě)入表達(dá)式結(jié)束符和字符串結(jié)束符0，整個(gè)轉(zhuǎn)換過(guò)程就處理完畢，在s2中就得到了轉(zhuǎn)換成的后綴表達(dá)式。47change.cpp#include sqstack.hint precede(char op)s

25、witch(op)case +:case -:return 1;case *:case /:return 2;case (:case :default:return 0;48void change(char* s1,char* s2)/將字符串s1中的中綴表達(dá)式轉(zhuǎn)換為在于s2中的后綴表達(dá)式SqStack r;initStack(r);/初始化棧push(r,);/給棧底放入字符，它具有最低優(yōu)先級(jí)int i,j;i=0;j=0;char ch=s1i;49while(ch!=)if(ch= )ch=s1+i;else if(ch=()push(r,ch);ch=s1+i;else if(ch=)

26、while(peek(r)!=()s2j+=pop(r);pop(r);ch=s1+i;50else if(ch=+|ch=-|ch=*|ch=/)char w=peek(r);while(precede(w)=precede(ch)s2j+=w;pop(r);w=peek(r);push(r,ch);ch=s1+i;51elsewhile(isdigit(ch)|ch=.)s2j+=ch;ch=s1+i;s2j+= ;52ch=pop(r);while(ch!=)if(ch=()cerrexpression error!endl;exit(1);elses2j+=ch;ch=pop(r);s

27、2j+=;s2j+=0;533.2.4.3 后綴表達(dá)式求值后綴表達(dá)式的求值比較簡(jiǎn)單，掃描一遍即可完成。它需要使用一個(gè)棧，用以存儲(chǔ)后綴表達(dá)式中的操作數(shù)、計(jì)算的中間結(jié)果以及最后結(jié)果。假定一個(gè)后綴表達(dá)式以字符作為結(jié)束符，并且以字符串方式提供。54后綴表達(dá)式求值算法的基本思路：把包含后綴表達(dá)式的字符串定義為一個(gè)輸入字符串流對(duì)象，每次從中讀入一個(gè)字符時(shí)，若它是運(yùn)算符，則表明它的兩個(gè)操作數(shù)已經(jīng)在棧中，把它們彈出后進(jìn)行運(yùn)算即可，然后把運(yùn)算結(jié)果再壓入棧中；否則，讀入的字符必為操作數(shù)的最高位數(shù)字，應(yīng)把它重新送回輸入流中，然后把下一個(gè)數(shù)據(jù)作為浮點(diǎn)數(shù)輸入，并把它壓入到棧中；依次掃描每一個(gè)字符并進(jìn)行上述處理，直到遇到

28、結(jié)束符為止，表明后綴表達(dá)式計(jì)算完畢，最終結(jié)果保存在棧中，并且棧中僅存一個(gè)值，把它彈出返回即可。55compute.cpp#include sqstack.h#include double compute(char* str)SqStack s;initStack(s);istringstream ins(str); /把str定義為string流對(duì)象inschar ch; /用于輸入字符double x; /用于輸入浮點(diǎn)數(shù)insch;56while(ch!=)switch(ch)case +:x=pop(s)+pop(s);break;case -:x=pop(s); /pop(s)彈出減數(shù)x

29、=pop(s)-x; /pop(s)彈出被減數(shù)break;case *:x=pop(s)*pop(s);break;57case /:x=pop(s);if(x!=0.0)x=pop(s)/x;cerrDivide by 0!x; /從字符串輸入流中讀入一個(gè)浮點(diǎn)數(shù)58push(s,x); /把讀入的數(shù)或進(jìn)行相應(yīng)運(yùn)算的結(jié)果壓入到s棧中insch;if(!isEmpty(s)x=pop(s);if(isEmpty(s)return x;elsecerrexpression error!endl;exit(1);elsecerrStack is emppty!endl;exit(1);59棧定義如下

30、：sqstack.h#include using namespace std;const int MAXSIZE=100;template struct SqStackElemType baseMAXSIZE;int top;60template void initStack(SqStack& s)s.top=0;template void clearStack(SqStack& s)s.top=0;template bool isEmpty(SqStack& s)return s.top=0;61template bool isFull(SqStack& s)return s.top=MAX

31、SIZE;template ElemType peek(SqStack& s)if(s.top=0)cerrStack is empty!endl;exit(1);return s.bases.top-1;62template void push(SqStack& s,const ElemType& e)if(s.top=MAXSIZE)cerrStack overflow!endl;exit(1);s.bases.top=e;+s.top;63template ElemType pop(SqStack& s)if(s.top=0)cerrStack is empty!endl;exit(1)

32、;-s.top;ElemType temp=s.bases.top;return temp;64main.cpp#include using namespace std;int precede(char op);void change(char* s1,char* s2);double compute(char* str);int main()char s1=34*(2+5)+3;char s230;change(s1,s2);couts2endl;double r=compute(s2);coutr0實(shí)現(xiàn)遞歸調(diào)用，由n的值乘以f(n-1)的返回值求出f(n)。67用C+語(yǔ)言編寫(xiě)出求解n!的遞

33、歸函數(shù)為：long f(int n)if(n=0)return 1;elsereturn n*f(n-1);68在計(jì)算機(jī)系統(tǒng)內(nèi)，執(zhí)行遞歸函數(shù)是通過(guò)棧來(lái)實(shí)現(xiàn)的，棧中的每個(gè)元素包含有遞歸函數(shù)的每個(gè)參數(shù)域、每個(gè)局部變量域和調(diào)用后的返回地址域。每次進(jìn)行函數(shù)調(diào)用時(shí)，都把相應(yīng)的值壓入棧。每次調(diào)用結(jié)束時(shí)，都按照本次返回地址返回到指定位置執(zhí)行，并且自動(dòng)作一次退棧操作，使得上一次調(diào)用所使用的參數(shù)成為新的棧頂，繼續(xù)被使用。棧和遞歸是可以相互轉(zhuǎn)換的，當(dāng)編寫(xiě)遞歸算法時(shí)，雖然表面上沒(méi)有使用棧，但系統(tǒng)執(zhí)行時(shí)會(huì)自動(dòng)建立和使用棧。69求解迷宮問(wèn)題也是一個(gè)遞歸問(wèn)題，適合采用遞歸算法來(lái)解決。若迷宮中的當(dāng)前位置（初始上入口點(diǎn)）就是

34、出口位置，則表示找到了通向出口的一條路徑，應(yīng)返回true；若從當(dāng)前位置按東、南、西、北方向的次序前進(jìn)到下一個(gè)位置，該位置可通行且沒(méi)有被訪問(wèn)過(guò)，則以該位置為參數(shù)進(jìn)行遞歸調(diào)用，若返回true的話，表明從該位置到出口點(diǎn)有通路，標(biāo)記該位置后向上一個(gè)位置返回true，結(jié)束遞歸。若當(dāng)前位置上的所有方向都試探完畢，表明從當(dāng)前位置出發(fā)沒(méi)有尋找到通向出口點(diǎn)的路徑，返回false結(jié)束遞歸。70#include #include #include using namespace std;const int MAXLENGTH=25; / 設(shè)迷宮的最大行列為25typedef int MazeTypeMAXLENGT

35、HMAXLENGTH; / 迷宮數(shù)組行列struct PosType / 迷宮坐標(biāo)位置類型int x; / 行值int y; / 列值;71struct Elem / 棧的元素類型int ord; / 通道塊在路徑上的序號(hào)PosType seat; / 通道塊在迷宮中的坐標(biāo)位置int di; / 從此通道塊走向下一通道塊的方向(03表示東北);MazeType m; / 迷宮數(shù)組int curstep=0; / 當(dāng)前足跡,初值為1 / 定義墻元素值為0,可通過(guò)路徑為1,不能通過(guò)路徑為-1,通過(guò)路徑為足跡72bool pass(PosType b) / 當(dāng)迷宮m的b點(diǎn)的序號(hào)為1(可通過(guò)路徑)，返

36、回 true; 否則，返回 false。if(mb.xb.y=1)return true;elsereturn false;void footPrint(PosType a) / 使迷宮m的a點(diǎn)的序號(hào)變?yōu)樽阚E(curstep)ma.xa.y=curstep;73 / 根據(jù)當(dāng)前位置及移動(dòng)方向，返回下一位置PosType nextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0; / 行增量,列增量/ 移動(dòng)方向,依次為東南西北c.x+=direcdi.x;c.y+=direcdi.y;return c;74/ 使迷宮m的b點(diǎn)的序號(hào)變?yōu)?1(

37、不能通過(guò)的路徑)void markPrint(PosType b)mb.xb.y=-1;void print(int x,int y) / 輸出迷宮的解for(int i=0;ix;i+)for(int j=0;jy;j+)coutsetw(3)mij;coutendl;75bool mazePath(PosType curpos,PosType end) /若存在從當(dāng)前位置到出口end的通道，則返回TRUE；否則返回FALSEif(curpos.x=end.x&curpos.y=end.y) / 到達(dá)終點(diǎn)(出口)return true;PosType nextpos;for(int i=0;

38、i4;+i)nextpos=nextPos(curpos,i);if(pass(nextpos)markPrint(nextpos);if(mazePath(nextpos,end)curstep+; / 足跡加1footPrint(nextpos);return true;return false;76int main()PosType begin,end;int x=8,y=10;begin.x=1;begin.y=1;end.x=6;end.y=8;ifstream infile;in(data.txt); /打開(kāi)文件for(int i=0;i8;i+)for(int j=0;jmij;

39、in(); /關(guān)閉文件77if(mazePath(begin,end) / 求得一條通路cout此迷宮從入口到出口的一條路徑如下:n;print(x,y); / 輸出此通路elsecout此迷宮沒(méi)有從入口到出口的路徑n;783.4 隊(duì)列3.4.1 抽象數(shù)據(jù)類型隊(duì)列的定義僅允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表，稱為隊(duì)列(queue)。允許插入的一端稱為隊(duì)尾(rear)，允許刪除的一端稱為隊(duì)頭（front）。隊(duì)列是一種先進(jìn)先出（First In First Out）的特殊線性表，或稱FIFO表。若隊(duì)列中沒(méi)有任何元素，則稱為空隊(duì)列，否則稱為非空隊(duì)列。79例：購(gòu)物排隊(duì) -新來(lái)的成員總是加入隊(duì)尾（

40、不允許加塞），每次離開(kāi)的成員總是隊(duì)列頭上的（不允許中途離隊(duì)）。例：解決主機(jī)與外部設(shè)備之間速度不匹配問(wèn)題。例：操作系統(tǒng)中資源競(jìng)爭(zhēng)。80隊(duì)列的抽象數(shù)據(jù)類型定義如下：ADT Queue isData：采用順序或鏈接方式存儲(chǔ)的隊(duì)列，假定其存儲(chǔ)類型用QueueType表示。Operation：void initQueue(QueueType& q); /初始化隊(duì)列q，置其為空void destroyQueue(QueueType& q);/銷毀隊(duì)列q，不再存在void clearQueue(QueueType& q); /清空隊(duì)列bool isEmpty(QueueType q); /若q為空，返回tr

41、ue，否則返回falseint getLength(QueueType q); /返回隊(duì)列q的長(zhǎng)度ElemType getHead(QueueType q); /返回q的隊(duì)頭元素void insertElem(QueueType& q,ElemType e); /在q的隊(duì)尾插入元素eElemType deleteElem(QueueType& q); /刪除隊(duì)頭元素，并將之返回void traverseQueue(QueueType q,void (*visit)(ElemType&);/從隊(duì)頭到隊(duì)尾，依次對(duì)每個(gè)元素調(diào)用函數(shù)visit()813.4.2 鏈隊(duì)列隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)用鏈表表示的隊(duì)

42、列稱為鏈隊(duì)列，一個(gè)鏈隊(duì)列需要兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針才能唯一確定。為操作方便，可給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)并令頭指針指向頭結(jié)點(diǎn)。由此，空的鏈隊(duì)列的判決條件為頭指針和尾指針均指向頭結(jié)點(diǎn)。8283鏈隊(duì)列的實(shí)現(xiàn)如下：linkqueue.h#include using namespace std;struct ElemTypeint d;struct QNodeElemType data;QNode* next;struct LinkQueueQNode* front;QNode* rear;84void initQueue(LinkQueue& q);void destroyQueue(LinkQu

43、eue& q);void clearQueue(LinkQueue& q);bool isEmpty(LinkQueue q);int getLength(LinkQueue q);ElemType getHead(LinkQueue q);void insertElem(LinkQueue& q,ElemType e);ElemType deleteElem(LinkQueue& q);void traverseQueue(LinkQueue q,void (*visit)(ElemType&);85linkqueue.cpp#include linkqueue.hvoid initQueu

44、e(LinkQueue& q)q.front=q.rear=new QNode;if(!q.front)exit(1);q.front-next=NULL;86void destroyQueue(LinkQueue& q)while(q.front)q.rear=q.front-next;delete q.front;q.front=q.rear;87void clearQueue(LinkQueue& q)QNode* p=q.front-next;while(p)q.rear=p-next;delete p;p=q.rear;bool isEmpty(LinkQueue q)return

45、q.front=q.rear;88int getLength(LinkQueue q)int n=0;QNode* p=q.front-next;while(p)+n;p=p-next;return n;89ElemType getHead(LinkQueue q)if(q.front=q.rear)cerrQueue is empty!next-data;90void insertElem(LinkQueue& q,ElemType e)QNode* p=new QNode;p-data=e;p-next=NULL;q.rear-next=p;q.rear=p;91ElemType dele

46、teElem(LinkQueue& q)if(q.front=q.rear)cerrQueue is empty!next;ElemType e=p-data;q.front-next=p-next;if(q.rear=p) /若鏈隊(duì)為空，則需同時(shí)使隊(duì)尾指針指向頭結(jié)點(diǎn)q.rear=q.front;delete p;return e;92void traverseQueue(LinkQueue q,void (*visit)(ElemType&)QNode* p=q.front-next;while(p)visit(p-data);p=p-next;coutendl;93main.cpp#include linkqueue.hvoid print(ElemType& e)coute.d ;94int main()LinkQueue q;initQueue(q);ElemType a=3;ElemType b=5;insertElem(q,a);insertElem(q,b);coutgetLength(q)endl;traverseQueue(q,print);ElemType c=getHead(q);coutc.dendl;deleteElem(q);coutgetLe