数据结构 迷宫问题(栈、c)

《数据结构 迷宫问题(栈、c)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2012～2013学年第二学期课程数据结构与算法课程设计名称迷宫问题（栈）学生姓名陈强学号1104014026指导教师李红专业班级计算机科学与技术11级2013年3月题目：迷宫问题（栈）：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走

2、到下一坐标的方向。一、问题分析和任务定义此程序可以用二维数组存储迷宫数据，设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通，并默认以东、南、西、北的顺序进行搜索路线。将走过的路线放入链栈中，当走出迷宫时，栈中及走出迷宫的路线；当走不出时，栈为空。实现本程序需要解决以下几个问题：1.如何通过二维数组建立并存储迷宫。2.如何进行路径搜索。3.按一个方向搜索不到出路时怎么办？4.将符合条件的路线存储。5.搜索到出路时按顺序输出路线。首先，

3、可以用二维数组存储迷宫，0和1分别表示迷宫中的通路和障碍,为处理方便起见，建立迷宫时在迷宫四周加一圈障碍。例如一个5*5的迷宫用二维数组可表示为：intmaze[7][7]={1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,0,1,1,0,0,0,0,0,1,1,0,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1};路径搜索时，需要知道出口和入口的坐标，本程序默认为（1,1）、（m，n）。定义一个移动坐标(xc,yc），用以记录搜索路线时当前位置的坐标。搜索时默认按照东、南、西、

4、北的优先顺序进行查找，其中，向东搜索用“1”表示，向南、向西、向北分别用“2”、“3”、“4”表示，“0”表示方向未知。当向东无路时，再向西查找……当某位置为通路时（maze[i][j]==0），则将这一步的信息放入栈中。同时，将此步设置为障碍，防止下一步搜索时出现“回头”的现象。若为障碍时，此时，将栈中元素出去，即沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。将栈中的元素输出，即寻找到的出迷宫的路线。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。如上面的例子中，最后输出的路线为：（1，1,1）、（1

5、,2,1）、（1,3,1）、（1,4,1）、（1,5,2）、（2,5,2）、（3,5,3）、（3,4,3）、（3,3,3）、（3,2,3）、（3,1,2）、（4,1,2）、（5,1,1）、（5,2,1）、（5,3,1）、（5,4,1）、（5,5,0）。二、数据结构的选择和概要设计迷宫数据用二维数组intmaze[SIZE+2][SIZE+2]来存储即可(迷宫四周加障碍，所以行列数加2)，在定义了迷宫的行列数后，利用两个for循环即可用键盘录入迷宫信息，并在迷宫周围加围墙。存储搜索路线按题目要求采用链栈的数据结构，用非递归的方法求解路线

6、。图（1）为程序的流程图。三、详细设计和编码首先建立迷宫。用户自定义迷宫的行列数m、n，利用嵌套循环将迷宫信息存储于数组maze[m+2][n+2]中：for(i=0;i

7、

8、i==m+1

9、

10、j==0

11、

12、j==n+1)//在迷宫周围加障碍maze[i][j]=1;elsescanf("%d",&maze[i][j]);}}在对迷宫探索时，每一步都有四个方向可以搜索，为实现这一操作，可建立一个移动数组move[8]。向东搜索时坐标变化为横坐标不变，纵坐标加一，向南搜索

13、时坐标变化为横坐标加一，纵坐标不变，向西搜索时坐标变化为横坐标不变，纵坐标减一，向北搜索时坐标变化为横坐标减一，纵坐标不变。这样就完成了向四个方向的搜索操作。建立链栈用于存储路线信息。链栈的数据域为包含了i，j，d的结构体，这样就能将路线的每一步信息存储下来。再建立一个移动坐标，以记录搜索过程中变化方向时坐标的变化。路线搜索：1.先将入口信息入栈，当栈不为空时，转2，否则转7；2.将当前位置信息（item->x、item->y、item->d）赋给动态变量（x、y、d）；3.此位置是否有方向可搜索，是则移动到下一方向，并判断是否为通路

14、，若为通路，转4，若不为通路，换个方向继续搜索，否则转6；4.则将此位置信息入栈，同时将此位置设置为障碍，避免下一步搜索时返回原路，并判断此位置是否为出口，是则转8，不是转5；5.初始化搜索方向，转3；6.执行出栈，判断