实验报告
【实验名称】 【实验目的】
1. 了解栈的基本操作以及充分理解栈的特点。熟悉掌握栈的基本操作和结构体的运用。
2. 学会用栈或者递归方法解决迷宫问题。
项目一 迷宫问题的求解
【实验原理】
1.本次实验中，以二维数组maze[row][col]表示迷宫，0表示通路，1表示墙，在构建迷宫时，为了清晰显示，在最外层添加一圈墙。
2.算法的核心思想是利用栈后进先出的特点，对迷宫进行探索，如果此路可行，则将此坐标的信息入栈，如果此路不通，则将此坐标的信息出栈。
3.输入形式：根据控制台的提示，依次输入迷宫的行数、列数，然后输入迷宫，再输入入口和出口坐标。
4.输出形式：由用户选择，由递归、非递归两种求解方式输出一条迷宫通路。以非递归方式会显示一种求解方案，并给出相应的三元组序列和迷宫方阵；以递归方式则会显示出所有的路线。
【实验内容】
1. 需求分析 （1） 问题描述
以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
要求以递归和非递归两种方式分别输出一条迷宫的通路，以带方向坐标和迷宫图像表示。
（2） 基本要求
（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。
（2）编写递归形式的算法，求得迷宫中所有可能的通路。 （3）以方阵形式输出迷宫及其通路。
2. 概要设计
（1） 栈的抽象数据类型 ADT Stack{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={
InitStack( &S )
操作结果：构造一个空栈S。 DestroyStack ( &S )
初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack( &S )
初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty( S )
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 StackLength( S )
初始条件：栈S已存在。
操作结果：返回S的数据元素个数，即栈的长度。 GetTop( S, &e )
初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push( &S, e )
初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。 Pop( &S, &e )
初始条件：栈S已存在且非空。
操作结果：删除S的栈顶元素，并用e返回其值。 }ADT Stack
（2） 程序模块
A. 主程序模块： int main() { }
B. 栈模块：
实现栈抽象数据类型 C. 迷宫模块：
实现迷宫抽象数据类型
3. 详细设计 （1） 类型定义
typedef struct {
int x; int y;
}coordinate; //迷宫中坐标类型
typedef struct {
int x; //x行 int y; //y列
int d; //下一步的位置 }SElemType;//数据类型
typedef struct Stack {
SElemType elem; struct Stack *next;
}Stack,*LinkStack; //链栈定义 （2） 递归求解算法
void MazePath2(int maze[M][N],int a,int b,coordinate end,int m,int n) //采用递归的方式进行四个方向的探索 {
maze[a][b]=-1; //起点标记为-1，即一定正确的通路，每次递归便将递归的坐标标记为正确的通路
if(a==end.x&&b==end.y) {
printf(\
PrintMaze2(maze,m,n); //找到了路径，绘制地图 }
if(maze[a][b+1]==0)
MazePath2(maze,a,b+1,end,m,n); //向右探索