數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-迷宮問題的操作要點教學(xué)教材

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

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

3、經(jīng)過多次試驗最終學(xué)會走通迷宮的路線。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的矩 形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。圖A2.2 設(shè)計要求：要求設(shè)計程序輸出如下：（1）建立一個大小為mxn的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生 成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點的坐標(biāo)：(3)用一種標(biāo)志(如數(shù)字8)在迷宮中標(biāo)出該條通路；(4)在屏幕上輸出迷宮和通路；(5)上述功能可用菜單選擇。3.課程設(shè)計總體方案及分析3.1 問題分析：1 .迷宮的建立：迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示

4、障礙， 這樣迷宮就可以用0、1矩陣來描述，2 .迷宮的存儲：迷宮是一個矩形區(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, 當(dāng)然，用戶也可根據(jù)需要，調(diào)整其大小。3 .迷宮路徑的搜索：首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜 索工作

5、結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動 到該位置，然后再從該位置開始搜索通往出口的路徑； 若是障礙就選擇另一個相 鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標(biāo) 記為2,同時保留搜索痕跡，在考慮進(jìn)入下一個位置搜索之前，將當(dāng)前位置保存 在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。 這實現(xiàn)的是廣度優(yōu)先遍歷的算法， 如果 找到路徑，則為最短路徑。以矩陣0 010 1為例，來示范一下首先，將位置(0,0)(序號0)放入隊列中，其前節(jié)點為空，從它開始搜索，其 標(biāo)記變?yōu)?,由于其只有一個非障礙位

6、置，所以接下來移動到(0,1)(序號1),其前 節(jié)點序號為0,標(biāo)記變?yōu)?,然后從(0,1)移動到(1,1)(序號2),放入隊列中，其前 節(jié)點序號為1, (1,1)存在(1, 2)(序號3)、(2, 1)(序號4)兩個可移動位置,其前節(jié) 點序號均為2.對于每一個非障礙位置，它的相鄰非障礙節(jié)點均入隊列，且它們的 前節(jié)點序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點的位置，逆 序就可以找到其從出口到入口的通路。如下表所示：0910(0,0)(0,1)(3,4)-101212345678(1,1)(1,2)(2,1)(2,2)(1,3)(2,3)(0,3)(3,3)2 3 4 56 7 9由此

7、可以看出，得到最短路徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)搜索算法流程圖如下所示判斷隊列否為空存在山路地跳存在通路切斷.濘書菱短一傳為通路迷盛路由算法流程圖:將(0,0)入隊列檔隊頭出隊存:儲節(jié)點.將節(jié)點點隊冽3.2概要設(shè)計1.構(gòu)建一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣自動或手動生成迷宮，即為二維數(shù)組 mazeM+2N+2賦值構(gòu)建一個隊列用于存儲迷宮路徑建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況實現(xiàn)搜索算法屏幕上顯示操作菜單2.本程序包含10個函數(shù):主函數(shù)main()(2)手動生成迷宮函數(shù) shoudong_m

8、aze()1 T行鼾迷宜加樣;束 無解迷宮(3)自動生成迷宮函數(shù)zidong_maze()將迷宮打印成圖形print_maze()(5)打印迷宮路徑(若存在路徑)result_maze()(6)入隊 enqueue。出隊dequeue。(8)判斷隊列是否為空is_empty()(9)訪問節(jié)點visit()(10)搜索迷宮路徑 mgpath()3.3詳細(xì)設(shè)計實現(xiàn)概要設(shè)計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法1 .節(jié)點類型和指針類型迷宮矩陣類型：int mazeM+2N+2;為方便操作使其為全局變量迷宮中節(jié)點類型及隊列類型：struct pointint row,col,predecessor q

9、ue5122 .迷宮的操作(1)手動生成迷宮void shoudong_maze(int m,int n)定義i,j為循環(huán)變量for(i=m)for(j=n)輸入mazeij的值(2)自動生成迷宮void zidong_maze(int m,int n)定義i,j為循環(huán)變量for(i=m)for(j=n)mazeij=rand()%2 由于 rand()產(chǎn)生的隨機數(shù)是從 0 到 RAND_MAX,RAND_MAX 是定義在stdlib.h中的，具值至少為32767)，要產(chǎn)生從X 到Y(jié)的數(shù)，只需要這樣寫：k=rand()%(Y-X+1)+X;(3)打印迷宮圖形void print_maze(in

10、t m,int n)用i,j循環(huán)變量，將mazeij輸出 口、打印迷宮路徑void result_maze(int m,int n)用i,j循環(huán)變量，將mazeij輸出 口、(5)搜索迷宮路徑迷宮中隊列入隊操作void enqueue(struct point p)將p放入隊尾，tail+迷宮中隊列出隊操作struct point dequeue(struct point p)head+,返回 quehead-1判斷隊列是否為空int is_empty()返回head=tail的值，當(dāng)隊列為空時，返回 0訪問迷宮矩陣中節(jié)點void visit(int row,int col,int maze4

11、141)建立新的隊列節(jié)點 visit_point,將其值分別賦為 row,col,head-1,mazerowcol=2, 表示該節(jié)點以被訪問過；調(diào)用enqueue(visit_point)將該節(jié)點入隊路徑求解void mgpath(int maze4141,int m,int n)先定義入口節(jié)點為struct point p=0,0,-1,從maze00開始訪問。如果入口處即 為障礙，則此迷宮無解，返回 0 ,程序結(jié)束。否則訪問入口節(jié)點，將入口節(jié)點 標(biāo)記為訪問過mazep.rowp.col=2,調(diào)用函數(shù)enqueue(p)等該節(jié)點入隊。判斷隊列是否為空，當(dāng)隊列不為空時，則運行以下操作：調(diào)用d

12、equeue(兩數(shù)，將隊頭元素返回給p,如果p.row=m-1且p.col=n-1,即到達(dá)出口節(jié)點，即找到了路徑，結(jié)束如果p.col+1n H mazep.rowp.col+1=0，說明未到迷宮右邊界，且其右方有通路，則visit(p.row,p.col+1,maze),將右邊節(jié)點入隊標(biāo)記已訪問如果p.row+10且mazep.rowp.col-1=0，說明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze),將左方節(jié)點入隊標(biāo)記已訪問如果p.row-10且mazep.row-1p.col=0，說明未到迷宮上邊界，且其上方有通路，則visit(p.row,p.co

13、l+1,maze),將上方節(jié)點入隊標(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)手動生成迷宮請按：1 自動生成迷宮 請按：2退出請按：3scanf(%d,&i);switch(i) case 1：請輸入行列數(shù)(如果超出預(yù)設(shè)范圍則提示重新輸入)shoudong_maze(m,n);print_maze(m,n);mg

14、path(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)試過程中，首先使用的是棧進(jìn)行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法3.5 測試結(jié)果1.手動輸入迷宮1C= Documents and SettinfsneT：MDebuCppl. e

15、sc,歡迎進(jìn)入迷宮求解系統(tǒng)ft1宮宮 迷迷 成成 生生 動動出44請輸入列數(shù)f 4抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍西7購7”.請重新輸入：請輸入行數(shù):4請輸入列數(shù)，q 清按行輸入迷宮.0表示通路，士表示障礙士B 0 1 16 1 ail 0 0 0D:VCMicrosoft Visual Stud。程的DebugNUM2.exe，請輸入行數(shù)，44清輸入列數(shù)：4根歌，你輸入的行列數(shù)超出預(yù)設(shè)范田(日-39.酎39),請我新約久:請輸入行數(shù)：*情輸入列數(shù)；， 請按行輸入迷宮.。表示逋路 1衣示障礙:g g e 10 10 1e e 1 1b Q 0 oa宮生成結(jié)果如下：1宮入口4 口 口 口口口口一

16、迷宮出口 迷宮路徑為：(3.3)(3.2)(3,1)(2,1)(2.0)(1曾)(0.8)迷宮通路(用表示)如下所示: ri -口 夕?nPres Enter Contiue!搜狗拼音輸入法全2自動生成迷宮:flD VCM crosoft Visual Stud oJDebugNUM2 exe-MM X# MR司君 RM R 網(wǎng) MH 網(wǎng)燈網(wǎng)餐內(nèi)同H M HHRH FH R M RM fl F MW歡迎進(jìn)入迷宮求解系統(tǒng)設(shè)計者:付與龍于物生成迷宮 臺防生成迷宮退出技技技吉青春，JTI 1 =12 3rc&s. Enter Centiut*物爐音詁入法金門4 .設(shè)計體會通過本次的課程設(shè)計，使我學(xué)會

17、了如何去組織代碼量較大大程序。 與此同時， 也使我學(xué)會了一些對代碼量較大的的程序進(jìn)行編寫、 連接、編譯運行、以及調(diào)試 和修改的技巧這次的課程設(shè)計涉及到編程語言和數(shù)據(jù)結(jié)構(gòu)的知識，要求和平時的實比相對 較高。從本次的課程設(shè)計可以檢驗我們對 C語言和數(shù)據(jù)結(jié)構(gòu)的掌握情況，同時也 檢驗了我們對所學(xué)習(xí)過的知識的靈活運用情況。 在創(chuàng)新性方面，這次的課程設(shè)計 雖然完成了課程設(shè)計的任務(wù)，但是缺乏創(chuàng)造性的設(shè)計思想，在以后的學(xué)習(xí)過程中 還得繼續(xù)努力。5 .參考文獻(xiàn)1 .嚴(yán)蔚敏編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，20022 .朱戰(zhàn)立.編著.數(shù)據(jù)結(jié)構(gòu)一一使用C語言.西安交通大學(xué)出版社，20043 .朱戰(zhàn)立，張選

18、平編著.數(shù)據(jù)機構(gòu)學(xué)習(xí)指導(dǎo)和典型題解.西安交通大學(xué)出版社,20024 .蘇小紅，孫志崗等編著.C語言大學(xué)實用教程（第2版）.電子工業(yè)出版社,20085 .梁肇新編著.編程高手箴言.電子工業(yè)出版社，2003附件：#includestdlib.h#includest dio.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

19、(請按行輸入迷宮，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,j;printf(n迷宮生成中nn);system(pause);for(i=0;im;i+)for(j=0;jn;j+)mazeij=rand()%2;由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX/RAND_MAX 是定義在 stdlib.h中的淇值至少為 32767)/要產(chǎn)生從 X到Y(jié)的數(shù)，只需要這樣寫：k=rand()%(Y-X+1)+X;void print_maze(

20、int m,int n)int i,j；printf(n迷宮生成結(jié)果如下：nn);printf(迷宮入口 n);printf( J );for(i=0;im;i+)printf(n);for(j=0;jn;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;im;i+)printf(n);for(j=0;jn;j+)if(mazeij=0|mazeij=2) printf( );

21、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(int row,int col,int maze4141)struct point visit_point=row,col,head-1;mazerowcol=2;enqueue(visit_point);int mgpath(int m

22、aze4141,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;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.

23、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=An);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;return 0;void main()int i,m,n,cycle=0;while(cycle!=(-1)printf(*n);printf(歡迎進(jìn)入迷宮求解系統(tǒng)printf(”*n);printf(printf(printf( 手動生成迷宮 請按: 自動生成迷宮 請按: 退出請按:n);1n);2n);3nn);printf(”*”*n);printf(n);printf(請選擇你的操作：n);scanf(%d,&i);switch(i)case 1:printf(n請輸入行數(shù)：);sca