迷宫求解实验报告

《迷宫求解实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、本科学生设计性实验报告数据结构课程设计项目组长钟杰学号0082865专业软件工程班级软件081成员郑兴林、邱凯实验项目名称迷宫求解指导教师及职称涂保东讲师开课学期2009至2010学年第二学期一、实验设计方案实验名称：深度优先搜索之迷宫求解实验时间：2010-3-31至2010-4-8实验场地：Z110成员角色：程序员：郑兴林测试员：邱凯文档员：钟杰软件环境：WindowsXP、VC++6.01、实验目的（简单介绍实验内容和涉及的算法背景，说明实验任务）迷宫以一个m×n的长方阵maze[m][n]表示，0和1分别

2、表示迷宫中的通路和障碍。本实验设计一个程序，对其任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。其中迷宫的生成可以是有系统随机产生，也可以从文件中进行读取。从迷宫的左上角进入，右下角为迷宫的终点maze[i][j]=0表示第i+1行第j+1列的点是通路；maze[i][j]=1代表该点是墙，无法通行。当处于迷宫中某一点的位置上，可以向8个方向前进，分别是：“上，下，左，右，左上，左下，右上，右下”8个方向。迷宫问题采取的是深度优先算法实现的，实际上也就是一个递归的过程。因为在查找通路的时候，移动

3、的方向是有多种的，程序利用栈来保存当前点的坐标，然后在这点A的基础上任意取一个方向（上、下、左、右、左上、左下、右上、右下）移动，如果在下一个方向存在通路时，就将该点B入栈，并在该点B的八个方向上任意取一个方向，如果不存在通路，则将该点B退栈，并从A点中剩余的七个方向中移动，如此循环下去，最终找出通路。在生成迷宫图的时候可以有两种方法供用户选择，一种是由系统随机生成，另外就是通过从文件中进行读取。在用于存储“0”与“1”的二维数组应该在行数以及列数上多增加2，并且所新增加的行与列都在最外层，默认是墙，为的是保证不

4、出界。如果不新增，当到边界上时，根据上面的算法，就会出现向某个方向上移动的时候，该方向上没有相应的“0”（通道）或者“1”（墙），二维数组会因此而出现越界问题。2、实验思路（详细描述解决问题的整体思路、数据结构及算法思想等）首先实现一个链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（x,y,pre）的形式输出，其中（x,y）指示迷宫中的一个坐标，pre表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3

5、，1，2），……对于d在函数中有相应的方向键代表数字1~~4.程序定义了以下四个类classDataType定义描述迷宫中当前位置的数据类型，其公有变量为x(行坐标)、y（列坐标）、pre(东南西北加其他四个方向)classMove定义下一个位置的方向classLinkNode链表结点定义，其公有变量为Tdata、next域classStack链栈存储定义及功能实现，主要的功能函数为创建栈、入栈、出栈、取栈顶元素、清空栈等。ClassStack{private:LinkNode*top;//指向第一个结点的栈顶指

6、针public:Stack();//构造函数，置空栈~Stack();//析构函数voidPush(DataTypedata);//把元素data压入栈中DataTypePop();//使栈顶元素出栈DataTypeGetPop();//取出栈顶元素voidClear();//把栈清空boolIsEmpty();//判断栈是否为空};主要功能函数介绍：q.int**GetMaze(int&m,int&n)函数功能：存取迷宫的二维指针函数，申请一个(m+2)*(n+2)的二维数组，对于数组中的内容（也就是迷宫的通路

7、与墙的情况），有两种选择可以得到，一个是通过系统本身随机生成，另外一个就是从已保存的文件中进行读取。由系统随机生成迷宫的代码：maze=newint*[m+2];//申请长度等于行数加2的二级指针for(i=0;i

8、0或1赋给迷宫数组maze[i][0]=maze[i][n+1]=1;//边界处理maze[0][i]=maze[m+1][i]=1;//边界处理maze[m+1][0]=maze[m+1][n+1]=1;//边界处理maze[m][n]=0;//入口以及出口的设置}从文件中读取数据生成迷宫的代码：maze=newint*[m+2];//申请长度等于行数加2的二级指针fo