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

课程设计报告课程名称： 数据结构课程设计 课程题目： 迷宫问题 《数据结构》课程设计题目一: 迷宫问题[实验目的]综合运用数组、递归等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力[实验内容及要求]以一个MN的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论1） 根据二维数组，输出迷宫的图形2） 探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从入口到出口的行走路径[测试数据]左上角（1，1）为入口，右下角（8，9）为出口001000100010001000101101011100100001000001000101011110011100010111000000[实现方法]可使用回溯方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路[具体思路及结果] 首先，事先声明好矩阵，矩阵长宽，栈顶元素，矩阵点左边等。

然后，要求用户尽享交互输入迷宫(maze)各个点处的值(1或0)保存并初始化栈顶元素，置所有方向数为下 之后，一比较整洁大方的形式打印原迷宫供用户查看 同时，开始本程序的重点，回溯算法，以1,2,3,4分别表示下上左右多次使用for循环寻找可以到达出口的路径，期间分别先后试探下，左，上，右置已经走过的点为2防止死循环，寻找完后存在TOP[]栈中 最后，打印找到的当前迷宫路径并以（坐标1）——>（坐标2）的形式输出路径，并且在原迷宫的基础上表示出当前找到的路径，以#代表走过的路径0代表没有障碍的地方，1代表障碍，画出迷宫路径图，并且立刻执行下一次循环，寻找下一条可通过的路径，并还原迷宫图，继续寻找路径知道找到所有解后自动退出[具体代码]#include #include #define n1 5#define n2 5typedef struct node{ int x;//存x坐标 int y;//存y坐标 int c;//存该点可能的下点所在的方向，表示向1表示向下，2左，3向上，4向右}linkstack;linkstack top[25];int rows=0;int cols=0;int i,j,k,m,p,q=0;int maze[n1][n2];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",&maze[p][q]); } } //初始化top[]，置所有方向为下 for(i=0;i",top[j].x,top[j].y);} printf("\n"); //打印选出路径的迷宫 for(j=0;j