[数据结构]深度与广度优先搜索：迷宫问题

数据结构课程设计 深度与广度优先搜索：迷宫问题

专业 Xxxxx 学生姓名 xxxxxx 班级 xxxxxxxxx 学号 xxxxxxxxxxxxxxxx 数据结构课程设计——深度与广度优先搜索：迷宫问题 目录

1 设计题目 .............................................................................................. 1 2 设计分析 .............................................................................................. 1 3 设计实现 .............................................................................................. 3 4测试方法 .............................................................................................. 3 4.1测试目的 ....................................................................................... 8 4.2 测试输入 ....................................................................................... 8 4.3 正确输出 ....................................................................................... 9 4.4 实际输出 ....................................................................................... 9 4.5 错误原因 ..................................................................................... 10 5 分析与探讨 ........................................................................................ 10 5.1 测试结果分析 ............................................................................. 10 5.2 探讨与改进 ................................................................................. 11 6 设计小结 ............................................................................................ 11 7 参考文献 数据结构课程设计——深度与广度优先搜索:迷宫问题

1 1 设计题目

a)迷宫问题求解的目标：寻找一条从入口点到出口点的通路。(迷宫可表示为一个二维平面图形，将迷宫的左上角作入口，右下角作出口。)例如，可以设计一个8*8矩阵maze[8][8]来表示迷宫，如下所示： 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 0 1 0 0 左下角maze[0][0]为起点，右下角maze[7][7]为终点；设“0”为通路，“1”为墙，既无法穿越。假设一只老鼠从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。 b)设计程序要求：能自动生成或者手动生成这样一个8*8矩阵；针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。如果不能，请指出；如果能，请用图形界面标出走出迷宫的路径。

2 设计分析 a)首先明确题目中的已知条件： ·迷宫是一个8*8大小的矩阵。 ·从迷宫的左上角进入，右下角为迷宫的终点。 ·maze[i][j]=0代表第i+1行第j+1列的点是通路；maze[i][j]=1代表该点是墙，无法通行。 ·迷宫有两种生成方式：手工设定和自动生成。 ·当老鼠处于迷宫中某一点的位置上，它可以向8个方向前进，分别是：“上、下、左、右、左上、左下、右上、右下”8个方向。 ·要实现这个程序，首先要考虑如何表示这个迷宫。在实例程序中使用二维数组,maze[N+2][N+2]来表示这个迷宫，其中N为迷宫的行、列数。当值为“0”时表示该点是通路，当值为“1”时表示该点是墙。老鼠在迷宫中的位置在任何时候都可以用行号row和列号col表示。 数据结构课程设计——深度与广度优先搜索:迷宫问题 2 b)为什么指定maze[N+2][N+2]表示迷宫，而不是使用maze[N][N]来表示迷宫？ ·原因是当老鼠跑到迷宫的边界点时就有可能跳出迷宫；而使用maze[N+2][N+2]就可以把迷宫的外面再包一层“1”，这样就能阻止老鼠走出格。 c)老鼠再每一点都有8种方向可以走，分别是：North，NorthEast,East,SouthEast,East,South,SouthWest,West,NorthWest.可以用数组move[8]来表示在每一个方向上的横纵坐标的偏移量，见表2—1。根据这个数组，就很容易计算出沿某个方向行走后的下一点的坐标。 Name dir Move[dir].vert Move[dir].horiz N 0 -1 0 NE 1 -1 1 E 2 0 1 SE 3 1 1 S 4 1 0 SW 5 1 -1 W 6 0 -1 NW 6 0 -1 表2—1 8种方向move的偏移量 d)迷宫问题可以用深度优先搜索方法实现。当老鼠当老鼠在迷宫中移动的时候，可能会有多种移动选择方向。程序需要记录并用栈来保存当前点的坐标，然后任意选取一个方向进行移动。由于应用栈保存了当前通道上各点的坐标，所以当前各方向上都走不通时可以返回上一个点，然后选择另一个方向前进。 ·可定义element结构用于存储每一步的横纵坐标和方向。 typedef struct{ short int row; short int col; short int dir; }element; Element stack[MAX _STACK_SIZE]; 根据表2—1可推算出每次移动后的坐标。设当前的坐标是(row,col),移动的方向是dir，移动后的点是next,则有 next_row=row+move[dir].vert; next_col=col+move[dir].horiz; ·可用另一个二维数组mark[N+2]来记录哪些点已经被访问过。当经过点maze[row][col]时，相应地将mark[row][col]的值从0置为1。 数据结构课程设计——深度与广度优先搜索:迷宫问题 3 e)本程序支持自动生成迷宫。利用random(2)函数可随机产生0或1，来支持迷宫的自动生成。注意maze[N][N]和maze[1][1]一定要等于0，因为他们分别是起点和终点。 f)如果找到了一条走出迷宫的路径，则需要在屏幕中打印出走出迷宫的信息。这里要用到graphics.h。为画出效果图，可使用circle()函数画圆，outtexttxy()函数标记文字，并用line()函数来划线。 g)程序的主要函数如下： ·函数void add(int*top,element item)，将当前步的信息item压入到作为全局变量的栈stack(栈顶为top)中。 ·函数element delete(int * top)，返回stack中栈顶的元素。 ·函数void path(void)，采用深度优先搜索算法，首先取出栈顶元素作为当前点选择一个方向前进到下一个点（如果能走得话）；然后，将下一个点压入栈，并将二维数组mark中对应的值改为1，表示该点已经走到了。反复执行上面两步，当走到一个点不能再走下去了（已经尝试了各个方向并失败），并且这个点不是终点，则这个点的上一个点会从栈中被跑抛出，从而“回朔”到上一点；当遇到终点时，程序结束，找到一条路径；当在程序循环过程中遇到栈为空，则说明该迷宫根本无法走到终点。

3 设计实现 /******This program can be compiled under VC6.0******/ #include #include #include #include #include #define N 8 #define MAX_STACK_SIZE N*N /*最大栈容量 */ #define TRUE 1 #define FALSE 0 #define LEN (300/N) /******结构体记录每一步的横坐标，纵坐标和方向******/ typedef struct { short int row; short int col;