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

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è)計目

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

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

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

5、路徑，搜索工作結(jié)束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復(fù)出現(xiàn)，則將已搜索過的位置標記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出口的路徑，則表明不存在從入口到出口的路徑。這實現(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)放入隊列中

6、，其前節(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é)點的位置，逆序就可以找到其從出口到入口的通路。如下表所示： 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,

7、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è)計1.構(gòu)建一個二維數(shù)組mazeM+2N+2用于存儲迷宮矩陣自動或手動生成迷宮，即為二維數(shù)組mazeM+2N+2賦值構(gòu)建一個隊列用于存儲迷宮路徑建立迷宮節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況實現(xiàn)搜索算法屏幕上顯示操作菜單 2.本程序包含10個函數(shù)： (1)主函數(shù) main()(2)手動生成迷宮函數(shù) shoudong_maze()(3)自動生成迷宮函數(shù) zidong_m

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

9、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(int m,int n)用i,j循

10、環(huán)變量，將mazeij輸出 、(4)打印迷宮路徑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的值，當隊列為空時，返回0訪問迷宮矩陣中節(jié)點void visit(int row,int col,int maze4141)建立新的隊列節(jié)點vis

11、it_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é)點標記為訪問過mazep.rowp.col=2,調(diào)用函數(shù)enqueue(p)將該節(jié)點入隊。判斷隊列是否為空，當隊列不為空時，則運行以下操作： 調(diào)用dequeue()函數(shù)，將隊頭元素返回給

12、p，如果p.row=m-1且p.col=n-1,即到達出口節(jié)點，即找到了路徑，結(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é)點入隊標記已訪問如果p.col-1>0且mazep.rowp.col-1=0,說明未到迷宮左邊界，且其左方有通路,則visit(p.row,p.col-1,maze

13、),將左方節(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,則逆序?qū)⒙窂綐擞洖?即mazep.rowp.col=3;while(p.predecessor!=-1)p=queuep.predecessor; mazep.rowp.col=3; 最后將路徑圖形打印出來。3.菜單選擇 while(cycle!=(-1) 手動生成迷宮 請按：1 自動生成迷宮 請按：2 退出 請按：3 sc

14、anf("%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

15、調(diào)試分析 在調(diào)試過程中，首先使用的是棧進行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法3.5 測試結(jié)果 1.手動輸入迷宮2自動生成迷宮：4設(shè)計體會 通過本次的課程設(shè)計，使我學(xué)會了如何去組織代碼量較大大程序。與此同時，也使我學(xué)會了一些對代碼量較大的的程序進行編寫、連接、編譯運行、以及調(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í)過程

16、中還得繼續(xù)努力。5參考文獻1.嚴蔚敏編著.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，20022.朱戰(zhàn)立. 編著.數(shù)據(jù)結(jié)構(gòu)使用C語言.西安交通大學(xué)出版社，20043.朱戰(zhàn)立，張選平編著.數(shù)據(jù)機構(gòu)學(xué)習(xí)指導(dǎo)和典型題解.西安交通大學(xué)出版社，20024.蘇小紅，孫志崗等編著.C語言大學(xué)實用教程（第2版）.電子工業(yè)出版社，20085.梁肇新編著.編程高手箴言.電子工業(yè)出版社，2003附件：#include"stdlib.h"#include"stdio.h"#define N 39#define M 39int X;int mazeN+2M+2;struct point

17、int 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;i<m;i+)for(j=0;j<n;j+) scanf("%d",&mazeij);void zidong_maze(int m,int n)int i,j;printf("n迷宮生成中nn");system(

18、"pause");for(i=0;i<m;i+)for(j=0;j<n;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(int m,int n)int i,j;printf("n迷宮生成結(jié)果如下:nn");printf("迷宮入口n");printf("");for(i=0;i<

19、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;i<m;i+)printf("n"); for(j=0;j<n;j+) if(mazeij=0|mazeij=2) pri

20、ntf(""); 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;mazerow

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

22、azep.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.row=m-1&&p.col=n-1)pr

23、intf("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("n=n"); printf("此迷宮無解！nn");X=0;return 0;void main()int i,

24、m,n,cycle=0;while(cycle!=(-1) printf("*n"); printf(" 歡迎進入迷宮求解系統(tǒng)n");printf("*n"); printf(" 手動生成迷宮 請按：1n"); printf(" 自動生成迷宮 請按：2n"); printf(" 退出 請按：3nn"); printf("*n"); printf("n"); printf("請選擇你的操作：n"); scanf(&qu

25、ot;%d",&i); switch(i) case 1:printf("n請輸入行數(shù)：");scanf("%d",&m); printf("n"); printf("請輸入列數(shù)：");scanf("%d",&n); while(m<=0|m>39)|(n<=0|n>39) printf("n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-39,0-39),請重新輸入：nn"); printf("請輸入行數(shù)：");scanf("%d",&m); printf("n"); printf("請輸入列數(shù)：");scanf("%d",&n); shoudong_maze(m,n); print_maze(m,n); mgpath(maze,