迷宮問(wèn)題課程設(shè)計(jì)報(bào)告

1、南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課 程 設(shè) 計(jì) 報(bào) 告 （ 2007 2008 學(xué)年度 第 1學(xué)期 ）課程名稱數(shù)據(jù)結(jié)構(gòu)c+描述課程設(shè)計(jì)名稱迷宮問(wèn)題姓名羅丹學(xué)號(hào) 20064440109專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)計(jì)算機(jī)01班地點(diǎn)8209教師 劉 霞 1.實(shí)驗(yàn)?zāi)康募耙?）、設(shè)計(jì)目標(biāo)（問(wèn)題描述）迷宮問(wèn)題問(wèn)題描述：迷宮實(shí)驗(yàn)是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無(wú)頂大盒子的門放入，在盒中設(shè)置了許多墻，對(duì)行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對(duì)同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口到出口，而不走錯(cuò)一步。老鼠經(jīng)多次試驗(yàn)終于得到它

2、學(xué)習(xí)走迷宮的路線。2）、功能設(shè)計(jì)要求編寫一個(gè)程序求解迷宮問(wèn)題。迷宮由m行n列的二維數(shù)組設(shè)置，0表示無(wú)障礙，1表示有障礙。設(shè)入口為（1，1），出口為（m，n），每次只能從一個(gè)無(wú)障礙單元移到周圍四個(gè)方向上任一無(wú)障礙單元。編程實(shí)現(xiàn)對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。算法輸入：代表迷宮入口的坐標(biāo)算法輸出：穿過(guò)迷宮的結(jié)果。算法要點(diǎn)：創(chuàng)建迷宮，試探法查找路徑，輸出解3）、實(shí)驗(yàn)?zāi)康?1、加深對(duì)棧特性理解，以便在解決實(shí)際問(wèn)題中靈活運(yùn)用它們 2、加深對(duì)棧操作實(shí)際算法的理解 3、進(jìn)一步熟悉掌握鏈表的操作； 4、掌握指針的應(yīng)用 5、更進(jìn)一步掌握有關(guān)類的操作  &#

3、160;              4）、 需求分析 1、本程序?qū)崿F(xiàn)迷宮的探索過(guò)程. 以用戶和計(jì)算機(jī)對(duì)話的方式，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就探索路徑并輸出路徑。 2、本演示程序中，輸入形式以“回車符”為結(jié)束標(biāo)志，且允許出現(xiàn)重復(fù)字符。 3、利用二維指針實(shí)現(xiàn)迷宮位置的存儲(chǔ)，并用棧存貯探索路徑，每個(gè)結(jié)點(diǎn)含三個(gè)整形變量。輸入的形式以回車結(jié)束。 4、本程序中，用戶可以讀去文件里的迷宮，也可自己

4、重新輸入迷宮，而且用戶可以輸入任意大小的迷宮，然后程序自動(dòng)探索路徑，并輸出迷宮的路徑 5）、創(chuàng)新（見源程序附錄）6）、軟件、硬件環(huán)境 軟件環(huán)境：Microsoft Windows Xp Processional2002 ServiceMicrosoft Visual C+6.0 硬件環(huán)境：cpu：AMD Athlon（tm）64x DualProcessor 3800+2.01GHz Main memory:960MB2.實(shí)驗(yàn)步驟a.認(rèn)真閱讀課本的相關(guān)知識(shí)章節(jié)。b.認(rèn)真分析課題的需求分析和功能分析。c.根據(jù)分析的思路寫出偽代碼。d.根據(jù)偽代碼上機(jī)編寫程序，進(jìn)行初步調(diào)試。e.逐步增加完善系統(tǒng)的功

5、能，實(shí)現(xiàn)人工智能化。f.記錄上機(jī)運(yùn)行時(shí)遇到的錯(cuò)誤，進(jìn)行認(rèn)真分析。g.最后認(rèn)真撰寫實(shí)驗(yàn)報(bào)告，寫出實(shí)驗(yàn)心得總結(jié)。3. 實(shí)驗(yàn)內(nèi)容1）、設(shè)計(jì)概述(a) 開發(fā)平臺(tái)：VC6.0(b) 參考書籍： 1.數(shù)據(jù)結(jié)構(gòu)C+描述 熊岳山 陳懷義 編著 國(guó)防科技大學(xué)出版社 2、數(shù)據(jù)結(jié)構(gòu)與算法黃定  黃煜廉 編著  廣東科技出版社  2000年1月第1版3、數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與提高徐孝凱  編著 清華大學(xué)出版社 2003年12月第1版(c) 開發(fā)周期： 10天（構(gòu)思3天、雛形3天、修改2天、再修改1天、完善1天）2）、處理流程(a)畫出功能結(jié)構(gòu)圖Main主函數(shù)模塊輸出

6、路徑模塊printpath（）獲取迷宮模塊探索路徑模塊Findpath（）寫文件Writefile（）讀文件Readfile（）存儲(chǔ)探索路徑模塊stack類Stack類操作模塊數(shù)據(jù)模塊盤空函數(shù)isempty（）清空函數(shù)clear（）取棧頂函數(shù)getpop（）進(jìn)棧與出棧函數(shù)push（）Pop（）構(gòu)造與析構(gòu)函數(shù)stack（）stack（）結(jié)點(diǎn)模塊Node*top結(jié)點(diǎn)數(shù)據(jù)類型模塊datatype類(b)畫出主要數(shù)據(jù)結(jié)構(gòu)的類圖class 類名DataType /定義描述迷宮中當(dāng)前位置的類型數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類型 變量名; public:int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y

7、代表當(dāng)前位置的列坐標(biāo) int pre; /pre表示移動(dòng)到下一步的方向 class 類名Move /定義下一個(gè)位置的方向數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類型 變量名; public:int x; int y;class 類名Node /結(jié)點(diǎn)數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類型 變量名; public: DataType data; Node *next;class 類名stack數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類型 變量名; private: Node *top; /指向第一個(gè)結(jié)點(diǎn)的棧頂指針成員函數(shù)訪問(wèn)控制權(quán)限 返回值類型 函數(shù)名(參數(shù)列表) public: stack(); /構(gòu)造函數(shù)，置空棧 stack()

8、; /析構(gòu)函數(shù) void Push(DataType data);/把元素data壓入棧中 DataType Pop(); /使棧頂元素出棧 DataType GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool IsEmpty(); /判斷棧是否為空，如果為空則返回1，否則返回0(c)主要函數(shù)的程序流程圖開始 1.main函數(shù)流程圖： 顯示系統(tǒng)信息選擇獲取迷宮的方式chCh= bCh=a自行輸入Writefile（）Readfile()文件讀取探索迷宮路徑是否存在輸出迷宮路徑是否繼續(xù)游戲退出開始2.探索路徑函數(shù)findpath（）Temp1.x=1Temp1.

9、y=1入口進(jìn)棧p.pushq.push是否非空temp2=q.getpop（）P q棧頂是否相等探索上下左右四個(gè)方位是否有路徑到達(dá)新位置是否到達(dá)出口最后一個(gè)元素進(jìn)棧輸出路徑回復(fù)以改變的迷宮結(jié)束 開始3.自行輸入迷宮函數(shù)writefile（）輸入長(zhǎng)寬m，n動(dòng)態(tài)申請(qǐng)空間二位數(shù)組空間i<=m是否保存迷宮J<=ni+ ；j+輸入迷宮輸入保存迷宮的文件名保存迷宮結(jié)束(d)寫出數(shù)據(jù)測(cè)試表（輸入數(shù)據(jù)/預(yù)期結(jié)果） 測(cè)試一：從文件中讀取迷宮： 0010001000010001010000110000111001000001000010100010100111100111100010111100000

10、00 輸出：探索路徑： （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，8，向右） （9，9）測(cè)試二： 自己輸入迷宮： 001000100 輸出探索路徑： （1，1，向下）（2，1，向右）（2，2，向下）（3，2，向右）（3，3）測(cè)試三：自己輸入迷宮： 111111000 輸出探索路徑： Sorry！找不到路徑！4.實(shí)驗(yàn)結(jié)果結(jié)果為以下三種情形之一：1）編譯不通過(guò)：

11、給出編譯錯(cuò)。Compiling.stack.cppSkipping. (no relevant changes detected)main.cppLinking.stack.obj : error LNK2005: "public: _thiscall stack:stack(void)" (?0stackQAEXZ) already defined in main.objstack.obj : error LNK2005: "public: _thiscall stack:stack(void)" (?1stackQAEXZ) already defi

12、ned in main.objstack.obj : error LNK2005: "public: void _thiscall stack:Push(struct DataType)" (?PushstackQAEXUDataTypeZ) already defined in main.objstack.obj : error LNK2005: "public: struct DataType _thiscall stack:Pop(void)" (?PopstackQAE?AUDataTypeXZ) already defined in main.

13、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:Clear(void)" (?ClearstackQAEXXZ) already defined in main.objstack.obj : error LN

14、K2005: "public: bool _thiscall stack:IsEmpty(void)" (?IsEmptystackQAE_NXZ) already defined in main.objDebug/迷宮問(wèn)題.exe : fatal error LNK1169: one or more multiply defined symbols found執(zhí)行 link.exe 時(shí)出錯(cuò).迷宮問(wèn)題.exe - 1 error(s), 0 warning(s)改正： 在main。cpp中原來(lái)包含的是stack.cpp把它改為包含stack.h即可錯(cuò)誤二： 用string直

15、接定義字符串str時(shí)，說(shuō)沒有定義str 原因：#include<string>using namespace std ;沒有用標(biāo)準(zhǔn)空間錯(cuò)誤三： 拼寫錯(cuò)誤正確結(jié)果輸出：接上面：接上面：5. 實(shí)驗(yàn)總結(jié)分析1)、時(shí)間和空間分析該算法的運(yùn)行時(shí)間和使用系統(tǒng)棧所占有的存儲(chǔ)空間與迷宮的大小成正比，迷宮長(zhǎng)為m，寬為n，在最好情況下的時(shí)間和空間復(fù)雜度均為O（m+n），在最差情況下均為O（m*n），平均情況在它們之間2)、程序的優(yōu)點(diǎn)a. 進(jìn)入演示程序后即顯示文本方式的用戶界面b. 本程序模塊劃分比較合理，且利用指針存儲(chǔ)迷宮，操作方便。c. 能按照玩游戲人的意愿任意輸入迷宮大小，并且可以保存新輸入的迷宮

16、，方便退出游戲后仍可打開自己定義文件查看迷宮。3)、遇到的問(wèn)題及如何解決 a.如何知道哪一點(diǎn)被探索過(guò)且路徑不通？ 答：maze【i】【j】本來(lái)時(shí)表示通與不通，那么可以當(dāng)探索該點(diǎn)之后，將其值賦為-1,就可以知道此點(diǎn)已經(jīng)被訪問(wèn)過(guò) b.如何正確的使用文件讀入迷宮？ 答：查看大一學(xué)的C+課本，仔細(xì)閱讀文件那一章。c.我想讓用戶在每次玩游戲之后都能查看輸入的迷宮，我想的是運(yùn)行程序時(shí)隨意新建文本文檔，開始是直接輸入一個(gè).txt結(jié)尾的字符串，但編譯好多錯(cuò)誤,我猜應(yīng)該是要調(diào)用相關(guān)函數(shù)，但具體是那一個(gè)不清楚。 答：去圖書館借閱相關(guān)資料，要調(diào)用相應(yīng)的庫(kù)函數(shù)。4)、存在的缺陷、改進(jìn)設(shè)想 每當(dāng)自行輸入迷宮后，生成相應(yīng)

17、的文件保存，但是我在想：一旦玩游戲的人多了，玩的次數(shù)多了，那么生成的保存迷宮文件就會(huì)很多，會(huì)給人工智能化系統(tǒng)造成文件冗余。我設(shè)想：能不能在一段時(shí)間之后系統(tǒng)自動(dòng)調(diào)用函數(shù)來(lái)清除冗余文件。5)、自我評(píng)價(jià)、經(jīng)驗(yàn)體會(huì)等通過(guò)這次課程設(shè)計(jì)，體會(huì)如下：、進(jìn)一步熟悉掌握了有關(guān)棧的基本操作；、對(duì)迷宮有了更多的認(rèn)識(shí)3、更進(jìn)一步掌握有關(guān)類的操作4、由于對(duì)棧的算法推敲不足，使程序調(diào)試時(shí)費(fèi)時(shí)不少總之：我認(rèn)為這次課程設(shè)計(jì)做的很好。課程設(shè)計(jì)的成功使我相信一句話：有付出就會(huì)有收獲，要相信自己。6. 附錄（源程序清單，要求含有至少30%的源碼附有注釋）迷宮程序代碼（本程序有個(gè)創(chuàng)新點(diǎn)）/* Name: stack.h Author

18、: 羅丹 Description: 用于記錄探索路徑的棧類頭文件 */#include<iostream>#include"fstream"using namespace std;class DataType /定義描述迷宮中當(dāng)前位置的類型public:int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int pre; /pre表示移動(dòng)到下一步的方向; class Move /定義下一個(gè)位置的方向 public:int x; int y;class Node /鏈表結(jié)點(diǎn)public: DataType data; Node *nex

19、t;/下面定義棧class stackprivate: Node *top; /指向第一個(gè)結(jié)點(diǎn)的棧頂指針 public: stack(); /構(gòu)造函數(shù)，置空棧 stack(); /析構(gòu)函數(shù) void Push(DataType data);/把元素data壓入棧中 DataType Pop(); /使棧頂元素出棧 DataType GetPop(); /取出棧頂元素 void Clear(); /把棧清空 bool IsEmpty(); /判斷棧是否為空，如果為空則返回1，否則返回0;/* Name: stack.cpp Author: 羅丹 Description: 用于記錄探索路徑的棧類實(shí)

20、現(xiàn)文件 */#include"stack.h"stack:stack() /構(gòu)造函數(shù)，置空棧top=NULL;stack:stack() /析構(gòu)函數(shù)void stack:Push(DataType x) /進(jìn)棧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->ne

21、xt; 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: 主函數(shù)文件 */#include"stack.h

22、"#include<iostream>#include<string>#include<fstream>using namespace std ;/* Description: 外部函數(shù)的聲明部分*/bool findpath(int *maze,int m,int n); /尋找迷宮路徑 void PrintPath(stack p); /輸出路徑void Restore(int *maze,int m,int n); /恢復(fù)迷宮Move move4=0,1,1,0,0,-1,-1,0; /定義當(dāng)前位置移動(dòng)的4個(gè)方向(上，右，下，左)int* r

23、eadFile (int &m,int &n);int* write &m,int &n);/* Description: main.cpp*/ void main() cout<<endl;/ cout<<""<<endl; cout<<" 2007-2008年度第一學(xué)期數(shù)據(jù)結(jié)構(gòu)課程之課程設(shè)計(jì) "<<endl; cout<<endl; cout<<" 迷宮問(wèn)題 "<<endl; cout<<&q

24、uot; 開發(fā)員 : 羅丹"<<endl; cout<<" 專業(yè)班級(jí): 計(jì)算機(jī)061班"<<endl; cout<<""<<endl; cout<<" 歡迎進(jìn)入迷宮游戲 "<<endl; int m=0,n=0; int *maze; char ch; int flag=0,flag1=0; while(flag1=0) while(flag=0)/標(biāo)志是否重新選擇 cout<<endl; cout<<" 請(qǐng)

25、從以下選項(xiàng)中選擇獲取迷宮的方法！"<<endl; cout<<" <a>從文件中讀取"<<endl; cout<<" <b>直接自行輸入"<<endl; cout<<" 請(qǐng)選擇:" cin>>ch; if(ch='a')maze=read);flag=1; else if(ch='b')maze=write);flag=1; else cout<<" Sorry!您

26、輸入的選擇代碼不在范圍內(nèi)!請(qǐng)從新選擇"<<endl; if(findpath(maze,m,n) cout<<" Congratulations! 迷宮路徑探索成功!"<<endl; /得到路徑 else cout<<" Sorry! 路徑不存在"<<endl; cout<<endl; cout<<" 繼續(xù)玩嗎？(y/n)" char c; cin>>c; if(c=n) flag1=1; else flag=0; cout<

27、;<" 謝謝,您已經(jīng)退出迷宮系統(tǒng) "<<endl; cout<<""<<endl;/* Description: 獲取迷宮函數(shù)*/int* readFile (int &m,int &n) /讀出文件int *maze; int i=0,j=0; cout<<" 您選擇的是直接從文件中讀取迷宮!"<<endl; cout<<endl; cout<<" 文件中的迷宮如下： "<<endl; char

28、ch; /定義一個(gè)字符，讀取文件中的內(nèi)容 ifstream open("maze.txt"); /定義一個(gè)文件對(duì)象，并打開文件"maze.txt" /讀取內(nèi)容記錄行數(shù)和列數(shù) （創(chuàng)新點(diǎn)一：從文件中直接讀取迷宮） while(open.get(ch) /從讀取文件中內(nèi)容（一旦個(gè)字符形式） if(ch='0'|ch='1') j+; /是0或1字符寬就加1 if(ch='n') i+; /如果是換行符，就行加1 n=j; /得列數(shù) j=0; open.close(); /讀取文件結(jié)束 m=i; maze=new

29、int *m+2; /申請(qǐng)長(zhǎng)度等于行數(shù)加2的二維指針(為后面的回復(fù)迷宮打下基礎(chǔ)) for(i= 0;i<m+2;i+) /申請(qǐng)空間 mazei=new intn+2; i=j=1; ifstream open1("maze.txt"); /重新讀取文件，以得到內(nèi)容 while(open1.get(ch) if(ch='1'|ch='0') mazeij=ch-'0' /把數(shù)字字符轉(zhuǎn)化為數(shù)字，并存到指針里 cout<<mazeij<<" " /在屏幕中顯示迷宮 j+; if(ch

30、='n') /遇到換行，指針也相應(yīng)換行 cout<<endl; i+; j=1; open1.close(); /讀取結(jié)束 return maze; int* writeFile (int &m,int &n) /將自定義迷宮寫入文件int a,b; int i,j;int*maze; cout<<" 您選擇的是自行輸入迷宮!"<<endl; cout<<" 請(qǐng)輸入迷宮的長(zhǎng):"cin>>b; /輸入迷宮的長(zhǎng)和寬 cout<<" 請(qǐng)輸入迷宮的寬

31、:"cin>>a; cout<<" 請(qǐng)輸入迷宮內(nèi)容(0代表可通，1代表不通):n" m=a; n=b; /m,n分別代表迷宮的行數(shù)和列數(shù) maze=new int *m+2; for(i= 0;i<m+2;i+) mazei=new intn+2; /創(chuàng)新點(diǎn)二：:隨意申請(qǐng)空間 for(i=1;i<=m;i+) /輸入迷宮的內(nèi)容，0代表可通，1代表不通 for(j=1;j<=n;j+) cin>>mazeij; cout<<" 是否保存新迷宮？(y/n): " char choos

32、e; cin>>choose; if(choose='Y'|choose='y') char ch; string str; cout<<" 請(qǐng)輸入保存迷宮的文件名(以.txt結(jié)束):" cin>>str; ofstream open(str.c_str(); /創(chuàng)新點(diǎn)三：按玩游戲人的意愿創(chuàng)建存儲(chǔ)迷宮的文件，也可不建立。 for(i=1;i<=m;i+) for(j=1;j<=n;j+) ch='0'+mazeij; open<<ch; open<<end

33、l; flush(cout); open.close(); for(i=0;i<m+2;i+) mazei0=mazein+1=1; for(i=0;i<n+2;i+) maze0i=mazem+1i=1; return maze; /* Description: 探索路徑函數(shù)*/bool findpath(int *maze,int m,int n)stack q,p; /創(chuàng)新點(diǎn)四：用棧p、q,分別存探索迷宮的過(guò)程和存儲(chǔ)路徑 DataType Temp1,Temp2; int x,y,loop; Temp1.x=1; Temp1.y=1; q.Push(Temp1); /將入口位

34、置入棧 p.Push(Temp1); maze11=-1; /創(chuàng)新點(diǎn)五：標(biāo)志入口位置已到達(dá)過(guò) while(!q.IsEmpty() /棧q非空，則反復(fù)探索 Temp2=q.GetPop(); if(!(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y) p.Push(Temp2); /如果有新位置入棧，則把上一個(gè)探索的位置存入棧p for(loop=0;loop<4;loop+) /探索當(dāng)前位置的4個(gè)相鄰位置 x=Temp2.x+moveloop.x; y=Temp2.y+moveloop.y; if(mazexy=

35、0) /判斷新位置是否可達(dá) Temp1.x=x; Temp1.y=y; mazexy=-1; /標(biāo)志新位置已到達(dá)過(guò) q.Push(Temp1); /新位置入棧 if(x=(m)&&(y=(n) /成功到達(dá)出口 Temp1.x=m; Temp1.y=n; Temp1.pre=0; p.Push(Temp1); /把最后一個(gè)位置入棧 PrintPath(p); Restore(maze,m,n); /恢復(fù)路徑（因?yàn)槊詫m里面的內(nèi)容已被改變 return 1; /表示成功找到路徑 if(p.GetPop().x=q.GetPop().x&&p.GetPop().y=q.GetPop().y)/如果沒有新位置入棧，則返回到上一個(gè)位置 p.Pop(); q.Pop(); return 0; /表示查找失敗，即迷宮無(wú)路經(jīng)/* Description: 輸出路徑函數(shù)*/void PrintPath(stack p) /輸出路徑cout<<endl; cout<<" 迷宮的路徑為"<&l