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

南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院試驗(yàn)報(bào)告南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院試驗(yàn)報(bào)告LDLD盡我所能南華大學(xué)課程設(shè)計(jì)報(bào)告〔2023 ~ 2023 學(xué)年度 第1學(xué)期〕課程名稱名稱

c++描述迷宮問(wèn)題姓名羅丹學(xué)號(hào)20234440109專業(yè)與技術(shù)班級(jí)01班地點(diǎn)8—209教師劉霞南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院試驗(yàn)報(bào)告南華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院試驗(yàn)報(bào)告1010LD盡我所能試驗(yàn)?zāi)康募耙蟆⒃O(shè)計(jì)目標(biāo)〔問(wèn)題描述〕迷宮問(wèn)題問(wèn)題描述：迷宮試驗(yàn)是取自心理學(xué)的一個(gè)古典試驗(yàn)。在該試驗(yàn)中，把一只老鼠從一個(gè)無(wú)頂大盒子的門(mén)放入，在盒中設(shè)置了很多墻，對(duì)行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中查找道路以到達(dá)出口。對(duì)同一只老鼠重復(fù)進(jìn)展上述試驗(yàn)，始終到老鼠從入口到出口，而不走錯(cuò)一步。老鼠經(jīng)屢次試驗(yàn)最終得到它學(xué)習(xí)走迷宮的路線。、功能設(shè)計(jì)要求編寫(xiě)一個(gè)程序求解迷宮問(wèn)題。迷宮由mn01有障礙。設(shè)入口為〔1，1，出口為〔m，n，每次只能從一個(gè)無(wú)障礙單元移到四周四個(gè)方向上任一無(wú)障礙單元。編程實(shí)現(xiàn)對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。算法輸入：代表迷宮入口的坐標(biāo)算法輸出：穿過(guò)迷宮的結(jié)果。算法要點(diǎn)：創(chuàng)立迷宮，摸索法查找路徑，輸出解、試驗(yàn)?zāi)康?、加深對(duì)棧特性理解，以便在解決實(shí)際問(wèn)題中敏捷運(yùn)用它們2、加深對(duì)棧操作實(shí)際算法的理解3、進(jìn)一步生疏把握鏈表的操作；4、把握指針的應(yīng)用5、更進(jìn)一步把握有關(guān)類的操作、需求分析1、本程序?qū)崿F(xiàn)迷宮的探究過(guò)程.以用戶和計(jì)算機(jī)對(duì)話的方式，即在計(jì)算機(jī)終端上顯示并輸出路徑。2、本演示程序中，輸入形式以“回車符”為完畢標(biāo)志，且允許消滅重復(fù)字符。3、利用二維指針實(shí)現(xiàn)迷宮位置的存儲(chǔ)，并用棧存貯探究路徑，每個(gè)結(jié)點(diǎn)含三個(gè)整形變量。輸入的形式以回車完畢。4、本程序中，用戶可以讀去文件里的迷宮，也可自己重輸入迷宮，而且用戶可以輸入任意大小的迷宮，然后程序自動(dòng)探究路徑，并輸出迷宮的路徑、創(chuàng)〔見(jiàn)源程序附錄〕、軟件、硬件環(huán)境軟件環(huán)境：MicrosoftWindowsXpProcessional2023ServiceMicrosoftVisualC++6.0硬件環(huán)境：cpu：AMD Athlon〔tm〕64xDualProcessor3800+2.01GHz Mainmemory:960MB試驗(yàn)步驟認(rèn)真閱讀課本的相關(guān)學(xué)問(wèn)章節(jié)。認(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ě)試驗(yàn)報(bào)告，寫(xiě)出試驗(yàn)心得總結(jié)。StackStack類數(shù)據(jù)模塊操作模塊〔〕〔〕Pop〔〕〔〕〔〕結(jié)點(diǎn)數(shù)據(jù)類型 模 塊datatype類、設(shè)計(jì)概述開(kāi)發(fā)平臺(tái)：VC6.0參考書(shū)籍：C++描述熊岳山陳懷義編著國(guó)防科技大學(xué)出版社2、《數(shù)據(jù)構(gòu)造與算法》黃定黃煜廉編著廣東科技出版社2023113《數(shù)據(jù)構(gòu)造輔導(dǎo)與提高》徐孝凱編著 清華大學(xué)出版社2023年12月第1版開(kāi)發(fā)周期：10天〔33211天〕、處理流程MainMain主函數(shù)模塊獵取迷宮模塊探究路徑模塊Findpath〔〕輸出路徑模塊printpath〔〕讀文件Readfile〔〕寫(xiě)文件Writefile〔〕存儲(chǔ)探究路徑模塊stack類結(jié)點(diǎn)模塊構(gòu)進(jìn)棧與清空函盤(pán)空函Node*top析出棧函函 數(shù)數(shù)數(shù)數(shù)stackpushgetpopcler〕isemptyclassclassMove//定義下一個(gè)位置的方向數(shù) 訪問(wèn)掌握權(quán)限數(shù)據(jù)類型變量名;據(jù) public:成 intx;員 inty;classNode//結(jié)點(diǎn)數(shù) 訪問(wèn)掌握權(quán)限數(shù)據(jù)類型變量名;據(jù) public:成 DataTypedata;員 Node*next;classstack數(shù)據(jù)成訪問(wèn)掌握權(quán)限數(shù)據(jù)類型變量名;private:Node*top;//指向第一個(gè)結(jié)點(diǎn)的棧頂指針voidPush(DataTypedata);//dataDataTypePop; //使棧頂元素出棧DataTypeGetPop; //取出棧頂元素voidClear; //把棧清空boolIsEmpty; //推斷棧是否為空，假設(shè)為空則返回1，否則0classclassDataType//定義描述迷宮中當(dāng)前位置的類型數(shù)據(jù)成員訪問(wèn)掌握權(quán)限數(shù)據(jù)類型變量名;public:intx;inty;intpre;//x//y//pre員成員函訪問(wèn)掌握權(quán)限public:stack;返回值類型函數(shù)名(參數(shù)列表)//構(gòu)造函數(shù)，置空棧數(shù)~stack;//析構(gòu)函數(shù)開(kāi)頭主要函數(shù)的程序流程圖1.開(kāi)頭main函數(shù)流程圖：顯示系統(tǒng)信息顯示系統(tǒng)信息選擇獵取迷宮的方式chCh==’a’Ch==’b’Readfile文件讀取自行輸入探究迷宮路徑是否存在輸出迷宮續(xù)玩耍退出探究路徑函數(shù)findpath〔〕 開(kāi)頭Temp1.x=1Temp1.y=1入口進(jìn)棧p.pushq.push是否非空temp2=q.getpop〔〕Pq棧頂是否相等探究上下左右四個(gè)方位是否有路徑

到達(dá)位置是否到達(dá)出最終一個(gè)元素進(jìn)棧輸出路徑回復(fù)以轉(zhuǎn)變的迷宮完畢開(kāi)頭輸入長(zhǎng)寬m，開(kāi)頭輸入長(zhǎng)寬m，n動(dòng)態(tài)申請(qǐng)空間二位數(shù)組空間i<=m是否保存迷宮J<=ni++；j++輸入迷宮輸入保存迷宮的文件名保存迷宮完畢寫(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，8，向右〕〔9，9〕測(cè)試二：自己輸入迷宮：001000100輸出探究路徑：〔1，1，向下〕〔2，1，向右〕〔2，2，向下〕〔3，2，向右〕〔3，3〕測(cè)試三：自己輸入迷宮：111111000輸出探究路徑：Sorry！找不到路徑！試驗(yàn)結(jié)果結(jié)果為以下三種情形之一：1〕編譯不通過(guò)：給出編譯錯(cuò)。Compiling...stack.cppSkipping...(norelevantchangesdetected)main.cppLinking...stack.obj:errorLNK2023:“public: thiscallstack::stack(void)“(??0stack@@QAE@XZ)alreadydefinedinmain.objstack.obj : error LNK2023: “public:(??1stack@@QAE@XZ)alreadydefinedinmain.obj

thiscall stack::~stack(void)“stack.obj : error LNK2023: “public: void thiscall stack::Push(struct (?Push@stack@@QAEXUDataType@@@Z)alreadydefinedinmain.objstack.obj : error LNK2023: “public: struct DataType thiscall stack::Pop(void)“(?Pop@stack@@QAE?AUDataType@@XZ)alreadydefinedinmain.objstack.obj:errorLNK2023:“public:structDataType thiscallstack::GetPop(void)“(?GetPop@stack@@QAE?AUDataType@@XZ)alreadydefinedinmain.objstack.obj : error LNK2023: “public: void(?Clear@stack@@QAEXXZ)alreadydefinedinmain.obj

thiscall stack::Clear(void)“stack.obj : error LNK2023: “public: bool thiscall stack::IsEmpty(void)“(?IsEmpty@stack@@QAE_NXZ)alreadydefinedinmain.objDebug/迷宮問(wèn)題.exe:fatalerrorLNK1169:oneormoremultiplydefinedsymbolsfoundlink.exe時(shí)出錯(cuò).迷宮問(wèn)題.exe1error(s),0warning(s)改正：main。cpp中原來(lái)包含的是stack.cpp把它改為包含stack.h即可錯(cuò)誤二：string直接定義字符串str時(shí)，說(shuō)沒(méi)有定義str緣由：#include<string>usingnamespacestd沒(méi)有用標(biāo)準(zhǔn)空間錯(cuò)誤三：拼寫(xiě)錯(cuò)誤正確結(jié)果輸出：接上面：接上面：試驗(yàn)總結(jié)分析、時(shí)間和空間分析該算法的運(yùn)行時(shí)間和使用系統(tǒng)棧所占有的存儲(chǔ)空間與迷宮的大小成正比，迷宮長(zhǎng)為m，寬為，在最好狀況下的時(shí)間和空間簡(jiǎn)單度均為〔m+，在最差狀況下均為平均狀況在它們之間、程序的優(yōu)點(diǎn)進(jìn)入演示程序后即顯示文本方式的用戶界面本程序模塊劃分比較合理，且利用指針存儲(chǔ)迷宮，操作便利。玩耍后仍可翻開(kāi)自己定義文件查看迷宮。、遇到的問(wèn)題及如何解決如何知道哪一點(diǎn)被探究過(guò)且路徑不通？答：maze【ij-1,就可以知道此點(diǎn)已經(jīng)被訪問(wèn)過(guò)如何正確的使用文件讀入迷宮？答：查看大一學(xué)的C++課本，認(rèn)真閱讀文件那一章。我想讓用戶在每次玩玩耍之后都能查看輸入的迷宮，我想的是運(yùn)行程序時(shí)隨便建文本文檔，開(kāi)頭是直接輸入一個(gè).txt結(jié)尾的字符串，但編譯好多錯(cuò)誤,我猜應(yīng)當(dāng)是要調(diào)用相關(guān)函數(shù)，但具體是那一個(gè)不清楚。答：去圖書(shū)館借閱相關(guān)資料，要調(diào)用相應(yīng)的庫(kù)函數(shù)。、存在的缺陷、改進(jìn)設(shè)想能不能在一段時(shí)間之后系統(tǒng)自動(dòng)調(diào)用函數(shù)來(lái)去除冗余文件。、自我評(píng)價(jià)、閱歷體會(huì)等通過(guò)這次課程設(shè)計(jì)，體會(huì)如下：１、進(jìn)一步生疏把握了有關(guān)棧的根本操作；２、對(duì)迷宮有了更多的生疏3、更進(jìn)一步把握有關(guān)類的操作4、由于對(duì)棧的算法推敲缺乏，使程序調(diào)試時(shí)費(fèi)時(shí)不少收獲，要信任自己。附錄〔30%的源碼附有注釋〕迷宮程序代碼〔本程序有個(gè)創(chuàng)點(diǎn)〕//////////////////////////////////////////////////////////////////////*Name: stack.hAuthor:羅丹Description:用于記錄探究路徑的棧類頭文件*/#include<iostream>#include“fstream“usingnamespacestd;classDataType //定義描述迷宮中當(dāng)前位置的類型{public:intx; //xinty; //yintpre; //pre};classMove //定義下一個(gè)位置的方向{public:intx;inty;};classNode //鏈表結(jié)點(diǎn){public:DataTypedata;Node*next;};//下面定義棧classstack{private:Node*top; //指向第一個(gè)結(jié)點(diǎn)的棧頂指針public:stack; //構(gòu)造函數(shù)，置空棧~stack; //析構(gòu)函數(shù)voidPush(DataTypedata);//把元素data壓入棧中DataTypePop; //使棧頂元素出棧DataTypeGetPop; //取出棧頂元素voidClear; //把棧清空boolIsEmpty; //推斷棧是否為空，假設(shè)為空則返回10};//////////////////////////////////////////////////////////////////////*Name: stack.cppAuthor:羅丹Description:用于記錄探究路徑的棧類實(shí)現(xiàn)文件*/#include“stack.h“stack::stack //構(gòu)造函數(shù)，置空棧{top=NULL;}stack::~stack //析構(gòu)函數(shù){}voidstack::Push(DataTypex) //進(jìn)棧{Node*TempNode;TempNode=newNode;TempNode->data=x;TempNode->next=top;top=TempNode;}DataTypestack::Pop //棧頂元素出棧{DataTypeTemp;Node*TempNode=NULL;TempNode=top;top=top->next;Temp=TempNode->data;deleteTempNode;returnTemp;}DataTypestack::GetPop //取出棧頂元素{returntop->data;}voidstack::Clear //把棧清空{(diào)top=NULL;}boolstack::IsEmpty //推斷棧是否為空，假設(shè)為空則返回1，否則返回0{if(top==NULL)returntrue;elsereturnfalse;}//////////////////////////////////////////////////////////////////////*Name: main.cppAuthor:羅丹Description:主函數(shù)文件*/#include“stack.h“#include<iostream>#include<string>#include<fstream>usingnamespacestd;/*Description:外部函數(shù)的聲明局部*/boolfindpath(int**maze,intm,intn); //查找迷宮路徑voidPrintPath(stackp); voidRestore(int**maze,intm,intn); Movemove[4]={{0,1},{1,0},{0,-1},{-1,0}}; //4向(上，右，下，左)int**readFile(int&m,int&n);int**writeFile(int&m,int&n);/*Description:main.cpp*/voidmain{cout<<endl;//cout<<“◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆“<<endl;cout<<“ 2023-2023“<<endl;cout<<endl;cout<<“ “<<endl;cout<<“開(kāi)發(fā)員:羅丹“<<endl;cout<<“專業(yè)班級(jí):計(jì)算機(jī)061班“<<endl;cout<<“◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆“<<endl;cout<<“ 歡送進(jìn)入迷宮玩耍 “<<endl;intm=0,n=0;int**maze;charch;intflag=0,flag1=0;while(flag1==0){while(flag==0)//標(biāo)志是否重選擇{cout<<endl;cout<<“★請(qǐng)從以下選項(xiàng)中選擇獵取迷宮的方法！“<<endl;cout<<“ <a>從文件中讀取“<<endl;cout<<“ <b>直接自行輸入“<<endl;cout<<“★請(qǐng)選擇:“;cin>>ch;if(ch==”a”){maze=readFile(m,n);flag=1;}elseif(ch==”b”){maze=writeFile(m,n);flag=1;}elsecout<<“★Sorry!您輸入的選擇代碼不在范圍內(nèi)!請(qǐng)從選擇“<<endl;}if(findpath(maze,m,n))cout<<“★Congratulations!迷宮路徑探究成功!“<<endl;//得到路徑elsecout<<“★Sorry!路徑不存在★“<<endl;cout<<endl;cout<<“★連續(xù)玩嗎？(y/n)“;charc;cin>>c;if(c==n)flag1=1;elseflag=0;}cout<<“◆◆◆◆◆◆◆感謝,您已經(jīng)退出迷宮系統(tǒng)◆◆◆◆◆◆◆“<<endl;cout<<“◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆“<<endl;}/*Description:獵取迷宮函數(shù)*/int**readFile(int&m,int&n) //讀出文件{int**maze;inti=0,j=0;cout<<“★您選擇的是直接從文件中讀取迷宮!“<<endl;cout<<endl;cout<<“ 文件中的迷宮如下： “<<endl;charch; //定義一個(gè)字符，讀取文件中的內(nèi)容ifstreamopen(“maze.txt“); //定義一個(gè)文件對(duì)象，并翻開(kāi)文件“maze.txt“//讀取內(nèi)容記錄行數(shù)和列數(shù) 〔創(chuàng)點(diǎn)一 ：從文件中直接讀取迷宮〕while(open.get(ch)) //從讀取文件中內(nèi)容〔一旦個(gè)字符形式〕{if(ch==”0”||ch==”1”){j++;} //是‘0’或‘11if(ch==”\n”){i++; //1n=j; //得列數(shù)j=0;}}open.close; //讀取文件完畢m=i;maze=newint*[m+2]; //2指針(為后面的回復(fù)迷宮打下根底)for(i=0;i<m+2;i++) //申請(qǐng)空間{maze[i]=newint[n+2];}i=j=1;ifstreamopen1(“maze.txt“); //重讀取文件，以得到內(nèi)容while(open1.get(ch)){if(ch==”1”||ch==”0”){maze[i][j]=ch-”0”; //把數(shù)字字符轉(zhuǎn)化為數(shù)字，并存到指針里cout<<maze[i][j]<<““;//在屏幕中顯示迷宮j++;}if(ch==”\n”)//遇到換行，指針也相應(yīng)換行{cout<<endl;i++;j=1;}}open1.close;//讀取完畢returnmaze;}int**writeFile(int&m,int&n) //將自定義迷宮寫(xiě)入文件{inta,b;inti,j;int**maze;cout<<“★您選擇的是自行輸入迷宮!“<<endl;cout<<“ 請(qǐng)輸入迷宮的長(zhǎng):“;cin>>b; //輸入迷宮的長(zhǎng)和寬cout<<“ 請(qǐng)輸入迷宮的寬:“;cin>>a;cout<<“★請(qǐng)輸入迷宮內(nèi)容(01):\n“;m=a;n=b; //m,n分別代表迷宮的行數(shù)和列數(shù)maze=newint*[m+2];for(i=0;i<m+2;i++){maze[i]=newint[n+2];} //創(chuàng)點(diǎn)二 ：:隨便申請(qǐng)空間for(i=1;i<=m;i++) //輸入迷宮的內(nèi)容，01for(j=1;j<=n;j++)cin>>maze[i][j];cout<<“★是否保存迷宮？(y/n):“;charchoose;cin>>choose;if(choose==”Y”||choose==”y”){charch;stringstr;cout<<“★請(qǐng)輸入保存迷宮的文件名(以.txtcin>>str;ofstreamopen(str.c_str); //：按玩玩耍人的意愿創(chuàng)立存儲(chǔ)迷宮的文件，也可不建立。for(i=1;i<=m;i++){for(j=1;j<=n;j++){ch=”0”+maze[i][j];open<<ch;}open<<endl;flush(cout);}open.close;}for(i=0;i<m+2;i++)maze[i][0]=maze[i][n+1]=1;for(i=0;i<n+2;i++)maze[0][i]=maze[m+1][i]=1;returnmaze;}/*Description:探究路徑函數(shù)*/boolfindpath(int**maze,intm,intn){stackq,p; //p、q,分別存探究迷宮的過(guò)程和存儲(chǔ)路徑DataTypeTemp1,Temp2;intx,y,loop;Temp1.x=1;Temp1.y=1;q.Push(Temp1); //將入口位置入棧p.Push(Temp1);maze[1][1]=-1; //標(biāo)志入口位置已到達(dá)過(guò)while(!q.IsEmpty) //q{Temp2=q.GetPop;if(!(p.GetPop.x==q.GetPop.x&&p.GetPop.y==q.GetPop.y))p.Push(Temp2);//假設(shè)有位置入棧，則把上一個(gè)探究的位置存入棧pfor(loop=0;loop<4;loop++) //探究當(dāng)前位置的4個(gè)相鄰位置{x=Temp2.x+move[loop].x;y=Temp2.y+move[loop].y;if(maze[x][y]==0) //推斷位置是否可達(dá){Temp1.x=x;Temp1.y=y;maze[x][y]=-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); //〔由于迷宮里面的內(nèi)容已被轉(zhuǎn)變r(jià)eturn1;}} //表示成功找到路徑if(p.GetPop.x==q.GetPop.x&&p.GetPop.y==q.GetPop.y)//假設(shè)沒(méi)有位置入棧，則返回到上一個(gè)位置{p.Pop;q.Pop;}}return0; //表示查