數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—迷宮問題

1、<p><b>　　課程設(shè)計(jì)說明書</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</p><p><b>　　一、課程設(shè)計(jì)的題目</b></p><p><b>　　迷宮問題</b>&

2、lt;/p><p><b>　　二、設(shè)計(jì)內(nèi)容</b></p><p><b>　　1、迷宮問題</b></p><p><b>　　問題描述：</b></p><p>　　以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求求出從入口（1，1）到出口（m,n

3、）的一條通路，或得出沒有通路的結(jié)論。</p><p><b>　　基本要求：</b></p><p>　　首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求迷宮問題的非遞歸程序，求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)， d表示走到下一坐標(biāo)的方向。</p><p><b>　　測(cè)試數(shù)據(jù)：<

4、;/b></p><p>　　左上角（1，1）為入口，右下角（m,n）為出口。</p><p><b>　　選作內(nèi)容：</b></p><p>　?。?）編寫遞歸形式的算法，求得迷宮中的所有可能的通路</p><p>　?。?）以方陣的形式輸出迷宮及其通路迷宮中的所有可能的通路</p><p&g

5、t;　　設(shè)計(jì)工作量：40課時(shí)</p><p><b>　　工作計(jì)劃：</b></p><p><b>　　見課表</b></p><p>　　指導(dǎo)教師簽名：　　　　　　　　　日期：　　　　　　　　</p><p>　　教研室主任簽名：　　　　　　　 日期：　　　　　　　　</p>&

6、lt;p>　　系主任簽名：　　　　　　　　　 日期：　　　　　　　　</p><p>　　長(zhǎng)沙學(xué)院課程設(shè)計(jì)鑒定表</p><p><b>　　摘 要</b></p><p>　　計(jì)算機(jī)系的課程設(shè)計(jì)，我設(shè)計(jì)了一個(gè)迷宮系統(tǒng)，利用了棧結(jié)構(gòu)來保存所走的迷宮路徑，可以實(shí)現(xiàn)尋找迷宮通路的功能，當(dāng)無法找到出口時(shí)，可提示用戶不存在路徑。</p&

7、gt;<p>　　迷宮的地圖可由手動(dòng)輸入，包括迷宮的行數(shù)與列數(shù)、迷宮的具體布局。</p><p>　　關(guān)鍵詞：課程設(shè)計(jì)；迷宮；數(shù)據(jù)結(jié)構(gòu)。</p><p><b>　　目錄</b></p><p>　　1.設(shè)計(jì)內(nèi)容與要求1</p><p><b>　　2.設(shè)計(jì)說明2</b></

8、p><p><b>　　2.1界面設(shè)計(jì)2</b></p><p>　　2.2 數(shù)據(jù)結(jié)構(gòu)3</p><p><b>　　3.實(shí)現(xiàn)與測(cè)試4</b></p><p><b>　　3.1結(jié)果4</b></p><p><b>　　3.2測(cè)試過程5

9、</b></p><p><b>　　總結(jié)7</b></p><p><b>　　參考文獻(xiàn)8</b></p><p><b>　　附錄A 源代碼9</b></p><p><b>　　1.設(shè)計(jì)內(nèi)容與要求</b></p>&l

10、t;p><b>　　設(shè)計(jì)要求：</b></p><p><b>　　問題描述：</b></p><p>　　以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。迷宮問題要求求出從入口（1，1）到出口（m,n）的一條通路，或得出沒有通路的結(jié)論。</p><p><b>　　基本要求：</b&

11、gt;</p><p>　　首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求迷宮問題的非遞歸程序，求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)， d表示走到下一坐標(biāo)的方向。</p><p><b>　　測(cè)試數(shù)據(jù)：</b></p><p>　　左上角（1，1）為入口，右下角（m,n）為出口。</p&g

12、t;<p><b>　　選作內(nèi)容：</b></p><p>　　（1）編寫遞歸形式的算法，求得迷宮中的所有可能的通路</p><p>　?。?）以方陣的形式輸出迷宮及其通路迷宮中的所有可能的通路</p><p><b>　　2.設(shè)計(jì)說明</b></p><p><b>　　2

13、.1界面設(shè)計(jì)</b></p><p>　　迷宮系統(tǒng)歡迎界面如圖2.1所示。</p><p>　　由三個(gè)菜單組成，為創(chuàng)建地圖、打印路徑與退出。</p><p>　　圖2.1 迷宮系統(tǒng)歡迎界面</p><p>　　迷宮界面如圖2.2所示。</p><p>　　先按1創(chuàng)建地圖，再輸入迷宮行與列，再輸入迷宮布局，

14、出現(xiàn)圖2.2的內(nèi)容。</p><p>　　圖2.2 迷宮游戲界面</p><p>　　路徑界面如圖2.3所示。</p><p>　　創(chuàng)建好地圖之后，按2就可以打印路徑。</p><p><b>　　圖2.3 路徑界面</b></p><p><b>　　2.2數(shù)據(jù)結(jié)構(gòu)</b>

15、</p><p>　　數(shù)據(jù)結(jié)構(gòu)圖如 圖2.4所示。</p><p>　　主函數(shù)調(diào)用迷宮函數(shù)，迷宮函數(shù)調(diào)用輸出路徑函數(shù)，從而實(shí)現(xiàn)功能。</p><p>　　圖2.4 數(shù)據(jù)結(jié)構(gòu)圖</p><p><b>　　3.實(shí)現(xiàn)與測(cè)試</b></p><p>　　優(yōu)良。整個(gè)測(cè)試包含如下內(nèi)容：</p>

16、<p><b>　　綜合評(píng)估：</b></p><p>　　整個(gè)軟件開發(fā)難度還算較簡(jiǎn)單，過程雖然繁瑣，容易出錯(cuò)，但總的結(jié)果還算可以。</p><p>　　整體上較好，樣式簡(jiǎn)單，美觀。</p><p>　　b. 軟件開發(fā)中計(jì)劃的執(zhí)行情況：</p><p>　　測(cè)試頁面的連接情況及是否出現(xiàn)異常狀況。</p

17、><p>　　測(cè)試結(jié)果狀況良好，無出現(xiàn)不良情況。</p><p>　　c. 軟件質(zhì)量目標(biāo)完成情況： </p><p>　　完成情況良好，質(zhì)量品質(zhì)</p><p><b>　　3.1結(jié)果</b></p><p>　　輸入一些臨界數(shù)據(jù)進(jìn)行測(cè)試:</p><p>　　當(dāng)輸入的迷宮為4

18、*4的</p><p><b>　　1 1 1 1</b></p><p><b>　　1 1 1 1</b></p><p><b>　　1 1 1 1</b></p><p><b>　　1 1 1 1</b></p><p>

19、　　時(shí)，輸出結(jié)果為“不存在路徑”。如下圖3.1：</p><p>　　圖3.1 </p><p>　　當(dāng)輸入的迷宮為4*4的</p><p><b>　　0 0 0 0</b></p><p><b>　　0 0 0 0</b></p><p><b>

20、;　　0 0 0 0 </b></p><p><b>　　0 0 0 0</b></p><p>　　時(shí)，輸出結(jié)果如下圖3.2</p><p><b>　　圖3.2 </b></p><p><b>　　3.2測(cè)試過程</b></p><p&g

21、t;　　頁面測(cè)試報(bào)告如表3.1：</p><p>　　表3.1 頁面測(cè)試報(bào)告</p><p>　　迷宮結(jié)果測(cè)試報(bào)告如表3.2：</p><p>　　表3.2 迷宮輸出報(bào)告</p><p><b>　　總結(jié)</b></p><p><b>　　綜合評(píng)估：</b></p&g

22、t;<p>　　整個(gè)軟件開發(fā)難度還算較簡(jiǎn)單，過程雖然繁瑣，容易出錯(cuò)，但總的結(jié)果還算可以。</p><p>　　整體上較好，樣式簡(jiǎn)單，美觀。</p><p>　　軟件開發(fā)中計(jì)劃的執(zhí)行情況</p><p>　　測(cè)試頁面的連接情況及是否出現(xiàn)異常狀況。</p><p>　　測(cè)試結(jié)果狀況良好，無出現(xiàn)不良情況。</p><

23、;p>　　軟件質(zhì)量目標(biāo)完成情況： </p><p>　　完成情況良好，質(zhì)量品質(zhì)優(yōu)良。</p><p>　　總結(jié)開發(fā)活動(dòng)中的檢驗(yàn)與教訓(xùn)</p><p>　　在本次課程設(shè)計(jì)中，我學(xué)會(huì)了許多的東西，開始的時(shí)候，我犯了許多的錯(cuò)誤，通過同學(xué)和老師的幫助，一個(gè)個(gè)突破，才有這次的課程設(shè)計(jì)。所以。做啥事都得認(rèn)真對(duì)待，這樣才能提升自己。</p><p>

24、<b>　　參考文獻(xiàn)</b></p><p>　　[1] 王挺. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社，2005.</p><p>　　[2] 吳偉民. 數(shù)據(jù)結(jié)構(gòu)[M]. 北京：清華大學(xué)出版社，2006. </p><p><b>　　附錄A 源代碼</b></p><p>　　#include&

25、lt;iostream></p><p>　　using namespace std;</p><p>　　struct D </p><p><b>　　{</b></p><p>　　int x; //x代表當(dāng)前位置的行坐標(biāo)</p><p>　　int y;

26、 //y代表當(dāng)前位置的列坐標(biāo)</p><p>　　int dir; </p><p><b>　　};</b></p><p>　　struct Link </p><p><b>　　{</b></p><p><b>　

27、　D data;</b></p><p>　　Link *next;</p><p><b>　　};</b></p><p><b>　　//Stack</b></p><p>　　class Stack</p><p><b>　　{</b&g

28、t;</p><p><b>　　private:</b></p><p>　　Link *top; //指向棧頂節(jié)點(diǎn)的指針</p><p><b>　　public:</b></p><p>　　Stack(); </p><p>

29、;　　~Stack(); </p><p>　　void Push(const D& e); //把元素data壓入棧中</p><p>　　D Pop(); //使棧頂元素出棧</p><p>　　D GetTop(); //取出棧頂元素

30、 </p><p>　　bool Empty(); //判斷棧是否為空,是空的話返回true</p><p><b>　　};</b></p><p>　　Stack::Stack() //構(gòu)造函數(shù)，置空棧</p><p><b>　　{</b></p>

31、;<p><b>　　top=NULL;</b></p><p><b>　　}</b></p><p>　　Stack::~Stack() {} //析構(gòu)函數(shù)</p><p>　　void Stack::Push(const D & e) //把元素x壓入棧中<

32、/p><p><b>　　{</b></p><p>　　Link *P=new Link;</p><p>　　P->data=e;</p><p>　　P->next=top;</p><p><b>　　top=P;</b></p><p&g

33、t;<b>　　}</b></p><p>　　D Stack::Pop() //使棧頂元素出棧</p><p><b>　　{ </b></p><p>　　Link *P=top;</p><p>　　top=top->next;</p>&l

34、t;p>　　D Temp=P->data;</p><p><b>　　delete P;</b></p><p>　　return Temp;</p><p><b>　　}</b></p><p>　　D Stack::GetTop() {return top->data;}

35、 //取出棧頂元素</p><p>　　bool Stack::Empty() { return (top==NULL);}</p><p>　　int move[8][2]={ {0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1} }; //定義當(dāng)前位置移動(dòng)的8個(gè)方向</p><p&

36、gt;　　bool FindPath(int **maze,const int& m,const int & n); //尋找路徑</p><p>　　void Print(Stack & p,int ** maze,const int & m,const int & n); //輸出迷宮的路徑</p><p>　　int** Cr

37、eateMaze(int &m,int &n); //創(chuàng)建迷宮</p><p>　　//返回存取迷宮的二維指針</p><p>　　int main()</p><p><b>　　{</b></p><p>　　int m=0,n=0; //定義迷宮的長(zhǎng)和寬</p>

38、<p>　　int **maze; //定義二維指針存取迷宮</p><p>　　int choice=1,create=0;</p><p>　　while(choice)</p><p><b>　　{</b></p><p>　　cout<<"************

39、*******迷宮系統(tǒng)*************************"<<endl;</p><p>　　cout<<" 請(qǐng)選擇"<<endl;</p><p>　　cout<<"創(chuàng)建迷宮地圖-----------------------------------

40、---①"<<endl;</p><p>　　cout<<"打印路徑 --------------------------------------②"<<endl;</p><p>　　cout<<"退出 --------------------------------------○

41、"<<endl;</p><p>　　cout<<"****************************************************"<<endl;</p><p>　　cin>>choice;</p><p>　　switch(choice)</p>

42、<p><b>　　{</b></p><p><b>　　case 1: </b></p><p>　　maze=CreateMaze(m,n); //調(diào)用GetMaze(int &m,int &n)函數(shù)，得到迷宮</p><p><b>　　create=1;</b>

43、</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p>　　if(0==create)</p><p><b>　　{</b></p><p>　　cout<<"未創(chuàng)建

44、迷宮地圖，請(qǐng)先創(chuàng)建地圖??！"<<endl;</p><p>　　maze=CreateMaze(m,n); </p><p><b>　　}</b></p><p>　　if(FindPath(maze,m,n)) //調(diào)用Mazepath(int **maze,int m,int n)函數(shù)獲取路徑</p>

45、<p>　　cout<<"迷宮路徑探索成功!\n";</p><p><b>　　else </b></p><p>　　cout<<"路徑不存在!\n";</p><p><b>　　break;</b></p><p>&

46、lt;b>　　case 0:</b></p><p><b>　　break;</b></p><p><b>　　default:</b></p><p>　　cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;</p><p><

47、b>　　break;</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><

48、p>　　int** CreateMaze(int &m,int &n)//返回存取迷宮的二維指針</p><p><b>　　{</b></p><p>　　int **maze; //定義二維指針存取迷宮</p><p>　　int i=0,j=0,a,b;</p><p&g

49、t;　　cout<<"請(qǐng)輸入迷宮的長(zhǎng)和寬:";</p><p>　　cin>>a>>b; //輸入迷宮的長(zhǎng)和寬</p><p>　　if(a<=1||b<=1)</p><p><b>　　{</b></p><p>　　cout<<&

50、quot;設(shè)置有誤，默認(rèn)設(shè)為2X2大小的"<<endl;</p><p><b>　　a=2;</b></p><p><b>　　b=2;</b></p><p><b>　　}</b></p><p>　　cout<<"請(qǐng)輸入迷宮

51、內(nèi)容:(0代表可通,1代表不可通)\n";</p><p><b>　　m=a;</b></p><p>　　n=b; //m,n分別代表迷宮的行數(shù)和列數(shù)</p><p>　　maze=new int *[m+2]; </p><p>　　for(i= 0;i<m+2;++i) &l

52、t;/p><p><b>　　{</b></p><p>　　maze[i]=new int[n+2];</p><p><b>　　}</b></p><p>　　for(i=1;i<=m;++i) </p><p>　　for(j=1;j<=n;

53、++j)</p><p>　　cin>>maze[i][j];</p><p>　　for(i=0;i<m+2;++i)</p><p>　　maze[i][0]=maze[i][n+1]=1;</p><p>　　for(i=0;i<n+2;++i)</p><p>　　maze[0][i]=

54、maze[m+1][i]=1;</p><p><b>　　//設(shè)置邊界</b></p><p>　　return maze; //返回存貯迷宮的二維指針maze</p><p><b>　　};</b></p><p>　　bool FindPath(int **maze

55、,const int& m,const int & n)//尋找迷宮maze中從（0，0）到（m,n）的路徑</p><p>　　//到則返回true,否則返回false</p><p><b>　　{</b></p><p>　　Stack Spath,Sproc; //定義棧Sproc、Spath,分別存

56、 探索迷宮的過程 和 存儲(chǔ)路徑</p><p>　　D Temp1,Temp2; </p><p>　　int x,y,loop;</p><p>　　Temp1.x=1;</p><p>　　Temp1.y=1;</p><p>　　Sproc.Push(Temp1); /

57、/將入口位置入棧</p><p>　　Spath.Push(Temp1);</p><p>　　maze[1][1]=2; //標(biāo)志入口位置已到達(dá)過</p><p>　　while(!Sproc.Empty()) //棧Sproc非空，則反復(fù)探索</p><p><b>　　{</b></p>

58、<p>　　Temp2=Sproc.GetTop(); //獲取棧頂元素</p><p>　　if(!(Sproc.GetTop().x==Spath.GetTop().x&&Sproc.GetTop().y==Spath.GetTop().y)) </p><p>　　Spath.Push(Temp2); //如果有新位置入棧，則把上一個(gè)探索的位置

59、存入棧Spath</p><p>　　for(loop=0;loop<8;++loop) //探索當(dāng)前位置的8個(gè)相鄰位置</p><p><b>　　{</b></p><p>　　x=Temp2.x+move[loop][0]; //計(jì)算出新位置x位置值</p><p>　　y=Temp2.y+mov

60、e[loop][1]; //計(jì)算出新位置y位置值</p><p>　　if(maze[x][y]==0) //判斷新位置是否可達(dá)</p><p><b>　　{</b></p><p>　　Temp1.x=x;</p><p>　　Temp1.y=y;</p><p>　

61、　maze[x][y]=2; //標(biāo)志新位置已到達(dá)過</p><p>　　Sproc.Push(Temp1); //新位置入棧</p><p><b>　　}</b></p><p>　　if((x==(m))&&(y==(n))) //成功到達(dá)出口</p><p>

62、;<b>　　{</b></p><p>　　Temp1.x=m;</p><p>　　Temp1.y=n;</p><p>　　Temp1.dir=0;</p><p>　　Spath.Push(Temp1); //把最后一個(gè)位置入棧</p><p>　　Print(Spath,ma

63、ze,m,n); //輸出路徑</p><p>　　return true; //表示成功找到路徑</p><p><b>　　}</b></p><p><b>　　}//for</b></p><p>　　//如果沒有新位置入棧，則返回到上一個(gè)位置&l

64、t;/p><p>　　if(Sproc.GetTop().x==Spath.GetTop().x&&Sproc.GetTop().y==Spath.GetTop().y)</p><p><b>　　{</b></p><p>　　Sproc.Pop();</p><p>　　Spath.Pop();<

65、;/p><p><b>　　}</b></p><p><b>　　}//while</b></p><p>　　return false; //表示查找失敗，即迷宮無路經(jīng)</p><p><b>　　}</b></p><p>　　vo

66、id Print(Stack & p,int ** maze,const int & m,const int & n) //輸出路徑</p><p><b>　　{</b></p><p>　　Stack temp=p;</p><p><b>　　D data;</b></p&

67、gt;<p>　　while(!temp.Empty())</p><p><b>　　{</b></p><p>　　data=temp.Pop();</p><p>　　maze[data.x][data.y]=8;</p><p><b>　　}</b></p>&

68、lt;p><b>　　int i,j;</b></p><p>　　for(i=1;i<=m;++i)</p><p>　　for(j=1;j<=n;++j)</p><p><b>　　{</b></p><p>　　if(maze[i][j]==8)</p>&l

69、t;p>　　cout<<'*';</p><p><b>　　else</b></p><p>　　cout<<maze[i][j];</p><p>　　cout<<' ';</p><p><b>　　if(j==n)</b&g