迷宮問(wèn)題求解

1、課程設(shè)計(jì)報(bào)告課題名稱： 迷宮問(wèn)題的求解及演示 姓 名： 學(xué) 號(hào)： 專 業(yè)： 計(jì)算機(jī)與信息學(xué)院 班 級(jí)： 指導(dǎo)教師： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書(shū)針對(duì)本課程設(shè)計(jì)，完成以下課程設(shè)計(jì)任務(wù)書(shū)：1. 熟悉系統(tǒng)實(shí)現(xiàn)工具和上機(jī)環(huán)境。2. 根據(jù)課程設(shè)計(jì)任務(wù)，查閱相關(guān)資料。3. 針對(duì)所選課題完成以下工作： （1）需求分析（2）概要設(shè)計(jì)（3）詳細(xì)設(shè)計(jì)（4）編寫(xiě)源程序（5）靜態(tài)走查程序和上機(jī)調(diào)試程序 4.書(shū)寫(xiě)上述文檔和撰寫(xiě)課程設(shè)計(jì)報(bào)告目 錄第一部分 課程設(shè)計(jì)任務(wù)書(shū) 1 第二部分 課程設(shè)計(jì)報(bào)告 2第一章 課程設(shè)計(jì)內(nèi)容和要求42.1 問(wèn)題描述42.2 需求分析4第二章 課程設(shè)計(jì)總體方案及分析43.1 概要設(shè)計(jì)73.2 詳細(xì)設(shè)

2、計(jì)73.3 調(diào)試分析103.4 測(cè)試結(jié)果10第三章 設(shè)計(jì)總結(jié)134.1課程設(shè)計(jì)總結(jié)134.2參考文獻(xiàn) 4.3 附錄(源代碼)14 第二部分 課程設(shè)計(jì)報(bào)告 第一章  課程設(shè)計(jì)內(nèi)容和要求  2.1問(wèn)題描述： 迷宮以16*16的矩陣存儲(chǔ)在數(shù)據(jù)文件中（迷宮中的障礙物要占到一定比例），編寫(xiě)非遞歸的程序，求出一條從入口到出口的路徑并顯示之（結(jié)果若能用C的繪圖函數(shù)顯示更好）2.2需求分析：1要求設(shè)計(jì)程序輸出如下：(1) 建立一個(gè)大小為m×n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動(dòng)生成），并在屏幕上顯示出來(lái)；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某

3、一點(diǎn)的坐標(biāo)。（3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路；（4）在屏幕上輸出迷宮和通路；（5）上述功能可用菜單選擇。2.迷宮的建立：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來(lái)描述，3.迷宮的存儲(chǔ)：迷宮是一個(gè)矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個(gè)位置都可以用其行列號(hào)來(lái)唯一指定，但是二維數(shù)組不能動(dòng)態(tài)定義其大小，我們可以考慮先定義一個(gè)較大的二維數(shù)組mazeM+2N+2,然后用它的前m行n列來(lái)存放元素，即可得到一個(gè)m×n的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。注：其中M，N分別

4、表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。4.迷宮路徑的搜索：首先從迷宮的入口開(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)先遍歷的算法，如

5、果找到路徑，則為最短路徑。以矩陣 0 0 1 0 1 為例，來(lái)示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，將位置(0,0)(序號(hào)0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開(kāi)始搜索，其標(biāo)記變?yōu)?，由于其只有一個(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)的位

6、置，逆序就可以找到其從出口到入口的通路。如下表所示： 0 1 2 3 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)(3,3)(3,4)-10122345679 由此可以看出，得到最短路徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0) 搜索算法流程圖如下所示： 第二章      課程設(shè)計(jì)總體方案及分析3.1概要設(shè)計(jì)1.構(gòu)建一個(gè)二維數(shù)組mazeM+2N+2用于存儲(chǔ)迷宮矩陣自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組mazeM+2N+2賦值構(gòu)建一個(gè)隊(duì)列用

7、于存儲(chǔ)迷宮路徑建立迷宮節(jié)點(diǎn)struct point,用于存儲(chǔ)迷宮中每個(gè)節(jié)點(diǎn)的訪問(wèn)情況實(shí)現(xiàn)搜索算法屏幕上顯示操作菜單 2.本程序包含10個(gè)函數(shù)： (1)主函數(shù) main()(2)手動(dòng)生成迷宮函數(shù) shoudong_maze()(3)自動(dòng)生成迷宮函數(shù) zidong_maze()(4)將迷宮打印成圖形 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.2 詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)

8、類型及操作的偽代碼算法1. 節(jié)點(diǎn)類型和指針類型迷宮矩陣類型：int mazeM+2N+2;為方便操作使其為全局變量迷宮中節(jié)點(diǎn)類型及隊(duì)列類型：struct pointint row,col,predecessor que5122. 迷宮的操作(1)手動(dòng)生成迷宮void shoudong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n)輸入mazeij的值(2)自動(dòng)生成迷宮void zidong_maze(int m,int n)定義i,j為循環(huán)變量for(i<=m)for(j<=n) mazeij=rand()%2 /由于rand

9、()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫(xiě)：k=rand()%(Y-X+1)+X;(3)打印迷宮圖形void print_maze(int m,int n)用i,j循環(huán)變量，將mazeij輸出 、(4)打印迷宮路徑void result_maze(int m,int n)用i,j循環(huán)變量，將mazeij輸出 、(5)搜索迷宮路徑 迷宮中隊(duì)列入隊(duì)操作void enqueue(struct point p)將p放入隊(duì)尾，tail+迷宮中隊(duì)列出隊(duì)操作struct point dequeue(stru

10、ct point p)head+,返回quehead-1判斷隊(duì)列是否為空int is_empty()返回head=tail的值，當(dāng)隊(duì)列為空時(shí)，返回0訪問(wèn)迷宮矩陣中節(jié)點(diǎn)void visit(int row,int col,int maze4141)建立新的隊(duì)列節(jié)點(diǎn)visit_point,將其值分別賦為row,col,head-1,mazerowcol=2,表示該節(jié)點(diǎn)以被訪問(wèn)過(guò);調(diào)用enqueue(visit_point),將該節(jié)點(diǎn)入隊(duì)路徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點(diǎn)為struct point p=0,0,-1,從maze00開(kāi)始訪問(wèn)

11、。如果入口處即為障礙，則此迷宮無(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+1<n且mazep.rowp.col+1=0,說(shuō)明未到迷宮右邊界，且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問(wèn)如果p.row+1<m且mazep.row+1p.col=0,

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

13、hile(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3; 最后將路徑圖形打印出來(lái)。3.菜單選擇 while(cycle!=(-1) 手動(dòng)生成迷宮 請(qǐng)按：1 自動(dòng)生成迷宮 請(qǐng)按：2 退出 請(qǐng)按：3 scanf("%d",&i); switch(i) case 1：請(qǐng)輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 2 ：請(qǐng)輸入行列數(shù)(如

14、果超出預(yù)設(shè)范圍則提示重新輸入) zidong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 3：cycle=(-1); break;注：具體源代碼見(jiàn)附錄3.3 調(diào)試分析（1）在調(diào)試過(guò)程中，首先使用的是棧進(jìn)行存儲(chǔ)，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過(guò)算法比較，改用此算法。（2）在編寫(xiě) while 語(yǔ)句時(shí)，另一種情況（即當(dāng)前位置不能通過(guò)時(shí)）也同樣出現(xiàn)在墻節(jié)點(diǎn)就直接往南走的情況，綜合上面的情況，同樣的，也是退位沒(méi)有賦值。這種錯(cuò)誤比較難發(fā)現(xiàn)，往往只有在復(fù)雜的迷宮求解過(guò)程中才能發(fā)現(xiàn)。這類錯(cuò)

15、誤屬于邏輯錯(cuò)誤，調(diào)試不會(huì)顯示，需要自己拙句地查看和分析，并能充分的理解程序每一步的認(rèn)識(shí)，才能發(fā)現(xiàn)并解決這樣的問(wèn)題。 （3）在編寫(xiě)MazePath函數(shù)時(shí)，當(dāng)遇到墻（即遇到下一位置為1）時(shí)，直接從現(xiàn)在墻位置進(jìn)行往南跳轉(zhuǎn)。以至有許多應(yīng)該走的通路位置沒(méi)有走，而且使總共走的步數(shù)變短。在測(cè)試前期怎么也想不明白，出棧操作也有，退位也有，但就是不進(jìn)行退到上一位置的操作。最后發(fā)現(xiàn)，少了一步把出棧的數(shù)進(jìn)行賦值的操作。（4）在進(jìn)行對(duì)迷宮的輸出時(shí)，變成按行輸出，得不到預(yù)期的迷宮結(jié)果，更不用說(shuō)驗(yàn)證其正確性。這就是粗心造成的 。 3.4 測(cè)試結(jié)果 1.手動(dòng)輸入迷宮  2.自動(dòng)生成迷宮 第二部分 設(shè)計(jì)總結(jié)4.1

16、課程設(shè)計(jì)總結(jié)通過(guò)這次的數(shù)據(jù)結(jié)構(gòu)課程設(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í)間里，我對(duì)for、while等的循環(huán)函數(shù)用

17、法更加熟悉，逐漸形成了較好的編程習(xí)慣。在老師的指導(dǎo)幫助下，同學(xué)們課余時(shí)間的討論中，這些問(wèn)題都一一得到了解決。在程序的調(diào)試能力上，無(wú)形中得到了許多的提高。 在實(shí)際的上機(jī)操作過(guò)程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知識(shí)，更重要的是培養(yǎng)解決實(shí)際問(wèn)題的能力，譬如迷宮的實(shí)現(xiàn)，面對(duì)問(wèn)題時(shí)我學(xué)會(huì)了應(yīng)該如何解決。同時(shí)，也讓我對(duì)棧這一章節(jié)有更深的體會(huì)，以及用不同的方法解決問(wèn)題相比較得出較好的解決方案。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的主要目的是介紹一些常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種數(shù)據(jù)結(jié)構(gòu)，討論對(duì)他們實(shí)行的各種運(yùn)算的實(shí)現(xiàn)算法。 此次迷宮問(wèn)題的求解及演示課程設(shè)計(jì)你在實(shí)際操作中也

18、犯了很多錯(cuò)誤，這些錯(cuò)誤同時(shí)也讓我意外的收獲了很多。對(duì)我所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)理論也得到鞏固。通過(guò)實(shí)際的設(shè)計(jì)和分析，讓我學(xué)會(huì)了編程的基本步驟和方法，同時(shí)也開(kāi)發(fā)了自己的邏輯思維能力，提高了解決問(wèn)題的能力。在不斷的遇到問(wèn)題，不斷的解決問(wèn)題的過(guò)程中，培養(yǎng)的專業(yè)的思維是最重要的，也是這次課程設(shè)計(jì)所要達(dá)到的目的，我很慶幸我做到了。4.2 參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社【2】數(shù)據(jù)結(jié)構(gòu) (C語(yǔ)言版） 秦鋒 編著 清華大學(xué)出版社【3】C+程序設(shè)計(jì)杜茂康 編著 清華大學(xué)出版社43 附錄（程序清單）：#include"stdlib.h"#includ

19、e"stdio.h"#define N 39#define M 39int X;int mazeN+2M+2;struct pointint row,col,predecessor;queue512;int head=0,tail=0;void shoudong_maze(int m,int n)int i,j;printf("nn");printf("請(qǐng)按行輸入迷宮，0表示通路，1表示障礙:nn");for(i=0;i<m;i+)for(j=0;j<n;j+) scanf("%d",&maze

20、ij);void zidong_maze(int m,int n)int i,j;printf("n迷宮生成中nn");system("pause");for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2;/由于rand()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX/RAND_MAX是定義在stdlib.h中的,其值至少為32767)/要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫(xiě)：k=rand()%(Y-X+1)+X; void print_maze(int m,int n)int i,j;printf("n迷宮

21、生成結(jié)果如下:nn");printf("迷宮入口n");printf("");for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+) if(mazeij=0) printf(""); if(mazeij=1) printf("");printf("迷宮出口n");void result_maze(int m,int n)int i,j;printf("迷宮通路(用表示)如下所示：nt");for(i=0;

22、i<m;i+)printf("n"); for(j=0;j<n;j+) if(mazeij=0|mazeij=2) printf(""); if(mazeij=1) printf(""); if(mazeij=3) printf(""); void enqueue(struct point p)queuetail=p;tail+;struct point dequeue()head+;return queuehead-1;int is_empty()return head=tail;void visit

23、(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int maze4141,int m,int n)X=1;struct point p=0,0,-1;if(mazep.rowp.col=1)printf("n=n");printf("此迷宮無(wú)解nn");X=0;return 0;mazep.rowp.col=2;enqueue(p);while(!is_empty()p=de

24、queue();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<m)&&(mazep.row+1p.col=0) visit(p.row+1,p.col,maze);if(p.col-1>=0)&&(mazep.rowp.col-1=0) visit(p.row,p.col-1,maze);if(p.row-1>=0)&&(maz

25、ep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&&p.col=n-1)printf("n=n");printf("迷宮路徑為：n");printf("(%d,%d)n",p.row,p.col);mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor;printf("(%d,%d)n",p.row,p.col);mazep.rowp.col=3;else printf(

26、"n=n"); printf("此迷宮無(wú)解！nn");X=0;return 0;void main()int i,m,n,cycle=0;while(cycle!=(-1) printf("*n"); printf("t*歡迎使用迷宮模擬程序*n"); printf(" 設(shè)計(jì)者: 安徽工程大學(xué) n"); printf("*n"); printf(" 手動(dòng)生成迷宮 請(qǐng)按：1n"); printf(" 自動(dòng)生成迷宮 請(qǐng)按：2n"); pri

27、ntf(" 退出 請(qǐng)按：3nn"); printf("*n"); printf("n"); printf("請(qǐng)選擇你的操作：n"); scanf("%d",&i); switch(i) case 1:printf("n請(qǐng)輸入行數(shù)：");scanf("%d",&m); printf("n"); printf("請(qǐng)輸入列數(shù)：");scanf("%d",&n); while(m<=0|m>39)|(n<=0|n>39) printf("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請(qǐng)重新輸入：nn"); printf("請(qǐng)輸入行數(shù)：");scanf("%d",&m); printf("n"); printf("請(qǐng)輸入列數(shù)：");scanf("%d"