迷宮問題課程設計報告

1、南華大學計算機科學與技術學院課 程 設 計 報 告 （ 2007 2008 學年度 第 1學期 ）課程名稱數據結構c+描述課程設計名稱迷宮問題姓名羅丹學號 20064440109專業(yè)計算機科學與技術班級計算機01班地點8209教師 劉 霞 1.實驗目的及要求1）、設計目標（問題描述）迷宮問題問題描述：迷宮實驗是取自心理學的一個古典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒中設置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗，一直到老鼠從入口到出口，而不走錯一步。老鼠經多次試驗終于得到它

2、學習走迷宮的路線。2）、功能設計要求編寫一個程序求解迷宮問題。迷宮由m行n列的二維數組設置，0表示無障礙，1表示有障礙。設入口為（1，1），出口為（m，n），每次只能從一個無障礙單元移到周圍四個方向上任一無障礙單元。編程實現對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。算法輸入：代表迷宮入口的坐標算法輸出：穿過迷宮的結果。算法要點：創(chuàng)建迷宮，試探法查找路徑，輸出解3）、實驗目的 1、加深對棧特性理解，以便在解決實際問題中靈活運用它們 2、加深對棧操作實際算法的理解 3、進一步熟悉掌握鏈表的操作； 4、掌握指針的應用 5、更進一步掌握有關類的操作4）、需求分析 1、本程序實

3、現迷宮的探索過程. 以用戶和計算機對話的方式，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令，然后程序就探索路徑并輸出路徑。 2、本演示程序中，輸入形式以“回車符”為結束標志，且允許出現重復字符。 3、利用二維指針實現迷宮位置的存儲，并用棧存貯探索路徑，每個結點含三個整形變量。輸入的形式以回車結束。 4、本程序中，用戶可以讀去文件里的迷宮，也可自己重新輸入迷宮，而且用戶可以輸入任意大小的迷宮，然后程序自動探索路徑，并輸出迷宮的路徑 5）、創(chuàng)新（見源程序附錄）6）、軟件、硬件環(huán)境 軟件環(huán)境：Microsoft Windows Xp Processional200

4、2 ServiceMicrosoft Visual C+6.0 硬件環(huán)境：cpu：AMD Athlon（tm）64x DualProcessor 3800+2.01GHz Main memory:960MB2.實驗步驟a.認真閱讀課本的相關知識章節(jié)。b.認真分析課題的需求分析和功能分析。c.根據分析的思路寫出偽代碼。d.根據偽代碼上機編寫程序，進行初步調試。e.逐步增加完善系統(tǒng)的功能，實現人工智能化。f.記錄上機運行時遇到的錯誤，進行認真分析。g.最后認真撰寫實驗報告，寫出實驗心得總結。3. 實驗內容1）、設計概述(a) 開發(fā)平臺：VC6.0(b) 參考書籍： 1.數據結構C+描述 熊岳山 陳

5、懷義 編著 國防科技大學出版社 2、數據結構與算法黃定 黃煜廉編著 廣東科技出版社 2000年1月第1版3、數據結構輔導與提高徐孝凱 編著 清華大學出版社2003年12月第1版(c) 開發(fā)周期： 10天（構思3天、雛形3天、修改2天、再修改1天、完善1天）2）、處理流程(a)畫出功能結構圖Main主函數模塊輸出路徑模塊printpath（）獲取迷宮模塊探索路徑模塊Findpath（）寫文件Writefile（）讀文件Readfile（）存儲探索路徑模塊stack類Stack類操作模塊數據模塊盤空函數isempty（）清空函數clear（）取棧頂函數getpop（）進棧與出棧函數push（）Po

6、p（）構造與析構函數stack（）stack（）結點模塊Node*top結點數據類型模塊datatype類(b)畫出主要數據結構的類圖class 類名DataType /定義描述迷宮中當前位置的類型數據成員訪問控制權限 數據類型 變量名; public:int x; /x代表當前位置的行坐標 int y; /y代表當前位置的列坐標 int pre; /pre表示移動到下一步的方向 class 類名Move /定義下一個位置的方向數據成員訪問控制權限 數據類型 變量名; public:int x; int y;class 類名Node /結點數據成員訪問控制權限 數據類型 變量名; public

7、: DataType data; Node *next;class 類名stack數據成員訪問控制權限 數據類型 變量名; private: Node *top; /指向第一個結點的棧頂指針成員函數訪問控制權限 返回值類型 函數名(參數列表) public: stack(); /構造函數，置空棧 stack(); /析構函數 void Push(DataType data);/把元素data壓入棧中 DataType Pop(); /使棧頂元素出棧 DataType GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool IsEmpty(); /判斷棧是否為空，如

8、果為空則返回1，否則返回0(c)主要函數的程序流程圖開始 1.main函數流程圖： 顯示系統(tǒng)信息選擇獲取迷宮的方式chCh= bCh=a自行輸入Writefile（）Readfile()文件讀取探索迷宮路徑是否存在輸出迷宮路徑是否繼續(xù)游戲退出開始2.探索路徑函數findpath（）Temp1.x=1Temp1.y=1入口進棧p.pushq.push是否非空temp2=q.getpop（）P q棧頂是否相等探索上下左右四個方位是否有路徑到達新位置是否到達出口最后一個元素進棧輸出路徑回復以改變的迷宮結束 開始3.自行輸入迷宮函數writefile（）輸入長寬m，n動態(tài)申請空間二位數組空間i=m是否

9、保存迷宮J=ni+ ；j+輸入迷宮輸入保存迷宮的文件名保存迷宮結束(d)寫出數據測試表（輸入數據/預期結果） 測試一：從文件中讀取迷宮： 001000100001000101000011000011100100000100001010001010011110011110001011110000000 輸出：探索路徑： （1，1，向下） （2，1，向下）（3，1，向下）（4，1，向下）（5，1，向右）（5，2，向右） （5，3，向下）（6，3，向右）（6，4，向右）（6，5，向上）（5，5，向右）（5，6，向右）（5，7，向下）（6，7，向下）（7，7，向下）（8，7，向下）（9，7，向右）（9

10、，8，向右） （9，9）測試二： 自己輸入迷宮： 001000100 輸出探索路徑： （1，1，向下）（2，1，向右）（2，2，向下）（3，2，向右）（3，3）測試三：自己輸入迷宮： 111111000 輸出探索路徑： Sorry！找不到路徑！4.實驗結果結果為以下三種情形之一：1）編譯不通過：給出編譯錯。Compiling.stack.cppSkipping. (no relevant changes detected)main.cppLinking.stack.obj : error LNK2005: public: _thiscall stack:stack(void) (?0stack

11、QAEXZ) already defined in main.objstack.obj : error LNK2005: public: _thiscall stack:stack(void) (?1stackQAEXZ) already defined in main.objstack.obj : error LNK2005: public: void _thiscall stack:Push(struct DataType) (?PushstackQAEXUDataTypeZ) already defined in main.objstack.obj : error LNK2005: pu

12、blic: struct DataType _thiscall stack:Pop(void) (?PopstackQAE?AUDataTypeXZ) already defined in main.objstack.obj : error LNK2005: public: struct DataType _thiscall stack:GetPop(void) (?GetPopstackQAE?AUDataTypeXZ) already defined in main.objstack.obj : error LNK2005: public: void _thiscall stack:Cle

13、ar(void) (?ClearstackQAEXXZ) already defined in main.objstack.obj : error LNK2005: public: bool _thiscall stack:IsEmpty(void) (?IsEmptystackQAE_NXZ) already defined in main.objDebug/迷宮問題.exe : fatal error LNK1169: one or more multiply defined symbols found執(zhí)行 link.exe 時出錯.迷宮問題.exe - 1 error(s), 0 war

14、ning(s)改正： 在main。cpp中原來包含的是stack.cpp把它改為包含stack.h即可錯誤二： 用string直接定義字符串str時，說沒有定義str 原因：#includeusing namespace std ;沒有用標準空間錯誤三： 拼寫錯誤正確結果輸出：接上面：接上面：5. 實驗總結分析1)、時間和空間分析該算法的運行時間和使用系統(tǒng)棧所占有的存儲空間與迷宮的大小成正比，迷宮長為m，寬為n，在最好情況下的時間和空間復雜度均為O（m+n），在最差情況下均為O（m*n），平均情況在它們之間2)、程序的優(yōu)點a. 進入演示程序后即顯示文本方式的用戶界面b. 本程序模塊劃分比較合理

15、，且利用指針存儲迷宮，操作方便。c. 能按照玩游戲人的意愿任意輸入迷宮大小，并且可以保存新輸入的迷宮，方便退出游戲后仍可打開自己定義文件查看迷宮。3)、遇到的問題及如何解決 a.如何知道哪一點被探索過且路徑不通？ 答：maze【i】【j】本來時表示通與不通，那么可以當探索該點之后，將其值賦為-1,就可以知道此點已經被訪問過 b.如何正確的使用文件讀入迷宮？ 答：查看大一學的C+課本，仔細閱讀文件那一章。c.我想讓用戶在每次玩游戲之后都能查看輸入的迷宮，我想的是運行程序時隨意新建文本文檔，開始是直接輸入一個.txt結尾的字符串，但編譯好多錯誤,我猜應該是要調用相關函數，但具體是那一個不清楚。 答

16、：去圖書館借閱相關資料，要調用相應的庫函數。4)、存在的缺陷、改進設想 每當自行輸入迷宮后，生成相應的文件保存，但是我在想：一旦玩游戲的人多了，玩的次數多了，那么生成的保存迷宮文件就會很多，會給人工智能化系統(tǒng)造成文件冗余。我設想：能不能在一段時間之后系統(tǒng)自動調用函數來清除冗余文件。5)、自我評價、經驗體會等通過這次課程設計，體會如下：、進一步熟悉掌握了有關棧的基本操作；、對迷宮有了更多的認識3、更進一步掌握有關類的操作4、由于對棧的算法推敲不足，使程序調試時費時不少總之：我認為這次課程設計做的很好。課程設計的成功使我相信一句話：有付出就會有收獲，要相信自己。6. 附錄（源程序清單，要求含有至少

17、30%的源碼附有注釋）迷宮程序代碼（本程序有個創(chuàng)新點）/* Name: stack.h Author: 羅丹 Description: 用于記錄探索路徑的棧類頭文件 */#include#includefstreamusing namespace std;class DataType /定義描述迷宮中當前位置的類型public:int x; /x代表當前位置的行坐標 int y; /y代表當前位置的列坐標 int pre; /pre表示移動到下一步的方向; class Move /定義下一個位置的方向 public:int x; int y;class Node /鏈表結點public: Da

18、taType data; Node *next;/下面定義棧class stackprivate: Node *top; /指向第一個結點的棧頂指針 public: stack(); /構造函數，置空棧 stack(); /析構函數 void Push(DataType data);/把元素data壓入棧中 DataType Pop(); /使棧頂元素出棧 DataType GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool IsEmpty(); /判斷棧是否為空，如果為空則返回1，否則返回0;/* Name: stack.cpp Author: 羅丹 Des

19、cription: 用于記錄探索路徑的棧類實現文件 */#includestack.hstack:stack() /構造函數，置空棧top=NULL;stack:stack() /析構函數void stack:Push(DataType x) /進棧Node *TempNode; TempNode=new Node; TempNode-data=x; TempNode-next=top; top=TempNode;DataType stack:Pop() /棧頂元素出棧 DataType Temp; Node *TempNode=NULL; TempNode=top; top=top-next

20、; Temp=TempNode-data; delete TempNode; return Temp;DataType stack:GetPop() /取出棧頂元素return top-data;void stack:Clear() /把棧清空top=NULL;bool stack:IsEmpty() /判斷棧是否為空，如果為空則返回1，否則返回0if(top=NULL) return true; else return false;/* Name: main.cpp Author: 羅丹 Description: 主函數文件 */#includestack.h#include#include

21、#includeusing namespace std ;/* Description: 外部函數的聲明部分*/bool findpath(int *maze,int m,int n); /尋找迷宮路徑 void PrintPath(stack p); /輸出路徑void Restore(int *maze,int m,int n); /恢復迷宮Move move4=0,1,1,0,0,-1,-1,0; /定義當前位置移動的4個方向(上，右，下，左)int* readFile (int &m,int &n);int* write &m,int &n);/* Description: main.

22、cpp*/ void main() coutendl;/ coutendl; cout 2007-2008年度第一學期數據結構課程之課程設計 endl; coutendl; cout 迷宮問題 endl; cout 開發(fā)員 : 羅丹endl; cout 專業(yè)班級: 計算機061班endl; coutendl; cout 歡迎進入迷宮游戲 endl; int m=0,n=0; int *maze; char ch; int flag=0,flag1=0; while(flag1=0) while(flag=0)/標志是否重新選擇 coutendl; cout 請從以下選項中選擇獲取迷宮的方法！e

23、ndl; cout 從文件中讀取endl; cout 直接自行輸入endl; coutch; if(ch=a)maze=read);flag=1; else if(ch=b)maze=write);flag=1; else cout Sorry!您輸入的選擇代碼不在范圍內!請從新選擇endl; if(findpath(maze,m,n) cout Congratulations! 迷宮路徑探索成功!endl; /得到路徑 else cout Sorry! 路徑不存在endl; coutendl; coutc; if(c=n) flag1=1; else flag=0; cout 謝謝,您已經退

24、出迷宮系統(tǒng) endl; coutendl;/* Description: 獲取迷宮函數*/int* readFile (int &m,int &n) /讀出文件int *maze; int i=0,j=0; cout 您選擇的是直接從文件中讀取迷宮!endl; coutendl; cout 文件中的迷宮如下： endl; char ch; /定義一個字符，讀取文件中的內容 ifstream open(maze.txt); /定義一個文件對象，并打開文件maze.txt /讀取內容記錄行數和列數 （創(chuàng)新點一：從文件中直接讀取迷宮） while(open.get(ch) /從讀取文件中內容（一旦個

25、字符形式） if(ch=0|ch=1) j+; /是0或1字符寬就加1 if(ch=n) i+; /如果是換行符，就行加1 n=j; /得列數 j=0; open.close(); /讀取文件結束 m=i; maze=new int *m+2; /申請長度等于行數加2的二維指針(為后面的回復迷宮打下基礎) for(i= 0;im+2;i+) /申請空間 mazei=new intn+2; i=j=1; ifstream open1(maze.txt); /重新讀取文件，以得到內容 while(open1.get(ch) if(ch=1|ch=0) mazeij=ch-0; /把數字字符轉化為數

26、字，并存到指針里 coutmazeij ; /在屏幕中顯示迷宮 j+; if(ch=n) /遇到換行，指針也相應換行 coutendl; i+; j=1; open1.close(); /讀取結束 return maze; int* writeFile (int &m,int &n) /將自定義迷宮寫入文件int a,b; int i,j;int*maze; cout 您選擇的是自行輸入迷宮!endl; coutb; /輸入迷宮的長和寬 couta; cout 請輸入迷宮內容(0代表可通，1代表不通):n; m=a; n=b; /m,n分別代表迷宮的行數和列數 maze=new int *m+

27、2; for(i= 0;im+2;i+) mazei=new intn+2; /創(chuàng)新點二：:隨意申請空間 for(i=1;i=m;i+) /輸入迷宮的內容，0代表可通，1代表不通 for(j=1;jmazeij; coutchoose; if(choose=Y|choose=y) char ch; string str; coutstr; ofstream open(str.c_str(); /創(chuàng)新點三：按玩游戲人的意愿創(chuàng)建存儲迷宮的文件，也可不建立。 for(i=1;i=m;i+) for(j=1;j=n;j+) ch=0+mazeij; opench; openendl; flush(co

28、ut); open.close(); for(i=0;im+2;i+) mazei0=mazein+1=1; for(i=0;in+2;i+) maze0i=mazem+1i=1; return maze; /* Description: 探索路徑函數*/bool findpath(int *maze,int m,int n)stack q,p; /創(chuàng)新點四：用棧p、q,分別存探索迷宮的過程和存儲路徑 DataType Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /將入口位置入棧 p.Push(Temp1);

29、maze11=-1; /創(chuàng)新點五：標志入口位置已到達過 while(!q.IsEmpty() /棧q非空，則反復探索 Temp2=q.GetPop(); if(!(p.GetPop().x=q.GetPop().x&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入棧，則把上一個探索的位置存入棧p for(loop=0;loop4;loop+) /探索當前位置的4個相鄰位置 x=Temp2.x+moveloop.x; y=Temp2.y+moveloop.y; if(mazexy=0) /判斷新位置是否可達 Temp1.x=x; Temp1.y=y; mazexy=-1; /標志新位置已到達過 q.Push(Temp1); /新位置入棧 if(x=(m)&(y=(n) /成功到達出口 Temp1.x=m; Temp1.y=n; Temp1.pre=0; p.Push(Temp1); /把最后一個位置入棧 PrintPath(p); Restore(maze,m,n); /恢復路徑（因為迷宮里面的內容已被改變 return 1; /表示成功找到路徑 if(p.G