1、長 春 大 學課 程 設 計 任 務 書題目名稱 走迷宮游戲 院 （系） 計算機科學技術學院 課程名稱 數據結構課程設計 班 級 網絡10406 學生姓名 指導教師 起止日期 2012.7.162012.7.20 課程設計任務書技術參數）及要求題目名稱（包括主要題目名稱：走迷宮游戲設計目的1了解并掌握數據結構與算法的設計方法，具備初步的獨立分析和設計能力；2.初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能；3.提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；4.訓練用系統的觀點和軟件開發一般規范進行軟件開發，培養軟件工作者所應具備的科學的工作方法和作風。設計

2、要求1.問題分析和任務定義：根據設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 2.邏輯設計：對問題描述中涉及的操作對象定義相應的數據類型，并按照以數據結構為中心的原則劃分模塊，定義主程序模塊和各抽象數據類型。邏輯設計的結果應寫出每個抽象數據類型的定義(包括數據結構的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調用關系圖。3.詳細設計：定義相應的存儲結構并寫出各函數的偽碼算法。在這個過程中，要綜合考慮系統功能，使得系統結構清晰、合理、簡單和易于調試，抽象數據類型的實現盡可能做到數據封裝，基本操作的規格說明盡可能明確具體。詳細

3、設計的結果是對數據結構和基本操作作出進一步的求精，寫出數據存儲結構的類型定義，寫出函數形式的算法框架。4.程序編碼：把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。5.程序調試：采用自底向上，分模塊進行，即先調試低層函數。能夠熟練掌握調試工具的各種功能，設計測試數據確定疑點，通過修改程序來證實它或繞過它。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果。6.結果分析：程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法的時間、空間復雜性分析。7.編寫課程設計說明書，封面和說明書紙到教務處網站下載，裝訂格式如

4、下：一、封面；二、目錄；三、說明書正文，主要內容包括：1設計題目；2設計目的；3算法思想分析；4算法描述與實現；5結論設計內容及工作量【問題描述】以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。【基本要求】1首先用二維數組存儲迷宮數據，迷宮數據由用戶輸入。2一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個坐標，d表示走到下一坐標的方向（東、南、西、北四個方向所用代表數字，自行定義）。3可以用多

5、種方法實現，但至少用兩種方法，用三種以上可加分。【實現提示】1計算機解迷宮問題通常用的是“窮舉求解”方法，即從入口出發，順著某一個方向進行探索，若能走通，則繼續往前進；否則沿著原路退回，換一個方向繼續探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。迷宮的入口點的下標為（1，1），出口點的下標為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮的任一位置，均可約定有東、南、西、北四個方向可通。2有一種簡單走出迷宮的方法，把手放在右邊的墻上開始前進，始終不要把手從墻上移開。如果迷宮向右拐，你也順著墻向右拐。只要不把手從墻上移開，最終就

6、會到達迷宮的出口。當然這樣得到的路徑可能不是一個最短的路徑，但它可以最終得到結果，換句話說，這種方法走不出迷宮的風險是最小的。主要參考資料數據結構程序設計題典李春葆等編 清華大學出版社數據結構(C語言版) 黃國瑜 葉乃菁編 清華大學出版社數據結構課程設計蘇仕華 等編 機械工業出版社進 度 計 劃 表階段日期計劃完成工作量指導教師檢查意見備注7.16分析題目，查閱資料；7.177.18算法設計，編碼，調試；7.19編碼、調試運行；撰寫設計說明書；7.20答辯設計總結：考核成績及評語 指導教師簽字 年 月 日教研室意見教研室主任簽字 年 月 日長 春 大 學課 程 設 計 說 明 書題目名稱 走迷

7、宮游戲 院（系）計算機科學技術學院 專業（班級） 網絡10406 學生姓名 指導教師 起止日期2012.7.20 目錄一、設計題目2二、設計目的2三、算法思想析3 1、類的分析與計3 2、程序設計流圖3四、算法描述與現 51、概要計52、調試析53、測試果7五、總結與會10六、程序碼11七、參考獻16一、設計題目1、題目：走迷宮游戲2、問題描述以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。3、基本要求（1）、首先用二維數組存儲迷宮數據，迷宮數據由用戶輸入。（2）、一個以鏈表作存儲結構的

8、棧類型，然后編寫一個求解迷宮的遞歸或非遞歸程序。求得的通路以三元組（i，j，d）形式輸出，其中：（i，j）指示迷宮中的一個坐標，d表示走到下一坐標的方向（東、南、西、北四個方向所用代表數字，自行定義）。（3）、可以用多種方法實現，但至少用兩種方法，用三種以上可加分。二、設計目的1、需求分析與設計要求隨著社會經濟和人們物質生活的不斷提高，人們對精神生活的需求也越來越高，在現今社會里，人們對諸如智商、情商等的重視無疑反映了對精神生活的態度。當然具體到我們每個人來說，想必大多數人小時候都曾玩過魔方、迷宮吧。作為這種智力游戲，人們是百玩不厭的。正是鑒于這種需求，本設計應用計算機語言及其算法，將人的意志

9、賦予機器實現，使人們不必再陷于枯燥的重復勞動，從而將更多的精力投入到對未知領域的探索上。這次課程設計要求我們在了解并掌握數據結構與算法的設計方法的基礎上，具備初步的獨立分析和設計能力；初步掌握軟件開發過程的問題分析、系統設計、程序編碼、測試等基本方法和技能。同時要求在提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力的同時，訓練用系統的觀點和軟件開發一般規范進行軟件開發的方法，培養一個軟件工作者所應具備的科學的工作方法和作風。三、算法思想分析1、類的分析與設計由于計算機解謎宮時，通常用的是“窮舉求解”的方法，即從入口出發，順某一方向向前探索，若能走通，則繼續往前走；否則沿原路退回，換一個

10、方向再繼續探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。為了保證在任何位置上都能沿原路退回，顯然需要用一個后進先出的結構來保存從入口到當前位置的路徑。因此，在求迷宮通路的算法中應用“棧”也就是自然而然的事了。首先，迷宮圖用方塊表示，每個方塊或為通道，或為墻。迷宮的入口點的下標為（1，1），出口點的下標為（m，n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮的任一位置，均可約定有東、南、西、北四個方向可通。有一種簡單走出迷宮的方法，把手放在右邊的墻上開始前進，始終不要把手從墻上移開。如果迷宮向右拐，你也順著墻向右拐。只要不把手從墻上移

11、開，最終就會到達迷宮的出口。當然這樣得到的路徑可能不是一個最短的路徑，但它可以最終得到結果，換句話說，這種方法走不出迷宮的風險是最小的。假設“當前位置”指的是“在搜索過程中某一時刻所在圖中某個方塊位置”，則求迷宮中一條路徑的算法的基本思想是：若當前位置“可通”，則納入“當前路徑”，并繼續朝“下一位置”探索，即切換“下一位置”為“當前位置”，如此重復直至到達出口；若當前位置“不可通”，則應順著“來向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續探索；若該通道塊的四周4個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。所謂“下一位置”指的是“當前位置”四周4個方向（東、南、西、北

12、）上相鄰的方塊。假設以棧S記錄“當前路徑”，則棧頂中存放的是“當前路徑”上最后一個通道塊。由此，“納入路徑”的操作即為“當前位置入棧”；“從當前路徑上刪除前一通道塊”的操作即為“出棧”。2、程序設計流程圖（1）程序主要項目主函數數據存儲棧的初始化及入棧出棧函數走過通道留下的痕跡探索從出口到入口的路徑切換當前探索位置輸出迷宮信息（2）程序運行主流程開始建立迷宮并確定當前位置當前位置是否可通NY朝默認方向繼續探索換下一個方向探索結束 四、算法描述與實現1、概要設計以二維數組mazemapMN表示迷宮，數組中0表示通路，1表示障礙，3表示求解之后的迷宮路徑。M為迷宮的寬，N為迷宮的長。 程序設置一個

13、演示迷宮，另外可由用戶自己輸入迷宮數據建立迷宮。用戶根據提示輸入迷宮的長和寬，入口和出口，以及迷宮每一行的數據，同樣用1表示障礙，0表示通路，迷宮周邊用1表示。以圖形顯示出迷宮，用“墻”表示障礙，“口”表示路徑。若存在路徑，則顯示出路徑，否則提示沒有路徑。2、調試分析（1）設定棧的抽象數據類型定義ADT Stack 數據對象：D=ai|ai屬于ElemSet,i=1,2,3,4,n,n>=0 數據關系：R1=<ai-1,ai>|ai-1,ai屬于D,i=1,2,3.n基本操作： InitStack(&s) 操作結果：構造一個空棧s DestroyStack(&

14、s) 初始條件：棧s已存在 操作結果：張s被撤銷ClearStack(&s) 初始條件：棧s已存在 操作結果：將s清為空棧StackEmpty(s) 初始條件：棧s已存在 操作結果：若s為空棧，則返回true，否則返回falseGetTop(s,&e) 初始條件：棧s存在且非空 操作結果：用e返回s的棧頂元素Push(&s,e) 初始條件：棧s已存在 操作結果：插入s的棧頂元素為ePop(&s,&e) 初始條件：棧s存在且非空 操作結果：刪除s的棧頂元素，并用e返回值ADT Stack（2）設定迷宮的數據類型ADT maze數據對象：D=aij|aij屬

15、于“墻”，“口”，“ ”，i<m,j<n,m,n<100數據關系：R=ROW，COLROW=<ai-1 j,aij>|ai-1 j,aij屬于D COL=<aij,ai j-1>|ai-1 j,aij屬于D基本操作：Initmaze(&maze,row,col) 初始條件：二維數組mazerowcol已存在。 基本操作：用1表示障礙，0表示通路，由用戶輸入。 Mazepath(&maze,start,end) 初始條件：迷宮maze以被賦值。 操作結果：找出一條迷宮路徑。若沒有路徑，則提示沒有。Printmaze(maze)初始條件：迷

16、宮maze已存在 操作結果：以字符形式顯示出迷宮ADT maze（3）程序三個模塊設計 主程序模塊 void main() 初始化； Dowhile(命令!=退出)棧模塊-實現棧的抽象數據類型迷宮模塊-實現迷宮的抽象數據類型各模塊的調用關系如下： 主程序模塊à迷宮模塊à棧模塊球迷宮一條從入口到出口的路徑算法可描述如下：do若當前位置可通，則將當前位置插入棧頂； 若該位置是出口位置，則結束； 否則切換當前位置的東鄰塊為當前位置； 否則， 若棧不空且棧頂位置尚有其他方向未經探索， 則設定新的當前位置為沿順時針方向旋轉到棧頂位置的下一相鄰塊 若棧不空但棧頂位置的四周均不通 則刪除

17、棧頂位置；若棧不空，則重新測試新的棧頂位置，知道找到下一個可通的相鄰塊或出棧至棧空；while(棧不空)；迷宮建立模塊：此模塊的調試主要在于能否成功將迷宮用二維數組矩陣儲存，能否成功調用File_Save(int maze50,int x,int y)函數，保存文件文件的調取模塊：此模塊的調試主要在于對文件打開不成功時的應對。3、測試結果（1）進入程序后顯示主頁面圖1主頁面（2）按任意鍵繼續下一步圖2 迷宮路徑（3）按任意鍵后自己構建迷宮圖3構建迷宮例：迷宮過后，會提示用戶輸入迷宮。選測試迷宮數據如下Maze66= 1，1，1，1，1，1， 1，0，1，0，0，1， 1，0，1，0，1，1，

18、1，0，0，0，1，1， 1，0，1，0，0，1， 1，1，1，1，1，1；迷宮入口坐標(1,1)，出口(1,4)，如圖所示圖4構建迷宮（4）按回車鍵可得到自己構建的迷宮地圖，如圖所示圖5迷宮地圖（5）按Q鍵即退出程序圖6退出程序五、總結和體會通過迷宮求解的編程練習思考數據結構的使用，比如對棧、指針、鏈表等的深入了解，讓我們感受到了數據結構及其算法的重要。此外還熟悉了各種函數的應用。通過編程我知道了想要寫出好的程序，需要有扎實的基礎，這樣才會遇到一些基本算法時做的游刃有余。在編程時，我們要有豐富的想象力，不拘泥于固定的思維方式，試試別人從沒想過的方法。豐富的想象力是建立在豐富的知識的基礎上，所

19、以我們要通過多個途徑來幫助自己建立較豐富的知識結構。在編程時，遇到了很多的困難，需要我們多與別人交流。在編程時我們也看到了有良好的編程風格是十分重要的，至少在時間效率上就體現了這一點。六、程序源碼#include<iostream>#include<windows.h>#include<conio.h>#define MAXSIZE 100using namespace std;int signMAXSIZEMAXSIZE;/標記矩陣，當相應塊走過后，值變為1typedef structint x;int y;PosType;typedef structin

20、t ord; PosType seat;int di;SElemType;typedef structint m;int n;int mapMAXSIZEMAXSIZE;MazeType;class Stackpublic:SElemType dataMAXSIZE;int top;Stack(void)top=-1;void push(SElemType e)top+;datatop.ord=e.ord;datatop.di=e.di;datatop.seat=e.seat;void pop(SElemType &e)e.di=datatop.di;e.ord=datatop.ord

21、;e.seat=datatop.seat;top-;int empty()if(top=-1)return 1;elsereturn 0;void FootPrint(PosType ps)signps.xps.y=1;int Pass(MazeType mazemap,PosType ps)if(mazemap.mapps.xps.y=0&&signps.xps.y=0)return 1;else return 0;PosType NextPos(PosType ps,int di)PosType temp;switch(di)case 1:temp.x=ps.x+1;tem

22、p.y=ps.y;break;case 2:temp.x=ps.x;temp.y=ps.y-1;break;case 3:temp.x=ps.x-1;temp.y=ps.y;break;case 4:temp.x=ps.x;temp.y=ps.y+1;break;return temp;int MazePath(MazeType &mazemap,PosType start,PosType end)Stack st;SElemType e;PosType curpos=start;int curstep=1;for(int i=0;i<mazemap.m;i+)for(int j

23、=0;j<mazemap.n;j+)signij=0;doif(Pass(mazemap,curpos)FootPrint(curpos);e.ord=curstep;e.seat=curpos;e.di=1;st.push(e);if(curpos.x=end.x&&curpos.y=end.y)for(int i=0;i<=st.top;i+)mazemap.mapst.datai.seat.xst.datai.seat.y=3;/cout<<"("<<st.datai.seat.x<<",&qu

24、ot;<<st.datai.seat.y<<")"<<"t"return 1;curpos=NextPos(curpos,1);curstep+;elseif(!st.empty()st.pop(e);while(e.di=4&&!st.empty()FootPrint(e.seat);st.pop(e);if(e.di<4)e.di+;st.push(e);/cout<<"("<<(e.seat).x<<","<&

25、lt;(e.seat).y<<")"<<endl;curpos=NextPos(e.seat,e.di);while(!st.empty();return 0;void printmaze(MazeType mazemap,PosType start,PosType end)for(int i=0;i<mazemap.m;i+)cout<<"tt"for(int j=0;j<mazemap.n;j+)if(1=mazemap.mapij)cout<<"墻"else if(i=

26、start.x&&j=start.y)cout<<"口"else if(i=end.x&&j=end.y)cout<<"口"else if(3=mazemap.mapij)cout<<"口"else cout<<" "cout<<endl;void usermaze()MazeType usermap;PosType m_start,m_end;cout<<"輸入迷宮寬度:"<<e

27、ndl;cin>>usermap.n;cout<<"輸入迷宮高度:"<<endl;cin>>usermap.m;for(int i=0;i<usermap.m;i+)cout<<"輸入第"<<i+1<<"行迷宮圖"<<endl;for(int j=0;j<usermap.n;j+)cin>>usermap.mapij;cout<<"輸入迷宮入口橫坐標:"<<endl;cin

28、>>m_start.x;cout<<"輸入迷宮入口縱坐標:"<<endl;cin>>m_start.y;cout<<"輸入迷宮出口橫坐標:"<<endl;cin>>m_end.x;cout<<"輸入迷宮出口縱坐標:"<<endl;cin>>m_end.y;cout<<"下面是您輸入的迷宮地圖:"<<endl<<endl;printmaze(usermap,m_s

29、tart,m_end);if(MazePath(usermap,m_start,m_end)cout<<"按任意鍵顯示路徑··· ···"<<endl;getch();printmaze(usermap,m_start,m_end);cout<<endl<<endl;cout<<"tt"<<"迷宮路徑如上"<<endl<<endl;elsecout<<"沒有路

30、徑!"<<endl;void demomaze()MazeType mazemap;PosType start,end;start.x=1,start.y=1;end.x=8,end.y=8;mazemap.m=10,mazemap.n=10;for(int i=0;i<10;i+)for(int j=0;j<10;j+)mazemap.mapij=1;mazemap.map11=mazemap.map12=mazemap.map14=mazemap.map15=mazemap.map16=mazemap.map18=0;mazemap.map21=mazem

31、ap.map22=mazemap.map24=mazemap.map25=mazemap.map26=mazemap.map28=0;mazemap.map31=mazemap.map32=mazemap.map33=mazemap.map34=mazemap.map37=mazemap.map38=0;mazemap.map41=mazemap.map45=mazemap.map46=mazemap.map47=mazemap.map58=0;mazemap.map51=mazemap.map52=mazemap.map53=mazemap.map55=mazemap.map56=mazem

32、ap.map57=mazemap.map58=0;mazemap.map61=mazemap.map63=mazemap.map64=mazemap.map65=mazemap.map67=mazemap.map68=0;mazemap.map71=mazemap.map75=mazemap.map78=0;mazemap.map82=mazemap.map83=mazemap.map84=mazemap.map85=mazemap.map86=mazemap.map87=mazemap.map88=0;/*1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,*/printmaze(mazemap,start,en