数据结构实验报告
实验三 迷宫
姓名：xxx 学号：xxx 专业：信息安全
实验日期：第十二.三周周日
实验三 迷宫 一、实验目的
1、了解回溯法在求解迷宫问题中的应用 2、进一步掌握栈的使用
二、实验内容
用回溯法求解迷宫问题，可以用一个栈保存探索的序列。并且在该迷宫的行走中，站在一点可以有八个方向选择。 比如如下的迷宫
Enter-> 0 1 1 1 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 0
0 0 0 0 1 0 1 1 0 0 --> EXIT
下面是可能的路径（注意：从入口到出口可能有多条路径，优先选择的方向不同，路径可能也不一样！）
Path: ( maze[0][0], maze[1][0], maze[1][1], maze[1][2], maze[2][2],
maze[3][2], maze[3][3], maze[4][3], maze[5][3], maze[6][3],
maze[6][4], maze[6][5], maze[5][5], maze[4][5], maze[3][5], maze[2][5], maze[2][6], maze[1][6], maze[0][6], maze[0][7], maze[0][8], maze[1][8], maze[2][8], maze[3][8], maze[4][8], maze[5][8], maze[5][7], maze[6][7], maze[7][7], maze[8][7], maze[8][8], maze[8][9], maze[9][9])
Enter-> X 1 1 1 0 0 X---X---X 0
1、提示： （1）数据结构：
? 用二维数组MAZE[m+2][n+2]表示迷宫的结构，数组中的值为1表示是墙，
为0表示可以走通。（用MAZE[m+2][n+2]而不用MAZE[m][n]的原因在于想表示和编写代码的时候简单些，而且让迷宫周围都是墙，防止错误的走出去） ? 用二维数组MARK[m+2][n+2]表示迷宫是否被走过，主要是为了回溯时已经
证明走不通的路线就不要再去走了。（用MARK[m+2][n+2]而不用MARK[m][n]的原因在于想表示和编写代码的时候简单些）
X---X---X 1 0 0 X 1 X 0 0 1 X 1 1 X---X 1 X 0 0 1 X---X 1 X 1 1 X 0 0 1 0 X 1 X 1 1 X 0 1 1 1 X 1 X 1 X---X 0 0 0 1 X---X---X 1 X 1 1 0 0 1 0 0 0 1 X 1 1 0 1 1 0 1 0 1 X-- X-- X 0 0 0 0 1 0 1 1 0 X --> EXIT
? 二维数据MOVE[8][2]是为了更方便的移动到下一步，改变坐标。这个二维数
组是为了更好的转换坐标（八个方向，从0到7），而且也能避免重复走路 ? 用栈保存走过的路径 （2）输出：
? 迷宫布局，用0表示可以走通的地方，用1表示墙
? 如果能走通，则输出路径和路径的长度；若不能走通，则输出提示不能走通 ? 带有路径的迷宫布局
头文件部分
#ifndef MIG_H #define MIG_H struct zhan { int MAX; int n; int*s; };
typedef struct zhan*seqstack; seqstack voidzhan(int m);
int isnullzhan(seqstack pastack); void yazhan(seqstack pastack,int k); void chuzhan(seqstack pastack); void nizhan(seqstack pastack); int topzhan(seqstack pastack); void printzhan(seqstack pastack);
void migonglujin(int maze[8][11],int direction[4][2],int x1,int y1,int x2,int y2,int m);#endif
函数算法实现部分
#include\#include
seqstack voidzhan(int m)//创建一个空栈
{ seqstack pastack=(seqstack)malloc(sizeof(struct zhan)); if(pastack!=NULL)
{ pastack->s=(int*)malloc(sizeof(int)*m); if(pastack->s )
{ pastack->MAX=m; pastack->n=-1;