数据结构课程设计——迷宫求解问题(共21页).doc
《数据结构课程设计——迷宫求解问题(共21页).doc》由会员分享,可在线阅读,更多相关《数据结构课程设计——迷宫求解问题(共21页).doc(21页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上数据结构课程设计:迷宫实验报告任务分配:l 程序员: 主要任务:负责整体的算法设计以及程序的主要源代码的编写。l 测试员: 主要任务:负责在程序员每完成一个阶段对程序进行挑错,测试主程序并对实验结果进行整理分析,最后完成实验报告的第三、四部分即测试结果与分析探讨的内容。l 文档员: 主要任务:负责对程序及界面的美观提出改善意见,查找程序的小漏洞,负责撰写实验报告的第一、二部分即实验内容简介与算法描述的内容。同时完成整个文档的整合,使整篇报告排版、文字风格统一。一、 简介图的遍历就是从指定的某个顶点(称其为初始点)出发,按照一定的搜索方法对图中的所有顶点各做一次访问过程
2、。根据搜索方法不同,遍历一般分为深度优先搜索遍历和广度优先搜索遍历。本实验中用到的是广度优先搜索遍历。即首先访问初始点vi,并将其标记为已访问过,接着访问vi的所有未被访问过的邻接点,顺序任意,并均标记为已访问过,以此类推,直到图中所有和初始点vi有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历,直到遍历出迷宫出口,生成的路径为最短路径。因此我们采用了广度优先搜索。无论是深度优先搜索还是广度优先搜索,其本质都是将图的二维顶点结构线性化的过程,并将当前顶点相邻的未被访问的顶点作为下一个顶点。广度优先搜索采用队列作为数据结构。本实验的目的是设计一个程序,实现手动或者自动
3、生成一个n×m矩阵的迷宫,寻找一条从入口点到出口点的通路。具体实验内容如下:选择手动或者自动生成一个n×m的迷宫,将迷宫的左上角作入口,右下角作出口,设“0”为通路,“1”为墙,即无法穿越。假设一只老鼠从起点出发,目的为右下角终点,可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。如果迷宫可以走通,则用“”代表“1”,用“”代表“0”,用“”代表行走迷宫的路径。输出迷宫原型图、迷宫路线图以及迷宫行走路径。如果迷宫为死迷宫,则只输出迷宫原型图。二、 算法说明根据实验内容,本实验主要设计实现手动输入迷宫,判断迷宫能否走通;自动生成迷宫,判断迷宫能否走通。迷宫算法的整体
4、思想如下: 1、迷宫的创建迷宫中存在通路和障碍,为了方便迷宫的创建,可用0表示通路,用1表示障碍,这样迷宫就可以用0、1矩阵来描述。设置迷宫的长为n、宽为m,范围为49×49,用int mazeN+2M+2来表示,这样相当于在迷宫外层包了一层1,即防止搜索路径时跳出迷宫。(1)手动生成迷宫void hand_maze(int m,int n) /手动生成迷宫int i,j; for(i=0;i<m;i+) for(j=0;j<n;j+)cin>>mazeij; (2) 自动生成迷宫void automatic_maze(int m,int n) /自动生成迷宫
5、int i,j;for(i=0;i<m;i+)for(j=0;j<n;j+)mazeij=rand()%2; /随机生成0、1maze00=0; /将开始和结束位置强制为0,保证有可能出来迷宫mazem-1n-1=0;2、迷宫路径的搜索在生成的0、1矩阵迷宫中,首先从迷宫的入口开始,如果该位置就是迷宫出口,则已经找到了一条路径,搜索工作结束。否则搜索其北(-1,0),东北(-1,-1),东(0,1),东南(1,1),南(1,0),西南(1,-1),西(0,-1),西北(-1,-1)8个方向位,是否是障碍,若不是障碍,就移动到该位置,然后再从该位置开始搜索通往出口的路径;若是障碍就选
6、择另一个相邻的位置,并从它开始搜索路径。为防止搜索重复出现,则将已搜索过的位置标记为2,同时保留搜索痕迹,在考虑进入下一个位置搜索之前,将当前位置保存在一个队列中,如果所有相邻的非障碍位置均被搜索过,且未找到通往出口的路径,则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法,如果找到路径,则为最短路径。逆序输出路径,将已输出的路径标记为3。实验数据如下:列 行012300101100102101031100123456789(0,0)(1,1)(1,0)(0,2)(2,1)(1,3)(3,2)(2,3)(3,3)-111223456算法如下:int path(int maze5151
7、,int m,int n) /路径求解X=1; /初始值定为1struct point p=0,0,-1; /定义入口节点if(mazep.rowp.col=1) /入口为1时,迷宫不可解 cout<<"此迷宫无解nn" X=0; return 0; mazep.rowp.col=2; /标记为已访问 enqueue(p); /将p入队列while(!is_empty() p=dequeue(); if(p.row=m-1)&&(p.col=n-1) /当行和列为出口时跳出 break; /定义8个走位方向 if(p.row-1)>=0)&
8、amp;&(p.row-1)<m)&&(p.col+0)<n)&&(mazep.row-1p.col+0=0) visit(p.row-1,p.col+0,maze); /北 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col+1)<n)&&(mazep.row-1p.col+1=0) visit(p.row-1,p.col+1,maze); /东北 if(p.row+0)<m)&&(p.col+1)<n)&&
9、(mazep.row+0p.col+1=0) visit(p.row+0,p.col+1,maze); /东 if(p.row+1)<m)&&(p.col+1)<n)&&(mazep.row+1p.col+1=0) visit(p.row+1,p.col+1,maze); /东南 if(p.row+1)<m)&&(p.col+0)<n)&&(mazep.row+1p.col+0=0) visit(p.row+1,p.col+0,maze); /南 if(p.row+1)<m)&&(p.
10、col-1)<n)&&(p.col-1)>=0)&&(mazep.row+1p.col-1=0) visit(p.row+1,p.col-1,maze); /西南 if(p.row+0)<m)&&(p.col-1)<n)&&(p.col-1)>=0)&&(mazep.row+0p.col-1=0) visit(p.row+0,p.col-1,maze); /西 if(p.row-1)>=0)&&(p.row-1)<m)&&(p.col-1)&
11、lt;n)&&(p.col-1)>=0)&&(mazep.row-1p.col-1=0) visit(p.row-1,p.col-1,maze); /西北if(p.row=m-1&&p.col=n-1) /如果当前矩阵点是出口点,输出路径 cout<<"迷宫路径为:n" cout<<"出口"<<endl; cout<<" "<<""<<endl; printf("(%d,%d)n&
12、quot;,p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; /逆序将路径标记为3 while(p.predecessor!=-1) p=queuep.predecessor; printf("(%d,%d)n",p.row+1,p.col+1); cout<<" "<<""<<endl; mazep.rowp.col=3; cout<<"
13、入口"<<endl;else cout<<"此迷宫无解!nn" X=0;return 0;3、 输出迷宫图(1)、生成迷宫图,将迷宫外壳输出为,将迷宫中的0输出为,将1输出为for(k=0;k<n;k+)cout<<"" /这两个黑三角用来生成顶部外壳for(i=0;i<m;i+)cout<<"n"cout<<"" /生成左外壳for(j=0;j<n;j+) if(mazeij=0) cout<<"&quo
14、t;if(mazeij=1) cout<<""cout<<"" /生成右外壳cout<<endl;for(k=0;k<n;k+)cout<<""cout<<" n" /生成底部外壳(2)、生成迷宫路径图,for(i=0;i<m;i+)cout<<"n"for(j=0;j<n;j+)if(mazeij=0|mazeij=2) /2是队列中访问过的点 cout<<""if(maz
15、eij=1) cout<<""if(mazeij=3) /3是标记的可以走通的路径cout<<""(3)总界面的实现考虑到添加画图部分,对我们的原程序改动较大,因此我们没有采用画图画线输出迷宫路径,同时,我们也扩充了迷宫的功能,可以定义任意宽度和长度的迷宫并实现手动、自动生成迷宫等功能。输出界面有三个选项,1为手动生成迷宫,2为自动生成迷宫,3为推出程序。当程序运行时,设cycle为0,当选择3退出程序时,cycle为-1。void main() int i,m,n,cycle=0; while(cycle!=(-1) switc
16、h(i) case 1: /手动输出迷宫 cout<<"n请输入行数:" cin>>m; cout<<"n" cout<<"请输入列数:" cin>>n; while(m<0|m>49)|(n<0|n>49) cout<<"n抱歉,你输入的行列数超出预设范围(0-49,0-49),请重新输入nn" cout<<"n请输入行数:" cin>>m; cout<<&quo
17、t;n" cout<<"请输入列数:" cin>>n; shoudong_maze(m,n); data(m,n); print_maze(m,n); mgpath(maze,m,n); if(X!=0) result_maze(m,n); cout<<"nnPress Enter Contiue!n" getchar(); while(getchar()!='n'); break; case 2: /自动输出迷宫 cout<<"n请输入行数:" cin>
18、>m; cout<<"n" cout<<"请输入列数:" cin>>n; while(m<0|m>49)|(n<0|n>49) cout<<"n抱歉,你输入的行列数超出预设范围(0-49,0-49),请重新输入nn" cout<<"n请输入行数:" cin>>m; cout<<"n" cout<<"请输入列数:" cin>>n; zidon
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 迷宫 求解 问题 21
限制150内