數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----迷宮求解

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　目 錄</b></p><p><b>　　摘 要3</b></p><p>　　Abstract3</p><p><b>　　一、引 言1</b><

2、;/p><p>　　二、設(shè)計(jì)目的與任務(wù)1</p><p><b>　　1、設(shè)計(jì)目的是1</b></p><p><b>　　2、設(shè)計(jì)任務(wù)是2</b></p><p>　　三、設(shè)計(jì)方案與實(shí)施2</p><p>　　1、總體設(shè)計(jì)思想2</p><p>

3、;<b>　　2、設(shè)計(jì)流程圖3</b></p><p><b>　　3、詳細(xì)設(shè)計(jì)4</b></p><p><b>　　4、程序清單4</b></p><p>　　5、程序調(diào)試與體會(huì)4</p><p>　　6、運(yùn)行結(jié)果（截圖）5</p><p>

4、;<b>　　五、致 謝13</b></p><p><b>　　參考文獻(xiàn)14</b></p><p><b>　　附件14</b></p><p><b>　　摘 要</b></p><p>　　隨著計(jì)算機(jī)的高速發(fā)展，計(jì)算機(jī)能很簡(jiǎn)便地解決很多

5、問(wèn)題。C語(yǔ)言編程也是解決問(wèn)題的一種語(yǔ)言。而此我們的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)是解決迷宮問(wèn)題。求迷宮(老鼠吃奶酪)中從入口到出口的路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問(wèn)題?！皵?shù)據(jù)結(jié)構(gòu)”成為計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)學(xué)科的核心課程，而且已成為其它理工專(zhuān)業(yè)的熱門(mén)選修課。主要包括線(xiàn)性表、樹(shù)和二叉樹(shù)以及圖等基本類(lèi)型的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存

6、儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算這三個(gè)方面的內(nèi)容，其中邏輯結(jié)構(gòu)可分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)；存儲(chǔ)結(jié)構(gòu)可分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩類(lèi)，圖則屬于邏輯結(jié)構(gòu)中的非線(xiàn)性結(jié)構(gòu)。廣度優(yōu)先搜索(BFS)用的隊(duì)列一步一步完成的，從而找到的是最短路徑。</p><p>　　關(guān)鍵詞：隊(duì)列，廣度優(yōu)先，搜索，最短路徑，遍歷</p><p><b>　　Abstract</b></p><p&

7、gt;　　With the rapid development of the computer,the computer can very easily solve many problems. C programming language is a language problem. Our data structure and this program is designed to solve maze problems.Find

8、the maze(Mouse eat cheese) to the exit path from the entrance is a classic programming problem."data structure" has become the important theory and the foundation of computer programming.It is not only the core

9、 curriculum of computer science,but also has became the hottest elective co</p><p>　　Key words: Queue，Breadth-first ，search，Shortest path，Traversal</p><p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p>　　----

10、迷宮求解設(shè)計(jì)</p><p><b>　　一、引 言</b></p><p>　　《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)和信息管理與信息系統(tǒng)專(zhuān)業(yè)的必修課之一，是一門(mén)綜合性的專(zhuān)業(yè)基礎(chǔ)課。本課程較系統(tǒng)地介紹了軟件設(shè)計(jì)中常用的數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的實(shí)現(xiàn)算法，如線(xiàn)性表、棧、隊(duì)列、樹(shù)和二叉樹(shù)，圖、檢索和排序等，并對(duì)性能進(jìn)行分析和比較，內(nèi)容非常豐富。</p><p&

11、gt;　　本課程設(shè)計(jì)我們要解決的問(wèn)題是圖迷宮求解問(wèn)題。本需要用到棧的相關(guān)數(shù)據(jù)結(jié)構(gòu)。但我們這個(gè)程序沒(méi)有用棧，而是用隊(duì)列替代棧的功能，使程序運(yùn)行效率更加高。還用到求迷宮問(wèn)題最平常的數(shù)據(jù)結(jié)構(gòu)算法，即廣度優(yōu)先搜索算法(BFS)，還保持了它的路徑，再?gòu)拇休敵鰣D。</p><p>　　本課程設(shè)計(jì)總的思路要解決的問(wèn)題是構(gòu)造迷宮，尋找路線(xiàn)，打印路徑。我們首先要做的是創(chuàng)建一個(gè)二維數(shù)組，用以來(lái)存儲(chǔ)圖，然后我們要想好怎樣利用BFS算

12、法來(lái)尋找路線(xiàn)。把這個(gè)算法以及其他過(guò)程寫(xiě)成調(diào)用函數(shù)，各自調(diào)用后調(diào)試程序。達(dá)到滿(mǎn)意結(jié)果后寫(xiě)報(bào)告。</p><p><b>　　二、設(shè)計(jì)目的與任務(wù)</b></p><p><b>　　1、設(shè)計(jì)目的是</b></p><p>　　根據(jù)課堂講授內(nèi)容，學(xué)生做相應(yīng)的自主練習(xí)，消化數(shù)據(jù)結(jié)構(gòu)課堂所講解的內(nèi)容；通過(guò)調(diào)試典型例題或習(xí)題積累調(diào)試C

13、程序的經(jīng)驗(yàn)；通過(guò)完成輔導(dǎo)教材中的編程題，逐漸培養(yǎng)學(xué)生的編程能力、用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力、團(tuán)體合作能力。</p><p><b>　　2、設(shè)計(jì)任務(wù)是</b></p><p>　　它的任務(wù)就是訓(xùn)練學(xué)生對(duì)計(jì)算機(jī)數(shù)據(jù)對(duì)象進(jìn)行分析的能力，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)及相關(guān)算法的能力。 此程序的任務(wù)是實(shí)現(xiàn)把能走的最短路找到，并很直觀的顯示在屏幕上的功能。</p><

14、p><b>　　三、設(shè)計(jì)方案與實(shí)施</b></p><p><b>　　1、總體設(shè)計(jì)思想</b></p><p>　　(1) 迷宮形狀由0表示可通過(guò)，用1表示是障礙。為方便用0,1輸入。并把迷宮圖形保存在二維數(shù)組Map中。而打印出的圖形中 ‘●’表示能過(guò)‘□’表示障礙.</p><p>　　(2) 對(duì)探索過(guò)的位置加以

15、標(biāo)記Used[][]，輸入起點(diǎn)終點(diǎn)后可由BFS（）來(lái)完成搜索。到目的點(diǎn)就可退出該調(diào)用程序。把每步路徑保存到Mark[][]內(nèi)，通過(guò)反向進(jìn)行退步可把完整的路徑保存在結(jié)構(gòu)體result數(shù)組re[][]內(nèi)，通過(guò)標(biāo)記的路徑可將串str作相應(yīng)的改變就能輸出的帶路徑的圖。</p><p>　　(3) 根據(jù)二維字符數(shù)組和加標(biāo)記的位置坐標(biāo)，輸出迷宮的圖形。</p><p>　　(4) 該程序在獲取迷宮圖結(jié)

16、構(gòu)后，可對(duì)迷宮任意入口到出口的路線(xiàn)進(jìn)行搜索，主要由廣度優(yōu)先搜索完成該操作。它可以是100以?xún)?nèi)大小的迷宮，有自行提供的迷宮圖，本課程設(shè)計(jì)是以二維數(shù)組作為迷宮的存儲(chǔ)結(jié)構(gòu)。而廣度優(yōu)先搜索(BFS)用的隊(duì)列一步一步完成的，從而找到的是最短路徑；該程序還能選擇是4方向還是8方向的迷宮走法。并能輸出打印</p><p><b>　　2、設(shè)計(jì)流程圖</b></p><p><

17、b>　　3、詳細(xì)設(shè)計(jì)</b></p><p>　　struct Point</p><p>　　{int x,y,s;}</p><p>　　這個(gè)結(jié)構(gòu)體是用來(lái)做廣度搜索的對(duì)每個(gè)迷宮節(jié)點(diǎn)有相應(yīng)的s(最短的步數(shù)，當(dāng)然有些是不可達(dá)的)</p><p>　　int move[8][2] = {{1,0},{0,1},{-1,0},{

18、0,-1},{1,1},{-1,-1},{1,-1},{-1,1}} ;//</p><p>　　int BFS(int step)// 廣度搜索用來(lái)算出最短路徑的走法 并將走法保存在re數(shù)組結(jié)構(gòu)體中</p><p>　　int Initialization()// 將str[][]圖形初始化</p><p>　　int Format_Limit()//圖形打印格

19、式限制</p><p>　　int Print_Maze_Figure()//打印出圖形</p><p>　　int PPMF()// 打印出迷宮圖形</p><p>　　int Save_Path()// 將路徑保存在str[][]中并打印出路徑迷宮圖形</p><p>　　int Init()// 從文件中植入數(shù)據(jù) 完成對(duì)Map迷宮圖的結(jié)

20、構(gòu)</p><p>　　int Judge()//判斷輸入的起點(diǎn)終點(diǎn)是否符合實(shí)際</p><p>　　int main()//對(duì)上面函數(shù)的結(jié)合應(yīng)用</p><p><b>　　4、程序清單</b></p><p><b>　　見(jiàn)附件</b></p><p><b>

21、　　5、程序調(diào)試與體會(huì)</b></p><p>　　調(diào)試：在我組的集體努力下，課程設(shè)計(jì)終于完成，由于我們對(duì)數(shù)據(jù)結(jié)構(gòu)和c語(yǔ)言不是很了解，有時(shí)忽略了一些關(guān)鍵的細(xì)節(jié)，使得在編寫(xiě)程序的過(guò)程中出現(xiàn)了一些問(wèn)題。對(duì)于打字有時(shí)粗心導(dǎo)致出現(xiàn)一些難以發(fā)現(xiàn)的小錯(cuò)誤，在我們的耐心，細(xì)致的調(diào)試下最終使得程序能夠運(yùn)行，課程設(shè)計(jì)完滿(mǎn)完工。</p><p>　　1、問(wèn)題一：求出起點(diǎn)到終點(diǎn)的路徑 </p&

22、gt;<p>　　現(xiàn)象：求出的結(jié)果總是無(wú)任何現(xiàn)象</p><p>　　原因：把相關(guān)重要的變量重復(fù)定義以至賦過(guò)的值被覆蓋</p><p>　　問(wèn)題二：常量轉(zhuǎn)義字符</p><p>　　現(xiàn)象：出現(xiàn)不正常字符常量</p><p>　　原因：'\'字符常量形式弄錯(cuò)</p><p>　　3、問(wèn)題三：

23、輸入起點(diǎn)終點(diǎn)時(shí)，未判斷下標(biāo)越界就使用數(shù)據(jù)</p><p><b>　　現(xiàn)象：</b></p><p>　　原因：未判斷下標(biāo)越界就使用數(shù)據(jù)</p><p>　　體會(huì)：在復(fù)雜的程序，都可以拆成一個(gè)個(gè)簡(jiǎn)單的小部分，逐個(gè)擊破，再拼湊起來(lái)，在復(fù)雜的事也變的簡(jiǎn)單了。由于本程序較大，調(diào)試時(shí)多人協(xié)作能更容易找出程序的錯(cuò)誤并修改。</p><

24、p>　　6、運(yùn)行結(jié)果（截圖）</p><p>　　將程序員錄入后,讓其運(yùn)行。將會(huì)出現(xiàn)一個(gè)菜單的界面，執(zhí)行各種操作均有其對(duì)應(yīng)的代碼。要執(zhí)行何種操作只需輸入對(duì)應(yīng)的指令即可進(jìn)行，在每步操作后均會(huì)有相應(yīng)的提示。操作簡(jiǎn)單方便實(shí)用，下面即為一些操作的示意圖。</p><p>　　運(yùn)行程序后出界面，運(yùn)行結(jié)果如圖所示。</p><p><b>　　四、結(jié) 論<

25、;/b></p><p>　　經(jīng)過(guò)我們不懈的努力我們終于完成了本次課程設(shè)計(jì)，通過(guò)這次課程設(shè)計(jì)，我感覺(jué)到要真正做出一個(gè)程序并不很容易，但只要用心去做，總會(huì)有收獲，特別是當(dāng)我遇到 一個(gè)問(wèn)題，想辦法去解決，最后終于找到方法時(shí)，心里的那份喜悅之情真是難以形容。編寫(xiě)程序中遇到問(wèn)題再所難免，應(yīng)耐心探究其中的原因，從出現(xiàn)問(wèn)題的地方起，并聯(lián)系前后程序，仔細(xì)推敲，逐個(gè)排查。直到最終搞清為止。我們本次做的是迷宮求解問(wèn)題，深刻的

26、體會(huì)到它的游戲可玩性。通過(guò)本次課程設(shè)計(jì)我們發(fā)現(xiàn)我們對(duì)于C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu)還有很多地方不了解，今后繼續(xù)努力學(xué)習(xí)。</p><p><b>　　五、致 謝</b></p><p>　　在這里我真心的感謝xx老師對(duì)我們精心的指導(dǎo)和不倦的教育,她在我們的課程設(shè)計(jì)過(guò)程中提出了指導(dǎo)性的方案和架構(gòu),時(shí)事關(guān)注我們?cè)O(shè)計(jì)的進(jìn)程，并指引我們閱讀相關(guān)的資料和書(shū)籍，使我們的課設(shè)能夠按時(shí)順利的完

27、成。還有周?chē)?guó)柱同學(xué)全面承擔(dān)本次課程設(shè)計(jì)的程序編寫(xiě)工作,并為此付出大量的時(shí)間和精力。在這里我代表我們組全體同學(xué)對(duì)他表示感謝,同時(shí)也有組員的積極配合與協(xié)作。</p><p>　　同時(shí)也感謝學(xué)校給我們這次機(jī)會(huì)，訓(xùn)練我們靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析的能力，讓我們學(xué)會(huì)怎樣結(jié)合數(shù)據(jù)結(jié)構(gòu)理論知識(shí)去解決實(shí)際問(wèn)題。</p><p><b>　　參考文獻(xiàn)</b></p

28、><p>　　[1]數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M],嚴(yán)蔚敏等編著.清華大學(xué)出版社,2004,</p><p>　　[2]數(shù)據(jù)結(jié)構(gòu)－用面向?qū)ο蠓椒ㄅcC++描述，殷人昆，陶水雷，謝若陽(yáng)，盛絢華，清華大學(xué)出版社</p><p>　　[3]任意N重循環(huán)的設(shè)計(jì)方法與應(yīng)用[J]--《計(jì)算機(jī)工程》，肖建華,歐陽(yáng)浩,何宏，2004年22期 </p><p>　　[4

29、]用人工智能中的搜索原理解決迷宮問(wèn)題--《微計(jì)算機(jī)信息》，陳春梅，楊世恩，2006年11期</p><p><b>　　附件</b></p><p>　　#include <stdlib.h></p><p>　　#include <iostream></p><p>　　#include <

30、;string></p><p>　　#include <queue>// 這個(gè)是stl 它是一個(gè)方便的東西 </p><p>　　#include <fstream></p><p>　　#include <conio.h></p><p>　　using namespace std;</p&

31、gt;<p>　　struct result</p><p><b>　　{</b></p><p>　　int rx,ry;</p><p>　　}re[100*100];</p><p>　　int ri=-1;</p><p>　　struct Point</p>

32、<p><b>　　{</b></p><p>　　int x,y,s;</p><p>　　}s,t;//s代表起點(diǎn) t代表終點(diǎn)</p><p>　　int mark[100][100]; //用來(lái)標(biāo)記怎么走到這個(gè)地方的 (保存的是方向的序號(hào)):0,1,2,3,4,5,6,7</p><p>　　bool

33、Used[100][100];//標(biāo)記已經(jīng)走過(guò)的地方</p><p>　　bool Map[100][100];//輸入0，1表示迷宮</p><p>　　int move[8][2] = {{1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1}} ;//</p><p><b>　　int n,m;&l

34、t;/b></p><p>　　int BFS(int step) // 廣度搜索用來(lái)算出最短路徑的走法 并將走法保存在re結(jié)構(gòu)體中</p><p><b>　　{</b></p><p>　　queue<Point> My;</p><p><b>　　s.s =0;</b>&

35、lt;/p><p>　　while(!My.empty())My.pop();</p><p>　　My.push(s);</p><p>　　Point temp,s1;</p><p>　　while(!My.empty())</p><p><b>　　{</b></p><

36、p>　　s1 = My.front();</p><p><b>　　My.pop();</b></p><p>　　if(s1.x == t.x&&s1.y==t.y)</p><p><b>　　{</b></p><p><b>　　int u;</b&g

37、t;</p><p>　　re[++ri].rx=s1.x;</p><p>　　re[ri].ry=s1.y;</p><p>　　printf("到目的地了\n步數(shù):%d\n(%2d,%2d) <- ",s1.s,s1.x,s1.y);</p><p>　　for(int j = 1 ;j <= s1.s

38、;j++)</p><p><b>　　{</b></p><p><b>　　u = s1.x;</b></p><p>　　s1.x = s1.x - move[ mark[s1.x][s1.y]][0];</p><p>　　s1.y = s1.y - move[ mark[u][s1.y]

39、 ][1];</p><p>　　re[++ri].rx=s1.x;</p><p>　　re[ri].ry=s1.y;</p><p>　　printf("(%2d,%2d) <- ",s1.x,s1.y);</p><p>　　if((j+1)%5==0)printf("\n");<

40、/p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　system("pause");</p><p>　　system("cls");</p><p><b>　　return

41、1;</b></p><p><b>　　}</b></p><p>　　for(int i =0 ;i < step ; i++)</p><p><b>　　{</b></p><p>　　temp.x = s1.x + move[i][0];</p><p

42、>　　temp.y = s1.y + move[i][1];</p><p>　　temp.s = s1.s;</p><p>　　if(temp.x<0||temp.x>=n||temp.y<0||temp.y>=n||Used[temp.x][temp.y]||Map[temp.x][temp.y])</p><p><b&g

43、t;　　continue;</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　mark[temp.x][temp.y] = i;</p><p>　　temp.s += 1 ;</p><p>　　M

44、y.push(temp);</p><p>　　Used[temp.x][temp.y] = true;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　prin

45、tf("不好意思,起點(diǎn)至終點(diǎn)無(wú)路徑不可達(dá)!!!!\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　char str[256*256][3]; //串保存圖</p><p>　　int Initiali

46、zation()// 將str[][]圖形初始化</p><p><b>　　{</b></p><p>　　int i1,j1,xj;</p><p>　　for(i1=0;i1<256*256;i1++)</p><p>　　strcpy(str[i1]," ");</p>

47、<p>　　for(i1=0;i1<n;i1++)</p><p><b>　　{</b></p><p>　　for(j1=0,xj=0;xj<n;j1=j1+2,xj++)</p><p><b>　　{</b></p><p>　　if(Map[i1][xj] == 0)

48、</p><p>　　strcpy(str[2*i1*(2*n-1)+j1],"●");</p><p><b>　　else</b></p><p>　　strcpy(str[2*i1*(2*n-1)+j1],"□");</p><p><b>　　}</b>

49、;</p><p><b>　　}</b></p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int Format_Limit()//圖形打印格式限制</p><p><b>　

50、　{</b></p><p>　　for(int i =0; i <35-2*n&&(35-2*n)>0;i++)</p><p>　　printf(" ");</p><p><b>　　return 1;</b></p><p><b>　　}&l

51、t;/b></p><p>　　int Print_Maze_Figure()//打印出圖形</p><p><b>　　{</b></p><p>　　int i,xi,xj;</p><p>　　Format_Limit();</p><p>　　for(i =0 ;i <= n*

52、2;i++)</p><p>　　printf("□");</p><p>　　printf("\n");</p><p>　　for(xi=0,xj=0;xj<((2*n-1)*(2*n-1));xj++,xi++)</p><p><b>　　{</b></p>

53、;<p>　　if(0 == xi)</p><p><b>　　{</b></p><p>　　Format_Limit();</p><p>　　printf("□");</p><p><b>　　}</b></p><p>　　pri

54、ntf("%s",str[xj]);</p><p>　　if(xi==2*n-2)</p><p><b>　　{</b></p><p>　　printf("□\n");</p><p><b>　　xi=-1; </b></p><p

55、><b>　　}</b></p><p><b>　　}</b></p><p>　　Format_Limit();</p><p>　　for(i =0 ;i <= n*2 ;i++)</p><p>　　printf("□");</p><p&

56、gt;　　printf("\n");</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p>　　int PPMF()// 打印出迷宮圖形</p><p><b>　　{</b></p>

57、<p>　　printf("\t\t\t\t[迷宮為]\n\t\t\t ●表可走，□表不可走 \n");</p><p>　　Initialization();</p><p>　　Print_Maze_Figure();</p><p><b>　　return 1;</b></p><p&g

58、t;<b>　　}</b></p><p>　　int Save_Path()// 將路徑保存在str[][]中并打印出路徑迷宮圖形</p><p><b>　　{</b></p><p>　　printf("\t\t\t [迷宮路徑圖]\n(%d,%d)至(%d,%d)\t\t ●表可走，□表不可走 \

59、n",s.x,s.y,t.x,t.y);</p><p>　　Initialization();</p><p>　　strcpy(str[2*s.x*(2*n-1)+2*s.y],"起");</p><p>　　strcpy(str[2*t.x*(2*n-1)+2*t.y],"終");</p><

60、;p>　　for(int wri=0;wri<ri;wri++)</p><p><b>　　{</b></p><p>　　if(re[wri].rx<re[wri+1].rx&&re[wri].ry==re[wri+1].ry)</p><p>　　strcpy(str[2*re[wri].rx*(2*n-

61、1)+(2*n-1)+2*re[wri].ry],"↑");</p><p>　　if(re[wri].rx==re[wri+1].rx&&re[wri].ry<re[wri+1].ry)</p><p>　　strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri+1].ry-1],"←");</

62、p><p>　　if(re[wri].rx>re[wri+1].rx&&re[wri].ry==re[wri+1].ry)</p><p>　　strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)+2*re[wri].ry],"↓");</p><p>　　if(re[wri].rx==re[wri+1

63、].rx&&re[wri].ry>re[wri+1].ry)</p><p>　　strcpy(str[2*re[wri].rx*(2*n-1)+2*re[wri].ry-1],"→");</p><p>　　if(re[wri].rx<re[wri+1].rx&&re[wri].ry<re[wri+1].ry)<

64、/p><p>　　strcpy(str[2*re[wri].rx*(2*n-1)+(2*n-1)+1+2*re[wri].ry],"↖");</p><p>　　if(re[wri].rx<re[wri+1].rx&&re[wri].ry>re[wri+1].ry)</p><p>　　strcpy(str[2*re[wr

65、i].rx*(2*n-1)+(2*n-1)-1+2*re[wri].ry],"↗");</p><p>　　if(re[wri].rx>re[wri+1].rx&&re[wri].ry<re[wri+1].ry)</p><p>　　strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-2)+2*re[wri].ry],&

66、quot;↙");</p><p>　　if(re[wri].rx>re[wri+1].rx&&re[wri].ry>re[wri+1].ry)</p><p>　　strcpy(str[2*re[wri].rx*(2*n-1)-(2*n-1)-1+2*re[wri].ry],"↘");</p><p>&l

67、t;b>　　}</b></p><p>　　Print_Maze_Figure();</p><p><b>　　return 1;</b></p><p><b>　　}</b></p><p><b>　　//隊(duì)列</b></p><p

68、>　　int Init()// 從文件中植入數(shù)據(jù) 完成對(duì)Map迷宮圖的結(jié)構(gòu)</p><p><b>　　{</b></p><p>　　FILE *pf;int i,j;</p><p>　　pf = fopen("maze.txt","r");</p><p>　　if

69、(pf==NULL)return 0;</p><p>　　fscanf(pf,"%d",&n);</p><p>　　for(i = 0;i < n; i++)</p><p>　　for(j = 0 ; j < n; j++)</p><p><b>　　{</b></p

70、><p>　　Used[i][j] = false;</p><p>　　fscanf(pf,"%d",&Map[i][j]);</p><p><b>　　}</b></p><p>　　fclose(pf);</p><p><b>　　return 1;&l

71、t;/b></p><p><b>　　}</b></p><p>　　int Judge()//判斷輸入的起點(diǎn)終點(diǎn)是否符合實(shí)際</p><p><b>　　{</b></p><p>　　bool flag = true;</p><p>　　if(s.x<0|

72、|s.x>=n||s.y<0||s.y>=n){printf("起點(diǎn)越界,不符合!\n");flag = false;}</p><p>　　else if(t.x<0||t.x>=n||t.y<0||t.y>=n){printf("終點(diǎn)越界,不符合!\n");flag = false;}</p><p>　

73、　else if(Map[s.x][s.y]){printf("起點(diǎn)是墻,不符合!\n");flag = false;}</p><p>　　else if(Map[t.x][t.y]){printf("終點(diǎn)是墻,不符合!\n");flag = false;}</p><p>　　else if(s.x==t.x&&s.y==t.y)

74、{printf("起點(diǎn)是終點(diǎn),不符合!\n");flag = false;}</p><p><b>　　if(!flag)</b></p><p>　　{printf("是則再輸入\\否則退出程序:(Y/N)\n");</p><p>　　char ch[20];</p><p&g

75、t;　　scanf("%s",ch);</p><p>　　if(ch[0] == 'Y'||ch[0] =='y')return 1;</p><p>　　else return 0;</p><p><b>　　}</b></p><p><b>　　re

76、turn 2;</b></p><p><b>　　}</b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p>　　int i,j,ste

77、p;</p><p>　　printf("\t\t\t<請(qǐng)按提示操作>\n");</p><p>　　next:system("pause");</p><p>　　system("cls");</p><p>　　printf("是否使用系統(tǒng)提供的迷宮圖:(Y

78、/N)\n");</p><p>　　ch = getch();</p><p>　　if(ch == 'Y'||ch =='y')</p><p><b>　　Init();</b></p><p><b>　　else</b></p>&l

79、t;p><b>　　{</b></p><p>　　printf("請(qǐng)輸入迷宮的大小:(n*n)");</p><p>　　scanf("%d",&n);</p><p>　　printf("\t請(qǐng)輸入迷宮的結(jié)構(gòu)0,1表示0是路1是墻\n");</p>&l

80、t;p>　　for(i = 0;i < n; i++)</p><p>　　for(j = 0 ; j < n; j++)</p><p><b>　　{</b></p><p>　　Used[i][j] = false;</p><p>　　scanf("%d",&Map[

81、i][j]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　bool flag=true;</p><p>　　while(flag)</p><p><b>　　{</b></p>

82、<p>　　for(i =0 ;i < n;i++)</p><p>　　for(j =0 ;j < n ;j++)</p><p>　　Used[i][j] = false;</p><p><b>　　ri = -1;</b></p><p>　　system("pause"

83、);</p><p>　　system("cls");</p><p>　　printf("是否顯示原始迷宮:(Y/N)\n");</p><p>　　ch = getch();</p><p>　　if(ch == 'Y'||ch =='y')</p>&

84、lt;p><b>　　PPMF();</b></p><p>　　again:printf("請(qǐng)輸入起點(diǎn)與終點(diǎn):(x1 y1 x2 y2)");</p><p>　　scanf("%d %d %d %d",&s.x,&s.y,&t.x,&t.y);</p><p>

85、　　if(1==Judge())goto again;</p><p><b>　　else</b></p><p>　　if(0==Judge())break;</p><p>　　printf("請(qǐng)選擇4方向還是8方向的迷宮:");</p><p>　　scanf("%d",&

86、amp;step);</p><p>　　if(8==step)step=8;</p><p>　　else step = 4;</p><p>　　system("pause");</p><p>　　system("cls");</p><p>　　BFS(step);<

87、;/p><p>　　Save_Path();</p><p>　　printf("是否繼續(xù)(Y/N)\n");</p><p>　　ch = getch();</p><p>　　if(ch != 'Y'&&ch !='y') flag = false;</p>&

88、lt;p><b>　　if(flag)</b></p><p>　　{printf("是否更換迷宮(Y/N)\n");</p><p>　　ch = getch();</p><p>　　if(ch == 'Y'||ch =='y')</p><p>　　got

89、o next;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　/

90、*測(cè)試?yán)?lt;/b></p><p><b>　　5</b></p><p><b>　　0 0 0 0 0</b></p><p><b>　　1 1 1 1 0</b></p><p><b>　　0 0 0 0 0</b></p>

91、;<p><b>　　0 1 1 1 1</b></p><p><b>　　0 0 0 0 0</b></p><p><b>　　0 0 4 4 4</b></p><p><b>　　16</b></p><p>　　0 0 0 0 0

92、 0 0 0 0 0 0 0 0 0 0 0</p><p>　　1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0</p><p>　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0</p><p>　　0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0</p><p>　　0 1 0 0 0 0 0

93、 0 0 0 0 0 1 0 1 0</p><p>　　0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0</p><p>　　0 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 1 1 1 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 0 1 1

94、 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 0</p><p>　　0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0</p><p>　　0 1 0 1 1 1 1 1 1 1 1

95、 1 1 0 1 0</p><p>　　0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0</p><p>　　0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0</p><p>　　0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0</p><p><b>　　0 0 8 6 4</b&

96、gt;</p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0&

97、lt;/p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</

98、p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</p>

99、;<p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</p><p>　　0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0</p>&

100、lt;p>　　0 0 15 15 8</p><p>　　0 0 14 0 8</p><p>　　0 1 0 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 1</p><p>　　1 0 1 1 1 1 1 1</p><p>　　1 0 0 0 1 0 1 0</p>&l

101、t;p>　　0 1 1 1 1 1 0 1</p><p>　　1 0 1 1 1 1 1 1</p><p>　　0 1 1 1 0 1 0 1</p><p>　　1 0 1 0 1 0 1 0</p><p><b>　　0 0 7 9 8</b></p><p>　　0 0 0 0

102、1 0 1 0 1 1 1 0 1 1 1 0</p><p>　　1 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0</p><p>　　0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 0</p><p>　　0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0</p><p>　　0 0 0 1 0 0

103、1 0 1 1 1 0 0 0 0 1</p><p>　　1 1 1 0 1 0 1 0 0 0 0 1 0 1 0 0</p><p>　　0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0</p><p>　　0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0</p><p>　　0 0 0 1 0 1 0 1

104、0 0 0 0 1 1 0 0</p><p>　　0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 1</p><p>　　0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0</p><p>　　0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0</p><p>　　0 0 0 1 0 0 0 0 1 0

105、1 0 0 1 0 0</p><p>　　0 1 1 0 0 1 1 1 0 0 0 1 0 1 0 0</p><p>　　0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0</p><p>　　1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0</p><p>　　0 11 0 15 4</p>&

106、lt;p>　　0 11 0 15 8</p><p>　　0 2 14 12 4</p><p>　　0 2 14 12 8</p><p>　　0 0 0 15 4</p><p>　　0 0 0 15 8</p><p><b>　　*/</b></p><p>

107、　　返回課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定</p><p>　　課題名稱(chēng)： 迷宮求解 </p><p>　　完成者： 李小鋒、田芳、黃健、周?chē)?guó)柱 </p><p>　　1、設(shè)計(jì)的目的與要求： </p><

108、p>　　靈活應(yīng)用所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)，獨(dú)立完成問(wèn)題分析。</p><p>　　初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等方法。</p><p>　　訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開(kāi)發(fā)一般規(guī)范進(jìn)行軟件開(kāi)發(fā)。</p><p>　　提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力。</p><p><b>　　設(shè)計(jì)進(jìn)度及

109、完成情況</b></p><p><b>　　3、成績(jī)?cè)u(píng)定： </b></p><p>　　設(shè)計(jì)成績(jī)： （教師填寫(xiě)）</p><p>　　指導(dǎo)老師： （簽字）</p><p>　　二00 年 月 日</p>