數據結構迷宮求解課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：19 大小：658.50KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩18頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計報告　　課程名稱：數據結構 　　報告題目：迷宮求解 　　學生姓名： XX

2、　　所在學院：信息科學與工程 　　專業(yè)班級：軟件工程 　　學生學號：XXXXXXXXXXX 　　指導教師： XXX

3、　　2017 年 12 月 29 日　　課程設計任務書　　摘要　　本程序主要是求迷宮中從人口到出口的所有路徑是一個經典的程序設計問題。計算機解迷宮時，通常用的是“窮舉求解”的方法，即從入口出發(fā)

4、，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路返回，換一個方向在繼續(xù)探索，直至所有可能的通路都探索完為止。　　當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索，即切換為“下一位置”為“當前位置”，如此重復直至到達出口；若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，若該通道塊的四周4個方塊均“不可通”則應從當前路徑刪除該通道塊。所謂“下一位置”指的是“當前

5、位置”四周4個方向（東、南、西、北）上相鄰的方塊。以棧S來記錄“當前路徑”，則棧頂中存放的是“當前路徑上最后一個通道塊”。所以即為“當前路徑入?！保弧皬漠斍奥窂缴蟿h除前一通道塊”為“出?！?。　　在這個過程中可以輸出迷宮所走通的路徑，在這次課程設計中迷宮是由數組預先定義好的，不能由用戶定義生成，可以加入隨機函數，自動生成二維數組，還可以用戶自己輸入迷宮。

6、　關鍵詞：棧；存儲結構；數組　　目錄　　一、課題分析1　　二、需求分析1　　1. 主模塊功能描述1　　2.

7、子程序模塊設計1　　三、設計方案1　　1.類設計1　　2.程序模塊設計2　　設計方案與實施與總體設計思想2　　3. 主模塊

8、3　　3.1 子模塊4　　3.1 主菜單5　　3.2 功能A模塊5　　3.3 功能B模塊5　　3.4 功能C模塊6</

9、p>　　四、詳細設計7　　1.用結構體構建棧7　　2.構建類7　　3.用數組構建一個迷宮8　　4.游戲移動控制指令9

10、　　5.游戲移動控制指令四個方向的實現10　　6.游戲移動過程中若是未找到通路，需要返回的指令11　　7.游戲的主循環(huán)11　　8.游戲的開始于結束12　　9.迷宮地圖的查看與通關后的路徑查詢13　　五、

11、設計總結13　　結論與心得13　　五、參考文獻15　　一、課題分析　　（1）該題目為迷宮求解。<p&g

12、t;　　（2）此課題是對迷宮問題的求解。包括用數組生成迷宮，顯示輸出路徑因此，本程序設計共需設計一個主程序以及若干個子程序。　　（3）在本課程設計程序里，主程序主要是以一個m×n的長方形表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對設定的迷宮，求出一條從入口到出口的通路，子程序實現迷宮地圖的查看和通過迷宮后的路徑查詢。<b&

13、gt;　　二、需求分析　　1. 主模塊功能描述 　　顯示提示語句提示用用戶選擇輸入執(zhí)行的功能。　?。?）開始迷宮求解游戲 　　（2）查詢迷宮地圖　?。?）查詢通過迷宮后的

14、路徑 　　2. 子程序模塊設計　?。?）迷宮求解游戲　　輸入1開始游戲　?。?）查詢迷宮地圖　　在菜單中輸入2查看迷

15、宮求解的地圖　　（3）查詢通過迷宮后的路徑　　輸入2查詢通關路徑　　三、設計方案　　1.類設計　　構建一個Hiddi

16、ng類，并有私有成員：x坐標，y坐標，位置標志，初始方向；共有成員：PrintMap打印地圖，GameFunction游戲主循環(huán)，Move_up向上移動，Move_down向下移動，Move_left向左移動，Move_right向右移動，IsGameOver判斷游戲是否結束，Move_Keys接收移動的指令，InDirection相反方向輸出，dir_flage方向標志，Hidding::Start()開始游戲等等類，在通過類的實現來

17、執(zhí)行相應的功能，具體代碼如下：　　class Hidding　　{　　private:　　int point_x; //控制運動的點的x坐標

18、　int point_y; //控制運動的點的y坐標　　int flage; //判斷標志　　int direction; //初始方向　　public:　　Hidding();

19、　　int PrintMap(int map[H][H]); //打印地圖　　int GameFunction(int map[H][H], SqStack &S);//游戲主循環(huán)　　int Move_up(int map[H][H],SqStack &S); //向上移動<

20、;p>　　int Move_down(int map[H][H], SqStack &S); //向下移動　　int Move_left(int map[H][H], SqStack &S); //向左移動　　int Move_right(int map[H][H], SqStack &S); //向右移動<

21、/p>　　bool IsGameOver(int map[H][H]); //判斷游戲是否結束　　int Move_Keys(int key, int map[H][H], SqStack &S); //接收移動的指令　　int InDirection(int key);

22、 //相反方向輸出　　int dir_flage; //方向標志　　int Out(int map[H][H]);//顯示通關路徑　　int Outa(int map[H][H]);　　int Hidding::menu();//菜單&l

23、t;p>　　int Hidding::Start();//開始游戲　　};　　2.程序模塊設計　　設計方案與實施與總體設計思想　　迷宮形狀由0表示可通過，用1表示障礙。為方便用0,1輸入，2

24、表示起點，3表示終點。并把迷宮圖形保存在二維數組Map中，而打印出的圖形中“□”表示能通過，“■”表示障礙。對探索過的位置加以標記“☆”，起點和終點分別由“⊙”，“◎”表示，“★”表示為當前目標位置。　　根據二位字符數組和加標記的位置坐標，輸出迷宮的圖形。　　該程序在獲取迷宮圖形結構后，目標點從起點開始搜索可通過的路徑，目標點通過判斷身邊上下左右四個位置

25、是否有障礙而選擇前進路徑，如果判斷之后遇到沒有可以通過的方向，將會退回之前的位置，另行判斷。直至目標點找到出口后，輸出通過的路徑，程序結束。　　1.2程序設計流程圖　　入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路返回，換一個方向在繼續(xù)探索，直至所有可能的通路都探索完為止。

26、3. 主模塊　　若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索，即切換為“下一位置”為“當前位置”，如此重復直至到達出口；若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周4個方塊均“不可通”則應從當前路徑刪除該通道塊。所謂“下一位置”指的是“當前位置”四周4個方向（東、南、西、北）上

27、相鄰的方塊。以棧S來記錄“當前路徑”，則棧頂中存放的是“當前路徑上最后一個通道塊”。所以即為“當前路徑入?！?；“從當前路徑上刪除前一通道塊”為“出?！?。　　3.1 子模塊　　3.程序調試結果及分析　　3.1 主菜單

28、　　這是主界面，提示A、B、C各自代表的功能，輸入1或2或3會跳轉到相應的功能模塊，輸入1開始游戲，輸入2可查看需要通關的游戲地圖，輸入3返回。　　3.2 功能A模塊　　當從鍵盤輸入1進入A功能模塊，此圖是尋找迷宮路徑，游戲會由電腦自動完成，入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則

29、沿原路返回，換一個方向在繼續(xù)探索，直至所有可能的通路都探索完為止，若是成功找到路徑，則輸出恭喜過關，并且提示是否查看通關路徑。　　3.3 功能B模塊　　從鍵盤輸入2查詢迷宮地圖，可顯示游戲需要通關的迷宮地圖，繼續(xù)輸入1可以開始游戲。　　3.4 功能C模塊&l

30、t;/b>　　游戲的主循環(huán)的類的實現表示游戲的開始，判斷當前位置標記是否為3，如果為3，則表示該位置為終點，游戲結束，輸出恭喜過關，提示是否查看通關路徑,從鍵盤輸入2查詢通關路徑 　　四、詳細設計　　1.用結構體構建棧</p

31、>　　通過構建的棧實現迷宮求解時尋找路徑的數據的存放于取出，其關鍵代碼如下：　　typedef struct　　{　　SElemType *top; //頂部指針　　SElemType *bas

32、e; //底部指針　　int stacksize; //當前棧的大小　　}SqStack;　　2.構建類　　構建一個Hidding類，并有私有成員：x坐標，y坐標，位置標志，初

33、始方向；共有成員：PrintMap打印地圖，GameFunction游戲主循環(huán)，Move_up向上移動，Move_down向下移動，Move_left向左移動，Move_right向右移動，IsGameOver判斷游戲是否結束，Move_Keys接收移動的指令，InDirection相反方向輸出，dir_flage方向標志，Hidding::Start()開始游戲等等類，在通過類的實現來執(zhí)行相應的功能，具體代碼如下：

34、　　class Hidding　　{　　private:　　int point_x; //控制運動的點的x坐標　　int point_y; //控制運

35、動的點的y坐標　　int flage; //判斷標志　　int direction; //初始方向　　public:　　Hidding();　　int PrintMap

36、(int map[H][H]); //打印地圖　　int GameFunction(int map[H][H], SqStack &S);//游戲主循環(huán)　　int Move_up(int map[H][H],SqStack &S); //向上移動　　int Move_down(int

37、 map[H][H], SqStack &S); //向下移動　　int Move_left(int map[H][H], SqStack &S); //向左移動　　int Move_right(int map[H][H], SqStack &S); //向右移動　　bool I

38、sGameOver(int map[H][H]); //判斷游戲是否結束　　int Move_Keys(int key, int map[H][H], SqStack &S); //接收移動的指令　　int InDirection(int key); //相反方向輸出

39、　　int dir_flage; //方向標志　　int Out(int map[H][H]);//顯示通關路徑　　int Outa(int map[H][H]);　　int Hidding::menu();//菜單　　int Hidding::Sta

40、rt();//開始游戲　　};　　3.用數組構建一個迷宮　　1.迷宮形狀由0表示可通過，用1表示障礙。為方便用0,1輸入，2表示起點，3表示終點。并把迷宮圖形保存在二維數組Map中，而打印出的圖形中“□”表示能通過，“■”表示障礙。對探索過的位置加以標記“☆”，起點和終點分別

41、由“⊙”，“◎”表示，“★”表示為當前目標位置，其關鍵代碼如下：　　int map[H][H] =　　{　　1,1,1,1,1,1,1,1,1,1, //(9,0) (9,9)　　1,0,0,0,0,0,1,0,0,1,<

42、/p>　　1,0,1,1,0,0,1,0,0,1,　　1,0,0,1,1,0,1,0,1,1,　　1,1,0,0,1,0,0,0,1,1,　　1,1,0,1,1,1,1,0,0,1,　　1,1,0,1,1,1,1,1,0,1,

43、;　　1,0,0,1,1,1,1,1,0,1,　　1,2,1,1,1,1,1,1,3,1,　　1,1,1,1,1,1,1,1,1,1 //(0,0) (0,9)　　};　　2.打印出的圖形中“□”表示能通

44、過，“■”表示障礙。對探索過的位置加以標記“☆”，起點和終點分別由“⊙”，“◎”表示，“★”表示為當前目標位置，其關鍵代碼如下：　　int Hidding::PrintMap(int map[H][H])　　{　　for (int i = 0; i < H; i++)&

45、lt;/p>　　{　　for (int j = 0; j < H; j++)　　{　　switch (map[i][j])　　{</b&g

46、t;　　case 0:　　cout << "□";　　break;　　case 1: //墻

47、　cout << "■";　　break;　　case 2: //起點　　cout << "⊙";　　break;</

48、b>　　case 3: //終點　　cout << "◎";　　break;　　case 7: //走過的路徑<

49、p>　　cout << "☆";　　break;　　case 9:　　cout << "★"; 　　brea

50、k;　　default:　　break;　　}　　}　　c

51、out << endl;　　}　　return 0;　　}//PrintMap　　4.游戲移動控制指令　　構建一個棧，用Key控制移動，上移指

52、令Key=8，下移指令Key=5，左移指令Key=4，右移指令Key=6，其關鍵代碼如下： 　　int Hidding::Move_Keys(int key,int map[H][H], SqStack &S)　　{　　switch (key)

53、;　　{　　case 8:　　Move_up(map,S);　　break;　　case 4:&l

54、t;/p>　　Move_left(map,S);　　break;　　case 6:　　Move_right(map,S);　　break;</b

55、>　　case 5:　　Move_down(map,S);　　break;　　default:

56、;　　break;　　}　　return 0;　　}//Move_Keys　　5.游戲移動控制指令四個方向的實現　　以向上移動指令的實

57、現為例，判斷是否是走過的路徑，若是則x-1當前位置標記為0；判斷前方是否可行，若是x-1，當前位置標記為7，（7為走過的路徑），并且入棧執(zhí)行一次；若前方數組值為1，表示不能通過，繼續(xù)判斷其他方向是否可以通過，如map[point_x][point_y - 1] == 0則表示左側可以通過，direction=4，移動方向為左，入棧一次，其他方向的移動指令大致相同，都是先判斷，在通過入棧實現移動游戲移動過程中若是未找到通路，需要返回，則執(zhí)

58、行InDirection反方向移動指令。　　其關鍵代碼如下：　　int Hidding::Move_up(int map[H][H],SqStack &S)　　{　　if (map[poi

59、nt_x - 1][point_y] == 7)　　{　　map[point_x][point_y] = 0;　　point_x -= 1;　　}　　el

60、se if ((map[point_x - 1][point_y] == 0 && direction != 5) || map[point_x - 1][point_y] == 3) //如果前方可行　　{　　map[point_x][point_y] = 7;&

61、lt;p>　　point_x -= 1;　　Push(S, direction);　　}　　if (map[point_x - 1][point_y] == 1)　　{

62、　　if (map[point_x][point_y - 1] == 0)　　{　　direction = 4;　　Push(S, direction);　　}</p&g

63、t;　　else if (map[point_x][point_y + 1] == 0)　　{　　direction = 6;　　Push(S, direction);　　}

64、　　else　　{　　dir_flage = Pop(S);　　InDirection(dir_flage);　　map[point_x][point_y

65、] = 0;　　}　　}　　return 0;　　}//Move_up　　6.游戲移動過程中若是未找到通路，需要返回

66、的指令　　判斷上一步執(zhí)行的指令Key，在執(zhí)行放方向移動的指令,具體代碼如下：　　int Hidding::InDirection(int key)　　{　　switch (key)<b&

67、gt;　　{　　case 8:　　direction = 5;　　break;　　case 4:

68、;　　direction = 6;　　break;　　case 5:　　direction = 8;　　break; <

69、p>　　case 6: 　　direction = 4;　　break; 　　default:　　break;

70、　　}　　return 0;　　}//InDirection　　7.游戲的主循環(huán)　　用一個sleep函數控制游戲的速

71、度，具體代碼如下：　　int Hidding::GameFunction(int map[H][H], SqStack &S)　　{　　Sleep(100);　　PrintMap(map);<p

72、>　　system("cls");　　while (!IsGameOver(map))　　{　　map[point_x][point_y] = 9;　　PrintMap(map);&l

73、t;p>　　Move_Keys(direction, map,S);　　cout<<"方向：";　　switch(direction)　　{　　case 8:

74、　　cout << "上" << endl;　　break;　　case 5:　　cout<<"下";

75、;　　break;　　case 6:　　cout<<"右";　　break;　　cas

76、e 4:　　cout<<"左";　　break;　　}　　cout << direction << endl;</

77、p>　　system("cls");　　Sleep(100);　　}　　return 0;　　}//GameFunction

78、　　8.游戲的開始于結束　　游戲的主循環(huán)的類的實現表示游戲的開始，判斷當前位置標記是否為3，如果為3，則表示該位置為終點，游戲結束，輸出恭喜過關，提示是否查看通關路徑，具體代碼如下：　　int Hidding::Start()　　{

79、　　hid.GameFunction(map,S1);　　if (hid.IsGameOver(map)　　cout << "恭喜過關！" << endl;　　cout<<"輸入2顯示通關路徑。"<<end

80、l;　　}　　bool Hidding::IsGameOver(int map[H][H])　　{　　if (map[point_x][point_y] == 3) //3表示終點

81、　　return true;　　else　　return false;　　}//IsGameOver　　9.迷宮地圖的查看與通關后的路徑查詢　　開始游

82、戲前可以查看迷宮的地圖，在開始游戲尋找到通關路徑后可以查看對應的路徑，用for循環(huán)實現二維數組的讀出，相應的通關路徑會以☆符合標記出來，具體代碼如下：　　for(int i=1;i<=H;i++)　　for(int j=1;j<=H;j++)　　if(map[i][j]=0)&

83、lt;p>　　cout<<map[i][j];　　五、設計總結 　　結論與心得　　本次課程設計題目為迷宮求解，通過該題目的設計過程,我們小組加深了對棧的邏輯結構,存儲結構及入棧出棧過程的理解,對棧的基本運算的實現有所掌握

84、,對課本中所學的各種數據結構進一步理解和掌握,學會了如何把學到的知識用于解決實際問題,鍛煉了自己動手的能力。　　本次課程設計，使我們對數據結構設計方法、步驟、思路，有一定的了解和認識，它相當于實際設計工作的模擬。在課程設計過程中，基本能按照規(guī)定的程序進行，先針對表達式算法為背景，建立系統模型：收集、調查有關資料，共同與老師和同學進行討論、修改、再討論、再修改，最后確定方案。 </

85、p>　　一個人要完成所有的工作是非常困難和耗時的，我們小組都是分工合作，這樣既鍛煉了每個人，又學到了很多的知識。在以后的學習中我會更加注意各個方面的能力的協調發(fā)展。在課程設計時遇到了很多的問題，在老師的幫助，和對各種資料的查閱中，將問題解決，培養(yǎng)了自主動手，獨立研究的能力，為今后在學習工作中能更好的發(fā)展打下了堅實的基礎。兩周的課程設計很短暫，但其間的內容是很充實的，在其中我學習到了很多平時書本中無

86、法學到的東西，積累了經驗，鍛煉了自己分析問題，解決問題的能力，并學會了如何將所學的各課知識融會，組織，來配合學習，兩周中我們小組收益很大，學到很多。　　心得體會：　　通過此次課程設計，使我更加了解了數據結構著方面的知識，在設計的過程中遇到了一些很難的問題，經過一遍一遍地思考，與同學和老師的交流中找到了問題原因的所在，

87、也知道了自己在這方面的知識欠缺和經驗不足。通過這次的課程設計，獲得了很多寶貴的經驗，特別是怎么樣通過理論與實踐相結合，把書本上的內容應用到我們做的程序上去。學會了調試程序的一般方法，知道了如何在困難重重中一步一步發(fā)現問題，解決問題。 　　五、參考文獻　　[1] 鄭莉,董淵,何江舟.

88、C++語言程序設計(第4版)[M].北京:清華大學出版社,2010:123—145　　[2] 蔚敏，吳偉民.數據結構（C語言版）[M].北京:清華大學出版社（范素珍白立軍），2007：142—160　　[3] 呂鳳翥.C++語言程序設計(第3版)[M].北京:電子工業(yè)出版社,2009:151—175　　[4]

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數據結構迷宮求解課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

數據結構迷宮求解課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載