數(shù)據(jù)結構課程設計-迷宮問題的操作

1、課程設計說明書No. 23課程設計任務書專業(yè)計算機科學與技術班級姓名設計起止日期設計題目：迷宮問題的操作設計任務（主要技術參數(shù)）：學會運用數(shù)據(jù)結構建立迷宮問題，編造出迷宮并設計出走出迷宮的方法 硬件環(huán)境：處理器：英特爾 第三代酷睿i3-3110M 2.40GHz雙核內(nèi)存：4GB（三星 DDR3 1333MHz）主硬盤：希捷 ST500LM012 HN-M500MBB （500GB/5400 轉/分） 顯示器：三星 SEC3649（14英寸）軟件環(huán)境：操作系統(tǒng)： Win dows 8 64位（DirectX 11）開發(fā)環(huán)境：VC+6.0指導教師評語：成績：簽字：年 月日1、課程設計目的為了配合數(shù)

2、據(jù)結構課程的開設，通過設計一完整的程序，掌握數(shù)據(jù) 結構的應用、算法的編寫、類C語言的算法轉換成C程序并用TC上機調(diào)試的基本 方法特進行題目為兩個鏈表合并的課程設計。 通過此次課程設計充分鍛煉有關數(shù) 據(jù)結構中鏈表的創(chuàng)建、合并等方法以及怎樣通過轉化成 C語言在微機上運行實現(xiàn) 等其他方面的能力。2. 課程設計的內(nèi)容與要求2.1問題描述：迷宮問題是取自心理學的一個古典實驗。 在該實驗中，把一只老鼠從一個無頂大 盒子的門放入，在盒子中設置了許多墻，對行進方向形成了多處阻擋。盒子僅有 一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。 對 同一只老鼠重復進行上述實驗，一直到老鼠從入口走到

3、出口，而不走錯一步。老 鼠經(jīng)過多次試驗最終學會走通迷宮的路線。設計一個計算機程序對任意設定的矩 形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結論。出口 *入口+4*PP衛(wèi)aP口dP£P+J££t3圖A2.2設計要求：要求設計程序輸出如下：（1）建立一個大小為m x n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生 成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點的坐標。(3) 用一種標志(如數(shù)字8)在迷宮中標出該條通路；(4) 在屏幕上輸出迷宮和通路；(5) 上述功能可用菜單選擇。3. 課程設計

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

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

6、1 0 0 1 0首先，將位置（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é)點序號均為該位置的序號， 序就可以找到其從出口到入口的通路如卜表所示：0123910(0,0) (0,1)(1,1)(1

7、,2)(2,1)(3,4)-10 122 3456 7由此可以看出，得到最短路徑:搜索算法流程圖如下所示45678(2,2)(1,3)(2,3)(0,3)(3,3)9(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)左邊辿存在迷迪谿Y亍II達下邊上邊將(0,0)入趴列痔隊頭岀隊1 T冇斛迷宮存儲勒戊.將巧點入隊列3.2概要設計1構建一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣 自動或手動生成迷宮，即為二維數(shù)組mazeM+2N+2賦值 構建一個隊列用于存儲迷宮路徑 建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況 實現(xiàn)搜索算法 屏幕上顯示操

8、作菜單2. 本程序包含10個函數(shù)：主函數(shù)main()(2)手動生成迷宮函數(shù) shoudo ng_maze()(3)自動生成迷宮函數(shù)zido ng_maze()將迷宮打印成圖形prin t_maze()打印迷宮路徑(若存在路徑)result_maze()(6) 入隊 enqueue()出隊dequeue。(8) 判斷隊列是否為空is_empty()(9) 訪問節(jié)點visit()(10) 搜索迷宮路徑 mgpath()3.3詳細設計實現(xiàn)概要設計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法1. 節(jié)點類型和指針類型迷宮矩陣類型：int mazeM+2N+2;為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型：

9、struct poi nt in t row,col,predecessor que5122. 迷宮的操作(1) 手動生成迷宮void shoudo ng_maze(i nt m,i nt n)定義i,j為循環(huán)變量for(i<=m)for(jv=n)輸入mazeij的值(2) 自動生成迷宮void zid on g_maze(i nt m,i nt n)定義i,j為循環(huán)變量for(i<=m)for(jv=n)mazeij=ra nd()%2/由于 ran d()產(chǎn)生的隨機數(shù)是從 0 到RAND_MAX,RAND_MAX 是定義在stdlib.h中的，其值至少為32767)要產(chǎn)生從X

10、 到丫的數(shù)，只需要這樣寫：k=rand()%(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輸出 、 搜索迷宮路徑 迷宮中隊列入隊操作void enq ueue(struct point p)將p放入隊尾，tail+ 迷宮中隊列出隊操作struct point dequeue(struct point p)head+,返回 quehead-1 判斷隊列是否為空int is_empty()返回head=ta

11、il的值，當隊列為空時，返回 0 訪問迷宮矩陣中節(jié)點void visit(i nt row,i nt col,i nt maze4141)建立新的隊列節(jié)點 visit_poi nt,將其值分別賦為 row,col,head-1,mazerowcol=2, 表示該節(jié)點以被訪問過；調(diào)用enqueue(visit_point)將該節(jié)點入隊 路徑求解void mgpath(i nt maze4141,i nt m,i nt n)先定義入口節(jié)點為struct point p=0,0,-1,從maze00開始訪問。如果入口處即 為障礙，貝U此迷宮無解，返回0，程序結束。否則訪問入口節(jié)點，將入口節(jié)點標記為訪

12、問過mazep.rowp.col=2,調(diào)用函數(shù)enqueue(p將該節(jié)點入隊。判斷隊列是否為空，當隊列不為空時，則運行以下操作：調(diào)用dequeue(函數(shù)，將隊頭元素返回給p,如果p.row=m-1且p.col=n-1,即到達出口節(jié)點，即找到了路徑，結束如果p.col+1<n且mazep.rowp.col+1=0,說明未到迷宮右邊界，且其右方有通路，則visit(p.row,p.col+1,maze)，將右邊節(jié)點入隊標記已訪問如果p.row+1<m且mazep.row+1p.col=0,說明未到迷宮下邊界，且其下方有通路，則visit(p.row+1,p.col,maze)，將下方節(jié)

13、點入隊標記已訪問如果p.col-1>0且mazep.rowp.col-1=0,說明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze)將左方節(jié)點入隊標記已訪問如果p.row-1>0且mazep.row-1p.col=0,說明未到迷宮上邊界，且其上方有通路，則visit(p.row,p.col+1,maze)將上方節(jié)點入隊標記已訪問訪問到出口(找到路徑)即p.row=m-1且p.col=n-1,則逆序將路徑標記為3即mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.

14、rowp.col=3;最后將路徑圖形打印出來。3. 菜單選擇while(cycle!=(-1)手動生成迷宮請按：1 自動生成迷宮請按：2退出請按：3sca nf("%d",&i);switch(i) case 1：請輸入行列數(shù)(如果超出預設范圍則提示重新輸入)shoudo ng_maze( m,n);prin t_maze( m,n);mgpath(maze,m, n);if(X!=0) result_maze( m,n);case 2 :請輸入行列數(shù)(如果超出預設范圍則提示重新輸入)zido ng_maze( m,n);prin t_maze( m,n);mgpa

15、th(maze,m, n);if(X!=0) result_maze(m, n);case 3 cycle=(-1); break;注：具體源代碼見附錄3.4調(diào)試分析在調(diào)試過程中，首先使用的是棧進行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法3.5測試結果1手動輸入迷宮g Documents and SettinsneT：SiDebu£Cppl. ese*44請輸入列數(shù) 4次迎進入迷宮求解系統(tǒng)宮宮 迷迷 成成 生生 動動岀I 請請請抱歉，你輸入的行列數(shù)超出預i殳范E <0-39,0-395,請重新輸入:請輸入行數(shù)，青按行輸入謹宮円0表示通路，：L表示障

16、礙匕B 0 1 16 1 ail 0 0 02自動生成迷宮:"D:VCMicrosoft Visual Stud oVTjDebugXNUMZ exe'MM fl P MR 肩貳甩旺鼻貳武制 RM R 輕 RHH MFH R M RM fl F MWl<-RRH：ne Mm ft M-RA 覺肌弭矗 9RM 民 M ft-ft #fr H MR MMS4RN1HMmH RM: H :M RM » 料 fftrt 砸屛理昇覺 MLR M ft-MJt H fl ¥4 9< M：M>t Pt 豪 VtM 骨豪 MR % 弭 Z 囂豐 f送宮出

17、口rc&s. Enter Centiue»歡迎逬入迷宮求解梟統(tǒng)設計者：付考龍wwmI1J . IB- IIk4. 設計體會通過本次的課程設計，使我學會了如何去組織代碼量較大大程序。 與此同時， 也使我學會了一些對代碼量較大的的程序進行編寫、 連接、編譯運行、以及調(diào)試 和修改的技巧這次的課程設計涉及到編程語言和數(shù)據(jù)結構的知識，要求和平時的實比相對 較高。從本次的課程設計可以檢驗我們對 C語言和數(shù)據(jù)結構的掌握情況，同時也 檢驗了我們對所學習過的知識的靈活運用情況。 在創(chuàng)新性方面，這次的課程設計 雖然完成了課程設計的任務，但是缺乏創(chuàng)造性的設計思想，在以后的學習過程中 還得繼續(xù)努力。

18、5. 參考文獻1 .嚴蔚敏編著.數(shù)據(jù)結構（C語言版）清華大學出版社，20022 .朱戰(zhàn)立.編著.數(shù)據(jù)結構一一使用C語言.西安交通大學出版社，20043 .朱戰(zhàn)立，張選平編著.數(shù)據(jù)機構學習指導和典型題解.西安交通大學出版社,20024 .蘇小紅，孫志崗等編著.C語言大學實用教程（第2版）.電子工業(yè)出版社,2008.梁肇新編著.編程高手箴言.電子工業(yè)出版社，2003附件：#i nclude"stdlib.h"#include"st dio.h"#defi ne N 39#defi ne M 39int X;int mazeN+2M+2;struct poi

19、ntint row,col,predecessor;queue512;int head=0,tail=0;void shoudo ng_maze(i nt m,i nt n)int i,j;prin tf("nn");printf("請按行輸入迷宮，0表示通路，1表示障礙:nn");for(i=0;i<m;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&quo

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

21、=0;i<m;i+)pri ntf("n ”);for(j=0;j< n;j+)if(mazeij=0) prin tf("");if(mazeij=1) pri ntf(" ");printf(" t迷宮出口 n”);void result_maze(i nt m,i nt n)int i,j;nt");口");printf("迷宮通路(用表示)如下所示:for(i=0;i<m;i+)pri ntf("n ”);for(j=0;j< n;j+) if(mazeij=0|

22、mazeij=2) pri ntf(" if(mazeij=1) prin tf("");if(mazeij=3) prin tf("");void enq ueue(struct point p)queuetail=p;tail+;struct 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,

23、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)prin tf("n=n ”);printf("此迷宮無解 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.co

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

25、w=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;elseprin tf("n=n");printf("此迷宮無解！ nn");X=0;retur

26、n 0;void mai n()int i,m ,n, cycle=0;while(cycle!=(-1) printf( *n")printf(”歡迎進入迷宮求解系統(tǒng)n");printf(*printf(”手動生成迷宮請按：1n");printf(”自動生成迷宮請按：2n");prin tf("退出請按：3nn");printf(*n")prin tf("n ”);printf("請選擇你的操作：n");scan f("%d", &i);switch(i)case

27、1:pri ntf("n 請輸入行數(shù)：");sca nf("%d", &m);prin tf("n ”);printf("請輸入列數(shù)：");scanf("%d",&n);while(m<=0|m>39)|( n<=0| n>39)printf("n抱歉，你輸入的行列數(shù)超出預設范圍(0-39,0-39),請重新輸入:printf("請輸入行數(shù)：");scanf("%d",&m);prin tf("n ”);printf("請輸入列數(shù)：");scanf("%d",&n);shoudo