數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---走迷宮游戲

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告</p><p>　　完成日期：2012-6</p><p>　　目 錄</p><p>　　1課程設(shè)計的目的3</p><p>　　1.1課程設(shè)計的目的:3</p><p>　　1.2課程設(shè)計的題目:走迷宮游戲3</p><p>

2、;　　1.3題目要求:3</p><p>　　2課程設(shè)計的實驗報告內(nèi)容:4</p><p>　　3課程設(shè)計的原程序代碼:4</p><p><b>　　4運(yùn)行結(jié)果:16</b></p><p>　　5. 課程設(shè)計總結(jié)21</p><p><b>　　6參考書目：22</

3、b></p><p>　　1 課程設(shè)計的目的</p><p>　　1.1 課程設(shè)計的目的</p><p>　　數(shù)據(jù)結(jié)構(gòu)是實踐性很強(qiáng)的課程。課程設(shè)計是加強(qiáng)我們實踐能力的一個強(qiáng)有力手段。在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告，這樣對于我們對基本程序設(shè)計素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。</p><p>

4、　　1.2 課程設(shè)計的題目</p><p><b>　　走迷宮游戲</b></p><p><b>　　1.3 題目要求</b></p><p>　　老鼠形象可辨認(rèn)，可用鍵盤操縱老鼠上下左右移動；</p><p>　　迷宮的墻足夠結(jié)實，老鼠不能穿墻而過；</p><p>

5、　　正確檢測結(jié)果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，否則提示失??；</p><p>　　添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻；</p><p>　　找出走出迷宮的所有路徑，以及最短路徑。</p><p><b>　　2 概要設(shè)計</b></p><p><b>　　2.1 存儲結(jié)

6、構(gòu)</b></p><p>　　基本抽象數(shù)據(jù)類型：建立堆棧存儲結(jié)構(gòu)</p><p>　　Struct step</p><p><b>　　{</b></p><p>　　int x,y,n; //整形（注：基本數(shù)據(jù)類型，步子行、列坐標(biāo)、行走步數(shù)）</p><p><b>

7、　　}</b></p><p>　　Char **maze //字符數(shù)組（注：定義一個動態(tài)空間迷宮）</p><p>　　Int hang,lie; //整型（注：輸入迷宮的行、列數(shù)）</p><p>　　Int s; //整型（注：用于控制是否重新進(jìn)入運(yùn)行程序）</p><p><b>　　2.2 基本操作<

8、;/b></p><p>　　1）改變迷宮形狀模塊：</p><p>　　Void change(char **maze,int hang,int lie)</p><p>　　//輸入迷宮地圖，輸出形狀改變后迷宮。</p><p><b>　　2）單步輸出模塊</b></p><p>　　

9、void step_to_step (char **maze,step *step,int hang,int lie,int n) </p><p>　　//輸入迷宮地圖，輸出單步行走步法。</p><p><b>　　3）輸出路徑模塊</b></p><p>　　void out (char **maze,int hang,int lie,i

10、nt i,int j)</p><p>　　//輸入迷宮地圖，整體輸出行走路徑。</p><p>　　4）判斷行走路徑模塊</p><p>　　void cure (char **maze,int hang,int lie)</p><p>　　//輸入迷宮地圖，輸出每一步行走步法。</p><p><b>

11、　　5）主程序模塊</b></p><p>　　int main() </p><p><b>　　3 詳細(xì)設(shè)計</b></p><p><b>　　3.1 流程圖</b></p><p><b>　　主程序流程圖</b></p><p>

12、;<b>　　系統(tǒng)結(jié)構(gòu)圖</b></p><p><b>　　子流程圖</b></p><p>　　1） 改變迷宮形狀模塊</p><p>　　單步輸出路徑模塊：</p><p>　　3) 輸出整體路徑模塊：</p><p>　　3) 判斷每一步行走路徑模塊：<

13、/p><p><b>　　3.2 源程序</b></p><p>　　#include <iostream> </p><p>　　#include <conio.h> </p><p>　　using namespace std; </p><p>　　struct ste

14、p //定義一個棧 </p><p><b>　　{ </b></p><p>　　int x,y,n; //x，y表示步子坐標(biāo)，n表示步數(shù) </p><p><b>　　}; </b></p><p>　　void change(char **

15、maze,int hang,int lie) </p><p>　　//改變迷宮的樣子,便于觀察單步行走過程 </p><p><b>　　{ </b></p><p>　　for(int i=0;i<hang+2;i++) </p><p><b>　　{ </b></p>

16、<p>　　for(int j=0;j<lie+2;j++) </p><p>　　switch(maze[i][j]) </p><p><b>　　{ </b></p><p>　　case '1': maze[i][j]='#';break; </p><p>

17、　　case '+': </p><p>　　case '0': </p><p>　　case '.': maze[i][j]=' ';break; </p><p><b>　　} </b></p><p><b>　　}</b>

18、</p><p><b>　　} </b></p><p>　　void step_to_step(char **maze,step *Step,int hang,int </p><p>　　lie,int n) </p><p>　　{ //單步輸出 </p&

19、gt;<p>　　for(int k=0;k<=n;k++) //k為步數(shù) </p><p><b>　　{ </b></p><p>　　for(int i=0;i<hang+2;i++) </p><p><b>　　{ </b></p><p>　　for(i

20、nt j=0;j<lie+2;j++) </p><p><b>　　{ </b></p><p>　　if(Step[k].x==i&&Step[k].y==j)//找出走過每一步的坐標(biāo) </p><p>　　cout<<"."<<" "; </p&g

21、t;<p>　　else cout<<maze[i][j]<<" "; </p><p><b>　　} </b></p><p>　　cout<<endl; </p><p><b>　　} </b></p><p>　　cou

22、t<<"這是第"<<k+1<<"步"<<endl<<endl; </p><p>　　getch(); //顯示程序運(yùn)行結(jié)果 </p><p><b>　　} </b></p><p><b>　　} </b><

23、;/p><p>　　void out(char **maze,int hang,int lie,int i,int j) //輸出所走的路程 </p><p>　　{ </p><p>　　if(i==1&&j==1) //若回到原點則表明無出路 &

24、lt;/p><p><b>　　{ </b></p><p>　　cout<<endl; </p><p>　　cout<<"*************************************************"<<endl; </p><p>　　cou

25、t<<"|-------------此迷宮沒有出路，所走路線如下圖---------------|"<<endl; </p><p>　　cout<<"************************************************************"<<endl; </p><p&g

26、t;<b>　　} </b></p><p>　　else //否則有出路 </p><p><b>　　{ </b></p><p>　　cout<<endl;</p><p>　　cout<<"*****

27、*******************************************************"<<endl; </p><p>　　cout<<"|----------------找到迷宮出路，如圖所示--------------------|"<<endl; </p><p>　　cout<<

28、"************************************************************"<<endl; </p><p><b>　　} </b></p><p>　　for(i=0;i<hang+2;i++) //輸出步子 </p><p&g

29、t;<b>　　{ </b></p><p>　　for(j=0;j<lie+2;j++) </p><p>　　cout<<maze[i][j]<<" "; </p><p>　　cout<<endl; </p><p><b>　　} <

30、;/b></p><p><b>　　} </b></p><p>　　void cure(char **maze,int hang,int lie) </p><p>　　//判斷每一步行走步法 </p><p><b>　　{ </b></p><p>　　i

31、nt i=1,j=0,n=-1; </p><p><b>　　char Q; </b></p><p>　　step *Step; //定義一個存儲路程的棧 </p><p>　　Step=new step [hang*lie]; //事先給其分配一定的空間，[hang*lie]表示空

32、間足夠 </p><p>　　while(maze[hang][lie]!='.') //由右、下、左、上的順序判斷是否走通 </p><p>　　{ </p><p>　　//'1'表示走不通，'+'表示已經(jīng)走過但不通又回來的步子，'.'表示已經(jīng)走過并

33、通了的步子 </p><p>　　if(maze[i][j+1]!='1'&&maze[i][j+1]!='.'&&maze[i][j+1]!='+') //判斷向右是否可走 </p><p><b>　　{ </b></p><p>　　if(i==1&

34、&j==0) </p><p><b>　　{ </b></p><p>　　cout<<"老鼠"<<endl; </p><p><b>　　} </b></p><p><b>　　else </b></p>

35、<p>　　cout<<"右"<<endl; </p><p>　　maze[i][j+1]='.'; </p><p><b>　　j=j+1; </b></p><p><b>　　n++; </b></p><p>　　S

36、tep[n].x=i; </p><p>　　Step[n].y=j; //第n步的坐標(biāo) </p><p>　　cout<<i<<","<<j; </p><p><b>　　} else </b></p><p>　　if(maze[i+1][j]!='

37、1'&&maze[i+1][j]!='.'&&maze[i+1][j]!='+') //判斷向下 </p><p><b>　　{ </b></p><p>　　cout<<"下"<<endl; </p><p>　　maze[

38、i+1][j]='.'; </p><p><b>　　i=i+1; </b></p><p><b>　　n++; </b></p><p>　　Step[n].x=i; </p><p>　　Step[n].y=j; </p><p>　　cout<

39、<i<<","<<j; </p><p><b>　　} </b></p><p><b>　　else </b></p><p>　　if(maze[i][j-1]!='1'&&maze[i][j-1]!='.'&&

40、amp;maze[i][j-1]!='+') </p><p><b>　　{ </b></p><p>　　cout<<"左"<<endl; </p><p>　　maze[i][j-1]='.'; </p><p><b>　　j

41、=j-1; </b></p><p><b>　　n++; </b></p><p>　　Step[n].x=i; </p><p>　　Step[n].y=j; </p><p>　　cout<<i<<","<<j; </p><p

42、><b>　　} </b></p><p><b>　　else </b></p><p>　　if(maze[i-1][j]!='1'&&maze[i-1][j]!='.'&&maze[i-1][j]!='+') //判斷向上 </p><

43、;p><b>　　{ </b></p><p>　　cout<<"上"<<endl; </p><p>　　maze[i-1][j]='.'; </p><p><b>　　i=i-1; </b></p><p><b>　

44、　n++; </b></p><p>　　Step[n].x=i; </p><p>　　Step[n].y=j; </p><p>　　cout<<i<<","<<j; </p><p><b>　　} </b></p><p>

45、;　　else //若走不通則返回上一步 </p><p><b>　　{ </b></p><p>　　if(i==1&&j==1) //當(dāng)回到入口時，說明無通路，結(jié)束循環(huán) </p><p><b>　　break; </b><

46、/p><p><b>　　else </b></p><p><b>　　{ </b></p><p>　　maze[i][j]='+'; //將走不通的點置為+ </p><p><b>　　n--; </b></p><

47、p>　　i=Step[n].x; //返回上一個點 </p><p>　　j=Step[n].y; </p><p>　　cout<<"返回"<<endl<<i<<","<<j; //輸出返回信息 </p><p>　　}

48、 </p><p><b>　　} </b></p><p>　　if(i==hang&&j==lie) //到達(dá)糧倉 </p><p>　　cout<<"(出口)"<<" "<<&qu

49、ot;(共"<<n+1<<"步"<<")"; </p><p><b>　　} </b></p><p>　　out(maze,hang,lie,i,j); </p><p>　　cout<<endl<<endl<<endl

50、; </p><p>　　cout<<"是否想知道老鼠每一步是如何走的(y/n):"; </p><p><b>　　cin>>Q; </b></p><p>　　cout<<endl<<endl; </p><p>　　if(Q=='y'

51、;) </p><p><b>　　{ </b></p><p>　　change(maze,hang,lie); </p><p>　　step_to_step(maze,Step,hang,lie,n); </p><p><b>　　} </b></p><p><

52、;b>　　} </b></p><p>　　int main() </p><p><b>　　{</b></p><p>　　char **maze; //定義一個迷宮，空間可動態(tài) </p><p>　　int s=1, hang,lie,i,j; </p>&l

53、t;p><b>　　int Q; </b></p><p>　　cout<<"歡迎來到走迷宮游戲: "<<endl; </p><p>　　cout<<"想開始嗎？按1游戲開始"<<endl; </p><p><b>　　cin>&g

54、t;Q; </b></p><p>　　cout<<endl<<endl; </p><p><b>　　if(Q==1) </b></p><p><b>　　{ </b></p><p>　　cout<<"請輸入迷宮的行列"&l

55、t;<endl; </p><p>　　cout<<"行數(shù):"; </p><p>　　cin>>hang; </p><p>　　cout<<"列數(shù):"; </p><p>　　cin>>lie; </p><p>　　co

56、ut<<endl; </p><p>　　maze=new char *[hang+2]; //分配連續(xù)空間給迷宮 </p><p>　　for(i=0;i<hang+2;i++) </p><p>　　maze[i]=new char [lie+2]; </p><p>　　cout<<"請輸入

57、迷宮，0表示通路，1表示墻"<<endl; </p><p>　　for(i=1;i<=hang;i++) </p><p>　　for(j=1;j<=lie;j++) </p><p>　　cin>>maze[i][j]; </p><p><

58、;b>　　} </b></p><p>　　if(maze[1][1]=='1') //入口是墻 </p><p><b>　　{ </b></p><p>　　cout<<"入口是墻，老鼠進(jìn)不去!!!"<<endl<<endl; </p>

59、;<p>　　cout<<"請重新輸入!!!"<<endl<<endl; </p><p>　　for(i=1;i<=hang;i++) </p><p>　　for(j=1;j<=lie;j++) </p><p>　　cin>>maze[i][j]; </p&

60、gt;<p><b>　　} </b></p><p>　　for(i=0;i<hang+2;i++) maze[i][0]='1'; </p><p>　　for(i=0;i<lie+2;i++) maze[0][i]='1'; </p><p>　　for(i=0;i<lie+

61、2;i++) maze[hang+1][i]='1'; </p><p>　　for(i=0;i<hang+2;i++) maze[i][lie+1]='1'; //給迷宮外圍加圍墻 </p><p>　　cout<<endl<<endl; </p><p>　　cout<<"**

62、******************您輸入的迷宮為 ******************************"<<endl; </p><p>　　cout<<"行數(shù):"<<hang<<" "<<"列數(shù):"<<lie; </p><p>　　c

63、out<<" "<<"老鼠所在位置:"<<"1,1"<<" "<<"糧倉所在位置:"<<hang<<","<<lie<<endl; </p><p>　　for(i=0;i<h

64、ang+2;i++) </p><p><b>　　{ </b></p><p>　　for(j=0;j<lie+2;j++) </p><p>　　cout<<maze[i][j]<<" "; </p><p>　　cout<<endl; </p>

65、;<p><b>　　} </b></p><p>　　cout<<endl<<endl<<"老鼠所走的步驟如下:"<<endl; </p><p>　　cure(maze,hang,lie); </p><p>　　cout<<endl<<

66、;endl<<endl; </p><p><b>　　getch(); </b></p><p>　　cout<<"你猜對了嗎？"<<endl; </p><p>　　cout<<"你還想玩嗎？1：yes 2：no"<<endl; </

67、p><p><b>　　cin>>s; </b></p><p><b>　　if(s=1) </b></p><p><b>　　{ </b></p><p>　　cout<<"想開始嗎？按1游戲開始"<<endl; <

68、;/p><p><b>　　cin>>Q; </b></p><p>　　cout<<endl<<endl; </p><p><b>　　if(Q==1) </b></p><p><b>　　{ </b></p><p&g

69、t;　　cout<<"請輸入迷宮的行列"<<endl; </p><p>　　cout<<"行數(shù):"; </p><p>　　cin>>hang; </p><p>　　cout<<"列數(shù):"; </p><p>　　cin

70、>>lie; </p><p>　　cout<<endl; </p><p>　　maze=new char *[hang+2]; //分配連續(xù)空間給迷宮 </p><p>　　for(i=0;i<hang+2;i++) </p><p>　　maze[i]=new char [lie+2]; </

71、p><p>　　cout<<"請輸入迷宮，0表示通路，1表示墻"<<endl; </p><p>　　for(i=1;i<=hang;i++) </p><p>　　for(j=1;j<=lie;j++) </p><p>　　cin>>maze[i][j];

72、 </p><p><b>　　} </b></p><p>　　if(maze[1][1]=='1') </p><p><b>　　{ </b></p><p>　　cout<<"入口是墻，老鼠進(jìn)不去!!!"<&l

73、t;endl<<endl; </p><p>　　cout<<"請重新輸入!!!"<<endl<<endl; </p><p>　　for(i=1;i<=hang;i++) </p><p>　　for(j=1;j<=lie;j++) </p><p>　　cin

74、>>maze[i][j]; </p><p><b>　　} </b></p><p>　　for(i=0;i<hang+2;i++) maze[i][0]='1'; </p><p>　　for(i=0;i<lie+2;i++) maze[0][i]='1'; </p>

75、<p>　　for(i=0;i<lie+2;i++) maze[hang+1][i]='1'; </p><p>　　for(i=0;i<hang+2;i++) maze[i][lie+1]='1'; </p><p>　　cout<<endl<<endl; </p><p>　　cou

76、t<<"********************您輸入的迷宮為******************************"<<endl; </p><p>　　cout<<"行數(shù):"<<hang<<" "<<"列數(shù):"<<lie; </p&g

77、t;<p>　　cout<<" "<<"老鼠所在位置："<<"1,1"<<" "<<"糧倉所在位 置："<<hang<<","<<lie<<endl; </p><p>

78、;　　for(i=0;i<hang+2;i++) </p><p><b>　　{ </b></p><p>　　for(j=0;j<lie+2;j++) </p><p>　　cout<<maze[i][j]<<" "; </p><p>　　cout<&l

79、t;endl; </p><p><b>　　} </b></p><p>　　cout<<endl<<endl<<"老鼠所走的步驟如下:"<<endl; </p><p>　　cure(maze,hang,lie); </p><p>　　co

80、ut<<endl<<endl<<endl; </p><p><b>　　getch(); </b></p><p>　　cout<<"你還想玩嗎？1：yes 2：no"<<endl; </p><p><b>　　cin>>s;</b

81、></p><p><b>　　} </b></p><p><b>　　else </b></p><p>　　cout<<"走迷宮游戲結(jié)束！ "<<endl; </p><p>　　return 0; </p><p>&

82、lt;b>　　} </b></p><p><b>　　4 測試</b></p><p>　　1）進(jìn)入“走迷宮游戲”</p><p>　　2）第一次測試，輸入迷宮行列數(shù)和一個無通路迷宮，運(yùn)行結(jié)果如下：</p><p>　　3）第二次測試，輸入有通路迷宮，運(yùn)行結(jié)果如下：</p><

83、p>　　4）選擇單步運(yùn)行，運(yùn)行結(jié)果如下：</p><p><b>　　5 課程設(shè)計總結(jié)</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)科學(xué)與技術(shù)專業(yè)一門十分重要的專業(yè)技術(shù)基礎(chǔ)課，理論知識固然重要，但通過動手實踐將理論知識應(yīng)用于實際設(shè)計才是重中之重。在為期兩周的“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計”中，我明確了學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的最終目的是解決實際的應(yīng)用問題。</p>

84、<p>　　在課設(shè)中，通過分析任務(wù)書，在已學(xué)基礎(chǔ)上構(gòu)造出程序大體框架，畫出系統(tǒng)結(jié)構(gòu)圖，確定程序需要哪些模塊。當(dāng)遇到不懂的地方，借助圖書館的各種相關(guān)資料或參考網(wǎng)上資料，必要時求助老師和同學(xué)，最終解決問題。例如一種算法可以采用多種語句來實現(xiàn)，不知選擇哪種才是最優(yōu)？通過請教同學(xué)，比較每一種時間復(fù)雜性后最終選出最優(yōu)方法。通過完成“走迷宮游戲”，使我有了很多收獲，首先是拿到一個實際問題如何進(jìn)行分析，選擇哪種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn),并且學(xué)到了

85、如何從一個軟件工作者的角度來具體完成一個程序設(shè)計過程；其次，體會到了如何充分利用圖書館的資料解決存在的問題，也同時接觸到了一些課外的軟件工具，大大開拓了視野。最后，在對程序的多次調(diào)試改進(jìn)中，使我更進(jìn)一步熟悉了c++的運(yùn)行環(huán)境，也極大的提高了自身對程序的調(diào)試能力，能在編譯錯誤提示下，準(zhǔn)確找出錯誤并改正過來，使程序正常運(yùn)行。</p><p>　　總之，在本次課程設(shè)計中，使我對《數(shù)據(jù)結(jié)構(gòu)》這門課有了更進(jìn)一步的理解，理解

86、了其在程序開發(fā)中的地位及作用，課本上扎實的理論知識可謂編程的根基，在此基礎(chǔ)上通過親自動手實踐解決現(xiàn)實中具體問題。這次極大鍛煉了我的各方面能力，學(xué)到了許多課本上不曾接觸到的知識，提高了動手實踐能力，實現(xiàn)了從課本理論知識到實際編程設(shè)計的緊密連接，對一個具體的軟件開發(fā)過程有了大致了解，同時也明確了自身存在問題和發(fā)展方向，實為受益匪淺。</p><p><b>　　6參考書目：</b></p&

87、gt;<p>　　[1]譚浩強(qiáng)，《C++程序設(shè)計》，北京，清華大學(xué)出版社，2006年.</p><p>　　[2]數(shù)據(jù)結(jié)構(gòu)與算法，科學(xué)出版社，2005.08；趙文靜 祁飛等編著</p><p>　　[3]數(shù)據(jù)結(jié)構(gòu)-C++語言描述，西安交通大學(xué)出版社，1999.01，趙文靜編著</p><p>　　[4]數(shù)據(jù)結(jié)構(gòu) c語言版 人民郵電出版社 2011年 嚴(yán)