數據結構課程設計-迷宮求解

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數：20 大?。?35.34KB 人氣指數：12 舉報 版權申訴

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

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

文檔簡介

1、　　數據結構　　課程設計報告　　設計題目：迷宮求解　　專業(yè)：計算機科技　　院系：計算

2、機學院　　姓名： XXXXXX　　學號： 00000000　　時間：2013年9月27日　　目錄　　一實驗目的----------------------------

3、----------------------3　　二實驗內容及方法-----------------------------------------3　　2.1問題描述----------------------------------------------------------3　　2.2設計要求----

4、------------------------------------------------------3　　三實驗總體方案--------------------------------------------4　　3.1 問題分析----------------------------------------------------------

5、4　　3.2 概要設計----------------------------------------------------------6　　3.3 詳細設計----------------------------------------------------------7　　3.4 調試分析--------

6、-------------------------------------------------11　　3.5 測試結果---------------------------------------------------------11　　3.6 參考文獻------------------------------------------------

7、---------13　　四總結-------------------------------------------------------13　　五附錄-------------------------------------------------------14　　一實驗目的<

8、;/b>　　僅僅認識到隊列是一種特殊的線性表是遠遠不夠的，本次實習的目的在于使學生深入了解隊列的特征，以便在實際問題背景下靈活運用它，同時還將鞏固這種數據結構的構造方法。　　二實驗內容及方法　　2.1問題描述： 　　迷宮

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

10、

11、0; 圖A　　2.2設計要求：　　要求設計程序輸出如下：　　(1) 建立一個大小

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

13、上述功能可用菜單選擇。　　三實驗總體方案及分析　　3.1 問題分析：　　1.迷宮的建立：　　迷宮中存在通路和障礙，為了方便迷宮的創(chuàng)建，可用0表示通路，用1表示障礙，這樣迷宮就可以用0、1矩陣來描

14、述，　　2.迷宮的存儲：　　迷宮是一個矩形區(qū)域，可以使用二維數組表示迷宮，這樣迷宮的每一個位置都可以用其行列號來唯一指定，但是二維數組不能動態(tài)定義其大小，我們可以考慮先定義一個較大的二維數組maze[M+2][N+2],然后用它的前m行n列來存放元素，即可得到一個m×n的二維數組，這樣(0,0)表示迷宮入口

15、位置，(m-1,n-1)表示迷宮出口位置。　　注：其中M，N分別表示迷宮最大行、列數，本程序M、N的缺省值為39、39，當然，用戶也可根據需要，調整其大小。　　3.迷宮路徑的搜索：　　首先從迷宮的入口開始，如果該位置就是迷宮出口，則已經找到了一條路徑，搜索工作結束。否則搜索其上、下、左、右位置是否是障礙，若不是障

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

17、 0 1 0 1 為例，來示范一下　　1 0 0 1 0　　1 0 0 0 1　　0 0 1 0 0　　首先，將位置(0,0)(序號0)放入隊列中，其前節(jié)點

18、為空，從它開始搜索，其標記變?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é)點的位置，逆序就可以找到其從出

19、口到入口的通路。　　如下表所示：　　0 1 2 3 4 5 6 7 8 9 10　　由此可以看出，得到最短路徑：(3,4)(3,3)(2,3)(2,2)(1,2)(1,1)(0

20、,1)(0,0)　　搜索算法流程圖如下所示：　　3.2 概要設計　　1.①構建一個二維數組maze[M+2][N+2]用于存儲迷宮矩陣　?、谧詣踊蚴謩由擅詫m，即為二維數組maze[M+2][N+2]賦值<

21、;p>　　③構建一個隊列用于存儲迷宮路徑　?、芙⒚詫m節(jié)點struct point,用于存儲迷宮中每個節(jié)點的訪問情況　?、輰崿F(xiàn)搜索算法　?、奁聊簧巷@示操作菜單　　2.本程序包含10個函數：

22、;　　(1)主函數 main()　　(2)手動生成迷宮函數 shoudong_maze()　　(3)自動生成迷宮函數 zidong_maze()　　(4)將迷宮打印成圖形 print_maze()　　(5)打印迷宮路徑 (若存在路徑) result_maze()</

23、p>　　(6)入隊 enqueue()　　(7)出隊 dequeue()　　(8)判斷隊列是否為空 is_empty()　　(9)訪問節(jié)點 visit()　　(10)搜索迷宮路徑 mgpath()<

24、;b>　　3.3 詳細設計　　實現(xiàn)概要設計中定義的所有數據類型及操作的偽代碼算法　　節(jié)點類型和指針類型　　迷宮矩陣類型：int maze[M+2][N+2];為方便操作使其為全局變量　　迷宮中節(jié)點類型及隊列類

25、型：struct point{int row,col,predecessor} que[512]　　迷宮的操作　　(1)手動生成迷宮　　void shoudong_maze(int m,int n)

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

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

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

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

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

31、　　{將p放入隊尾，tail++}　?、诿詫m中隊列出隊操作　　struct point dequeue(struct point p)　　{head++,返回que[head-1]}　?、叟袛嚓犃惺欠駷榭?lt;/b><

32、;p>　　int is_empty()　　{返回head==tail的值，當隊列為空時，返回0}　?、茉L問迷宮矩陣中節(jié)點　　void visit(int row,int col,int maze[41][41])　　{建立新的隊列節(jié)點visit_point,將其值分

33、別賦為row,col,head-1,maze[row][col]=2,表示該節(jié)點以被訪問過;調用enqueue(visit_point),將該節(jié)點入隊}　?、萋窂角蠼?lt;/b>　　void mgpath(int maze[41][41],int m,int n)　　{先定義入口節(jié)點為s

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

35、返回給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),將右邊節(jié)點入隊標記已訪問　　如果p.row+1

36、<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.row,p.col-1,maze),將左方節(jié)點入隊標記已訪問&l

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

38、[p.row][p.col]==3;　　while(p.predecessor!=-1)　　{p=queue[p.predecessor]; maze[p.row][p.col]==3;}　　最后將路徑圖形打印出來。　　3.菜單選擇&

39、lt;/p>　　while(cycle!=(-1))　　{　　printf("╔══════════════════════════════════╗\n");　　printf("║

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

41、 1.手動生成迷宮 ║\n");　　printf("║ 2.自動生成迷宮 ║\n");　　printf("║

42、 3.退出系統(tǒng) ║\n");　　printf("╚══════════════════════════════════╝\n");　　printf("\n");　　scanf(&quo

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

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

45、　　mgpath(maze,m,n);　　if(X!=0) result_maze(m,n);　　case 3：cycle=(-1); break;　　}　　注：具體源代碼見附錄<p&

46、gt;　　3.4 調試分析　　在調試過程中，首先使用的是棧進行存儲，但是產生的路徑是多條或不是最短路徑，所以通過算法比較，改用此算法　　測試結果　　1.主界面

47、　　2.手動輸入迷宮　　自動生成迷宮　　3.6 參考文獻　　【1】嚴蔚敏吳偉民《數據結構(C語言版)》清華大學出版社， 2009年9月　　【2】

48、譚浩強《C程序設計(第三版)》清華大學出版社 2009年1月　　四總結　　通過這段時間的課程設計，本人對計算機的應用，數據結構的作用以及C語言的使用都有了更深的了解。尤其是C語言的進步讓我深刻的感受到任何所學的知識都需要實踐，沒有實踐就無法真正理解這些知識以及掌握它們，使其成為自己的財富。在理論學習和

49、上機實踐的各個環(huán)節(jié)中，通過自主學習和請教老師，我收獲了不少。當然也遇到不少的問題，也正是因為這些問題引發(fā)的思考給我?guī)Я耸斋@。從當初不喜歡上機寫程序到現(xiàn)在能主動寫程序，從當初拿著程序不只如何下手到現(xiàn)在知道如何分析問題，如何用專業(yè)知識解決實際問題的轉變，我發(fā)現(xiàn)無論是專業(yè)知識還是動手能力，自己都有很大程度的提高。在這段時間里，我對for、while等的循環(huán)函數用法更加熟悉，逐漸形成了較好的編程習慣。在老師的指導幫助下，同學們課余時間的討論中，

50、這些問題都一一得到了解決。在程序的調試能力上，無形中得到了許多的提高。例如：頭文件的使用，變量和數組的范圍問題，定義變量時出現(xiàn)的問題等等。　　在實際的上機操作過程中，不僅是讓我們了解數據結構的理論知識，更重要的是培養(yǎng)解決實際問題的能力，所以相信通過此次實習可以提高我們分析設計能力和編程能力，為后續(xù)課程的學習及實踐打下良好的基礎。　　在這次短短的課程實踐里

51、，我們得到了侯瑞蓮老師的關心和幫助。她給了我們很多的信息，與我們一起探討問題，詢問我們遇到了哪些問題并耐心給予指導。當我們遇到技術上難以解決的問題時，她就會指導我們解決問題，她把自己多年來積累的經驗教授給我們，使我們順利地完成了課程實踐任務。時間過得真快，大學生活不知不覺就走過了一年，一年的大學學習和課程實踐階段的提高，使我們本身知識得到提高的同時，也增強了我們對未來工作的信心，我們相信自己未來三年的學習更使我們有能力勝任將來的工作。&

52、lt;/p>　　五附錄　　#include"stdlib.h"　　#include"stdio.h"　　#define N 39　　#define M 39<

53、/p>　　int X;　　int maze[N+2][M+2];　　struct point{　　int row,col,predecessor;　　}queue[512];<

54、p>　　int head=0,tail=0;　　void shoudong_maze(int m,int n){　　int i,j;　　printf("\n\n");　　printf("請按行輸入迷

55、宮，0表示通路，1表示障礙:\n\n");　　for(i=0;i<m;i++)　　for(j=0;j<n;j++)　　scanf("%d",&maze[i][j]);　　}</

56、p>　　void zidong_maze(int m,int n){　　int i,j;　　printf("\n迷宮生成中……\n\n");　　system("pause");<

57、p>　　for(i=0;i<m;i++)　　for(j=0;j<n;j++)　　maze[i][j]=rand()%2;　　//由于rand()產生的隨機數是從0到RAND_MAX　　//RAND_MAX是定義在stdlib.h中的,其值至少為32767

58、)　　//要產生從X到Y的數,只需要這樣寫：k=rand()%(Y-X+1)+X; 　　}　　void print_maze(int m,int n){　　int i,j;

59、　　printf("\n迷宮生成結果如下:\n\n");　　printf("迷宮入口\n");　　printf("↓");　　for(i=0;i<m;i++)　　{printf("

60、;\n");　　for(j=0;j<n;j++) 　　{if(maze[i][j]==0) printf("□");　　if(maze[i][j]==1) printf("■");}　　}</

61、b>　　printf("→迷宮出口\n");　　}　　void result_maze(int m,int n){　　int i,j;<p&

62、gt;　　printf("迷宮通路(用☆表示)如下所示：\n\t");　　for(i=0;i<m;i++)　　{printf("\n");　　for(j=0;j<n;j++)　　{if(maze[i][j]==0||ma

63、ze[i][j]==2) printf("□");　　if(maze[i][j]==1) printf("■");　　if(maze[i][j]==3) printf("☆");　　}<

64、p>　　}　　}　　void enqueue(struct point p){　　queue[tail]=p;　　tail++;

65、　　}　　struct point dequeue(){　　head++;　　return queue[head-1];　　}</p&

66、gt;　　int is_empty(){　　return head==tail;　　}　　void visit(int row,int col,int maze[41][41]){　　struct point v

67、isit_point={row,col,head-1};　　maze[row][col]=2;　　enqueue(visit_point);　　}　　int mgpath(int maze[41][41],int m,int n){&

68、lt;/p>　　X=1;　　struct point p={0,0,-1};　　if(maze[p.row][p.col]==1)　　{printf("\n=========================================

69、======\n");　　printf("此迷宮無解\n\n");X=0;return 0;}　　maze[p.row][p.col]=2;　　enqueue(p);　　while(!is_empty())<p&

70、gt;　　{p=dequeue();　　if((p.row==m-1)&&(p.col==n-1)) break;　　if((p.col+1<n)&&(maze[p.row][p.col+1]==0)) visit(p.row,p.col+1,maze);　　if((p.ro

71、w+1<m)&&(maze[p.row+1][p.col]==0)) visit(p.row+1,p.col,maze);　　if((p.col-1>=0)&&(maze[p.row][p.col-1]==0)) visit(p.row,p.col-1,maze);　　if((p.row-1>=0)&am

72、p;&(maze[p.row-1][p.col]==0)) visit(p.row-1,p.col,maze);　　}　　if(p.row==m-1&&p.col==n-1)　　{printf("\n=====================

73、=============================================\n");　　printf("迷宮路徑為：\n");　　printf("(%d,%d)\n",p.row,p.col);　　maze[p.row][p.col]=3;<

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

75、　　}　　}　　else {printf("\n=============================================================\n");　　printf("此迷宮無

76、解！\n\n");X=0;}　　return 0;　　}　　void main()　　{　　int i,m

77、,n,cycle=0;　　system("cls");　　system("color 1f");　　printf(" ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");　　printf

78、(" ┃㊣必做題：稀疏矩陣運算器㊣┃\n");　　printf(" ┃ 姓名：XXX ┃\n");　　printf(" ┃

79、學號：000000000 ┃\n");　　printf(" ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");　　while(cycle!=(-1))　　{</p

80、>　　printf("╔═════════════════════════════════╗\n");　　printf("║ 歡迎進入迷宮求解系統(tǒng) ║\n");　　printf("║

81、 ------------------------------------------- ║\n");　　printf("║ 1.手動生成迷宮 ║\n");　　pr

82、intf("║ 2.自動生成迷宮 ║\n");　　printf("║ 3.退出系統(tǒng) ║\n");　　prin

83、tf("╚═════════════════════════════════╝\n");　　printf("\n");　　printf("請選擇你的操作：\n");　　scanf("%d",&i);&l

84、t;p>　　switch(i)　　{　　case 1:printf("\n請輸入行數：");scanf("%d",&m);　　printf("\n");</p

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

86、uot;);　　printf("請輸入行數：");scanf("%d",&m);　　printf("\n");　　printf("請輸入列數：");scanf("%d",&n);

87、　　}　　shoudong_maze(m,n);　　print_maze(m,n);　　mgpath(maze,m,n);　　if(X!=0) result_maze(m,n);<p

88、>　　printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　case 2:printf("\n請輸入行數：");scanf("%d",&m);　　printf(&q

89、uot;\n");　　printf("請輸入列數：");scanf("%d",&n);　　while((m<=0||m>39)||(n<=0||n>39))　　{printf("\n抱歉，你輸入的行列數超出預設范圍(0-3

90、9,0-39),請重新輸入：\n\n");　　printf("請輸入行數：");scanf("%d",&m);　　printf("\n");　　printf("請輸入列數：");scanf("%d"

91、;,&n);　　}　　zidong_maze(m,n);　　print_maze(m,n);　　mgpath(maze,m,n);　　if(X!=0) result_maze(m,n)

92、;　　printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　case 3:cycle=(-1);break;　　default:printf("\n");p

93、rintf("你的輸入有誤!\n");　　printf("\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　}　　}

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

溫馨提示

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

數據結構課程設計-迷宮求解

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計-迷宮求解

文檔簡介

溫馨提示

最新文檔

評論

免費下載