实验报告：迷宫问题
题目：编写一个求解迷宫通路的程序
一、 需求分析：
1) 采用二维数组maze[M][N]来表示迷宫，其中：maze[0][j]和maze[M-1][j](0≤j≤N-1)
及maze[i][0]和maze[i][N-1](0≤i≤M-1)为添加在迷宫外围的一圈障碍。数据元素值0表示通路，1表示障碍。限定迷宫的大小M≤8，N≤10. 2) 本次实验直接在主程序中输入表示迷宫的二维数组。另外，迷宫的入口和出口位置
都将在主程序中直接设置。
3) 实验中求出的迷宫通路用“-”表示，迷宫的障碍用“#”表示，已走过但未能求出
通路的路径用“@”表示。
4) 本程序只求出一条成功的通路。
5) 本次实验将直接输出构建迷宫的二维数组、初始化的二维数组和求解后的迷宫数组。
二、 概要设计：
数据结构及其抽象数据类型的定义。
（1）栈的抽象数据类型 ADT Stack{
数据对象：D={ai| ai∈CharSet,i=1,2?n,n>=0} 数据关系：R1={
操作结果：构造一个空栈S。 DestroyStack(&S)
初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(&S)
初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S)
初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S)
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 GetTop(S，&e)
初始条件：栈S已存在。
操作结果：若栈S不空，则以e返回栈顶元素。 Push(&S， e)
初始条件：栈S已存在。
操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(&S，&e)
初始条件：栈S已存在。
操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse（S，visit（）） 初始条件：栈S已存在。
操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit（）。 } ADT Stack
（2）迷宫的抽象数据类型 ADT maze{
数据对象：D={ai,j| ai,j∈{ ' ','#','@','*'},0<=i<=m+1,0<=j<=n+1,m,n<=10} 数据关系：R={ROW,COL} 基本操作：
InitMaze(&M,a,row,col)
初始条件：二维数组a[row+2][col+2]已存在，其中自第1行至第row+1行，每行中自第1列至第col+1列的元素已有值，并且以值0表示通路，以值1表示障碍。
操作结果：构成迷宫的字符型数组，以空白字符表示通路，以字符‘#’表示障碍，并在迷宫四周加上一圈障碍。
MazePath(&M)
初始条件：迷宫M已被赋值。
操作结果：若迷宫M中存在一条通路，则按以下规定改变迷宫M的状态：以字符’*’表示路径上的位置，字符‘@’表示“死胡同”，否则迷宫的状态不变。
PrintMaze（M）
初始条件：迷宫M已存在。
操作结果：以字符形式输出迷宫。 } ADT maze
三、 详细设计：
1、 程序具体代码为：
// MazePath.cpp : 定义控制台应用程序的入口点。 //
#include \
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0
#define INFEASIBLE -1 #define OVERFLOW -2 #include
#include
#define RANGE 20 //RANGE为实际分配的空间行列数 #define M 8 //maze数组的行数 #define N 11 // maze数组的列数
typedef struct //表达迷宫元素位置信息的坐标 {
int r,c; }PosType;
typedef struct//m，n为待处理的迷宫的行列数，RANGE为实际分配的空间行列数 {
int m,n;
char arr[RANGE][RANGE]; }MazeType;
typedef int directiveType;//东西南北方向用1，2，3，4整数对应
typedef struct//路径拟用栈来存储，此处定义栈元素中数据域的信息 {
int step;//存储到达该点时经历的步数 PosType seat;//该点位置
directiveType di;//从该点位置走向下一位置的方向 }ElemType;
typedef struct NodeType//路径拟用链栈来存储 {
ElemType data;
struct NodeType *next; }NodeType,*LinkType;
typedef struct//对链栈的头指针和元素个数进行封装 {
LinkType top; int size; }Stack;
//以上是对存储结构逐层进行定义 void InitStack(Stack &S) { //构建空链栈，不带头结点 S.top=NULL; S.size=0; }
Status MakeNode(LinkType &p,ElemType e)
{ //创建一个新结点，以便插入，本函数可作为链式存储创建结点的通用函数，可用于链表、链栈、链队的插入操作
p=(NodeType *)malloc(sizeof(NodeType)); if(!p)
return FALSE; p->data=e;
p->next=NULL; return TRUE; }
Status Push(Stack &S,ElemType e)
{ //入栈操作，在这里本质上是栈头（链表头）进行插入 LinkType p; if(MakeNode(p,e)) {
p->next=S.top; S.top=p; S.size++;
return TRUE; }
return FALSE; }
Status StackEmpty(Stack S)
{ //判断是否为空栈，这里是通过top指针为NULL来判断的，本质上也可以通过size是否为0来判断
if(S.top==NULL) return TRUE; return FALSE; }
Status Pop(Stack &S,ElemType &e) { //出栈操作，本质上是删除表头元素 LinkType p;
if(StackEmpty(S)) return FALSE; else {
p=S.top;
S.top=S.top->next; e=p->data; S.size--; free(p);
return TRUE; } }
Status pass(MazeType maze,PosType curpos)
{ //判断迷宫Maze中，当前位置curpos是否是一个可达位置 int m,n; //注意这里的m，n只是表达下标的临时变量，与前面出现的m，n是不一样的
m=curpos.r; n=curpos.c;
if(maze.arr[m][n]==' ') return TRUE; return FALSE; }
Status Same(PosType curpos,PosType end) { //判断当前位置curpos是否已达出口
if(curpos.r==end.r && curpos.c==end.c) return TRUE; return FALSE; }
void FootPrint(MazeType &maze,PosType curpos)
{ //在迷宫中标识走过的位置，避免在有路可走时还走回头路出现死循环 int m,n; m=curpos.r; n=curpos.c;
maze.arr[m][n]='-'; }
PosType NextPos(PosType curpos,int di)
{ //通过di的值，确定下一步的位置，下一步位置实际是当前位置的四个邻居中的一个
switch(di) {
case 1:
curpos.c++; //向东走 break; case 2:
curpos.r++; //向南走 break; case 3:
curpos.c--; //向西走 break;
数据结构试验报告-迷宫问题
