山大數(shù)據(jù)結(jié)構(gòu)-5精講課件

TheAbstractDataTypeDerivedClassesandInheritanceFormula-BasedRepresentationLinkedRepresentationApplicationsChapter5堆棧(Stacks)9/2/20231TheAbstractDataTypeChapter堆棧的實現(xiàn)堆棧的應(yīng)用本章重點9/2/20232堆棧的實現(xiàn)本章重點8/2/20232定義堆棧是一個線性表，其插入(也稱為添加)和刪除操作都在表的同一端進行。允許插入和刪除的一端被稱為棧頂(top)，另一端被稱為棧底(bottom)。堆棧是一個后進先出（last-in-first-out,LIFO）的數(shù)據(jù)結(jié)構(gòu)。堆棧(Stacks)9/2/20233定義堆棧是一個線性表，其插入(也稱為添加)和刪除操作都在表堆棧9/2/20234堆棧8/2/20234堆棧ADT9/2/20235堆棧ADT8/2/20235公式化描述(Formula-BasedRepresentation)效率、改進鏈接描述(Linked)Representation效率比較堆棧9/2/20236公式化描述(Formula-BasedRepresenta堆棧數(shù)據(jù)對象是更通用的線性表對象的限制版本。(插入和刪除操作僅能在表的同一端進行)例如，如果把表的左端定義為棧底，右端定義為棧頂，那么堆棧的添加操作等價于在表的右端進行插入操作，刪除操作等價于在表的右端進行刪除操作。繼承9/2/20237堆棧數(shù)據(jù)對象是更通用的線性表對象的限制版本。(插入和刪除操作template<classT>classStack::privateLinearList<T>{//LIFO對象public:Stack(intMaxStackSize=10):LinearList<T>(MaxStackSize){}boolIsEmpty()const {returnLinearList<T>::IsEmpty();}boolIsFull()const {return(Length()==GetMaxSize());}TTop()const {if(IsEmpty())throwOutOfBounds(); Tx;Find(Length(),x);returnx;}Stack<T>&Add(constT&x) {Insert(Length(),x);return*this;}Stack<T>&Delete(T&x) {LinearList<T>::Delete(Length(),x); return*this;}};公式化描述的堆棧類(派生)9/2/20238template<classT>公式化描述的堆棧類(派生)template<classT>classStack{//LIFO對象public: Stack(intMaxStackSize=10); ~Stack(){delete[]stack;} boolIsEmpty()const{returntop==-1;} boolIsFull()const{returntop==MaxTop;} TTop()const; Stack<T>&Add(constT&x); Stack<T>&Delete(T&x);private: inttop;//棧頂 intMaxTop;//最大的棧頂值 T*stack;//堆棧元素數(shù)組};自定義Stack9/2/20239template<classT>自定義Stack8/2/2template<classT>Stack<T>::Stack(intMaxStackSize){ MaxTop=MaxStackSize-1; stack=newT[MaxStackSize]; top=-1;}Stack類構(gòu)造函數(shù)9/2/202310template<classT>Stack類構(gòu)造函數(shù)8/template<classT>TStack<T>::Top()const{ if(IsEmpty())throwOutOfBounds(); elsereturnstack[top];}復(fù)雜性?返回棧頂元素9/2/202311template<classT>返回棧頂元素8/2/202template<classT>Stack<T>&Stack<T>::Add(constT&x){ if(IsFull())throwNoMem(); stack[++top]=x; return*this;}復(fù)雜性?添加元素x9/2/202312template<classT>添加元素x8/2/2023template<classT>Stack<T>&Stack<T>::Delete(T&x){ if(IsEmpty())throwOutOfBounds(); x=stack[top--]; return*this;}復(fù)雜性?刪除棧頂元素，并將其送入x9/2/202313template<classT>刪除棧頂元素，并將其送入x哪一端對應(yīng)棧頂?鏈表描述9/2/202314哪一端對應(yīng)棧頂?鏈表描述8/2/202314template<classT>classLinkedStack:privateChain<T>{public:boolIsEmpty()const {returnChain<T>::IsEmpty();}boolIsFull()const;TTop()const {if(IsEmpty())throwOutOfBounds(); Tx;Find(1,x);returnx;}LinkedStack<T>&Add(constT&x) {Insert(0,x);return*this;}LinkedStack<T>&Delete(T&x) {Chain<T>::Delete(1,x);return*this;}};從Chain派生的鏈表形式的堆棧9/2/202315template<classT>從Chain派生的鏈表形式template<classT>boolLinkedStack<T>::IsFu11()const{//堆棧是否滿?try{ ChainNode<T>*p=newChainNode<T>; deletep; returnfalse; }catch(NoMem){returntrue;}}從Chain派生的鏈表形式的堆棧9/2/202316template<classT>從Chain派生的鏈表形式template<classT>classNode{friendLinkedStack<T>;private: Tdata; Node<T>*link;};自定義鏈表形式的堆棧9/2/202317template<classT>自定義鏈表形式的堆棧8/template<classT>classLinkedStack{public:LinkedStack(){top=0;}~LinkedStack();boolIsEmpty()const{returntop==0;}boolIsFull()const;TTop()const;LinkedStack<T>&Add(constT&x);LinkedStack<T>&Delete(T&x);private:Node<T>*top;//指向棧頂節(jié)點}:自定義鏈表形式的堆棧9/2/202318template<classT>自定義鏈表形式的堆棧8/2template<classT>LinkedStack<T>::~LinkedStack(){ Node<T>*next; while(top){ next=top->link; deletetop; top=next; }}析構(gòu)函數(shù)9/2/202319template<classT>析構(gòu)函數(shù)8/2/20231template<classT>boolLinkedStack<T>::IsFu11()const{try{Node<T>*p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}堆棧是否滿?9/2/202320template<classT>堆棧是否滿?8/2/202template<classT>TLinkedStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();returntop->data;}返回棧頂元素9/2/202321template<classT>返回棧頂元素8/2/202template<classT>LinkedStack<T>&LinkedStack<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=top;top=p;return*this;}添加元素x9/2/202322template<classT>添加元素x8/2/2023template<classT>LinkedStack<T>&LinkedStack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=top->data;Node<T>*p=top;top=top->link;deletep;return*this;}刪除棧頂元素，并將其送入x9/2/202323template<classT>刪除棧頂元素，并將其送入x鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行鏈式棧的棧頂在鏈頭適合于多棧操作比較9/2/202324鏈式棧無棧滿問題，空間可擴充比較8/2/202324括號匹配(ParenthesisMatching)漢諾塔(TowersofHanoi)火車車廂重排(RearrangingRailroadCars)開關(guān)盒布線(SwitchBoxRouting)離線等價類(OfflineEquivalenceProblem)迷宮老鼠(RatinaMaze)應(yīng)用9/2/202325括號匹配(ParenthesisMatching)應(yīng)用8/目標:輸入一個字符串，輸出相互匹配的括號以及未能匹配的括號。例：字符串(a*(b+c)+d)例：字符串(a+b))(括號匹配9/2/202326目標:輸入一個字符串，輸出相互匹配的括號以及未能匹配的括號。如果從左至右掃描一個字符串，那么每個右括號將與最近遇到的那個未匹配的左括號相匹配。如何實現(xiàn)？觀察9/2/202327如果從左至右掃描一個字符串，那么每個右括號將與最近遇到的那個可以在從左至右的掃描過程中把所遇到的左括號存放到堆棧內(nèi)。每當遇到一個右括號時，就將它與棧頂?shù)淖罄ㄌ枺ㄈ绻嬖冢┫嗥ヅ?，同時從棧頂刪除該左括號。方法9/2/202328可以在從左至右的掃描過程中把所遇到的左括號存放到堆棧內(nèi)。每當已知n個碟子和3座塔。初始時所有的碟子按從大到小次序從塔1的底部堆放至頂部，需要把碟子都移動到塔2，每次移動一個碟子，而且任何時候都不能把大碟子放到小碟子的上面。漢諾塔問題9/2/202329已知n個碟子和3座塔。初始時所有的碟子按從大到小次序從塔1的為了把最大的碟子移動到塔2，必須把其余n-1個碟子移動到塔3，然后把最大的碟子移動到塔2。接下來是把塔3上的n-1個碟子移動到塔2，為此可以利用塔2和塔1?？梢酝耆鲆曀?上已經(jīng)有一個碟子的事實，因為這個碟子比塔3上將要移過來的任一個碟子都大，因此，可以在它上面堆放任何碟子。漢諾塔問題-遞歸方法9/2/202330為了把最大的碟子移動到塔2，必須把其余n-1個碟子移動到塔voidTowersOfHanoi(intn,intx,inty,intz){//把n個碟子從塔x移動到塔y，可借助于塔zif(n>0){ TowersOfHanoi(n-1,x,z,y);

cout<<"Movetopdiskfromtower"<<x<<"totopoftower"<<y<<endl; TowersOfHanoi(n-l,z,y,x);}}求解漢諾塔問題的遞歸程序9/2/202331voidTowersOfHanoi(intn,int希望給出每次移動之后三座塔的狀態(tài)（即塔上的碟子及其次序）進一步要求9/2/202332希望給出每次移動之后三座塔的狀態(tài)（即塔上的碟子及其次序）進一classHanoi{friendvoidTowersOfHanoi(int);public: voidTowersOfHanoi(intn,intx,inty,intz);private: Stack<int>*S[4];};使用堆棧求解漢諾塔問題9/2/202333classHanoi{使用堆棧求解漢諾塔問題8/2/202voidHanoi::TowersOfHanoi(intn,intx,inty,intz){//把n個碟子從塔x移動到塔y，可借助于塔z intd;//碟子編號 if(n>0){ TowersOfHanoi(n-l,x,z,y); S[x]->Delete(d);//從x中移走一個碟子 S[y]->Add(d);//把這個碟子放到y(tǒng)上 ShowState(); TowersOfHanoi(n-l,z,y,x);}}使用堆棧求解漢諾塔問題9/2/202334voidHanoi::TowersOfHanoi(intvoidTowersOfHanoi(intn){//Hanoi::towersOfHanoi的預(yù)處理程序HanoiX；X.S[1]=newStack<int>(n);X.S[2]=newStack<int>(n);X.S[3]=newStack<int>(n);for(intd=n;d>0;d--)//初始化X.S[1]->Add(d);//把碟子d放到塔1上//把塔1上的n個碟子移動到塔2上，借助于塔3的幫助X.TowersOfHanoi(n,1,2,3);}使用堆棧求解漢諾塔問題9/2/202335voidTowersOfHanoi(intn)使用堆棧求在一個轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個入軌、一個出軌和k個緩沖鐵軌(位于入軌和出軌之間)?；疖囓噹嘏艈栴}9/2/202336在一個轉(zhuǎn)軌站里完成車廂的重排工作，在轉(zhuǎn)軌站中有一個入軌、一個從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動到緩沖鐵軌上，直到按輸出次序要求輪到它時才將它放到出軌上。緩沖鐵軌按照何種方式使用?火車車廂重排方案9/2/202337從前至后依次檢查入軌上的所有車廂?；疖囓噹嘏欧桨?/2/2boolRailroad(intp[],intn,intk){//k個緩沖鐵軌，車廂初始排序為p[1:n]//如果重排成功，返回true，否則返回false//如果內(nèi)存不足，則引發(fā)異常NoMem。//創(chuàng)建與緩沖鐵軌對應(yīng)的堆棧LinkedStack<int>*H;H=newLinkedStack<int>[k+1];intNowOut=1;//下一次要輸出的車廂intminH=n+l;//緩沖鐵軌中編號最小的車廂intminS;//minH號車廂對應(yīng)的緩沖鐵軌火車車廂重排程序9/2/202338boolRailroad(intp[],intn,//車廂重排for(inti=1;i<=n;i++) if(p[i]==NowOut){//直接輸出t cout<<“將車廂”<<p[i]<<“從入軌移至出軌"<<endl;

NowOut++; //從緩沖鐵軌中輸出

while(minH==NowOut){

Output(minH,minS,H,k,n); NowOut++; } }else{//將p[i]送入某個緩沖鐵軌 if(!Hold(p[i],minH,minS,H,k,n)) returnfalse;}returntrue;}火車車廂重排程序9/2/202339//車廂重排火車車廂重排程序8/2/202339voidOutput(int&minH,int&minS,LinkedStack<int>H[],intk,intn){//把車廂從緩沖鐵軌送至出軌處，同時修改minS和minHintc;//車廂索引//從堆棧minS中刪除編號最小的車廂minHH[minS].Delete(c);cout<<"Movecar"<<minH<<"fromholdingtrack"<<minS<<"tooutput"<<endl;//通過檢查所有的棧頂，搜索新的minH和minSminH=n+2;for(inti=1;i<=k;i++) if(!H[i].IsEmpty()&&(c=H[i].Top())<minH){ minH=c; minS=i;}}Output函數(shù)9/2/202340voidOutput(int&minH,int&miboolHold(intc,int&minH,int&minS,LinkedStack<int>H[],intk,intn)(//在一個緩沖鐵軌中放入車廂c//如果沒有可用的緩沖鐵軌，則返回false//如果空間不足，則引發(fā)異常NoMem，否則返回true//為車廂c尋找最優(yōu)的緩沖鐵軌//初始化intBestTrack=0,//目前最優(yōu)的鐵軌BestTop=n+1,//最優(yōu)鐵軌上的頭輛車廂x;//車廂索引Hold函數(shù)9/2/202341boolHold(intc,int&minH,in//掃描緩沖鐵軌for(inti=1;i<=k;i++) if(!H[i].IsEmpty()){//鐵軌i不空 x=H[i].Top(); if(c<x&&x<BestTop){ //鐵軌i頂部的車廂編號最小 BestTop=x; BestTrack=i;} } else//鐵軌i為空 if(!BestTrack)BestTrack=i;Hold函數(shù)9/2/202342//掃描緩沖鐵軌Hold函數(shù)8/2/202342 if(!BestTrack)returnfalse;//沒有可用的鐵軌 //把車廂c送入緩沖鐵軌 H[BestTrack].Add(c); cout<<"Movecar"<<c<<"frominput""toholdingtrack"<<BestTrack<<endl; //必要時修改minH和minS if(c<minH){ minH=c; minS=BestTrack; } returntrue;}復(fù)雜性？Hold函數(shù)9/2/202343 if(!BestTrack)returnfalse;給定一個矩形布線區(qū)域，其外圍有若干針腳。兩個針腳之間通過布設(shè)一條金屬線路而實現(xiàn)互連。這條線路被稱為電線，被限制在矩形區(qū)域內(nèi)。如果兩條電線發(fā)生交叉，則會發(fā)生電流短路。所以，不允許電線間的交叉。每對互連的針腳被稱為網(wǎng)組。目標是要確定對于給定的網(wǎng)組，能否合理地布設(shè)電線以使其不發(fā)生交叉。開關(guān)盒布線問題9/2/202344給定一個矩形布線區(qū)域，其外圍有若干針腳。兩個針腳之間通過布設(shè)四個網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)可布線開關(guān)盒(routableswitchbox)開關(guān)盒布線示例9/2/202345四個網(wǎng)組(1,4,)，(2,3)，(5,6)和(7,8)開關(guān)當兩個針腳互連時，其電線把布線區(qū)分成兩個分區(qū)。如果有一個網(wǎng)組，其兩個針腳分別位于這兩個不同的分區(qū)，那么這個網(wǎng)組是不可以布線的，因而整個電路也是不可布線的。如果沒有這樣的網(wǎng)組，則可以繼續(xù)判斷每個獨立的分區(qū)是不是可布線的。為此，可以從一個分區(qū)中取出一個網(wǎng)組，利用該網(wǎng)組把這個分區(qū)又分成兩個子分區(qū)，如果任一個網(wǎng)組的兩個針腳都分布在同一個子分區(qū)之中(即不會出現(xiàn)兩個針腳分別位于兩個子分區(qū)的情形)，那么這個分區(qū)就是可布線的。策略9/2/202346當兩個針腳互連時，其電線把布線區(qū)分成兩個分區(qū)。策略8/2/2可以按順時針或反時針方向沿著開關(guān)盒的外圍進行遍歷。例：按順時針方向從針腳1開始遍歷，將依次檢查針腳1,2,...,8。針腳1和4屬于同一個網(wǎng)組，那么在針腳1至針腳4之間出現(xiàn)的所有針腳構(gòu)成了第一個分區(qū)，而在針腳4至針腳1之間未出現(xiàn)的所有針腳構(gòu)成了第二個分區(qū)。把針腳1放入堆棧，然后繼續(xù)處理，直至遇到針腳4。這個過程使我們僅在處理完一個分區(qū)之后才能進入下一個分區(qū)。方案9/2/202347可以按順時針或反時針方向沿著開關(guān)盒的外圍進行遍歷。方案8/2輸入是元素數(shù)目n、關(guān)系數(shù)目r以及r對關(guān)系，問題的目標是把n個元素分配至相應(yīng)的等價類。離線等價類問題9/2/202348輸入是元素數(shù)目n、關(guān)系數(shù)目r以及r對關(guān)系，問題的目標是把等價關(guān)系與等價類(EquivalenceClass)在求解實際應(yīng)用問題時常會遇到等價類問題。從數(shù)學(xué)上看，等價類是一個對象(或成員)的集合，在此集合中所有對象應(yīng)滿足等價關(guān)系。若用符號“

”表示集合上的等價關(guān)系，那么對于該集合中的任意對象x,y,

z，下列性質(zhì)成立：自反性：x

x(即等于自身)。對稱性：若x

y,則y

x。傳遞性：若x

y且y

z,則x

z。因此，等價關(guān)系是集合上的一個自反、對稱、傳遞的關(guān)系。9/2/202349等價關(guān)系與等價類(EquivalenceClass)在求解

“相等”(=)就是一種等價關(guān)系，它滿足上述的三個特性。一個集合S

中的所有對象可以通過等價關(guān)系劃分為若干個互不相交的子集S1,S2,S3,…，它們的并就是

S。這些子集即為等價類。確定等價類的方法分兩步走。第一步，讀入并存儲所有的等價對(i,j)；第二步，標記和輸出所有的等價類。9/2/202350“相等”(=)就是一種等價關(guān)系，它滿足上述的三個特給定集合

S={0,1,2,3,4,5,6,7,8,9,10,11},及如下等價對:

0

4,3

1,6

10,8

9,7

4,

6

8,3

5,2

11,11

09/2/202351給定集合S={0,1,2,3,4,5,6初始

{0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}0

4

{0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}3

1

{0,4},{1,3},{2},{5},{6},{7},{8},{9},{10},{11}6

10{0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}

8

9

{0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}7

4

{0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}6

8

{0,4,7},{1,3},{2},{5},{6,8,9,10},{11}3

5

{0,4,7},{1,3,5},{2},{6,8,9,10},{11}2

11{0,4,7},{1,3,5},{2,11},{6,8,9,10}11

0{0,2,4,7,11},{1,3,5},{6,8,9,10}9/2/202352初始{0},{1},{2},{3},{4},{5},{6}確定等價類的鏈表方法

設(shè)等價對個數(shù)為m，對象個數(shù)為n。一種可選的存儲表示為單鏈表。可為集合的每一對象建立一個帶表頭結(jié)點的單鏈表，并建立一個一維的指針數(shù)組seq[n]作為各單鏈表的表頭結(jié)點向量。seq[i]是第i個單鏈表的表頭結(jié)點，第i個單鏈表中所有結(jié)點的data域存放在等價對中與i等價的對象編號。

當輸入一個等價對(i,j)后，就將集合元素i鏈入第j個單鏈表，且將集合元素j鏈入第i個單鏈表。在輸出時，設(shè)置一個布爾數(shù)組out[n]，用out[i]標記第i個單鏈表是否已經(jīng)輸出。

9/2/202353確定等價類的鏈表方法設(shè)等價對個數(shù)為m，對象個數(shù)為n。算法的輸出從編號i=0的對象開始，對所有的對象進行檢測。在i=0時，循第0個單鏈表先找出形式為(0,j)的等價對，把0和j作為同一個等價類輸出。再根據(jù)等價關(guān)系的傳遞性，找所有形式為(j,k)的等價對，把k也納入包含0的等價類中輸出。如此繼續(xù)，直到包含0的等價類完全輸出為止。接下來再找一個未被標記的編號，如i=1，該對象將屬于一個新的等價類，我們再用上述方法劃分、標記和輸出這個等價類。在算法中使用了一個棧。每次輸出一個對象編號時，都要把這個編號進棧，記下以后還要檢測輸出的等價對象的單鏈表。9/2/202354算法的輸出從編號i=0的對象開始，對所有的對象進行檢輸入所有等價對后的seq數(shù)組及各單鏈表的內(nèi)容9/2/202355輸入所有等價對后的seq數(shù)組及各單鏈表的內(nèi)容8/2/2023voidmain(void){//離線等價類問題intn,r;//輸入n和rcout<<"Enternumberofelements"<<endl;cin>>n;if(n<2){cerr<<"Toofewelements"<<endl;exit(l);}cout<<"Enternumberofrelations"<<endl;cin>>r;if(r<1){cerr<<"Toofewrelations"<<endl;exit(l);}離線等價類程序(一)9/2/202356voidmain(void)離線等價類程序(一)8/2/2//創(chuàng)建一個指向n個鏈表的數(shù)組Chain<int>*chain;try{chain=newChain<int>[n+1];}catch(NoMem){cerr<<"Outofmemory"<<endl;exit(1);}//輸入r個關(guān)系，并存入鏈表for(inti=1;i<=r;i++){cout<<"Enternextrelation/pair"<<endl;inta,b;cin>>a>>b;chain[a].Insert(0,b);chain[b].Insert(0,a);}離線等價類程序(一)9/2/202357//創(chuàng)建一個指向n個鏈表的數(shù)組離線等價類程序(一)8/2/2//對欲輸出的等價類進行初始化LinkedStack<int>stack;bool*out;try{out=newbool[n+1];}catch(NoMem){cerr<<"Outofmemory"<<endl;exit(l);}for(inti=1;i<=n;i++) out[i]=false;//輸出等價類for(inti=1;i<=n;i++) if(!out[i]){//開始一個新的等價類 cout<<"Nextclassis:"<<i<<''; out[i]=true;

stack.Add(i);離線等價類程序(二)9/2/202358//對欲輸出的等價類進行初始化離線等價類程序(二)8/2/2//從堆棧中取其余的元素while(!stack.IsEmpty()){ int*q,j;

stack.Delete(j); //鏈表chain[j]中的元素在同一個等價類中，使用遍歷器取這些元素 ChainIterator<int>c; q=c.Initialize(chain[j]); while(q){ if(!out[*q]){cout<<"q<<'';out[*q]=true;

stack.Add(*q);} q=c.Next(); }}cout<<endl;}cout<<endl<<"Endofclasslist"<<endl;}離線等價類程序(二)9/2/202359//從堆棧中取其余的元素離線等價類程序(二)8/2/2023迷宮老鼠(ratinamaze)問題要求尋找一條從入口到出口的路徑。路徑是由一組位置構(gòu)成的，每個位置上都沒有障礙，且每個位置(第一個除外)都是前一個位置的東、南、西或北的鄰居。迷宮老鼠問題9/2/202360迷宮老鼠(ratinamaze)問題要求尋找一條從入口假定用n×m的矩陣來描述迷宮，位置(1,1)表示入口，(n,m)表示出口，n和m分別代表迷宮的行數(shù)和列數(shù)。迷宮中的每個位置都可用其行號和列號來指定。在矩陣中，當且僅當在位置(i,j)處有一個障礙時其值為1，否則其值為0。迷宮的描述9/2/202361假定用n×m的矩陣來描述迷宮，位置(1,1)表示入口迷宮的描述9/2/202362迷宮的描述8/2/202362首先把迷宮的入口作為當前位置。如果當前位置是迷宮出口，那么已經(jīng)找到了一條路徑，搜索工作結(jié)束。如果當前位置不是迷宮出口，則在當前位置上放置障礙物，以便阻止搜索過程又繞回到這個位置。然后檢查相鄰的位置中是否有空閑的(即沒有障礙物)，如果有，就移動到這個新的相鄰位置上，然后從這個位置開始搜索通往出口的路徑。如果不成功，選擇另一個相鄰的空閑位置，并從它開始搜索通往出口的路徑。如果所有相鄰的空閑位置都已經(jīng)被探索過，并且未能找到路徑，則表明在迷宮中不存在從入口到出口的路徑。方案9/2/202363首先把迷宮的入口作為當前位置。方案8/2/202363對于迷宮內(nèi)部的位置(非邊界位置)，有四種可能的移動方向：右、下、左和上。對于迷宮的邊界位置，只有兩種或三種可能的移動。為了避免在處理內(nèi)部位置和邊界位置時存在差別，可以在迷宮的周圍增加一圈障礙物。簡化算法9/2/202364對于迷宮內(nèi)部的位置(非邊界位置)，有四種可能的移動方向：右、迷宮的描述9/2/202365迷宮的描述8/2/202365可以用行號和列號來指定每個迷宮位置，行號和列號被分別稱之為迷宮位置的行坐標和列坐標?？梢远x一個相應(yīng)的類Position來表示迷宮位置，它有兩個私有成員row和col。為保存從入口到當前位置的路徑，可以采用以下基于公式化描述的堆棧： Stack<Position>path(MaxPathLength);其中MaxPathLength是指最大可能的路徑長度（從入口到迷宮中任一位置）。位置表示9/2/202366可以用行號和列號來指定每個迷宮位置，行號和列號被分別稱之為迷按一種固定的方式來選擇可行的位置，將可以使問題得到簡化。例如，可以首先嘗試向右移動，然后是向下，向左，最后是向上。移動到相鄰位置的方法9/2/202367按一種固定的方式來選擇可行的位置，將可以使問題得到簡化。移動移動到相鄰位置的方法9/2/202368移動到相鄰位置的方法8/2/202368假定maze、m(迷宮的大小)和path都是按如下方式定義的全局變量：int**maze,m;Stack<Position>*path;迷宮算法實現(xiàn)9/2/202369假定maze、m(迷宮的大小)和path都是按如下方式定義boolFindPath(){//尋找從位置(1,1)到出口(m,m)的路徑//如果成功則返回true，否則返回false//如果內(nèi)存不足則引發(fā)異常NoMempath=newS