數(shù)據(jù)結(jié)構(gòu)迷宮求解

1、棗莊學(xué)院 信息科學(xué)與工程學(xué)院 課程設(shè)計(jì)任務(wù)書(shū) 題目 迷宮求解 學(xué) 號(hào)： 201012120262 _ 姓 名： 趙延芳 _ 專 業(yè)： 網(wǎng)絡(luò)工程 _ 課 程： 數(shù)據(jù)結(jié)構(gòu) _ 指導(dǎo)教師： 楊振 _ 職稱： 教室 完成時(shí)間： 20 11 年 11 月-2011 年 12 月 棗莊學(xué)院信息科學(xué)與工程學(xué)院制 2011年12月17日1 課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定 要求 （1）建立一個(gè)大小為mKn的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動(dòng) 生成），并在屏幕上顯示出來(lái)； （2）找出一條通路的二元組（i,j ）數(shù)據(jù)序列，（i,j ）表示通路上某一點(diǎn)的 坐標(biāo)。 3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路； 指

2、導(dǎo)教師簽字： _ 、 _ 日期： _ 指導(dǎo)教師評(píng)語(yǔ) 成績(jī)： _ 指導(dǎo)教師簽字： 日期：2 電腦、VC+6.0、課本及參考資料 課程設(shè)計(jì)進(jìn)度計(jì)劃 起至日期 工作內(nèi)容 備注 2011 年 12 月 17 算法設(shè)計(jì)、編程設(shè)計(jì)、 調(diào)試、書(shū)寫(xiě)報(bào)告 參考文獻(xiàn)、資料索引 序號(hào):數(shù)程結(jié)構(gòu)計(jì)，語(yǔ)言版） 偉民:覃浩清華大學(xué)出版社 C程序設(shè)計(jì) 強(qiáng) 3 目錄 第一部課程設(shè)計(jì)報(bào)告 . 3 第一章課程設(shè)計(jì)目的 . 4 第二章 課程設(shè)計(jì)內(nèi)容和要求 . 4 2.1 問(wèn)題描述 . 4 2.2 設(shè)計(jì)要求 . 4 第三章課程設(shè)計(jì)總體方案及分析 . 5 3.1 問(wèn)題分析 . 5 3.2 概要設(shè)計(jì) . 7 3.3 詳細(xì)設(shè)計(jì) . 8 3

3、.4 調(diào)試分析 . 11 3.5 測(cè)試結(jié)果 . 12 第二部分 課程設(shè)計(jì)總結(jié) . 13 附錄（源代碼） . 13 4 第一章課程設(shè)計(jì)目的 僅僅認(rèn)識(shí)到隊(duì)列是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的， 本次實(shí)習(xí)的目的在于 使學(xué)生深入了解隊(duì)列的特征，以便在實(shí)際問(wèn)題背景下靈活運(yùn)用它，同時(shí)還將鞏 固這種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法 第二章 課程設(shè)計(jì)內(nèi)容和要求 2.1問(wèn)題描述： 迷宮問(wè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)，一

4、直到老鼠從入口走到出口， 而不走錯(cuò)一步。老鼠經(jīng)過(guò)多次試驗(yàn)最終學(xué)會(huì)走通迷宮的路線。 設(shè)計(jì)一個(gè)計(jì)算機(jī) 程序?qū)θ我庠O(shè)定的矩形迷宮如下圖 A所示，求出一條從入口到出口的通路, 2.2設(shè)計(jì)要求: 要求設(shè)計(jì)程序輸出如下: (1) 建立一個(gè)大小為mKn的任意迷宮(迷宮數(shù)據(jù)可由用戶輸入或由程序 自動(dòng)生成)，并在屏幕上顯示出來(lái)； (2) 找出一條通路的二元組(i,j )數(shù)據(jù)序列，(i,j )表示通路上某一 點(diǎn)的坐標(biāo)。 (3) 用一種標(biāo)志(如數(shù)字8)在迷宮中標(biāo)出該條通路； (4) 在屏幕上輸出迷宮和通路； (5) 上述功能可用菜單選擇。 5 第三章課程設(shè)計(jì)總體方案及分析 3.1問(wèn)題分析： 1. 迷宮的建立： 迷宮

5、中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用 0表示通路， 用1表示障礙，這樣迷宮就可以用 0、1矩陣來(lái)描述， 2. 迷宮的存儲(chǔ)： 迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每 一個(gè)位置都可以用其行列號(hào)來(lái)唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其 大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組 mazeM+2N+2,然后 用它的前m行n列來(lái)存放元素，即可得到一個(gè) mx n的二維數(shù)組，這樣 (0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。 注：其中M N分別表示迷宮最大行、列數(shù)，本程序 M N的缺省值 為39、39,當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。 3. 迷宮路徑的搜索：

6、首先從迷宮的入口開(kāi)始，如果該位置就是迷宮出口，則已經(jīng)找到 了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是 障礙，若不是障礙，就移動(dòng)到該位置，然后再?gòu)脑撐恢瞄_(kāi)始搜索通往 出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開(kāi)始搜索路 徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過(guò)的位置標(biāo)記為 2,同時(shí)保留 搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè) 隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過(guò)，且未找到通往出口 的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍 歷的算法，如果找到路徑，貝U為最短路徑。 以矩陣0 010 1 為例，來(lái)示范一下 1 0 0 1 0 1

7、0 0 0 1 0 0 1 0 0 6 首先，將位置(0,0)(序號(hào)0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從7 它開(kāi)始搜索，其標(biāo)記變?yōu)?2,由于其只有一個(gè)非障礙位置，所以接下 來(lái)移動(dòng)到(0,1)(序號(hào)1)，其前節(jié)點(diǎn)序號(hào)為0,標(biāo)記變?yōu)?,然后從(0,1) 移動(dòng)到(1,1)(序號(hào)2)，放入隊(duì)列中，其前節(jié)點(diǎn)序號(hào)為1, (1,1)存在(1， 2)(序號(hào)3)、(2，1)(序號(hào)4)兩個(gè)可移動(dòng)位置，其前節(jié)點(diǎn)序號(hào)均為 2. 對(duì)于每一個(gè)非障礙位置，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)列，且它們的前 節(jié)點(diǎn)序號(hào)均為該位置的序號(hào)，所以如果存在路徑，則從出口處節(jié)點(diǎn)的 位置，逆序就可以找到其從出口到入口的通路。 如卜表所示： 0 1 2 3

8、 4 5 6 7 8 9 10 (0,0) (0,1) (1,1) (1,2) (2,1) (2,2) (1,3) (2,3) (0,3 -1 0 1 2 2 3 4 5 6 由此可以看出，得到最短路徑： (3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 搜索算法流程圖如下所示： 8 3.2 概要設(shè)計(jì) 1. 構(gòu)建一個(gè)二維數(shù)組mazeM+2N+2用于存儲(chǔ)迷宮矩陣 自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組 mazeM+2N+2賦值 構(gòu)建一個(gè)隊(duì)列用于存儲(chǔ)迷宮路徑 建立迷宮節(jié)點(diǎn)struct point, 用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問(wèn)情況 循壞站束 無(wú)解迷宮 迷宮略由算法流程團(tuán)迷

9、宮略由算法流程團(tuán): : 將0,0）入隊(duì)列 將隊(duì)頭出臥 9 實(shí)現(xiàn)搜索算法 屏幕上顯示操作菜單 2. 本程序包含10個(gè)函數(shù)： 主函數(shù)mai n() (2) 手動(dòng)生成迷宮函數(shù)shoudong_maze() (3) 自動(dòng)生成迷宮函數(shù)zidong_maze() 將迷宮打印成圖形print_maze() (5) 打印迷宮路徑(若存在路徑)result_maze() (6) 入隊(duì) enqueue() (7) 出隊(duì) dequeue。 (8) 判斷隊(duì)列是否為空is_empty() (9) 訪問(wèn)節(jié)點(diǎn)visit() (10) 搜索迷宮路徑mgpath() 3.3 詳細(xì)設(shè)計(jì) 實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型及操作的偽

10、代碼算法 1. 節(jié)點(diǎn)類型和指針類型 迷宮矩陣類型：in t mazeM+2N+2;為方便操作使其為全局變量 迷宮中節(jié)點(diǎn)類型及隊(duì)列類型：struct poi nti nt row,col,predecessor que512 2. 迷宮的操作 (1) 手動(dòng)生成迷宮 void shoud on g_maze(i nt m,i nt n) 定義i,j為循環(huán)變量 for(i=m) for(jv=n) 輸入mazeij 的值 10 (2) 自動(dòng)生成迷宮 void zid on g maze(i nt m,i nt n)11 由于rand()產(chǎn)生的隨機(jī)數(shù)是從0 至U RAND_MAX,RAND_M是定 義

11、在stdlib.h 中的,其值至 少為32767),要產(chǎn)生從X到丫丫 的數(shù)，只需要這樣寫(xiě)： k=ra nd()%(Y-X+1)+X; 打印迷宮圖形 void prin t_maze(i nt m,i nt n) 用i,j循環(huán)變量，將 mazeij 打印迷宮路徑 void result_maze(i nt m,i nt n) 用i,j循環(huán)變量，將 mazeij (5)搜索迷宮路徑 迷宮中隊(duì)列入隊(duì)操作 void enq ueue(struct point p) 將p放入隊(duì)尾，tail+ 迷宮中隊(duì)列出隊(duì)操作 struct point dequeue(struct point p) head+,返回

12、quehead-1 判斷隊(duì)列是否為空 int is_empty() 返回head=tail的值，當(dāng)隊(duì)列為空時(shí)，返回0 訪問(wèn)迷宮矩陣中節(jié)點(diǎn) void visit(i nt row,i nt col,i nt maze4141) 建立新的隊(duì)列節(jié)點(diǎn)visit point, 將其值分別賦為別定義i,j為循環(huán)變量 for(i=m) for(jv=n) mazeij=ra nd()%2 / 輸出、 輸出、 12 路徑求解 void mgpath(i nt maze4141,i nt m,i nt n) 先定義入口節(jié)點(diǎn)為struct poi nt p=0,0,-1, 從 maze00開(kāi)始訪問(wèn)。如果入口處即為

13、障礙，貝U此迷宮 無(wú)解，返回0，程序結(jié)束。否則訪問(wèn)入口節(jié)點(diǎn)，將入口 節(jié)點(diǎn)標(biāo)記為訪問(wèn)過(guò) mazep.rowp.col=2, 調(diào)用函數(shù) enqueue(p)將該節(jié)點(diǎn)入隊(duì)。 判斷隊(duì)列是否為空，當(dāng)隊(duì)列不為空時(shí)，則運(yùn)行以下操作： 調(diào)用dequeue。函數(shù)，將隊(duì)頭元素返回給p， 如果p.row=m-1且p.col=n-1, 即到達(dá)出口節(jié)點(diǎn)， 即找到了路徑，結(jié)束 如果 p.col+1n 且 mazep.rowp.col+1=0,說(shuō)明 未到迷宮右邊界，且其右方有通路，則 visit(p.row,p.col+1,maze), 將右邊節(jié)點(diǎn)入隊(duì)標(biāo)記已訪 問(wèn) 如果 p.row+10 且 mazep.rowp.col-

14、1=0, 說(shuō)明 未到迷宮左邊界，且其左方有通路，則 visit(p.row,p.col-1,maze), 將左方節(jié)點(diǎn)入隊(duì) 標(biāo)記已訪問(wèn) 如果 p.row-10 且 mazep.row-1p.col=0, 說(shuō)明 未到迷宮上邊界，且其上方有通路，則 visit(p.row,p.col+1,maze), 將上方節(jié)點(diǎn)入隊(duì) 標(biāo)記已訪問(wèn) 13 訪問(wèn)到出口(找到路徑)即p.row=m-1且p.col=n-1. 則逆序?qū)⒙窂綐?biāo)記為3即mazep.rowp.col=3; while(p.predecessor!=-1) p=queuep.predecessor; mazep.rowp.col=3; 最后將路徑圖形

15、打印出來(lái)。 3.菜單選擇 while(cycle!=(-1) 手動(dòng)生成迷宮 請(qǐng)按：1 自動(dòng)生成迷宮 請(qǐng)按：2 退出 請(qǐng)按：3 scan f(%d,&i); switch(i) case 1 ：請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) shoudo ng_maze( m,n); prin t_maze( m,n); mgpath(maze,m, n); if(X!=0) result_maze( m,n); case 2 :請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) zid on g_maze( m,n); prin t_maze( m,n); mgpath(maze,m, n

16、); if(X!=0) result_maze(m, n); case 3 : cycle=(-1); break; 注：具體源代碼見(jiàn)附錄 14 3.4 調(diào)試分析 在調(diào)試過(guò)程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多 條或不是最短路徑，所以通過(guò)算法比較，改用此算法15 3.5 測(cè)試結(jié)果 1.手動(dòng)輸入迷宮 慮慮郴統(tǒng)陰硼 12 2 磧薪h行生6 橫菽人歹我6 港宮生咸中， 彊按圧巻樓進(jìn)墀. 2.自動(dòng)生成迷宮 請(qǐng)輸入列數(shù)，t 迷宮生脫中” 口 口口口 二 口 口口口口 口二I一這臺(tái)岀口 言無(wú)幅 PL與Etftetr 3”* 丄uu* 歡迎逬入達(dá)宮求解乘統(tǒng)設(shè)討者*卑廨佶出冊(cè) 7 班 t蹲蠶P：:

17、16 第二部分 課程設(shè)計(jì)總結(jié) 通過(guò)這段時(shí)間的課程設(shè)計(jì)，本人對(duì)計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及 C 語(yǔ)言的使用都有了更深的了解。尤其是C語(yǔ)言的進(jìn)步讓我深刻的感受到任何所 學(xué)的知識(shí)都需要實(shí)踐，沒(méi)有實(shí)踐就無(wú)法真正理解這些知識(shí)以及掌握它們， 使其 成為自己的財(cái)富。在理論學(xué)習(xí)和上機(jī)實(shí)踐的各個(gè)環(huán)節(jié)中， 通過(guò)自主學(xué)習(xí)和請(qǐng)教 老師，我收獲了不少。當(dāng)然也遇到不少的問(wèn)題，也正是因?yàn)檫@些問(wèn)題引發(fā)的思 考給我?guī)Я耸斋@。從當(dāng)初不喜歡上機(jī)寫(xiě)程序到現(xiàn)在能主動(dòng)寫(xiě)程序，從當(dāng)初拿著 程序不只如何下手到現(xiàn)在知道如何分析問(wèn)題，如何用專業(yè)知識(shí)解決實(shí)際問(wèn)題的 轉(zhuǎn)變，我發(fā)現(xiàn)無(wú)論是專業(yè)知識(shí)還是動(dòng)手能力， 自己都有很大程度的提高。在這 段時(shí)間

18、里，我對(duì)for、while等的循環(huán)函數(shù)用法更加熟悉，逐漸形成了較好的 編程習(xí)慣。在老師的指導(dǎo)幫助下，同學(xué)們課余時(shí)間的討論中，這些問(wèn)題都一一 得到了解決。在程序的調(diào)試能力上，無(wú)形中得到了許多的提高。例如：頭文件 的使用，變量和數(shù)組的范圍問(wèn)題，定義變量時(shí)出現(xiàn)的問(wèn)題等等。 在實(shí)際的上機(jī)操作過(guò)程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)， 更重 要的是培養(yǎng)解決實(shí)際問(wèn)題的能力，所以相信通過(guò)此次實(shí)習(xí)可以提高我們分析設(shè) 計(jì)能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。 在這次短短的課程實(shí)踐里，我們得到了侯瑞蓮老師的關(guān)心和幫助。她給了 我們很多的信息，與我們一起探討問(wèn)題，詢問(wèn)我們遇到了哪些問(wèn)題并耐心給予

19、指導(dǎo)。當(dāng)我們遇到技術(shù)上難以解決的問(wèn)題時(shí)， 她就會(huì)指導(dǎo)我們解決問(wèn)題，她把 自己多年來(lái)積累的經(jīng)驗(yàn)教授給我們， 使我們順利地完成了課程實(shí)踐任務(wù)。 時(shí)間 過(guò)得真快，大學(xué)生活不知不覺(jué)就走過(guò)了一年，一年的大學(xué)學(xué)習(xí)和課程實(shí)踐階段 的提高，使我們本身知識(shí)得到提高的同時(shí)，也增強(qiáng)了我們對(duì)未來(lái)工作的信心， 我們相信自己未來(lái)三年的學(xué)習(xí)更使我們有能力勝任將來(lái)的工作。 附錄: #i ncludestdlib.h #i ncludestdio.h 17 #defi ne N 39 #defi ne M 39 int X; int mazeN+2M+2; struct poi nt int row,col,predecess

20、or; queue512; int head=0,tail=0; void shoudo ng_maze(i nt m,i nt n) int i,j; prin tf(nn); printf(”請(qǐng)按行輸入迷宮，0 表示通路，1 表示障礙:nn); for(i=0;im;i+) for(j=0;j n;j+) scan f(%d,&mazeij); void zido ng_maze(i nt m,i nt n) int i,j; printf(n 迷宮生成中 . nn); system(pause); for(i=0;im;i+) for(j=0;j n;j+) mazeij=ra

21、nd()%2; /由于 rand()產(chǎn)生的隨機(jī)數(shù)是從 0 到 RAND_MAX RAND_MAX 是定義在 stdlib.h中的，其值至少為 32767) /要產(chǎn)生從 X 到 Y 的數(shù)，只需要這樣寫(xiě)：k=rand()%(Y-X+1)+X; void prin t_maze(i nt m,i nt n) int i,j; printf(n迷宮生成結(jié)果如下:nn); printf(迷宮入口 n”); printf( J ); for(i=0;im;i+) pri ntf(n ”); for(j=0;j n;j+) if(mazeij=0) prin tf( ); if(mazeij=1) pri

22、ntf( ); printf( T迷宮出口 n”); void result_maze(i nt m,i nt n) int i,j; printf(迷宮通路(用表示)如下所示：nt); for(i=0;im;i+) pri ntf(n ”); for(j=0;j n;j+) if(mazeij=0|mazeij=2) pri ntf( ); if(mazeij=1) printf(” ); if(mazeij=3) printf(” ); void enq ueue(struct point p)18 * *n); II 歡迎進(jìn)入迷宮求解系統(tǒng) n queuetail=p; tail+; st

23、ruct point dequeue() head+; retur n queuehead-1; int is_empty() retur n head=tail; void visit(i nt row,i nt col,i nt maze4141) struct point visit_po in t=row,col,head-1; mazerowcol=2; enq ueue(visit_po in t); - int mgpath(i nt maze4141,i nt m,i nt n) X=1; struct poi nt p=0,0,-1; if(mazep.rowp.col=1)

24、 prin tf(n=n); printf(此迷宮無(wú)解 nn);X=O;return 0; mazep.rowp.col=2; enq ueue(p); while(!is_empty() p=dequeue(); if(p.row=m-1) &(p.col=n-1) break; if(p.col+1 n)&( mazep.rowp.col+1=0) visit(p.row,p.col+1,maze); if(p.row+1=0)&( mazep.rowp.col-1=0) visit(p.row,p.col-1,maze); if(p.row-1=0)&(

25、mazep.row-1p.col=0) visit(p.row-1,p.col,maze); if(p.row=m-1 &p.col=n-1) pri ntf(n= :=n); printf(迷宮路徑為：n); prin tf(%d,%d)n,p.row,p.col); mazep.rowp.col=3; while(p.predecessor!=-1) p=queuep.predecessor; prin tf(%d,%d)n,p.row,p.col); mazep.rowp.col=3; else prin tf(n= =n); printf(此迷宮無(wú)解! nn );X=0; re

26、turn 0; void mai n() int i,m ,n, cycle=0; while(cycle!=(-1) printf( 19 printf(” n ”)； printf( * *n)； printf(” 手動(dòng)生成迷宮 請(qǐng)按： 1 n); printf(” 自動(dòng)生成迷宮 請(qǐng)按： 2n); prin tf( 退出 請(qǐng)按： 3nn) printf( prin tf(n); printf(請(qǐng)選擇你的操作：n); scan f(%d, &i); switch(i) case 1:printf(n 請(qǐng)輸入行數(shù)：);scanf(%d,&m); prin tf(n); printf(請(qǐng)輸入列數(shù):);s