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

1、南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課 程 設(shè) 計(jì) 報(bào) 告 （ 2007 2008 學(xué)年度 第 1學(xué)期 ）課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)c+描述課程設(shè)計(jì)名稱(chēng)迷宮問(wèn)題姓名羅丹學(xué)號(hào) 20064440109專(zhuān)業(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ú)頂大盒子的門(mén)放入，在盒中設(shè)置了許多墻，對(duì)行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對(duì)同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口到出口，而不走錯(cuò)一步。老鼠經(jīng)多次試驗(yàn)終于得到它

2、學(xué)習(xí)走迷宮的路線。2）、功能設(shè)計(jì)要求編寫(xiě)一個(gè)程序求解迷宮問(wèn)題。迷宮由m行n列的二維數(shù)組設(shè)置，0表示無(wú)障礙，1表示有障礙。設(shè)入口為（1，1），出口為（m，n），每次只能從一個(gè)無(wú)障礙單元移到周?chē)膫€(gè)方向上任一無(wú)障礙單元。編程實(shí)現(xiàn)對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(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)類(lèi)的操作4）、需求分析 1、本程序?qū)?/p>

3、現(xiàn)迷宮的探索過(guò)程. 以用戶和計(jì)算機(jī)對(duì)話的方式，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤(pán)上輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就探索路徑并輸出路徑。 2、本演示程序中，輸入形式以“回車(chē)符”為結(jié)束標(biāo)志，且允許出現(xiàn)重復(fù)字符。 3、利用二維指針實(shí)現(xiàn)迷宮位置的存儲(chǔ)，并用棧存貯探索路徑，每個(gè)結(jié)點(diǎn)含三個(gè)整形變量。輸入的形式以回車(chē)結(jié)束。 4、本程序中，用戶可以讀去文件里的迷宮，也可自己重新輸入迷宮，而且用戶可以輸入任意大小的迷宮，然后程序自動(dòng)探索路徑，并輸出迷宮的路徑 5）、創(chuàng)新（見(jiàn)源程序附錄）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.實(shí)驗(yàn)步驟a.認(rèn)真閱讀課本的相關(guān)知識(shí)章節(jié)。b.認(rèn)真分析課題的需求分析和功能分析。c.根據(jù)分析的思路寫(xiě)出偽代碼。d.根據(jù)偽代碼上機(jī)編寫(xiě)程序，進(jìn)行初步調(diào)試。e.逐步增加完善系統(tǒng)的功能，實(shí)現(xiàn)人工智能化。f.記錄上機(jī)運(yùn)行時(shí)遇到的錯(cuò)誤，進(jìn)行認(rèn)真分析。g.最后認(rèn)真撰寫(xiě)實(shí)驗(yàn)報(bào)告，寫(xiě)出實(shí)驗(yàn)心得總結(jié)。3. 實(shí)驗(yàn)內(nèi)容1）、設(shè)計(jì)概述(a) 開(kāi)發(fā)平臺(tái)：VC6.0(b) 參考書(shū)籍： 1.數(shù)據(jù)結(jié)構(gòu)C+描述 熊岳山 陳

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

6、p（）構(gòu)造與析構(gòu)函數(shù)stack（）stack（）結(jié)點(diǎn)模塊Node*top結(jié)點(diǎn)數(shù)據(jù)類(lèi)型模塊datatype類(lèi)(b)畫(huà)出主要數(shù)據(jù)結(jié)構(gòu)的類(lèi)圖class 類(lèi)名DataType /定義描述迷宮中當(dāng)前位置的類(lèi)型數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類(lèi)型 變量名; public:int x; /x代表當(dāng)前位置的行坐標(biāo) int y; /y代表當(dāng)前位置的列坐標(biāo) int pre; /pre表示移動(dòng)到下一步的方向 class 類(lèi)名Move /定義下一個(gè)位置的方向數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類(lèi)型 變量名; public:int x; int y;class 類(lèi)名Node /結(jié)點(diǎn)數(shù)據(jù)成員訪問(wèn)控制權(quán)限 數(shù)據(jù)類(lèi)型 變量名; public

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

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

9、保存迷宮J=ni+ ；j+輸入迷宮輸入保存迷宮的文件名保存迷宮結(jié)束(d)寫(xiě)出數(shù)據(jù)測(cè)試表（輸入數(shù)據(jù)/預(yù)期結(jié)果） 測(cè)試一：從文件中讀取迷宮： 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）測(cè)試二： 自己輸入迷宮： 001000100 輸出探索路徑： （1，1，向下）（2，1，向右）（2，2，向下）（3，2，向右）（3，3）測(cè)試三：自己輸入迷宮： 111111000 輸出探索路徑： Sorry！找不到路徑！4.實(shí)驗(yàn)結(jié)果結(jié)果為以下三種情形之一：1）編譯不通過(guò)：給出編譯錯(cuò)。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/迷宮問(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 war

14、ning(s)改正： 在main。cpp中原來(lái)包含的是stack.cpp把它改為包含stack.h即可錯(cuò)誤二： 用string直接定義字符串str時(shí)，說(shuō)沒(méi)有定義str 原因：#includeusing namespace std ;沒(méi)有用標(biāo)準(zhǔn)空間錯(cuò)誤三： 拼寫(xiě)錯(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. 本程序模塊劃分比較合理

15、，且利用指針存儲(chǔ)迷宮，操作方便。c. 能按照玩游戲人的意愿任意輸入迷宮大小，并且可以保存新輸入的迷宮，方便退出游戲后仍可打開(kāi)自己定義文件查看迷宮。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í)隨意新建文本文檔，開(kāi)始是直接輸入一個(gè).txt結(jié)尾的字符串，但編譯好多錯(cuò)誤,我猜應(yīng)該是要調(diào)用相關(guān)函數(shù)，但具體是那一個(gè)不清楚。 答

16、：去圖書(shū)館借閱相關(guān)資料，要調(diào)用相應(yīng)的庫(kù)函數(shù)。4)、存在的缺陷、改進(jìn)設(shè)想 每當(dāng)自行輸入迷宮后，生成相應(yīng)的文件保存，但是我在想：一旦玩游戲的人多了，玩的次數(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)類(lèi)的操作4、由于對(duì)棧的算法推敲不足，使程序調(diào)試時(shí)費(fèi)時(shí)不少總之：我認(rèn)為這次課程設(shè)計(jì)做的很好。課程設(shè)計(jì)的成功使我相信一句話：有付出就會(huì)有收獲，要相信自己。6. 附錄（源程序清單，要求含有至少

17、30%的源碼附有注釋?zhuān)┟詫m程序代碼（本程序有個(gè)創(chuàng)新點(diǎn)）/* Name: stack.h Author: 羅丹 Description: 用于記錄探索路徑的棧類(lèi)頭文件 */#include#includefstreamusing namespace std;class DataType /定義描述迷宮中當(dāng)前位置的類(lèi)型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: Da

18、taType data; Node *next;/下面定義棧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: 羅丹 Des

19、cription: 用于記錄探索路徑的棧類(lèi)實(shí)現(xiàn)文件 */#includestack.hstack: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-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: 主函數(shù)文件 */#includestack.h#include#include

21、#includeusing 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* readFile (int &m,int &n);int* write &m,int &n);/* Description: main.

22、cpp*/ void main() coutendl;/ coutendl; cout 2007-2008年度第一學(xué)期數(shù)據(jù)結(jié)構(gòu)課程之課程設(shè)計(jì) endl; coutendl; cout 迷宮問(wèn)題 endl; cout 開(kāi)發(fā)員 : 羅丹endl; cout 專(zhuān)業(yè)班級(jí): 計(jì)算機(jī)061班endl; coutendl; 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)志是否重新選擇 coutendl; cout 請(qǐng)從以下選項(xiàng)中選擇獲取迷宮的方法！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!您輸入的選擇代碼不在范圍內(nèi)!請(qǐng)從新選擇endl; if(findpath(maze,m,n) cout Congratulations! 迷宮路徑探索成功!endl; /得到路徑 else cout Sorry! 路徑不存在endl; coutendl; coutc; if(c=n) flag1=1; else flag=0; cout 謝謝,您已經(jīng)退

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

25、字符形式） 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 int *m+2; /申請(qǐng)長(zhǎng)度等于行數(shù)加2的二維指針(為后面的回復(fù)迷宮打下基礎(chǔ)) for(i= 0;im+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ù)

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

27、2; for(i= 0;im+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;jmazeij; coutchoose; if(choose=Y|choose=y) char ch; string str; coutstr; 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; 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: 探索路徑函數(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); /將入口位置入棧 p.Push(Temp1);

29、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;loop4;loop+) /探索當(dāng)前位置的4個(gè)相鄰位置 x=Temp2.x+moveloop.x; y=Temp2.y+moveloop.y; if(mazexy=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.G