数据结构课程设计报告----迷宫问题

《数据结构课程设计报告----迷宫问题》由会员分享，可在线阅读，更多相关《数据结构课程设计报告----迷宫问题（7页珍藏版）》请在毕设资料网上搜索。

1、 课程设计报告课程设计报告 课程名称： 数据结构课程设计 课程题目： 迷宫问题 数据结构课程设计数据结构课程设计 题目一题目一: 迷宫问题迷宫问题 实验目的实验目的 综合运用数组、递归等数据结构知识，掌握、提高分析、设计、实现及测试 程序的综合能力。 实验内容及要求实验内容及要求 以一个 M N 的长方阵表示迷宫，0 和 1 分别表示迷宫中的通路和障碍。设 计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通 路的结论。 （1） 根据二维数组，输出迷宫的图形。 （2） 探索迷宫的四个方向：RIGHT 为向右，DOWN 向下，LEFT 向左，UP 向 上，输出从入口到出口的行走

2、路径。 测试数据测试数据 左上角（1，1）为入口，右下角（8，9）为出口。 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 实现方法实现方法 可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则 继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一 条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通 路。

3、具体思路及结果 首先首先，事先声明好矩阵，矩阵长宽，栈顶元素，矩阵点左边等。 然后然后，要求用户尽享交互输入迷宫(maze)各个点处的值(1 或 0) 保存并初始化栈顶元素，置所有方向数为下。 之后之后，一比较整洁大方的形式打印原迷宫供用户查看。 同时同时，开始本程序的重点，回溯算法，以 1,2,3,4 分别表示下上左右。 多次使用 for 循环寻找可以到达出口的路径，期间分别先后试探下，左，上，右 置已经走过的点为 2 防止死循环，寻找完后存在 TOP栈中。 最后最后，打印找到的当前迷宫路径并以（坐标 1）（坐标 2）的形式输出路 径，并且在原迷宫的基础上表示出当前找到的路径，以#代表走过的

4、路径 0 代表 没有障碍的地方，1 代表障碍，画出迷宫路径图，并且立刻执行下一次循环，寻 找下一条可通过的路径，并还原迷宫图，继续寻找路径知道找到所有解后自动退 出。 具体代码 #include #include #define n1 5 #define n2 5 typedef struct node int x;/存 x 坐标 int y;/存 y 坐标 int c;/存该点可能的下点所在的方向，表示向 1 表示向下，2 左，3 向上，4 向右 linkstack; linkstack top25; int rows=0; int cols=0; int i,j,k,m,p,q=0; int mazen1n2; void main() for(p=0;p=n1-1;p+) for(q=0;q=n2-1;q+) printf(“请输入第%d 行第%d 列的数n“,p+1,q+1); scanf(“%d“, /初始化 top，置所有方向为下 for(i=0;in1 * n2;i+