數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之迷宮

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

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

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　《算法與數(shù)據(jù)結(jié)構(gòu)》　　課程設(shè)計說明書　　題目：漫步迷宮 　　目錄　　一、課程設(shè)

2、計題目3　　二、問題描述3　　三、基本要求3　　四、設(shè)計思想3　　4.1 函數(shù)的功能和參數(shù)3　　4.2存儲

3、結(jié)構(gòu)的選擇4　　4.3迷宮有解無解情況的解讀5　　五、漫步迷宮源程序5　　六、運行結(jié)果10　　6.1 主界面10　　6.2 手動生成迷宮10

4、;　　6.3 自動生成迷宮13　　七、設(shè)計過程出現(xiàn)的問題和優(yōu)點14　　八、設(shè)計的心得體會17　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計-------漫步迷宮　　課程設(shè)計題目：漫步迷宮　　問題描述：<

5、/p>　　用m行n列的m*n個正方格表示一個迷宮，其中劃有斜線的方格表示不可通行，未劃有斜線的方格表示通行。請編寫尋找從入口到出口的一條最短路徑的程序。　　基本要求：　　迷宮的規(guī)則（即行數(shù)和列數(shù)），狀態(tài)設(shè)置（即各方格能否通行的狀態(tài)），以及入口和出口的位置，均應(yīng)由輸入隨機確定。</p&

6、gt;　　求得的最短路徑，應(yīng)該以從入口到出口的路徑上的各個方格的坐標(biāo)的線性序列輸出。當(dāng)無通路是，應(yīng)該報告無路徑的信息。　　盡量采用結(jié)構(gòu)化程序設(shè)計方法，要求對各個模塊的功能及參數(shù)做必要的說明。　　設(shè)計思想　　函數(shù)的功能和參數(shù)</b&

7、gt;　　存儲結(jié)構(gòu)的選擇　　在這個編寫的迷宮程序中，我采用的是隊列，而沒有采用棧這種數(shù)據(jù)結(jié)構(gòu)。隊列將迷宮的每個點都用順序存儲的方式將它存儲起來，便于在需找路徑是廣度優(yōu)先搜索。　　首先是將迷宮的各個點的是否通路用0和1表示出來，形成數(shù)組，存入到maze這個數(shù)組中。當(dāng)指定一個入口

8、時，首先判斷該點是否為通路，若不為通路則直接輸出“此迷宮無解”，然后再判斷所處位置的前后左右的四個方向上的連通性和是否為出口，連通則記在隊列中，若為出口，則停止入隊列。在要尋找迷宮路徑時，從出口開始回溯查找，將在出口到入口這條路徑上的點的值記為3，便于輸出迷宮路徑。　　在這個程序中我們要尋找的是迷宮的最短路徑，所以要用廣度優(yōu)先搜索，在用廣度優(yōu)先搜索時，每個點都會觀察它的前后左右的連通性，每走一步

9、便記錄一下，最后走出迷宮的路徑便一定是最短的。　　編寫此段程序所用語言為C語言。　　4.3迷宮的有解和無解的情況解讀：　　在這個迷宮中會出現(xiàn)無解的情況，特別是在自動生成迷宮的時候，甚至還有自動生成迷宮的入口和出口，在自動生成時，給點的賦值為0或1，每個點連通的情況時一半一半的，這樣的概率也就導(dǎo)致了它的無解。無解也

10、就說明了出口和入口不在一個連通分量上。　　漫步迷宮源程序　　#include"stdlib.h"　　#include"stdio.h"　　#define N 50<

11、p>　　#define M 50　　int X;　　int maze[N][M];　　struct point{　　int row,col,predecessor;　　}queue[51

12、2];　　int head=0,tail=0;　　void creat_maze(int m,int n){　　int i,j;　　printf("\n\n");　　pri

13、ntf("請按行輸入迷宮，0表示通路，1表示障礙:\n\n");　　for(i=0;i<m;i++)　　for(j=0;j<n;j++)　　{　　printf("maze[%d][%d]:&q

14、uot;,i,j);　　scanf("%d",&maze[i][j]);　　}　　}　　void present_maze(int m,int n){

15、;　　int i,j;　　printf("\n迷宮自動生成中……\n\n");　　system("pause");　　for(i=0;i<m;i++)　　for(j=

16、0;j<n;j++)　　maze[i][j]=rand()%2;　　}　　void present_in(int m,int n,int &a,int &b)　　{</

17、p>　　printf("\n迷宮入口自動生成中……\n\n");　　system("pause");　　a=rand()%m;　　b=rand()%n;　　}<

18、/p>　　void present_out(int m,int n,int &c,int &d)　　{　　printf("\n迷宮出口自動生成中……\n\n");　　system("pause"

19、;);　　c=rand()%m;　　d=rand()%n;　　}　　void print_maze(int m,int n,int a,int b,int c,int d){

20、　　int i,j;　　printf("\n迷宮生成結(jié)果如下:\n\n");　　//printf("迷宮入口\n");　　//printf("↓");　　for(i=0;i<m;i++)

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

22、t;/p>　　}　　//printf("→迷宮出口\n");　　}　　void result_maze(int m,int n){

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

24、lt;/p>　　{if(maze[i][j]==0||maze[i][j]==2) printf("□");　　if(maze[i][j]==1) printf("■");　　if(maze[i][j]==3) printf("& ");

25、　　}　　}　　}　　void enqueue(struct point p){　　queue[tail]=p;&

26、lt;p>　　tail++;　　}　　struct point dequeue(){　　head++;　　return queue[head-1];&l

27、t;/p>　　}　　int is_empty(){　　return head==tail;　　}　　void visit(int row,int col,int maz

28、e[50][50]){　　struct point visit_point={row,col,head-1};　　maze[row][col]=2;　　enqueue(visit_point);　　}<p

29、>　　int mazepath(int maze[50][50],int m,int n,int a ,int b,int c,int d){　　X=1;　　struct point p={a,b,-1};　　if(maze[p.row][p.col]==1)</

30、p>　　{printf("\n*****************************************************\n");　　printf("此迷宮無解\n\n");X=0;return 0;}　　maze[p.row][p.col]=2;

31、　　enqueue(p);　　while(!is_empty())　　{p=dequeue();　　if((p.row==c)&&(p.col==d)) break;　　if((p.row+1<m)&&(maze[p

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

33、]==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);　　}　　if(p.row==c&&

34、amp;p.col==d)　　{printf("\n***************************************************n");　　printf("迷宮路徑為：\n");　　printf("(%d,%d)\n",p.ro

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

36、t;　　maze[p.row][p.col]=3;　　}　　}　　else {printf("\n************************************************\n&quo

37、t;);　　printf("此迷宮無解！\n\n");X=0;}　　return 0;　　}　　void main()　　{int i

38、,m,n,a,b,c,d,j,cycle=0;　　while(cycle!=(-1))　　{　　printf("*********************************************************************\n"

39、);　　printf(" 2011-2012學(xué)年第二學(xué)期數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 \n");　　printf(" ------漫步迷宮 \n");</

40、p>　　printf(" 開發(fā)員：曾祥柯 \n");　　printf(" 班級：10計算本1班 \n");</p&g

41、t;　　printf(" 學(xué) 號：1015023129 \n");　　printf(" 歡迎進入漫步迷宮 \n");</p&g

42、t;　　printf("*********************************************************************\n");　　printf(" 手動生成迷宮請按：1\n");　　printf("

43、自動生成迷宮請按：2\n");　　printf(" 退出漫步迷宮請按：3\n\n");　　printf("*********************************************************************\n");

44、;　　printf("\n");　　printf("請選擇你的操作：\n");　　scanf("%d",&i);　　switch(i)　　{ca

45、se 1:printf("\n請輸入行數(shù)：");scanf("%d",&m);　　printf("\n");　　printf("請輸入列數(shù)：");scanf("%d",&n);　　while((m&

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

47、;　　printf("\n");　　printf("請輸入列數(shù)：");scanf("%d",&n);　　}　　creat_maze(m,n);　　print_maze

48、(m,n,a,b,c,d);　　printf("\n");　　printf("*********************************************************************\n");　　printf("

49、手動輸入迷宮入口請按：1\n");　　printf(" 自動生成迷宮入口請按：2\n");　　printf("*********************************************************************\n");</p&g

50、t;　　printf("\n");　　printf("請選擇你的操作：\n");　　scanf("%d",&j);　　switch(j)　　{c

51、ase 1: printf("請輸入入口坐標(biāo)：");scanf("%d,%d",&a,&b);　　while((a<0||a>m-1)||(b<0||b>n-1))　　{printf("\n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-%d ,0-%d ),請重新輸入：\n

52、\n",m-1,n-1);　　printf("請輸入入口坐標(biāo)：");scanf("%d,%d",&a,&b);}break;　　case 2: present_in(m,n,a,b);break;　　}<

53、/p>　　printf("\n");　　printf("請輸入出口坐標(biāo)：");scanf("%d,%d",&c,&d);　　while((c<0||c>m-1)||(d<0||d>n-1))<p&g

54、t;　　{printf("\n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-%d ,0-%d ),請重新輸入：\n\n",m-1,n-1);　　printf("請輸入入口坐標(biāo)：");scanf("%d,%d",&c,&d);　　}

55、　　print_maze(m,n,a,b,c,d);　　mazepath(maze,m,n,a,b,c,d);　　if(X!=0) result_maze(m,n);　　printf("\n\nPress Enter Contiue!\n");getchar();whil

56、e(getchar()!='\n');break;　　case 2:printf("\n請輸入行數(shù)：");scanf("%d",&m);　　printf("\n");　　printf("請輸入列數(shù)：");sca

57、nf("%d",&n);　　while((m<=0||m>50)||(n<=0||n>50))　　{printf("\n抱歉，你輸入的行列數(shù)超出預(yù)設(shè)范圍(0-50,0-50),請重新輸入：\n\n");　　printf("請輸入行數(shù)

58、：");scanf("%d",&m);　　printf("\n");　　printf("請輸入列數(shù)：");scanf("%d",&n);　　}&l

59、t;p>　　present_maze(m,n);　　print_maze(m,n,a,b,c,d);　　printf("\n");　　printf("請輸入入口坐標(biāo)：");scanf("%d,%d",&a,&b);

60、;　　printf("\n");　　printf("請輸入出口坐標(biāo)：");scanf("%d,%d",&c,&d);　　mazepath(maze,m,n,a,b,c,d);　　if(X!=0) result_maz

61、e(m,n);　　printf("\n\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　case 3:cycle=(-1);break;　　default:printf("\n&qu

62、ot;);printf("你的輸入有誤!\n");　　printf("\nPress Enter Contiue!\n");getchar();while(getchar()!='\n');break;　　}<b&

63、gt;　　}　　}　　運行結(jié)果　　將該程序的各個功能都運行了結(jié)果，分為主界面、手動建立迷宮、自動生成迷宮、自動生成入口等模塊。　　主界面：

64、　　手動生成迷宮（老師所給迷宮）：　　此迷宮的圖解和路線可寫為：　　| 0 1 1 1 1 1 1 1 1 1 |　　| 0 1 0 0 1 0 0 0 1 1 |　　| 0 0 0 1 1 0 1 0 0 1 | 入口坐

65、標(biāo)為[0,0]　　A.maze= | 0 1 1 0 0 0 1 1 0 1 |　　| 0 0 0 0 1 0 0 0 0 1 | 出口坐標(biāo)為[5,9]　　| 1 1 1 1 1 1 1 1 0 0 |　　則輸出的最短路徑應(yīng)該是:<p

66、>　　[5,9] --[5,8]ß--[4,8]ß--[4,7]ß--[4,6]　　--[4,5]--[3,5]--[3,4]--[3, 3] --[4,3]　　--[4,2]--[4,1]--[4,0]--[3,0]--[2,0]　　--[1,0]--[0,0]</p&

67、gt;　　手動生成迷宮（自己編寫的迷宮）且自動生成迷宮入口：　　自動生成迷宮（無解的情況）：　　自動生成迷宮（有解的情況）：　　七、設(shè)計過程中出現(xiàn)的問題及優(yōu)點　　1、這段程序為網(wǎng)上下載而來，剛開始時程序有很多版塊都不夠完整，沒有歡迎界面，于是在主程序

68、中做了界面的輸出。　　2、在程序運行中還有一個問題是剛開始時是把迷宮的入口和出口的坐標(biāo)給出后才顯示原始的迷宮圖，這樣在自動生成迷宮時很容易出現(xiàn)無解的情況，也無法很好的驗證自動生成迷宮這一模塊的正確性。于是將原始迷宮的輸出函數(shù)print_maze(m,n,a,b,c,d)提前調(diào)用了，解決了這一問題。　　3、剛拿到這個程序時，它不能很好的對迷宮的大小超出范圍

69、進行報錯功能，這是因為沒有對輸入的行數(shù)列數(shù)與它的最大值進行比較，在加了　　while((m<=0||m>50)||(n<=0||n>50))后就解決了這個問題。　　4、做這個迷宮程序最主要的便是在找尋路徑時如何表示是路徑上的點，我采用的方法是將這個點的值賦值為3表示訪問過，將這個點的值賦值為2表示為通路但不在此路徑上。</p

70、>　　5、在此段程序中我并沒有采用老師所說的加圍墻的方法，這樣就減少了程序的空間復(fù)雜度，但增加了時間復(fù)雜度。　　6、這個程序有個閃光點就是可以自動生成迷宮、出口和入口，而自動生成所需進行的運算方法便是：maze[i][j]=rand()%2，通過除2取余的方法將點的值賦值為0或1。　　通過這個運算，我知道了要想隨機產(chǎn)生X到Y(jié)的

71、數(shù)可以講語句寫為：k=rand()%(Y-X+1)+X,這就是學(xué)習(xí)時的舉一反三。　　7、該程序還有個優(yōu)點便是能夠把迷宮的最短路徑用圖形直接的顯示出來，也讓我們不必去對著路徑重新畫圖。　　8、在自動生成迷宮后馬上將其圖形輸出出來，便于我們確定它的入口和出口，也就減少了迷宮無解的概率。　　9、這個迷宮的大小我設(shè)定的是

72、行列數(shù)各50，而屏幕只能裝下大概30*30的數(shù)，當(dāng)我們要創(chuàng)建大小為50*50的迷宮時就會出現(xiàn)迷宮輸出不完全的情況，反映出來的圖形如下：　　10、現(xiàn)在這個程序還是存在一些問題，在自動生成迷宮時他便不能在自動生成入口出口，這個是需要完善的，但如果都是自動生成的會造成的后果便是迷宮無解的情況概率會很大，運行時的顯示如下：　　11、還有個待解決的問題便是在手動輸

73、入迷宮時，只能自動生成入口而不能自動生成出口，運行情況如下：　　12、這個程序后來自己還有一個想法就是把自己以前手動創(chuàng)建的迷宮按創(chuàng)建者意見保存下來，以便下回用同一個迷宮時減少輸入的麻煩，但這個功能沒有實現(xiàn)。這個功能需要實現(xiàn)文件的讀取。同時可以增加在一次游戲時多次輸入出口和入口，提高一個迷宮的利用率。　　八、設(shè)計的心得體會</b&g

74、t;　　剛開始拿到這個課程設(shè)計的題目的時候有點手足無措，因為不知道從哪開始下手，也不知道到底用什么數(shù)據(jù)結(jié)構(gòu)比較好，后來老師跟我們花了一節(jié)課進行講解，自己查找了一些資料才開始了有了一些概念，通過這次課程設(shè)計，我了解到了做隊列的算法和廣度優(yōu)先搜索的方法，也更加熟悉了C語言。　　由于能力有限，有很多自己想要的功能都沒能實現(xiàn)，在這個時候自己也感到了十分的無奈，所

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之迷宮

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計之迷宮

文檔簡介

溫馨提示

最新文檔

評論

免費下載