《数据结构课程设计——迷宫求解问题》由会员分享，可在线阅读，更多相关《数据结构课程设计——迷宫求解问题（53页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计：迷宫实验报告任务分配：程序员： 主要任务：负责整体的算法设计以与程序的主要源代码的编 写。测试员： 主要任务：负责在程序员每完成一个阶段对程序进行挑错， 测试主程序并对实验结果进行整理分析，最后完成实验报告的第三、 四部分即测试结果与分析探讨的内容。文档员： 主要任务：负责对程序与界面的美观提出改善意见，查找程 序的小漏洞，负责撰写实验报告的第一、二部分即实验内容简介与算 法描述的内容。同时完成整个文档的整合，使整篇报告排版、文字风 格统一。一、 简介图的遍历就是从指定的某个顶点 （称其为初始点） 出发，按照一定的搜 索方法对图中的所有顶点各做一次访问过程。根据搜索方法不同，
2、遍历一 般分为深度优先搜索遍历和广度优先搜索遍历。本实验中用到的是广度优先搜索遍历。即首先访问初始点Vi,并将其标 记为已访问过，接着访问 Vi的所有未被访问过的邻接点，顺序任意，并均 标记为已访问过，以此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。鉴于广度优先搜索是将所有路径同时按照顺序遍历，直 到遍历出迷宫出口，生成的路径为最短路径。因此我们采用了广度优先搜 索。无论是深度优先搜索还是广度优先搜索， 其本质都是将图的二维顶点结 构线性化的过程，并将当前顶点相邻的未被访问的顶点作为下一个顶点。 广度优先搜索采用队列作为数据结构。本实验的目的是设计一个程序， 实现手动或者自动
3、生成一个 n xm矩阵 的迷宫，寻找一条从入口点到出口点的通路。具体实验内容如下：选择手动或者自动生成一个 nxm 的迷宫，将迷宫的左上角作入口，右 下角作出口，设“ 0 ”为通路， “ 1”为墙，即无法穿越。假设一只老鼠从 起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右 上、右下” 8个方向行走。如果迷宫可以走通，则用“”代表“1 ”，用“”代表“ 0”，用“”代表行走迷宫的路径。输出迷宫原型图、迷宫 路线图以与迷宫行走路径。如果迷宫为死迷宫，则只输出迷宫原型图。二、 算法说明根据实验内容，本实验主要设计实现手动输入迷宫，判断迷宫能否走 通；自动生成迷宫，判断迷宫能否走通。
4、迷宫算法的整体思想如下：了符迷宫罐宫有解打卬適瞪1、迷宫的创建迷宫中存在通路和障碍，为了方便迷宫的创建，可用 0 表示通路，用1 表示障碍，这样迷宫就可以用0、1 矩阵来描述。设置迷宫的长为n 、宽为m，范围为49 X49，用int mazeN+2M+2来表示，这样相当于在迷宫外层包了一层 1 ，即防止搜索路径时跳出迷宫。(1 )手动生成迷宫void hand_maze(int m,int n)/ 手动生成迷宫int i,j;for(i=0;im;i+)for(j=0;jmazeij;(2) 自动生成迷宫void automatic_maze(int m,int n)/ 自动生成迷宫int i
5、,j;for(i=0;im;i+) for（j=0;jn;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 。实验数据如下：X012300101100102101031100123456789(0,(1,1(1,0(0,2(2，(1,3(3,2(2,3(3,30)1)-111223456算法如下：int pat
7、h(i nt maze5151,i nt m,i nt n)/路径求解X=1;/初始值定为1struct point p=0,0,-1;/ 定义入口节点为1时，迷宫不可解/ 标当行8个cout=0)&(p.row-1)m)&(p.col+0)=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)&(mazep.row+0p.col+1=0)visit(p.row+0,p.col+1,maze);if(p.row+1)m)&(p.col+1)n)
8、&(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.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)=0)&(mazep.ro/ 东北/ 东/ 东南/ 南/ 西南visit(p.row+0,p.col-1,maze);/ 西if(p.row-1)
9、=0)&(p.row-1)m)&(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;coutvv f vvendl;printf(%d,%d)n,p.row+1,p.col+1);coutvv vvf vvendl;/ 逆序mazep.rowp.col=3;将路径标记为 3while(p.predecessor!=-1)p=queuep.predecessor; printf(%
10、d,%d)n,p.row+1,p.col+1);coutvv vv f vvendl;cout 入口 endl;elsecout 此迷宫无解！ nn;X=0;return 0;3、 输出迷宫图(1 )、生成迷宫图，将迷宫外壳输出为,将迷宫中的0输出为，将1输出为for(k=0;kn;k+)/ 这两个黑三角用cout ;来生成顶部外壳for(i=0;im;i+)coutn;/ 生成左外壳cout ;for(j=0;jn;j+)if(mazeij=0) cout;if(mazeij=1) cout;cout ;coutendl;for(k=0;kn;k+)cout ;coutn;2)、生成迷宫路径
11、图，for(i=0;im;i+)coutn;for(j=0;jn;j+) if(mazeij=0|mazeij=2) 列中访问过的点cout ;if(mazeij=1)/ 生成右外壳/ 生成底部外壳/2 是队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)switch(i)case 1: / 手动输出
