数据结构课程设计报告迷宫问题.doc
课程设计报告课程名称： 数据结构课程设计 课程题目： 迷宫问题 数据结构课程设计题目一: 迷宫问题实验目的综合运用数组、递归等数据结构知识，掌握、提高分析、设计、实现及测试程序的综合能力。实验内容及要求以一个M×N的长方阵表示迷宫，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 <stdio.h>#include <stdlib.h>#define n1 5#define n2 5typedef struct nodeint 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",&mazepq);/初始化top，置所有方向为下for(i=0;i<n1 * n2;i+)topi.c=1;printf("the maze is:n");/打印原迷宫for(i=0;i<n1;i+)for(j=0;j<n2;j+)printf(mazeij?"1 ":"0 ");printf("n");i=0;topi.x=0;topi.y=0;maze00=2;/回溯算法doif(topi.c<5) /还可以向前试探if(topi.x=4&&topi.y=4) /已找到一个组合 /打印路径printf("The way %d is:n",m+);for(j=0;j<=i;j+)printf("(%d,%d)->",topj.x,topj.y);printf("n");/打印选出路径的迷宫for(j=0;j<n1;j+)for(k=0;k<n2;k+)if(mazejk=0)printf("0 ");else if(mazejk=2) printf("# ");else printf("1 ");printf("n");mazetopi.xtopi.y=0;topi.c=1;i-;topi.c+=1;continue;switch(topi.c) /向前试探case 1:if(mazetopi.xtopi.y+1=0)/下i+;topi.x=topi-1.x;topi.y=topi-1.y+1;mazetopi.xtopi.y=2;elsetopi.c+=1;break;case 2:if(mazetopi-1.x-1topi.y=0)/左i+;topi.x=topi-1.x-1;topi.y=topi-1.y;mazetopi.xtopi.y=2;elsetopi.c+=1;break;case 3:if(mazetopi.xtopi.y-1=0)/上i+;topi.x=topi-1.x;topi.y=topi-1.y-1;mazetopi.xtopi.y=2;elsetopi.c+=1;break;case 4:if(mazetopi.x+1topi.y=0)/右i+;topi.x=topi-1.x+1;topi.y=topi-1.y;mazetopi.xtopi.y=2;elsetopi.c+=1;break;else /回溯if(i=0) return; /已找完所有解mazetopi.xtopi.y=0;topi.c=1;i-;topi.c+=1;while(1);程序效果图
