迷宮問題非遞歸求解--數(shù)據(jù)結(jié)構(gòu)c語言課程設(shè)計

1、. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 題目：迷宮問題非遞歸求解 2010年 6月 4日目錄 一. 實驗內(nèi)容.3二. 需求分析3三總體設(shè)計4四詳細設(shè)計6五代 碼10六. 測 試.15七. 總 結(jié).17一. 實驗內(nèi)容任務(wù)：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：二.需求分析1.可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求：使用非遞歸算法。2.用戶可以根據(jù)自己的需求進行輸入所需的迷宮，其中1表示迷宮的墻壁，0表示迷宮的通路，從而建立自己的迷宮；3.用戶還可以自己設(shè)計迷宮的入口坐標(biāo)，當(dāng)然也可以設(shè)計出口了；4.程序執(zhí)行的命

2、令包括：（1）構(gòu)造棧Stack, T 描述迷宮中當(dāng)前位置的結(jié)構(gòu)類型, LinkNode鏈表結(jié)點三個類,其中Stack是Linknode的友元類. （2）構(gòu)造存取迷宮的二維指針GetMaze(int &m,int &n) （3）恢復(fù)迷宮Restore(int *maze,int m,int n) （4）在迷宮中尋找一條通路Mazepath(int *maze,int m,int n) （5）輸出所找到的通路PrintPath() (6) 定義當(dāng)前位置移動的4個方向move數(shù)組.三總體設(shè)計存儲結(jié)構(gòu)：首先用二維指針存儲迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶輸入。一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編

3、寫一個求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向（東、南、西、北四個方向所用代表數(shù)字，自行定義）。1從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)定的迷宮沒有通路。迷宮的入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮的任一位置，均可約定有東、南、西、北四個方向可通。經(jīng)過的位置把0變?yōu)?1，帶輸出迷宮路徑后在恢復(fù)迷宮院士為止2

4、. 本程序有三個模塊： 主程序模塊 三個類模塊即其對象：實現(xiàn)棧鏈表抽象數(shù)據(jù)類型； 迷宮二維指針單元模塊：存儲迷宮,尋路徑,輸出迷宮,恢復(fù)迷宮。(二)流程圖存取迷宮GetMaze(int &m,int &n)求取一條路徑MazePath（）if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y)輸入迷宮的長和寬內(nèi)容顯示結(jié)果Printpath（）迷宮無路經(jīng) END數(shù)組move用于更改方向,函數(shù)Push, PrintPath, Restore調(diào)用函數(shù)GetPop, Push,Pop恢復(fù)迷宮Restore()調(diào)用四

5、詳細設(shè)計(一).基本算法：首先用二維指針存儲迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶輸入。一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向（東、南、西、北四個方向所用代表數(shù)字，自行定義）。迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、南、西、北4個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果4方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到

6、了一條通路；若退回到了入口處，則說明不存在通路。用一個二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點在位置（1，1）處，出口點在位置（m,n）處。設(shè)計一個模擬走迷宮的算法，為其尋找一條從入口點到出口點的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的外墻；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；其余元素值用GetMaze函數(shù)獲取.假設(shè)當(dāng)前所在位置是（x,y）。沿某個方向前進一步，它可能到達的位置最多有4。如果用二維數(shù)組move記錄4方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個方向前進

7、一步，可能到達的新位置坐標(biāo)可利用move數(shù)組確定： x=x+moveloop0 y=y+moveloop1從迷宮的入口位置開始，沿圖示方向順序依次進行搜索。定義一個棧，按從入口到出口存取路徑.在搜索過程中，每前進一步，如果有新位置入棧，則把上一個探索的位置存入棧中,當(dāng)前位置”-1”（表示這個位置在通路上），并將該位置的坐標(biāo)壓入棧中。如果沒有新位置入棧，則返回到上一個位置.到達出口后,最后一個位置入棧,輸出路徑,并回復(fù)路徑.把-1變?yōu)?.總之,入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未

8、能到達出口，則所設(shè)定的迷宮沒有通路。迷宮的入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮的任一位置，均可約定有東、南、西、北四個方向可通。(二). 為實現(xiàn)算法，需要類的象數(shù)據(jù)類型：類及其對象:類 Stack 對象成員如下:Stack(); 構(gòu)造函數(shù)，置空棧操作結(jié)果：構(gòu)造一個空的棧S。Stack(); 析構(gòu)函數(shù) void Push(T e); 把元素data壓入棧中T Pop(); 使棧頂元素出棧 T GetPop(); 取出棧頂元素 void Clear(); 把棧清空 bool empty(); 判斷棧是否為空，如果為空則返回1，否則返

9、回0T類 迷宮中當(dāng)前位置的結(jié)構(gòu)類型: T對象成員如下:x; x代表當(dāng)前位置的行坐標(biāo)y; y代表當(dāng)前位置的列坐標(biāo)dir; 0:無效,1:東,2:南,3:西,4:北LinkNode類 鏈表結(jié)點: 對象成員如下:友元類 StackT dataLinkNode *next(三).函數(shù)調(diào)用關(guān)系main GetMaze Mazepath Empy() GetPop() Push() PrintPath() Restore() Pop() GetPop() Push()(四) 算法的時間、空間復(fù)雜度1）本算法在空間上主要開辟了一個二維指針，規(guī)模都是迷宮(m+2)*(n+2)，一個是棧，一個是迷宮路徑記錄，輸

10、出時候調(diào)用棧，在恢復(fù)迷宮。2）在時間上為簡單的鏈表棧的存儲結(jié)構(gòu)，二維指針GetMaze, Restore兩函數(shù)算法時間復(fù)雜度為O（(m+2)*(n+2)）, Mazepath,PrintPath為O(1),（m為行數(shù)，n為列數(shù)）。(五) UML圖T+X:int+y:int+dir:int LinkNode+T dataStack+push(T e):void+T Getpop ( ):void+T pop ( )+empty ( ):bool+Stack ( )+Stack ( )+Clear ( ):void+nextLinkNodeLinkNode-top<<friend>

11、;>五代碼/*以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1,1,1），（1,2,2），（2,2,2），（3,2,3），（3,1,2），。*/#include<iostream>using namespace std;class T /定義描述

12、迷宮中當(dāng)前位置的結(jié)構(gòu)類型public: int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int dir; /0:無效,1:東,2:南,3:西,4:北;class LinkNode /鏈表結(jié)點 friend class Stack;public: T data; LinkNode *next;class Stackprivate: LinkNode *top; /指向第一個結(jié)點的棧頂指針public: Stack(); /構(gòu)造函數(shù)，置空棧 Stack(); /析構(gòu)函數(shù) void Push(T e); /把元素data壓入棧中 T Pop(); /使棧頂元素出棧 T

13、 GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool empty(); /判斷棧是否為空，如果為空則返回1，否則返回0;Stack:Stack() /構(gòu)造函數(shù)，置空棧 top=NULL;Stack:Stack() /析構(gòu)函數(shù)void Stack:Push(T e) /把元素x壓入棧中 LinkNode *P; P=new LinkNode; P->data=e; P->next=top; top=P;T Stack:Pop() /使棧頂元素出棧 T Temp; LinkNode *P; P=top; top=top->next; Temp=P

14、->data; delete P; return Temp;T Stack:GetPop() /取出棧頂元素 return top->data;void Stack:Clear() /把棧清空 top=NULL;bool Stack:empty() /判斷棧是否為空，如果為空則返回1，否則返回0 if(top=NULL) return 1; else return 0;int move42=0,1,1,0,0,-1,-1,0; /定義當(dāng)前位置移動的4個方向bool Mazepath(int *maze,int m,int n); /尋找迷宮maze中從（0，0）到（m,n）的路徑

15、/到則返回true,否則返回falsevoid PrintPath(Stack p); /輸出迷宮的路徑void Restore(int *maze,int m,int n); /恢復(fù)迷宮int* GetMaze(int &m,int &n); /獲取迷宮 /返回存取迷宮的二維指針int main() int m=0,n=0; /定義迷宮的長和寬 int *maze; /定義二維指針存取迷宮 maze=GetMaze(m,n); /調(diào)用GetMaze(int &m,int &n)函數(shù)，得到迷宮 if(Mazepath(maze,m,n) /調(diào)用Mazepath(

16、int *maze,int m,int n)函數(shù)獲取路徑 cout<<"迷宮路徑探索成功!n" else cout<<"路徑不存在!n" return 0;int* GetMaze(int &m,int &n)/返回存取迷宮的二維指針 int *maze; /定義二維指針存取迷宮 int i=0,j=0; cout<<"請輸入迷宮的長和寬:" int a,b;cin>>a>>b; /輸入迷宮的長和寬 cout<<"請輸入迷宮內(nèi)容:n&qu

17、ot; m=a; n=b; /m,n分別代表迷宮的行數(shù)和列數(shù) maze=new int *m+2; /申請長度等于行數(shù)加2的二級指針 for(i= 0;i<m+2;i+) /申請每個二維指針的空間 mazei=new intn+2; for(i=1;i<=m;i+) /輸入迷宮的內(nèi)容，0代表可通，1代表不通 for(j=1;j<=n;j+) cin>>mazeij; for(i=0;i<m+2;i+) mazei0=mazein+1=1; for(i=0;i<n+2;i+) maze0i=mazem+1i=1; return maze; /返回存貯迷宮

18、的二維指針maze;bool Mazepath(int *maze,int m,int n)/尋找迷宮maze中從（0，0）到（m,n）的路徑 /到則返回true,否則返回false Stack q,p; /定義棧p、q,分別存探索迷宮的過程和存儲路徑 T Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /將入口位置入棧 p.Push(Temp1); maze11=-1; /標(biāo)志入口位置已到達過 while(!q.empty() /棧q非空，則反復(fù)探索 Temp2=q.GetPop(); /獲取棧頂元素 if(!(

19、p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入棧，則把上一個探索的位置存入棧p for(loop=0;loop<4;loop+) /探索當(dāng)前位置的4個相鄰位置 x=Temp2.x+moveloop0; /計算出新位置x位置值 y=Temp2.y+moveloop1; /計算出新位置y位置值 if(mazexy=0) /判斷新位置是否可達 Temp1.x=x; Temp1.y=y; mazexy=-1; /標(biāo)志新位置已到達過 q.Push(Temp1); /新位置入棧

20、 if(x=(m)&&(y=(n) /成功到達出口 Temp1.x=m; Temp1.y=n; Temp1.dir=0; p.Push(Temp1); /把最后一個位置入棧 PrintPath(p); /輸出路徑 Restore(maze,m,n); /恢復(fù)路徑 return 1; /表示成功找到路徑 if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) /如果沒有新位置入棧，則返回到上一個位置 p.Pop(); q.Pop(); return 0; /表示查找失敗，即迷宮無路經(jīng)void PrintPa

21、th(Stack p) /輸出路徑 cout<<"迷宮的路徑為n" cout<<"括號內(nèi)的內(nèi)容分別表示為(行坐標(biāo),列坐標(biāo),數(shù)字化方向,方向)n" Stack t; /定義一個棧，按從入口到出口存取路徑 int a,b; T data; LinkNode *temp; temp=new LinkNode; /申請空間 temp->data=p.Pop(); /取棧p的頂點元素，即第一個位置 t.Push(temp->data); /第一個位置入棧t delete temp; /釋放空間 while(!p.empty()

22、/棧p非空，則反復(fù)轉(zhuǎn)移 temp=new LinkNode; temp->data=p.Pop(); /獲取下一個位置 /得到行走方向 a=t.GetPop().x-temp->data.x; /行坐標(biāo)方向 b=t.GetPop().y-temp->data.y; /列坐標(biāo)方向 if(a=1) temp->data.dir=1; /方向向下，用1表示 else if(b=1) temp->data.dir=2; /方向向右，用2表示 else if(a=-1) temp->data.dir=3; /方向向上，用3表示 else if(b=-1) temp-&

23、gt;data.dir=4; /方向向左，用4表示 t.Push(temp->data); /把新位置入棧 delete temp; /輸出路徑，包括行坐標(biāo)，列坐標(biāo)，下一個位置方向 while(!t.empty() /棧非空，繼續(xù)輸出 data=t.Pop(); cout<<'('<<data.x<<','<<data.y<<','<<data.dir<<"," /輸出行坐標(biāo)，列坐標(biāo) switch(data.dir) /輸出相應(yīng)的方向 case 1:cout<<")n"break; case 2:cout<<")n"break; case 3:cout<<")n"break; case 4:cout<<")n"break; case 0:cout<<&