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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課題名稱： 迷 宮 求解 姓 名： 馬 兆 瑞 學(xué) 號： 200903021071 專 業(yè)： 電子信息科學(xué)與技術(shù) 班 級： 信息09-2班 指導(dǎo)教師： 侯 瑞 蓮 目 錄第一部分 引言3第二部分 課程設(shè)計(jì)報(bào)告3第一章 課程設(shè)計(jì)目的3第二章 課程設(shè)計(jì)內(nèi)容和要求42.1 問題描述42.2 設(shè)計(jì)要求4第三章 課程設(shè)計(jì)總體方案及分析43.1 問題分析43.2 概要設(shè)計(jì)73.3 詳細(xì)設(shè)計(jì)73.4 調(diào)試分析103.5 測試結(jié)果103.6 參考文獻(xiàn)12第三部分 課程設(shè)計(jì)總結(jié)13附錄(源代碼)14第一部分 引言數(shù)據(jù)結(jié)構(gòu)是一門理論性強(qiáng)、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)

2、課之間的橋梁。該課程的先行課程是計(jì)算機(jī)基礎(chǔ)、程序設(shè)計(jì)語言、離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程等。 通過本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問題的能力，而且該課程的研究方法對我們學(xué)生在校和離校后的學(xué)習(xí)和工作，也有著重要的意義。數(shù)據(jù)結(jié)構(gòu)是電子信息科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問題的能力。對于現(xiàn)實(shí)世界中的問題，應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)

3、模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最后獲得問題的解答。基于此原因，暑期我們開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)。針對數(shù)據(jù)結(jié)構(gòu)課程的特點(diǎn)，著眼于培養(yǎng)我們的實(shí)踐能力。實(shí)習(xí)課程是為了加強(qiáng)編程能力的培養(yǎng)，鼓勵(lì)學(xué)生使用新興的編程語言。相信通過數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐，無論是理論知識，還是實(shí)踐動(dòng)手能力，同學(xué)們都會(huì)有不同程度上的提高。第二部分 課程設(shè)計(jì)報(bào)告第一章 課程設(shè)計(jì)目的僅僅認(rèn)識到隊(duì)列是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使學(xué)生深入了解隊(duì)列的特征，以便在實(shí)際問題背景下靈活運(yùn)用它，同時(shí)還將鞏固這種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法第二章 課程設(shè)計(jì)內(nèi)容和要求 2.1問

4、題描述： 迷宮問題是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對同一只老鼠重復(fù)進(jìn)行上述實(shí)驗(yàn)，一直到老鼠從入口走到出口，而不走錯(cuò)一步。老鼠經(jīng)過多次試驗(yàn)最終學(xué)會(huì)走通迷宮的路線。設(shè)計(jì)一個(gè)計(jì)算機(jī)程序?qū)θ我庠O(shè)定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。 圖A2.2設(shè)計(jì)要求：要求設(shè)計(jì)程序輸出如下：(1) 建立一個(gè)大小為mn的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動(dòng)生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（

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

6、0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。3.迷宮路徑的搜索：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動(dòng)到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個(gè)相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo)記為2，同時(shí)保留搜索痕跡，在考慮進(jìn)入下一個(gè)位置搜索之前，將當(dāng)前位置保存在一個(gè)隊(duì)列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往

7、出口的路徑，則表明不存在從入口到出口的路徑。這實(shí)現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。以矩陣 0 0 1 0 1 為例，來示范一下 1 0 0 1 0 1 0 0 0 1 0 0 1 0 0 首先，將位置(0,0)(序號0)放入隊(duì)列中，其前節(jié)點(diǎn)為空，從它開始搜索，其標(biāo)記變?yōu)?，由于其只有一個(gè)非障礙位置，所以接下來移動(dòng)到(0,1)(序號1)，其前節(jié)點(diǎn)序號為0，標(biāo)記變?yōu)?，然后從(0,1)移動(dòng)到(1,1)(序號2)，放入隊(duì)列中，其前節(jié)點(diǎn)序號為1，(1,1)存在(1，2)(序號3)、(2，1)(序號4)兩個(gè)可移動(dòng)位置，其前節(jié)點(diǎn)序號均為2.對于每一個(gè)非障礙位置，它的相鄰非障礙節(jié)點(diǎn)均入隊(duì)

8、列，且它們的前節(jié)點(diǎn)序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點(diǎn)的位置，逆序就可以找到其從出口到入口的通路。如下表所示： 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) 搜索算法流程圖如下所示： 3.2 概要設(shè)計(jì)1.構(gòu)建一個(gè)二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣自動(dòng)或手動(dòng)生成迷宮，即為二維數(shù)組mazeM+2N+2賦值構(gòu)建一個(gè)隊(duì)列用于存儲迷宮路

9、徑建立迷宮節(jié)點(diǎn)struct point,用于存儲迷宮中每個(gè)節(jié)點(diǎ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)訪問節(jié)點(diǎn) visit()(10)搜索迷宮路徑 mgpath()3.3 詳細(xì)設(shè)計(jì)實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型及操作的

10、偽代碼算法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()產(chǎn)生的隨機(jī)數(shù)是從0到RAND_MAX,R

11、AND_MAX是定義在stdlib.h中的,其值至少為32767),要產(chǎn)生從X到Y(jié)的數(shù),只需要這樣寫：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(struct point p)head+,返回que

12、head-1判斷隊(duì)列是否為空int is_empty()返回head=tail的值，當(dāng)隊(duì)列為空時(shí)，返回0訪問迷宮矩陣中節(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)以被訪問過;調(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開始訪問。如果入口處即為障礙，則此迷宮無解，返回0

13、，程序結(jié)束。否則訪問入口節(jié)點(diǎn)，將入口節(jié)點(diǎn)標(biāo)記為訪問過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,說明未到迷宮右邊界，且其右方有通路,則visit(p.row,p.col+1,maze),將右邊節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問如果p.row+10且mazep.rowp.col-1=0,說明未到迷宮左邊界，且其左方有通路,則visit(p.row

14、,p.col-1,maze),將左方節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問如果p.row-10且mazep.row-1p.col=0,說明未到迷宮上邊界，且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點(diǎn)入隊(duì)標(biāo)記已訪問訪問到出口(找到路徑)即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; 最后將路徑圖形打印出來。3.菜單選擇 while(cycle!=(-1) 手動(dòng)生成迷宮 請按：1 自動(dòng)生成迷宮 請按：2 退

15、出 請按：3 scanf(%d,&i); switch(i) case 1：請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入) shoudong_maze(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n);case 2 ：請輸入行列數(shù)(如果超出預(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;注：具體源代碼見附錄3.4 調(diào)試分析 在調(diào)

16、試過程中，首先使用的是棧進(jìn)行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法3.5 測試結(jié)果 1.手動(dòng)輸入迷宮 2.自動(dòng)生成迷宮3.6 參考文獻(xiàn) 【1】 嚴(yán)蔚敏 吳偉民 數(shù)據(jù)結(jié)構(gòu)(C語言版) 清華大學(xué)出版社， 2009年9月 【2】 譚浩強(qiáng) C程序設(shè)計(jì)(第三版) 清華大學(xué)出版社 2009年1月第三部分 課程設(shè)計(jì)總結(jié)通過這段時(shí)間的課程設(shè)計(jì)，本人對計(jì)算機(jī)的應(yīng)用，數(shù)據(jù)結(jié)構(gòu)的作用以及C語言的使用都有了更深的了解。尤其是C語言的進(jìn)步讓我深刻的感受到任何所學(xué)的知識都需要實(shí)踐，沒有實(shí)踐就無法真正理解這些知識以及掌握它們，使其成為自己的財(cái)富。在理論學(xué)習(xí)和上機(jī)實(shí)踐的各個(gè)環(huán)節(jié)中，通過自主學(xué)習(xí)

17、和請教老師，我收獲了不少。當(dāng)然也遇到不少的問題，也正是因?yàn)檫@些問題引發(fā)的思考給我?guī)Я耸斋@。從當(dāng)初不喜歡上機(jī)寫程序到現(xiàn)在能主動(dòng)寫程序，從當(dāng)初拿著程序不只如何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識解決實(shí)際問題的轉(zhuǎn)變，我發(fā)現(xiàn)無論是專業(yè)知識還是動(dòng)手能力，自己都有很大程度的提高。在這段時(shí)間里，我對for、while等的循環(huán)函數(shù)用法更加熟悉，逐漸形成了較好的編程習(xí)慣。在老師的指導(dǎo)幫助下，同學(xué)們課余時(shí)間的討論中，這些問題都一一得到了解決。在程序的調(diào)試能力上，無形中得到了許多的提高。例如：頭文件的使用，變量和數(shù)組的范圍問題，定義變量時(shí)出現(xiàn)的問題等等。在實(shí)際的上機(jī)操作過程中，不僅是讓我們了解數(shù)據(jù)結(jié)構(gòu)的理論知

18、識，更重要的是培養(yǎng)解決實(shí)際問題的能力，所以相信通過此次實(shí)習(xí)可以提高我們分析設(shè)計(jì)能力和編程能力，為后續(xù)課程的學(xué)習(xí)及實(shí)踐打下良好的基礎(chǔ)。在這次短短的課程實(shí)踐里，我們得到了侯瑞蓮老師的關(guān)心和幫助。她給了我們很多的信息，與我們一起探討問題，詢問我們遇到了哪些問題并耐心給予指導(dǎo)。當(dāng)我們遇到技術(shù)上難以解決的問題時(shí)，她就會(huì)指導(dǎo)我們解決問題，她把自己多年來積累的經(jīng)驗(yàn)教授給我們，使我們順利地完成了課程實(shí)踐任務(wù)。時(shí)間過得真快，大學(xué)生活不知不覺就走過了一年，一年的大學(xué)學(xué)習(xí)和課程實(shí)踐階段的提高，使我們本身知識得到提高的同時(shí)，也增強(qiáng)了我們對未來工作的信心，我們相信自己未來三年的學(xué)習(xí)更使我們有能力勝任將來的工作。附錄：#

19、includestdlib.h#includestdio.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(請按行輸入迷宮，0表示通路，1表示障礙:nn);for(i=0;im;i+)for(j=0;jn;j+) scanf(%d,&mazeij);void zidong_maze(int m,int n)int i

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

21、mazeij=0) printf(); if(mazeij=1) printf();printf(迷宮出口n);void result_maze(int m,int n)int i,j;printf(迷宮通路(用表示)如下所示：nt);for(i=0;im;i+)printf(n); for(j=0;jn;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 deque

22、ue()head+;return queuehead-1;int is_empty()return head=tail;void visit(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(此迷宮無解nn);X=0;return 0;maz

23、ep.rowp.col=2;enqueue(p);while(!is_empty()p=dequeue();if(p.row=m-1)&(p.col=n-1) break;if(p.col+1n)&(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)&(mazep.row-1p.col=0) visit(p.row-1,p.col,maze);if(p.row=m-1&p.col=n-1)printf(n=

24、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(n=n); printf(此迷宮無解！nn);X=0;return 0;void main()int i,m,n,cycle=0;while(cycle!=(-1) printf(*n); printf( 歡迎進(jìn)入迷宮求解系統(tǒng)n); printf( 設(shè)計(jì)者:馬兆瑞（信息09-2班）n); printf(*n); printf( 手動(dòng)生成迷宮 請按：1n); printf( 自動(dòng)生成迷宮 請按：2n); printf( 退出 請按：3nn); printf(*n); printf(n); printf(請選擇你的操作：n); scanf(%d,&i); switch(i) case 1:printf(n請輸入行數(shù)：);scanf(%d,&m); pri