版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、<p> 計算機科學與技術學院</p><p> 課 程 設 計 報 告 </p><p> ?。?2007 ~ 2008 學年度 第 1學期 )</p><p><b> 1.實驗目的及要求</b></p><p> 1)、設計目標(問題描述)</p><p>&
2、lt;b> 迷宮問題</b></p><p> 問題描述:迷宮實驗是取自心理學的一個古典實驗。在該實驗中,把一只老鼠從一個無頂大盒子的門放入,在盒中設置了許多墻,對行進方向形成了多處阻擋。盒子僅有一個出口,在出口處放置一塊奶酪,吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗,一直到老鼠從入口到出口,而不走錯一步。老鼠經(jīng)多次試驗終于得到它學習走迷宮的路線。</p>
3、<p><b> 2)、功能設計要求</b></p><p> 編寫一個程序求解迷宮問題。迷宮由m行n列的二維數(shù)組設置,0表示無障礙,1表示有障礙。設入口為(1,1),出口為(m,n),每次只能從一個無障礙單元移到周圍四個方向上任一無障礙單元。編程實現(xiàn)對任意設定的迷宮,求出一條從入口到出口的通路,或得出沒有通路的結論。</p><p> 算法輸入:
4、代表迷宮入口的坐標</p><p> 算法輸出:穿過迷宮的結果。</p><p> 算法要點:創(chuàng)建迷宮,試探法查找路徑,輸出解</p><p> 3)、實驗目的 1、加深對棧特性理解,以便在解決實際問題中靈活運用它們 2、加深對棧操作實際算法的理解 3、進一步熟悉掌握鏈表的操作; 4、掌握指針的應用 5、更進一步掌握有關
5、類的操作 </p><p> 4)、 需求分析 1、本程序實現(xiàn)迷宮的探索過程. 以用戶和計算機對話的方式,即在計算機終端上顯示“提示信息”之后,由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令,然后
6、程序就探索路徑并輸出路徑。 2、本演示程序中,輸入形式以“回車符”為結束標志,且允許出現(xiàn)重復字符。 3、利用二維指針實現(xiàn)迷宮位置的存儲,并用棧存貯探索路徑,每個結點含三個整形變量。輸入的形式以回車結束。 4、本程序中,用戶可以讀去文件里的迷宮,也可自己重新輸入迷宮,而且用戶可以輸入任意大小的迷宮,然后程序自動探索路徑,并輸出迷宮的路徑 </p><p> 5)、創(chuàng)新(見源程序附錄)
7、</p><p> 6)、軟件、硬件環(huán)境</p><p> 軟件環(huán)境:Microsoft Windows Xp Processional2002 Service</p><p> Microsoft Visual C++6.0 </p><p> 硬件環(huán)境:cpu:AMD Athlon(tm)64x Dual</p>
8、<p> Processor 3800+2.01GHz Main memory:960MB</p><p><b> 2.實驗步驟</b></p><p> a.認真閱讀課本的相關知識章節(jié)。</p><p> b.認真分析課題的需求分析和功能分析。</p><p> c.根據(jù)分析的思路寫出偽代碼。&
9、lt;/p><p> d.根據(jù)偽代碼上機編寫程序,進行初步調(diào)試。</p><p> e.逐步增加完善系統(tǒng)的功能,實現(xiàn)人工智能化。</p><p> f.記錄上機運行時遇到的錯誤,進行認真分析。</p><p> g.最后認真撰寫實驗報告,寫出實驗心得總結。</p><p><b> 3. 實驗內(nèi)容<
10、;/b></p><p><b> 1)、設計概述</b></p><p> (a) 開發(fā)平臺:VC6.0</p><p><b> (b) 參考書籍:</b></p><p> 1.數(shù)據(jù)結構C++描述 熊岳山 陳懷義 編著 國防科技大學出版社</p><p&g
11、t; 2、《數(shù)據(jù)結構與算法》黃定 黃煜廉 編著 廣東科技出版社 2000年1月第1版</p><p> 3、《數(shù)據(jù)結構輔導與提高》徐孝凱 編著 清華大學出版社 2003年12月第1版</p><p> (c) 開發(fā)周期: 10天(構思3天、雛形3天、修改2天、再修改1天、完善1天)</p><
12、p><b> 2)、處理流程</b></p><p> (a)畫出功能結構圖</p><p> (b)畫出主要數(shù)據(jù)結構的類圖</p><p> (c)主要函數(shù)的程序流程圖</p><p><b> 1.</b></p><p> main函數(shù)流程圖:<
13、/p><p> 2.探索路徑函數(shù)findpath()</p><p> 3.自行輸入迷宮函數(shù)writefile()</p><p> (d)寫出數(shù)據(jù)測試表(輸入數(shù)據(jù)/預期結果)</p><p> 測試一:從文件中讀取迷宮: 001000100</p><p><b> 001000101</b&g
14、t;</p><p><b> 000011000</b></p><p><b> 011100100</b></p><p><b> 000100001</b></p><p><b> 010001010</b></p>&l
15、t;p><b> 011110011</b></p><p><b> 110001011</b></p><p><b> 110000000</b></p><p><b> 輸出:</b></p><p> 探索路徑: (1,1,向下
16、) </p><p><b> ?。?,1,向下)</b></p><p><b> (3,1,向下)</b></p><p><b> ?。?,1,向下)</b></p><p><b> ?。?,1,向右)</b></p><p&
17、gt;<b> ?。?,2,向右)</b></p><p><b> ?。?,3,向下)</b></p><p><b> ?。?,3,向右)</b></p><p><b> ?。?,4,向右)</b></p><p><b> ?。?,5,向
18、上)</b></p><p><b> ?。?,5,向右)</b></p><p><b> ?。?,6,向右)</b></p><p><b> (5,7,向下)</b></p><p><b> ?。?,7,向下)</b></p&g
19、t;<p><b> ?。?,7,向下)</b></p><p><b> ?。?,7,向下)</b></p><p><b> ?。?,7,向右)</b></p><p><b> ?。?,8,向右)</b></p><p><b&g
20、t; ?。?,9)</b></p><p><b> 測試二:</b></p><p><b> 自己輸入迷宮:</b></p><p><b> 001</b></p><p><b> 000</b></p><
21、p><b> 100</b></p><p><b> 輸出探索路徑:</b></p><p><b> ?。?,1,向下)</b></p><p><b> ?。?,1,向右)</b></p><p><b> ?。?,2,向下)&l
22、t;/b></p><p><b> (3,2,向右)</b></p><p><b> (3,3)</b></p><p><b> 測試三:</b></p><p><b> 自己輸入迷宮:</b></p><p>
23、;<b> 111</b></p><p><b> 111</b></p><p><b> 000</b></p><p><b> 輸出探索路徑:</b></p><p> Sorry!找不到路徑!</p><p>
24、<b> 4.實驗結果</b></p><p> 結果為以下三種情形之一:</p><p> 1)編譯不通過:給出編譯錯。</p><p> Compiling...</p><p><b> stack.cpp</b></p><p> Skipping...
25、(no relevant changes detected)</p><p><b> main.cpp</b></p><p> Linking...</p><p> stack.obj : error LNK2005: "public: __thiscall stack::stack(void)" (??0sta
26、ck@@QAE@XZ) already defined in main.obj</p><p> stack.obj : error LNK2005: "public: __thiscall stack::~stack(void)" (??1stack@@QAE@XZ) already defined in main.obj</p><p> stack.obj :
27、 error LNK2005: "public: void __thiscall stack::Push(struct DataType)" (?Push@stack@@QAEXUDataType@@@Z) already defined in main.obj</p><p> stack.obj : error LNK2005: "public: struct DataType
28、 __thiscall stack::Pop(void)" (?Pop@stack@@QAE?AUDataType@@XZ) already defined in main.obj</p><p> stack.obj : error LNK2005: "public: struct DataType __thiscall stack::GetPop(void)" (?GetPop
29、@stack@@QAE?AUDataType@@XZ) already defined in main.obj</p><p> stack.obj : error LNK2005: "public: void __thiscall stack::Clear(void)" (?Clear@stack@@QAEXXZ) already defined in main.obj</p>
30、<p> stack.obj : error LNK2005: "public: bool __thiscall stack::IsEmpty(void)" (?IsEmpty@stack@@QAE_NXZ) already defined in main.obj</p><p> Debug/迷宮問題.exe : fatal error LNK1169: one or mo
31、re multiply defined symbols found</p><p> 執(zhí)行 link.exe 時出錯.</p><p> 迷宮問題.exe - 1 error(s), 0 warning(s)</p><p><b> 改正:</b></p><p> 在main。cpp中原來包含的是stack.
32、cpp把它改為包含stack.h即可</p><p><b> 錯誤二:</b></p><p> 用string直接定義字符串str時,說沒有定義str</p><p> 原因:#include<string></p><p> using namespace std ;沒有用標準空間</p&
33、gt;<p><b> 錯誤三:</b></p><p><b> 拼寫錯誤</b></p><p><b> 正確結果輸出:</b></p><p><b> 接上面:</b></p><p><b> 接上面:<
34、/b></p><p><b> 5. 實驗總結分析</b></p><p> 1)、時間和空間分析</p><p> 該算法的運行時間和使用系統(tǒng)棧所占有的存儲空間與迷宮的大小成正比,迷宮長為m,寬為n,在最好情況下的時間和空間復雜度均為O(m+n),在最差情況下均為O(m*n),平均情況在它們之間</p><
35、p><b> 2)、程序的優(yōu)點</b></p><p> 進入演示程序后即顯示文本方式的用戶界面</p><p> 本程序模塊劃分比較合理,且利用指針存儲迷宮,操作方便。</p><p> 能按照玩游戲人的意愿任意輸入迷宮大小,并且可以保存新輸入的迷宮,方便退出游戲后仍可打開自己定義文件查看迷宮。</p><p
36、> 3)、遇到的問題及如何解決</p><p> a.如何知道哪一點被探索過且路徑不通?</p><p> 答:maze【i】【j】本來時表示通與不通,那么可以當探索該點之后,將其值賦為-1,就可以知道此點已經(jīng)被訪問過</p><p> b.如何正確的使用文件讀入迷宮?</p><p> 答:查看大一學的C++課本,仔細閱讀文
37、件那一章。</p><p> c.我想讓用戶在每次玩游戲之后都能查看輸入的迷宮,我想的是運行程序時隨意新建文本文檔,開始是直接輸入一個.txt結尾的字符串,但編譯好多錯誤,我猜應該是要調(diào)用相關函數(shù),但具體是那一個不清楚。 </p><p> 答:去圖書館借閱相關資料,要調(diào)用相應的庫函數(shù)。</p><p> 4)、存在的缺陷、改進設想</p>&l
38、t;p> 每當自行輸入迷宮后,生成相應的文件保存,但是我在想:一旦玩游戲的人多了,玩的次數(shù)多了,那么生成的保存迷宮文件就會很多,會給人工智能化系統(tǒng)造成文件冗余。我設想:能不能在一段時間之后系統(tǒng)自動調(diào)用函數(shù)來清除冗余文件。</p><p> 5)、自我評價、經(jīng)驗體會等</p><p> 通過這次課程設計,體會如下:1、進一步熟悉掌握了有關棧的基本操作;2、對迷宮有了更多的認識
39、3、更進一步掌握有關類的操作4、由于對棧的算法推敲不足,使程序調(diào)試時費時不少</p><p> 總之:我認為這次課程設計做的很好。課程設計的成功使我相信一句話:有付出就會有收獲,要相信自己。</p><p> 6. 附錄(源程序清單,要求含有至少30%的源碼附有注釋)</p><p> 迷宮程序代碼(本程序有個創(chuàng)新點)</p><p&g
40、t; /////////////////////////////////////////////////////////////////////</p><p><b> /*</b></p><p> Name: stack.h </p><p> Author: 羅丹 </p><p> Descri
41、ption: 用于記錄探索路徑的棧類頭文件 </p><p><b> */</b></p><p> #include<iostream></p><p> #include"fstream"</p><p> using namespace std;</p>
42、<p> class DataType //定義描述迷宮中當前位置的類型</p><p><b> {public:</b></p><p> int x; //x代表當前位置的行坐標</p><p> int y; //y代表當前位置的列坐標&
43、lt;/p><p> int pre; //pre表示移動到下一步的方向</p><p> }; </p><p> class Move //定義下一個位置的方向</p><p><b> { public:</b></p>&l
44、t;p><b> int x; </b></p><p><b> int y;</b></p><p><b> };</b></p><p> class Node //鏈表結點</p><p><b> {publi
45、c:</b></p><p> DataType data;</p><p> Node *next;</p><p><b> };</b></p><p><b> //下面定義棧</b></p><p> class stack</p>
46、<p><b> {private:</b></p><p> Node *top; //指向第一個結點的棧頂指針</p><p><b> public:</b></p><p> stack(); //構造函數(shù),置空棧</p>
47、<p> ~stack(); //析構函數(shù)</p><p> void Push(DataType data);//把元素data壓入棧中</p><p> DataType Pop(); //使棧頂元素出棧</p><p> DataType GetPop(); //取出棧頂元素&l
48、t;/p><p> void Clear(); //把棧清空</p><p> bool IsEmpty(); //判斷棧是否為空,如果為空則返回1,否則返回0</p><p><b> };</b></p><p> /////////////////////////////
49、////////////////////////////////////////</p><p><b> /*</b></p><p> Name: stack.cpp </p><p> Author: 羅丹 </p><p> Description: 用于記錄探索路徑的棧類實現(xiàn)文件 </p&
50、gt;<p><b> */</b></p><p> #include"stack.h"</p><p> stack::stack() //構造函數(shù),置空棧</p><p> {top=NULL;}</p><p> stack::
51、~stack() //析構函數(shù)</p><p><b> {}</b></p><p> void stack::Push(DataType x) //進棧</p><p> {Node *TempNode;</p><p> TempNode=new Nod
52、e;</p><p> TempNode->data=x;</p><p> TempNode->next=top;</p><p> top=TempNode;}</p><p> DataType stack::Pop() //棧頂元素出棧</p><p><b
53、> {</b></p><p> DataType Temp;</p><p> Node *TempNode=NULL;</p><p> TempNode=top;</p><p> top=top->next;</p><p> Temp=TempNode->data;&
54、lt;/p><p> delete TempNode;</p><p> return Temp;</p><p><b> }</b></p><p> DataType stack::GetPop() //取出棧頂元素</p><p> {return top-&
55、gt;data;}</p><p> void stack::Clear() //把棧清空</p><p> {top=NULL;}</p><p> bool stack::IsEmpty() //判斷棧是否為空,如果為空則返回1,否則返回0</p><p> {if(t
56、op==NULL) return true;</p><p> else return false;}</p><p> /////////////////////////////////////////////////////////////////////</p><p><b> /*</b></p><p>
57、; Name: main.cpp </p><p> Author: 羅丹 </p><p> Description: 主函數(shù)文件 </p><p><b> */</b></p><p> #include"stack.h"</p><p> #inc
58、lude<iostream></p><p> #include<string></p><p> #include<fstream></p><p> using namespace std ;</p><p><b> /*</b></p><p>
59、 Description: 外部函數(shù)的聲明部分</p><p><b> */</b></p><p> bool findpath(int **maze,int m,int n); //尋找迷宮路徑 </p><p> void PrintPath(stack p);
60、 //輸出路徑</p><p> void Restore(int **maze,int m,int n); //恢復迷宮</p><p> Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; //定義當前位置移動的4個方向(上,右,下,左)</p><p&g
61、t; int** readFile (int &m,int &n);</p><p> int** writeFile(int &m,int &n);</p><p><b> /*</b></p><p> Description: main.cpp</p><p><b
62、> */</b></p><p> void main()</p><p><b> { </b></p><p> cout<<endl;//</p><p> cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<&
63、lt;endl;</p><p> cout<<" 2007-2008年度第一學期數(shù)據(jù)結構課程之課程設計 "<<endl;</p><p> cout<<endl;</p><p> cout<<"
64、 ——迷宮問題 "<<endl; </p><p> cout<<" 開發(fā)員 : 羅丹"<<endl;</p><p> cout<<" 專業(yè)班級: 計算機061班"<<endl;</p><p>
65、 cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;</p><p> cout<<" 歡迎進入迷宮游戲 "<<endl;</p><p> int m=0,n=0; </p>
66、<p> int **maze; </p><p><b> char ch;</b></p><p> int flag=0,flag1=0; </p><p> while(flag1==0)</p><p><b> {</b></p><p>
67、 while(flag==0)//標志是否重新選擇</p><p> {cout<<endl;</p><p> cout<<" ★請從以下選項中選擇獲取迷宮的方法!"<<endl;</p><p> cout<<" <a>從文件中讀取"<
68、;<endl;</p><p> cout<<" <b>直接自行輸入"<<endl;</p><p> cout<<" ★請選擇:";</p><p><b> cin>>ch;</b></p><
69、p> if(ch=='a'){maze=readFile(m,n);flag=1;}</p><p> else if(ch=='b'){maze=writeFile(m,n);flag=1;}</p><p><b> else </b></p><p> cout<<"
70、★ Sorry!您輸入的選擇代碼不在范圍內(nèi)!請從新選擇"<<endl;</p><p><b> }</b></p><p> if(findpath(maze,m,n)) </p><p> cout<<" ★ Congratulations! 迷宮路徑探索成功!"<<
71、;endl; //得到路徑</p><p><b> else </b></p><p> cout<<" ★Sorry! 路徑不存在★"<<endl;</p><p> cout<<endl;</p><p> cout<<" ★
72、 繼續(xù)玩嗎?(y/n)"; </p><p><b> char c;</b></p><p><b> cin>>c;</b></p><p> if(c==n) flag1=1;</p><p> else flag=0;</p><p>
73、<b> }</b></p><p> cout<<"◆◆◆◆◆◆◆ 謝謝,您已經(jīng)退出迷宮系統(tǒng) ◆◆◆◆◆◆◆"<<endl;</p><p> cout<<"◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆"<<endl;</p><p>&
74、lt;b> }</b></p><p><b> /*</b></p><p> Description: 獲取迷宮函數(shù)</p><p><b> */</b></p><p> int** readFile (int &m,int &n)
75、 //讀出文件</p><p> {int **maze; </p><p> int i=0,j=0;</p><p> cout<<" ★您選擇的是直接從文件中讀取迷宮!"<<endl;</p><p> cout<<en
76、dl;</p><p> cout<<" 文件中的迷宮如下: "<<endl;</p><p> char ch; //定義一個字符,讀取文件中的內(nèi)容</p><p> ifstream open("maze.txt");
77、 //定義一個文件對象,并打開文件"maze.txt"</p><p> //讀取內(nèi)容記錄行數(shù)和列數(shù) (創(chuàng)新點一:從文件中直接讀取迷宮)</p><p> while(open.get(ch)) //從讀取文件中內(nèi)容(一旦個字符形式)</p><p> {if(ch=='0'
78、;||ch=='1') </p><p> {j++; } //是‘0’或‘1’字符寬就加1</p><p> if(ch=='\n') </p><p><b> {</b></p><p> i++
79、; //如果是換行符,就行加1</p><p> n=j; //得列數(shù)</p><p><b> j=0; </b></p><p><b> }</b
80、></p><p><b> }</b></p><p> open.close(); //讀取文件結束</p><p> m=i; </p><p> maze=new int *[m+2];
81、 //申請長度等于行數(shù)加2的二維指針(為后面的回復迷宮打下基礎)</p><p> for(i= 0;i<m+2;i++) //申請空間</p><p> {maze[i]=new int[n+2];}</p><p><b> i=j=1;</
82、b></p><p> ifstream open1("maze.txt"); //重新讀取文件,以得到內(nèi)容</p><p> while(open1.get(ch))</p><p><b> {</b></p><p> if(ch==
83、9;1'||ch=='0')</p><p> {maze[i][j]=ch-'0'; //把數(shù)字字符轉化為數(shù)字,并存到指針里</p><p> cout<<maze[i][j]<<" "; //在屏
84、幕中顯示迷宮</p><p><b> j++;}</b></p><p> if(ch=='\n') //遇到換行,指針也相應換行</p><p> {cout<<endl;</p><p><b> i
85、++;</b></p><p><b> j=1;}</b></p><p><b> }</b></p><p> open1.close(); //讀取結束</p><p> return maze; <
86、/p><p><b> }</b></p><p> int** writeFile (int &m,int &n) //將自定義迷宮寫入文件</p><p> {int a,b; </p><p><b> int i,j;</b><
87、;/p><p> int**maze;</p><p> cout<<" ★您選擇的是自行輸入迷宮!"<<endl;</p><p> cout<<" 請輸入迷宮的長:";cin>>b; //輸入迷宮的長和寬</p><p> cout
88、<<" 請輸入迷宮的寬:";cin>>a; </p><p> cout<<" ★請輸入迷宮內(nèi)容(0代表可通,1代表不通):\n";</p><p><b> m=a;</b></p><p> n=b;
89、 //m,n分別代表迷宮的行數(shù)和列數(shù)</p><p> maze=new int *[m+2]; </p><p> for(i= 0;i<m+2;i++) </p><p> {maze[i]=new int[n+2];} //創(chuàng)新點二::隨意申請空間</p><p> for
90、(i=1;i<=m;i++) //輸入迷宮的內(nèi)容,0代表可通,1代表不通</p><p> for(j=1;j<=n;j++)</p><p> cin>>maze[i][j];</p><p> cout<<" ★是否保存新迷宮?(y/n): ";</p&g
91、t;<p> char choose;</p><p> cin>>choose;</p><p> if(choose=='Y'||choose=='y')</p><p><b> {char ch;</b></p><p> string str;
92、</p><p> cout<<" ★請輸入保存迷宮的文件名(以.txt結束):";</p><p> cin>>str; </p><p> ofstream open(str.c_str()); //創(chuàng)新點三:按玩游戲人的意愿創(chuàng)建存儲迷宮的文件,也可不建立。</p><
93、p> for(i=1;i<=m;i++)</p><p> {for(j=1;j<=n;j++)</p><p> {ch='0'+maze[i][j];</p><p> open<<ch;}</p><p> open<<endl;</p><p>
94、; flush(cout);}</p><p> open.close();}</p><p> for(i=0;i<m+2;i++) </p><p> maze[i][0]=maze[i][n+1]=1;</p><p> for(i=0;i<n+2;i++)</p><
95、p> maze[0][i]=maze[m+1][i]=1;</p><p> return maze;</p><p><b> } </b></p><p><b> /*</b></p><p> Description: 探索路徑函數(shù)</p><p>
96、<b> */</b></p><p> bool findpath(int **maze,int m,int n)</p><p> {stack q,p; //創(chuàng)新點四:用棧p、q,分別存探索迷宮的過程和存儲路徑</p><p> DataType Temp1,Temp2;
97、</p><p> int x,y,loop;</p><p> Temp1.x=1;</p><p> Temp1.y=1;</p><p> q.Push(Temp1); //將入口位置入棧</p><p> p.Push(Temp1);
98、</p><p> maze[1][1]=-1; //創(chuàng)新點五:標志入口位置已到達過</p><p> while(!q.IsEmpty()) //棧q非空,則反復探索</p><p> {Temp2=q.GetPop(); </p>
99、;<p> if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)) </p><p> p.Push(Temp2); </p><p> //如果有新位置入棧,則把上一個探索的位置存入棧p</p><p> for(loop=0;loop<
100、4;loop++) //探索當前位置的4個相鄰位置</p><p> {x=Temp2.x+move[loop].x; </p><p> y=Temp2.y+move[loop].y; </p><p> if(maze[x][y]==0) //判
101、斷新位置是否可達</p><p> {Temp1.x=x;</p><p> Temp1.y=y;</p><p> maze[x][y]=-1; //標志新位置已到達過</p><p> q.Push(Temp1); }
102、//新位置入棧</p><p> if((x==(m))&&(y==(n))) //成功到達出口</p><p> {Temp1.x=m;</p><p> Temp1.y=n;</p><p> Temp1.pre=0;</p><p> p.Pu
103、sh(Temp1); //把最后一個位置入棧</p><p> PrintPath(p); </p><p> Restore(maze,m,n); //恢復路徑(因為迷宮里面的內(nèi)容已被改變</p><p> return 1; }}
104、 //表示成功找到路徑 </p><p> if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)//如果沒有新位置入棧,則返回到上一個位置 </p><p><b> {p.Pop();</b></p>
105、<p> q.Pop();}}</p><p> return 0; //表示查找失敗,即迷宮無路經(jīng)</p><p><b> }</b></p><p><b> /*</b></p><p> Descr
106、iption: 輸出路徑函數(shù)</p><p><b> */</b></p><p> void PrintPath(stack p) //輸出路徑</p><p> {cout<<endl;</p><p> cout<<" ★
107、★迷宮的路徑為"<<endl;</p><p> cout<<" 說明:括號內(nèi)的內(nèi)容分別表示為(行坐標,列坐標,方向)\n";</p><p> stack t; //定義一個棧,按從入口到出口存取路徑</p><p> int ro
108、w,column;</p><p> DataType data;</p><p> Node *temp;</p><p> temp=new Node; //申請空間</p><p> temp->data=p.Pop(); </p>&
109、lt;p> t.Push(temp->data); //第一個位置入棧</p><p> delete temp; </p><p> while(!p.IsEmpty()) //棧p非空,則轉移</p><p> {temp=ne
110、w Node;</p><p> temp->data=p.Pop(); //獲取下一個位置</p><p><b> //得到行走方向</b></p><p> row=t.GetPop().x-temp->data.x; //行坐標方向</p
111、><p> column=t.GetPop().y-temp->data.y; //列坐標方向</p><p> if(row==1) temp->data.pre=1; //向下,用1表示</p><p> else if(column==1) temp->data.pre=2;
112、//向右,用2表示</p><p> else if(row==-1) temp->data.pre=3; //向上,用3表示</p><p> else if(column==-1) temp->data.pre=4; //向左,用4表示</p><p> t.Push(temp->data);
113、 //把新位置入棧</p><p> delete temp;</p><p><b> }</b></p><p> while(!t.IsEmpty()) //棧非空,繼續(xù)輸出</p><p> {data=t.Pop();&l
114、t;/p><p> cout<<" "<<'('<<data.x<<','<<data.y<<","; </p><p> switch(data.pre) //輸出相應的方向
115、 </p><p> {case 0:cout<<")\n";break;</p><p> case 1:cout<<"向下)\n";break;</p><p> case 2:cout<<"向右)\n";break;</p><p>
116、 case 3:cout<<"向上)\n";break;</p><p> case 4:cout<<"向左)\n";break;</p><p><b> }}}</b></p><p><b> /*</b></p><p>
117、 Description: 恢復路徑函數(shù)</p><p><b> */</b></p><p> void Restore(int **maze,int m,int n) //恢復迷宮</p><p><b> {int i,j;</b></p><p> for(i=0;
118、i<m+2;i++) //遍歷指針</p><p> for(j=0;j<n+2;j++) </p><p> {if(maze[i][j]==-1) //恢復探索過位置,即把-1恢復為0</p><p> maze[i][j]=0;}</p><p><b>
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 迷宮問題課程設計報告
- 迷宮問題課程設計報告
- 迷宮問題課程設計報告
- 迷宮問題課程設計報告
- 數(shù)據(jù)結構課程設計迷宮問題課程設計報告
- 迷宮課程設計報告
- 迷宮課程設計報告
- 迷宮問題——數(shù)據(jù)結構課程設計迷宮問題
- 數(shù)據(jù)結構課程設計報告---迷宮問題
- 數(shù)據(jù)結構課程設計報告----迷宮問題
- c語言課程設計--迷宮問題
- 課程設計(迷宮)
- 數(shù)據(jù)結構課程設計(迷宮問題)
- 數(shù)據(jù)結構課程設計迷宮問題
- 數(shù)據(jù)結構課程設計--迷宮問題
- 數(shù)據(jù)結構課程設計—迷宮問題
- 數(shù)據(jù)結構課程設計---迷宮問題
- 數(shù)據(jù)結構課程設計---迷宮問題
- 數(shù)據(jù)結構課程設計-迷宮問題
- 數(shù)據(jù)結構迷宮問題課程設計
評論
0/150
提交評論