迷宮問題求解

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

2、73.3調試分析3.4測試結果10第三章設計總結134.1課程設計總結134.2參考文獻4.3附錄源代碼14第二局部課程設計報告第一章課程設計內容和要求2.1問題描述：迷宮以16*16的矩陣存儲在數(shù)據(jù)文件中迷宮中的障礙物要占到一定比例,編寫非遞歸的程序,求出一條從入口到出口的路徑并顯示之結果假設能用C的繪圖函數(shù)顯示更好2.2需求分析：1 .要求設計程序輸出如下：101建立一個大小為mxn的任意迷宮迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成,并在屏幕上顯示出來；2找出一條通路的二元組i,j數(shù)據(jù)序列,i,j表示通路上某一點的坐標.3用一種標志如數(shù)字8在迷宮中標出該條通路；4在屏幕上輸出迷宮和通路；5上述

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

4、從迷宮的入口開始,如果該位置就是迷宮出口,那么已經(jīng)找到了一條路徑,搜索工作結束.否那么搜索其上、下、左、右位置是否是障礙,假設不是障礙,就移動到該位置,然后再從該位置開始搜索通往出口的路徑； 假設是障礙就選擇另一個相鄰的位置,并從它開始搜索路徑.為預防搜索重復出現(xiàn),那么將已搜索過的位置標記為2,同時保存搜索痕跡,在考慮進入下一個位置搜索之前,將當前位置保存在一個隊列中,如果所有相鄰的非障礙位置均被搜索過,且未找到通往出口的路徑,那么說明不存在從入口到出口的路徑.這實現(xiàn)的是廣度優(yōu)先遍歷的算法,如果找到路徑,那么為最短路徑.以矩陣00101為例,來示范一下100102000100100首先,將位置

5、(0,0)(序號0)放入隊列中,其前節(jié)點為空,從它開始搜索,具標記變?yōu)?,由于其只有一個非障礙位置,所以接下來移動到(0,1)(序號1),其前節(jié)點序號為0,標記變?yōu)?,然后從(0,1)移動到(1,1)(序號2),放入隊列中,其前節(jié)點序號為1,(1,1)存在(1,2)(序號3)、(2,1)(序號4)兩個可移動位置,其前節(jié)點序號均為2.對于每一個非障礙位置,它的相鄰非障礙節(jié)點均入隊列,且它們的前節(jié)點序號均為該位置的序號,所以如果存在路徑,那么從出口處節(jié)點的位置,逆序就可以找到其從出口到入口的通路.如下表所示：012345678910(0,0)(0,1)(1,1)(1,2)(2,1)(2,2)(1,

6、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)搜索算法流程圖如下所示:迷宮路由算法流程圖:衡環(huán)結束無解迷宮將(0,0)入隊列第二章課程設計總體方案及分析3.1概要設計1.構建一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣自動或手動生成迷宮,即為二維數(shù)組mazeM+2N+2賦值構建一個隊列用于存儲迷宮路徑建立迷宮節(jié)點structpoint,用于存儲迷宮中每個節(jié)點的訪問情況實現(xiàn)搜索算法屏幕上顯示操作菜單3.本程序包含10個函數(shù)：(1)主函數(shù)main()(2)手動生成迷

7、宮函數(shù)shoudong_maze()(3)自動生成迷宮函數(shù)zidong_maze()(4)將迷宮打印成圖形print_maze()(5)打印迷宮路徑(假設存在路徑)result_maze()(6)入隊enqueue()出隊dequeue()(8)判斷隊列是否為空is_empty()(9)訪問節(jié)點visit()(10)搜索迷宮路徑mgpath()4 .2詳細設計實現(xiàn)概要設計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法1 .節(jié)點類型和指針類型迷宮矩陣類型：intmazeM+2N+2;為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型：structpointintrow,col,predecessorque

8、5122 .迷宮的操作(1)手動生成迷宮voidshoudong_maze(intm,intn)定義i,j為循環(huán)變量for(i=m)for(j=n)輸入mazeij的值(2)自動生成迷宮voidzidong_maze(intm,intn)定義i,j為循環(huán)變量for(i=m)for(j=n)mazeij=rand()%2由于rand()產生的隨機數(shù)是從0到RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產生從X到Y的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;(3)打印迷宮圖形voidprint_maze(intm,intn)用i,j循環(huán)變量

9、,將mazeij輸出口、打印迷宮路徑voidresult_maze(intm,intn)用i,j循環(huán)變量,將mazeij輸出口、東搜索迷宮路徑迷宮中隊列入隊操作voidenqueue(structpointp)將p放入隊尾,tail+迷宮中隊列出隊操作structpointdequeue(structpointp)head+,返回quehead-1判斷隊列是否為空intis_empty()返回head=tail的值,當隊列為空時,返回0訪問迷宮矩陣中節(jié)點voidvisit(introw,intcol,intmaze4141)建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,

10、head-1,mazerowcol=2,表示該節(jié)點以被訪問過；調用enqueue(visit_point),將該節(jié)點入隊路徑求解voidmgpath(intmaze4141,intm,intn)先定義入口節(jié)點為structpointp=0,0,-1,從maze00開始訪問.如果入口處即為障礙,那么此迷宮無解,返回0,程序結束.否那么訪問入口節(jié)點,將入口節(jié)點標記為訪問過mazep.rowp.col=2,調用函數(shù)enqueue(p)將該節(jié)點入隊.判斷隊列是否為空,當隊列不為空時,那么運行以下操作：調用dequeue()函數(shù),將隊頭元素返回給p,如果p.row=m-1且p.col=n-1,即到達出口

11、節(jié)點,即找到了路徑,結束如果p.col+1n且mazep.rowp.col+1=0,說明未到迷宮右邊界,且其右方有通路,那么visit(p.row,p.col+1,maze),將右邊節(jié)點入隊標記已訪問如果p.row+10且mazep.rowp.col-1=0,說明未到迷宮左邊界,且其左方有通路,那么visit(p.row,p.col-1,maze),將左方節(jié)點入隊標記已訪問如果p.row-10且mazep.row-1p.col=0,說明未到迷宮上邊界,且其上方有通路,那么visit(p.row,p.col+1,maze),將上方節(jié)點入隊標記已訪問訪問到出口(找到路徑)即p.row=m-1且p.

12、col=n-1,那么逆序將路徑標記為3即mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor;mazep.rowp.col=3;最后將路徑圖形打印出來3 .菜單項選擇擇while(cycle!=(-1)手動生成迷宮請按：1自動生成迷宮請按：2退出scanf(%d,&i);switch(i)case1:請輸入行列數(shù)(如果超出預設范圍那么提示重新輸入)shoudong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);case2:請輸入行列數(shù)(

13、如果超出預設范圍那么提示重新輸入)zidong_maze(m,n);print_maze(m,n);mgpath(maze,m,n);if(X!=0)result_maze(m,n);case3：cycle=(-1);break;注：具體源代碼見附錄請按:3.3調試分析(1)在調試過程中,首先使用的是棧進行存儲,但是產生的路徑是多條或不是最短路徑,所以通過算法比擬,改用此算法.(2)在編寫while語句時,另一種情況(即當前位置不能通過時)也同樣出現(xiàn)在墻節(jié)點就直接往南走的情況,綜合上面的情況,同樣的,也是退位沒有賦值.這種錯誤比擬難發(fā)現(xiàn),往往只有在復雜的迷宮求解過程中才能發(fā)現(xiàn).這類錯誤屬于邏輯

14、錯誤,調試不會顯示,需要自己拙句地查看和分析,并能充分的理解程序每一步的熟悉,才能發(fā)現(xiàn)并解決這樣的問題.(3)在編寫MazePath函數(shù)時,當遇到墻(即遇到下一位置為1)時,直接從現(xiàn)在墻位置進行往南跳轉.以至有許多應該走的通路位置沒有走,而且使總共走的步數(shù)變短.在測試前期怎么也想不明白,出棧操作也有,退位也有,但就是不進行退到上一位置的操作.最后發(fā)現(xiàn),少了一步把出棧的數(shù)進行賦值的操作.(4)在進行對迷宮的輸出時,變成按行輸出,得不到預期的迷宮結果,更不用說驗證其正確性.這就是粗心造成的.3.4測試結果1.手動輸入迷宮*D:lyDocumentsGTAViceCityUserFiles迷宮 tD

15、ebugCppl.已又 2“歡送進入迷宮求解系統(tǒng)設計者:馬兆瑞(信息9-2班)請選擇你的操作I1請輸入行數(shù)：44情輸入列數(shù),4123tfe請請請宮宮迷迷成成生生動動出iHE退歡送進入迷宮求解系統(tǒng)設計者:馬兆瑞信息的-2班2.自動生成迷宮退出動生成迷宮請校.1動生成迷宮請嗖：2請按.3第二局部設計總結4.1課程設計總結通過這次的數(shù)據(jù)結構課程設計讓我對計算機的應用,數(shù)據(jù)結構的作用以及c語言的使用都有了更深的理解.尤其是C語言的進步讓我深刻的感受到任何所學的知識都需要實踐,沒有實踐就無法真正理解這些知識以及掌握它們,使其成為自己的財富.在理論學習和上機實踐的各個環(huán)節(jié)中,通過自主學習和請教老師,我收獲

16、了不少.當然也遇到不少的問題,也正是由于這些問題引發(fā)的思考給我?guī)Я耸斋@.從當初不喜歡上機寫程序到現(xiàn)在能主動寫程序,從當初拿著程序不只如何下手到現(xiàn)在知道如何分析問題,如何用專業(yè)知識解決實際問題的轉變,我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力,自己都有很大程度的提升.在這段時間里,我對for、while等的循環(huán)函數(shù)用法更加熟悉,逐漸形成了較好的編程習慣.在老師的指導幫助下,同學們課余時間的討論中,這些問題都一一得到了解決.在程序的調試水平上,無形中得到了許多的提升.在實際的上機操作過程中,不僅是讓我們了解數(shù)據(jù)結構的理論知識,更重要的是培養(yǎng)解決實際問題的水平,譬如迷宮的實現(xiàn),面對問題時我學會了應該如何解決.

17、同時,也讓我對棧這一章節(jié)有更深的體會,以及用不同的方法解決問題相比擬得出較好的解決方案.數(shù)據(jù)結構課程設計的主要目的是介紹一些常用的數(shù)據(jù)結構,說明數(shù)據(jù)結構內在的邏輯關系,討論它們在計算機中的存儲表示,并結合各種數(shù)據(jù)結構,討論對他們實行的各種運算的實現(xiàn)算法.此次迷宮問題的求解及演示課程設計你在實際操作中也犯了很多錯誤,這些錯誤同時也讓我意外的收獲了很多.對我所學的數(shù)據(jù)結構知識理論也得到穩(wěn)固.通過實際的設計和分析,讓我學會了編程的根本步驟和方法,同時也開發(fā)了自己的邏輯思維水平,提升了解決問題的水平.在不斷的遇到問題,不斷的解決問題的過程中,培養(yǎng)的專業(yè)的思維是最重要的,也是這次課程設計所要到達的目的,

18、我很慶幸我做到了.4.2參考文獻【1】數(shù)據(jù)結構C語言版嚴蔚敏吳偉民編著清華大學出版社4.4.3 3 附錄(程序清單)：#includestdlib.h#includestdio.h#defineN39#defineM39intX;intmazeN+2M+2;structpointintrow,col,predecessor;queue512;inthead=0,tail=0;voidshoudong_maze(intm,intn)inti,j;printf(nn);printf(請按行輸入迷宮,0表示通路,for(i=0;im;i+)for(j=0;jn;j+)scanf(%d,&mazeij

19、);voidzidong_maze(intm,intn)system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;由于rand()產生的隨機數(shù)是從0到RAND./RAND_MAX是定義在stdlib.h中的,其值至少為32767)/要產生從X到Y的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;voidprint_maze(intm,intn)inti,j;printf(n迷宮生成結果如下：nn);printf(迷宮入口n);【2】數(shù)據(jù)結構(C語言版)秦鋒編者【3】C+程序設計杜茂康編者清華大學出版社清華大學出版社表示障礙：nn

20、);inti,j;printf(n迷宮生成中nn);MAXprintf(V);for(i=0;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0)printf(口)；if(mazeij=1)printf();printf(-迷宮出口n);voidresult_maze(intm,intn)inti,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

21、();voidenqueue(structpointp)queuetail=p;tail+;structpointdequeue()head+;returnqueuehead-1;intis_empty()returnhead=tail;voidvisit(introw,intcol,intmaze4141)structpointvisit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);intmgpath(intmaze4141,intm,intn)X=1;structpointp=0,0,-1;if(mazep.rowp.col

22、=1)printf(n=n);printf(此迷宮無解nn);X=0;return0;mazep.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.

23、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;elseprintf(n=n);printf(此迷宮無解！nn);X=0;return0;voidmain()inti,m,n,cycle=0;while(cycle!=(-1)printf(*設計者：安徽工程大學printf(t*歡送使用迷宮模擬程序*n);printf(printf(*n)；printf(n);printf(請選擇你的操作：n);scanf(%d,&i);switch(i)case1:printf(n請輸入行數(shù)：);scanf(%d,&m);printf(n);printf(請輸入列數(shù)：);scanf(%d,&n);while(m39)|(n39)printf(n抱歉,你輸入的行列數(shù)超出預設范圍(0-39,0-39),請重新輸入:printf(請輸入行數(shù)：);scanf