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

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之迷宮_第1頁(yè)

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

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

文檔簡(jiǎn)介

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

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

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

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

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

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

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

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

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

10、就說(shuō)明了出口和入口不在一個(gè)連通分量上。　　漫步迷宮源程序　　#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("請(qǐng)按行輸入迷宮，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迷宮自動(dòng)生成中……\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迷宮入口自動(dòng)生成中……\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迷宮出口自動(dòng)生成中……\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("此迷宮無(wú)解\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("此迷宮無(wú)解！\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è)計(jì) \n");　　printf(" ------漫步迷宮 \n");</

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

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

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

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

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

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

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

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

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

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

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

51、ase 1: printf("請(qǐng)輸入入口坐標(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 ),請(qǐng)重新輸入：\n

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

53、/p>　　printf("\n");　　printf("請(qǐng)輸入出口坐標(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 ),請(qǐng)重新輸入：\n\n",m-1,n-1);　　printf("請(qǐng)輸入入口坐標(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請(qǐng)輸入行數(shù)：");scanf("%d",&m);　　printf("\n");　　printf("請(qǐng)輸入列數(shù)：");sca

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

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

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

60、;　　printf("\n");　　printf("請(qǐng)輸入出口坐標(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;　　}　　}　　運(yùn)行結(jié)果　　將該程序的各個(gè)功能都運(yùn)行了結(jié)果，分為主界面、手動(dòng)建立迷宮、自動(dòng)生成迷宮、自動(dòng)生成入口等模塊。　　主界面：

64、　　手動(dòng)生成迷宮（老師所給迷宮）：　　此迷宮的圖解和路線可寫(xiě)為：　　| 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;　　手動(dòng)生成迷宮（自己編寫(xiě)的迷宮）且自動(dòng)生成迷宮入口：　　自動(dòng)生成迷宮（無(wú)解的情況）：　　自動(dòng)生成迷宮（有解的情況）：　　七、設(shè)計(jì)過(guò)程中出現(xiàn)的問(wèn)題及優(yōu)點(diǎn)　　1、這段程序?yàn)榫W(wǎng)上下載而來(lái)，剛開(kāi)始時(shí)程序有很多版塊都不夠完整，沒(méi)有歡迎界面，于是在主程序

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

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

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

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

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

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

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

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

溫馨提示

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

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

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

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載