迷宮求解數(shù)據(jù)結構課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：21 大?。?20.50KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩20頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　《數(shù)據(jù)結構》課程設計報告書　　設計題目：迷宮求解 　　專業(yè)：班級： 　　學生姓名：學號： 　　指導教師：

2、 　　2012年12月　　目錄　　摘要II　　第一章問題描述1　　第二章設計思路2

3、　　第三章課程設計總體方案及分析3　　第四章調試分析10　　總結12　　附錄：III　　1.程序清單III<

4、;b>　　2.文獻VII　　摘要　　設計一個簡單程序，來實現(xiàn)迷宮的求解，首先在設計的時候就想了一下，應該運用到那些知識，不管是C語言還是數(shù)據(jù)結構的首先我們想到是運用到什么相關知識，設計一個計算機程序對任意設定的矩形迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。

5、　　首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經(jīng)找到了一條路徑，搜索工作結束。否則搜索其上、下、左、右位置是否是障礙，若不是障礙，就移動到該位置，然后再從該位置開始搜索通往出口的路徑；若是障礙就選擇另一個相鄰的位置，并從它開始搜索路徑。為防止搜索重復出現(xiàn)，則將已搜索過的位置標記為2，同時保留搜索痕跡，在考慮進入下一個位置搜索之前，將當前位置保存在一個隊列中，如果所有相鄰的非障礙位置均被搜索過，且未找到通往出

6、口的路徑，則表明不存在從入口到出口的路徑。這實現(xiàn)的是廣度優(yōu)先遍歷的算法，如果找到路徑，則為最短路徑。　　本課程我將用源代碼和流程圖來說明和設計我的論文。　　關鍵字：迷宮求解、數(shù)據(jù)結構、 C語言　　第一章問題描述 　　迷宮問題是取自心理學的一個古典實驗

7、。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒子中設置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠經(jīng)過多次試驗最終學會走通迷宮的路線。設計一個計算機程序對任意設定的矩形迷宮如下圖A所示，求出一條從入口到出口的通路，或得出沒有通路的結論。

8、60; &

9、#160; 圖A　　第二章設計思路　　2.1設計要求　　要求設計程序輸出如下

10、：　　(1) 建立一個大小為m×n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；　　（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點的坐標。　?。?）用一種標志（如數(shù)字8）在迷宮中標出該條通路；　?。?）在屏幕上

11、輸出迷宮和通路；　?。?）上述功能可用菜單選擇。　　第三章課程設計總體方案及分析　　3.1 問題分析：　　1.迷宮的建立：　　迷宮中存在通路和

12、障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描述，　　2.迷宮的存儲：　　迷宮是一個矩形區(qū)域，可以使用二維數(shù)組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數(shù)組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數(shù)組maze[M+2][N+2],然后用它的前

13、m行n列來存放元素，即可得到一個m×n的二維數(shù)組，這樣(0,0)表示迷宮入口位置，(m-1,n-1)表示迷宮出口位置。　　注：其中M，N分別表示迷宮最大行、列數(shù)，本程序M、N的缺省值為39、39，當然，用戶也可根據(jù)需要，調整其大小。　　3.迷宮路徑的搜索：　　首先從迷宮的入口開始，如果該位置就是迷宮出口

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

15、，如果找到路徑，則為最短路徑。　　以矩陣 0 0 1 0 1 為例，來示范一下　　1 0 0 1 0　　1 0 0 0 1　　0 0 1 0 0</p

16、>　　首先，將位置(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é)點均入隊列，且它們的前

17、節(jié)點序號均為該位置的序號，所以如果存在路徑，則從出口處節(jié)點的位置，逆序就可以找到其從出口到入口的通路。　　如下表所示：　　0 1 2 3 4 5 6 7 8 9 10　　由此可

18、以看出，得到最短路徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0,1)(0,0)　　搜索算法流程圖如下所示：　　3.2 概要設計　　1.①構建一個二維數(shù)組maze[M+2][N+2]用于存儲迷宮矩陣　?、谧詣踊蚴?/p>

19、動生成迷宮，即為二維數(shù)組maze[M+2][N+2]賦值　　③構建一個隊列用于存儲迷宮路徑　?、芙⒚詫m節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況　?、輰崿F(xiàn)搜索算法　?、奁聊簧巷@示操作菜單&

20、lt;p>　　2.本程序包含10個函數(shù)：　　(1)主函數(shù) main()　　(2)手動生成迷宮函數(shù) shoudong_maze()　　(3)自動生成迷宮函數(shù) zidong_maze()　　(4)將迷宮打印成圖形 print_maze()<

21、p>　　(5)打印迷宮路徑 (若存在路徑) result_maze()　　(6)入隊 enqueue()　　(7)出隊 dequeue()　　(8)判斷隊列是否為空 is_empty()　　(9)訪問節(jié)點 visit()

22、(10)搜索迷宮路徑 mgpath()　　3.3 詳細設計　　實現(xiàn)概要設計中定義的所有數(shù)據(jù)類型及操作的偽代碼算法　　節(jié)點類型和指針類型　　迷宮矩陣類型：int maze[M+2][N+2];為方便

23、操作使其為全局變量　　迷宮中節(jié)點類型及隊列類型：struct point{int row,col,predecessor} que[512]　　迷宮的操作　　(1)手動生成迷宮　　void sho

24、udong_maze(int m,int n)　　{定義i,j為循環(huán)變量　　for(i<=m)　　for(j<=n)　　輸入maze[i][j]的值<p&

25、gt;　　}　　(2)自動生成迷宮　　void zidong_maze(int m,int n)　　{定義i,j為循環(huán)變量　　for(i<=m)<

26、/p>　　for(j<=n)　　maze[i][j]=rand()%2 //由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX,RAND_MAX是定義在stdlib.h中的,其值至少為32767),要產(chǎn)生從X到Y的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X;<

27、b>　　}　　(3)打印迷宮圖形　　void print_maze(int m,int n)　　{用i,j循環(huán)變量，將maze[i][j]輸出 □、■}　　(4)打印迷宮路徑</b&g

28、t;　　void result_maze(int m,int n)　　{用i,j循環(huán)變量，將maze[i][j]輸出 □、■、☆}　　(5)搜索迷宮路徑　?、倜詫m中隊列入隊操作　　void e

29、nqueue(struct point p)　　{將p放入隊尾，tail++}　?、诿詫m中隊列出隊操作　　struct point dequeue(struct point p)　　{head++,返回que[head-1]}&l

30、t;b>　?、叟袛嚓犃惺欠駷榭?lt;/b>　　int is_empty()　　{返回head==tail的值，當隊列為空時，返回0}　　④訪問迷宮矩陣中節(jié)點　　void visit(int row,int col,int maze[41][41])</

31、p>　　{建立新的隊列節(jié)點visit_point,將其值分別賦為row,col,head-1,maze[row][col]=2,表示該節(jié)點以被訪問過;調用enqueue(visit_point),將該節(jié)點入隊}　?、萋窂角蠼?lt;/b>　　void mgpath(int maze[41][41],in

32、t m,int n)　　{先定義入口節(jié)點為struct point p={0,0,-1},從maze[0][0]開始訪問。如果入口處即為障礙，則此迷宮無解，返回0 ，程序結束。否則訪問入口節(jié)點，將入口節(jié)點標記為訪問過maze[p.row][p.col]=2,調用函數(shù)enqueue(p)將該節(jié)點入隊。　　判斷隊列是否為空，當隊列不為空時，則運行以下操作：&

33、lt;/p>　　{ 調用dequeue()函數(shù)，將隊頭元素返回給p，　　如果p.row==m-1且p.col==n-1,即到達出口節(jié)點，即找到了路徑，結束　　如果p.col+1<n且maze[p.row][p.col+1]==0,說明未到迷宮右邊界，且其右方有通路,則visit(p.row,p.col+1,maze),將

34、右邊節(jié)點入隊標記已訪問　　如果p.row+1<m且maze[p.row+1][p.col]==0,說明未到迷宮下邊界，且其下方有通路,則visit(p.row+1,p.col,maze),將下方節(jié)點入隊標記已訪問　　如果p.col-1>0且maze[p.row][p.col-1]==0,說明未到迷宮左邊界，且其左方有通路,則visit(p.r

35、ow,p.col-1,maze),將左方節(jié)點入隊標記已訪問　　如果p.row-1>0且maze[p.row-1][p.col]==0,說明未到迷宮上邊界，且其上方有通路,則visit(p.row,p.col+1,maze),將上方節(jié)點入隊標記已訪問　　}　　訪問到出口(

36、找到路徑)即p.row==m-1且p.col==n-1,則逆序將路徑標記為3即maze[p.row][p.col]==3;　　while(p.predecessor!=-1)　　{p=queue[p.predecessor]; maze[p.row][p.col]==3;}　　最后將路徑圖形打印出來。</p

37、>　　3.菜單選擇　　while(cycle!=(-1))　　☆ 手動生成迷宮請按：1　　☆ 自動生成迷宮請按：2　　☆ 退出請按：3<p&g

38、t;　　scanf("%d",&i);　　switch(i)　　{ case 1：請輸入行列數(shù)(如果超出預設范圍則提示重新輸入) 　　shoudong_maze(m,n);　　print_maze(m,n)

39、;　　mgpath(maze,m,n);　　if(X!=0) result_maze(m,n);　　case 2 ：請輸入行列數(shù)(如果超出預設范圍則提示重新輸入)　　zidong_maze(m,n);　　print_maze(m,

40、n);　　mgpath(maze,m,n);　　if(X!=0) result_maze(m,n);　　case 3：cycle=(-1); break;　　第四章調試分析　　在調試過程中，

41、首先使用的是棧進行存儲，但是產(chǎn)生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法　　4.1測試結果　　2.自動生成迷宮　　總結　　通過這段時間的課程設

42、計，本人對計算機的應用，數(shù)據(jù)結構的作用以及C語言的使用都有了更深的了解。尤其是C語言的進步讓我深刻的感受到任何所學的知識都需要實踐，沒有實踐就無法真正理解這些知識以及掌握它們，使其成為自己的財富。在理論學習和上機實踐的各個環(huán)節(jié)中，通過自主學習和請教老師，我收獲了不少。當然也遇到不少的問題，也正是因為這些問題引發(fā)的思考給我?guī)Я耸斋@。從當初不喜歡上機寫程序到現(xiàn)在能主動寫程序，從當初拿著程序不只如何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識解

43、決實際問題的轉變，我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力，自己都有很大程度的提高。在這段時間里，我對for、while等的循環(huán)函數(shù)用法更加熟悉，逐漸形成了較好的編程習慣。在老師的指導幫助下，同學們課余時間的討論中，這些問題都一一得到了解決。在程序的調試能力上，無形中得到了許多的提高。例如：頭文件的使用，變量和數(shù)組的范圍問題，定義變量時出現(xiàn)的問題等等。　　在實際的上機操作過程中，不僅是讓我們了解數(shù)據(jù)結構

44、的理論知識，更重要的是培養(yǎng)解決實際問題的能力，所以相信通過此次實習可以提高我們分析設計能力和編程能力，為后續(xù)課程的學習及實踐打下良好的基礎。　　在這次短短的課程實踐里，我們得到了侯瑞蓮老師的關心和幫助。她給了我們很多的信息，與我們一起探討問題，詢問我們遇到了哪些問題并耐心給予指導。當我們遇到技術上難以解決的問題時，她就會指導我們解決問題，她把自己多年來積累的經(jīng)驗教授給我們，使我們順利地完成了課程

45、實踐任務。時間過得真快，大學生活不知不覺就走過了一年，一年的大學學習和課程實踐階段的提高，使我們本身知識得到提高的同時，也增強了我們對未來工作的信心。　　附錄：　　1.程序清單　　#include"stdlib.h"&

46、lt;/p>　　#include"stdio.h"　　#define N 39　　#define M 39　　int X;　　int maze[N+2][M+2];

47、　　struct point{　　int row,col,predecessor;　　}queue[512];　　int head=0,tail=0;　　void shoudong_maze(int m,int n){<p

48、>　　int i,j;　　printf("\n\n");　　printf("請按行輸入迷宮，0表示通路，1表示障礙:\n\n");　　for(i=0;i<m;i++)　　for(j=

49、0;j<n;j++)　　scanf("%d",&maze[i][j]);　　}　　void zidong_maze(int m,int n){　　int i,j;

50、　　printf("\n迷宮生成中……\n\n");　　system("pause");　　for(i=0;i<m;i++)　　for(j=0;j<n;j++)　　maze[i]

51、[j]=rand()%2;　　//由于rand()產(chǎn)生的隨機數(shù)是從0到RAND_MAX　　//RAND_MAX是定義在stdlib.h中的,其值至少為32767)　　//要產(chǎn)生從X到Y的數(shù),只需要這樣寫：k=rand()%(Y-X+1)+X; 　　}&l

52、t;/b>　　void print_maze(int m,int n){　　int i,j;　　printf("\n迷宮生成結果如下:\n\n");　　printf("迷宮入口\n");&

53、lt;/p>　　printf("↓");　　for(i=0;i<m;i++)　　{printf("\n");　　for(j=0;j<n;j++) 　　{if(maze[i][j]==0) pr

54、intf("□");　　if(maze[i][j]==1) printf("■");}　　}　　printf("→迷宮出口\n");　　}

55、;　　void result_maze(int m,int n){　　int i,j;　　printf("迷宮通路(用☆表示)如下所示：\n\t");　　for(i=0;i<m;i++)

56、　　{printf("\n");　　for(j=0;j<n;j++)　　{if(maze[i][j]==0||maze[i][j]==2) printf("□");　　if(maze[i][j]==1) printf("■");

57、　　if(maze[i][j]==3) printf("☆");　　}　　}　　}　　void

58、enqueue(struct point p){　　queue[tail]=p;　　tail++;　　}　　struct point dequeue(){

59、　　head++;　　return queue[head-1];　　}　　int is_empty(){　　return head==tail;<b

60、>　　}　　void visit(int row,int col,int maze[41][41]){　　struct point visit_point={row,col,head-1};　　maze[row][col]=2;　　enqueue

61、(visit_point);　　}　　int mgpath(int maze[41][41],int m,int n){　　X=1;　　struct point p={0,0,-1};</p

62、>　　if(maze[p.row][p.col]==1)　　{printf("\n===============================================\n");　　printf("此迷宮無解\n\n");X=0;return 0;}<

63、;p>　　maze[p.row][p.col]=2;　　enqueue(p);　　while(!is_empty())　　{p=dequeue();　　if((p.row==m-1)&&(p.col==n-1)) break;

64、　　if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze);　　if((p.row+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze);　　if(

65、(p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze);　　if((p.row-1>=0)&&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze);　　}</

66、b>　　if(p.row==m-1&&p.col==n-1)　　{printf("\n==================================================================\n");　　printf("迷宮路徑為：\

67、n");　　printf("(%d,%d)\n",p.row,p.col);　　maze[p.row][p.col]=3;　　while(p.predecessor!=-1)　　{p=queue[p.predecessor];</p&g

68、t;　　printf("(%d,%d)\n",p.row,p.col);　　maze[p.row][p.col]=3;　　}　　}　　else {prin

69、tf("\n=============================================================\n");　　printf("此迷宮無解！\n\n");X=0;}　　return 0;<b&g

70、t;　　}　　void main()　　{int i,m,n,cycle=0;　　while(cycle!=(-1))　　{　　printf("*********

71、***********************************************************************\n");　　printf(" 歡迎進入迷宮求解系統(tǒng)\n");　　printf("

72、設計者:吳明華 \n");　　printf("********************************************************************************\n");　　prin

73、tf(" ☆ 手動生成迷宮請按：1\n");　　printf(" ☆ 自動生成迷宮請按：2\n");　　printf(" ☆ 退出

74、請按：3\n\n");　　printf("********************************************************************************\n");　　printf("\n");　　pr

75、intf("請選擇你的操作：\n");　　scanf("%d",&i);　　switch(i)　　{case 1:printf("\n請輸入行數(shù)：");scanf("%d",&m)

76、;　　printf("\n");　　printf("請輸入列數(shù)：");scanf("%d",&n);　　while((m<=0||m>39)||(n<=0||n>39))　　{pr

77、intf("\n抱歉，你輸入的行列數(shù)超出預設范圍(0-39,0-39),請重新輸入：\n\n");　　printf("請輸入行數(shù)：");scanf("%d",&m);　　printf("\n");　　printf("

78、請輸入列數(shù)：");scanf("%d",&n);　　}　　shoudong_maze(m,n);　　print_maze(m,n);　　mgpath(maze,m,n);&

79、lt;p>　　if(X!=0) result_maze(m,n);　　printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　case 2:printf("\n請輸入行數(shù)：");scanf(&q

80、uot;%d",&m);　　printf("\n");　　printf("請輸入列數(shù)：");scanf("%d",&n);　　while((m<=0||m>39)||(n<=0||n>39))</p

81、>　　{printf("\n抱歉，你輸入的行列數(shù)超出預設范圍(0-39,0-39),請重新輸入：\n\n");　　printf("請輸入行數(shù)：");scanf("%d",&m);　　printf("\n");<

82、p>　　printf("請輸入列數(shù)：");scanf("%d",&n);　　}　　zidong_maze(m,n);　　print_maze(m,n);　　mgpath(maze,

83、m,n);　　if(X!=0) result_maze(m,n);　　printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　case 3:cycle=(-1);break;&l

84、t;/p>　　default:printf("\n");printf("你的輸入有誤!\n");　　printf("\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;&l

85、t;b>　　}　　}　　}　　2.文獻　　【1】嚴蔚敏吳偉民《數(shù)據(jù)結構(C語言版)》清華大學出版社， 2009年9月&

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

迷宮求解數(shù)據(jù)結構課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

迷宮求解數(shù)據(jù)結構課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載