《数据结构（C语言版）》栈的应用之迷宫求解
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对紫皮书第三章3.2节栈的应用举例中3.2.4迷宫求解的代码，3.2.1数制转换、3.2.2括号匹配的检验、3.2.3行编辑程序的代码已在上一节写出，话不多说上运行结果：
可执行代码如下
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
#define LENGTH 10
#define WIDTH 10
typedef int Status;
typedef int MazeType[LENGTH][WIDTH];//迷宫大小
typedef struct
{
int row;//行
int col;//列
}PosType;
typedef struct
{
int ord;//通道块在路径上的“序号”
PosType seat;//通道快在迷宫中的“坐标位置”
int di;//从此通道块走向下一通道块的“方向”
//1表示东，2表示南，3表示西，4表示北
}SElemType;//栈的元素类型
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
void FootPrint(PosType curpos, int curstep);//留下足迹
void ShowMaze(PosType start);//打印地图
Status Pass(PosType pos);//判断当前位置是否可以通过
PosType NextPos(PosType CurPos, int i);//返回下一位置
void MarkPrint(PosType pos);//标记走不通的位置
Status MazePath(MazeType maze, PosType start, PosType end);//若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈中
Status InitStack(SqStack& S);//初始化一个空栈
Status Push(SqStack& S, SElemType e);//顺序栈的入栈
Status Pop(SqStack& S, SElemType& e);//顺序栈的出栈
Status StackEmpty(SqStack S);//判断栈是否为空
//用全局变量表示迷宫地图
MazeType maze =
{
/*用0表示墙，用1表示路*/
//0,1,2,3,4,5,6,7,8,9
{0,0,0,0,0,0,0,0,0,0}, //0
{0,1,1,0,1,1,1,0,1,0}, //1
{0,1,1,0,1,1,1,0,1,0}, //2
{0,1,1,1,1,0,0,1,1,0}, //3
{0,1,0,0,0,1,1,1,1,0}, //4
{0,1,1,1,0,1,1,1,1,0}, //5
{0,1,0,1,1,1,0,1,1,0}, //6
{0,1,0,0,0,1,0,0,1,0}, //7
{0,0,1,1,1,1,1,1,1,0}, //8
{0,0,0,0,0,0,0,0,0,0} //9
};
int main()
{
printf("迷宫地图如下：\n");
PosType Start = { 1,1 };
PosType End = { 8,8 };
ShowMaze(Start);
if (MazePath(maze, Start, End))
{
printf("该迷宫的一条通路为：\n");
ShowMaze(Start);
}
return 0;
}
void FootPrint(PosType curpos, int curstep)//留下足迹
{
maze[curpos.row][curpos.col] = curstep;
}
void ShowMaze(PosType start)//打印地图
{
for (int i = 0; i < LENGTH; i++)
{
for (int j = 0; j < 10; j++)
{
if (i == start.row && j == start.col)//打印起始位置
{
printf("1 ");
}
else if (maze[i][j] == 0)
{
printf("■");
}
else if (maze[i][j] == 1 || maze[i][j] == -1)
{
printf(" ");
}
else
{
printf("%-2d", maze[i][j]);
}
}
printf("\n");
}
}
Status Pass(PosType pos)//判断当前位置是否可以通过
{
if (maze[pos.row][pos.col] == 1)
{
return TRUE;
}
return FALSE;
}
PosType NextPos(PosType CurPos, int i)//返回下一位置
{
switch (i)
{
case 1:
++CurPos.col;//向东走一步
break;
case 2:
++CurPos.row;//向南走一步
break;
case 3:
--CurPos.col;//向西走一步
break;
case 4:
--CurPos.row;//向北走一步
break;
}
return CurPos;
}
void MarkPrint(PosType pos)//标记走不通的位置
{
maze[pos.row][pos.col] = -1;//-1表示该位置走不通
}
Status MazePath(MazeType maze, PosType start, PosType end)//若迷宫中存在从入口start到出口end的通道，则求得一条存放在栈中
{
SqStack S;
PosType curpos;//cur为current的缩写，表示当前位置(position)
SElemType e;
int curstep;//表示当前走过的步数
InitStack(S);
curpos = start;//设定“当前位置”为“入口位置”
curstep = 1;//记录当前走过的步数
do
{
if (Pass(curpos))//当前位置可以通过，即是未曾走到过的通道块
{
FootPrint(curpos, curstep);//留下足迹
printf("step%d:\t(%d,%d)\n", curstep, curpos.col, curpos.row);
e = { curstep,curpos,1 };//1表示当前方位为东
Push(S, e);//加入路径
if (curpos.col == end.col && curpos.row == end.row)//到达终点（出口）
{
printf("到达终点：(%d,%d)\n", e.seat.col, e.seat.row);
return TRUE;
}
curpos = NextPos(curpos, 1);//下一位置是当前位置的东邻
curstep++;
//ShowMaze(start);//可以打开这一步注释看看具体每一步代码是怎么走的
}
else//当前位置不能通过
{
if (!StackEmpty(S))
{
Pop(S, e);
while (e.di == 4 && !StackEmpty(S))//如果
{
MarkPrint(e.seat);
Pop(S, e);//留下不能通过的标记，并退回一步
curstep--;
printf("倒退一步到step%d:(%d, %d)\n",curstep-1, e.seat.col, e.seat.row);
}
if (e.di < 4)
{
e.di++;//换下一个方向探索
Push(S, e);
curpos = NextPos(e.seat, e.di);//设定当前位置是该新方向上的相邻块
}
}
}
} while (!StackEmpty(S));//如果栈空表示所有方向都不通
printf("对不起，找不到出口");
return FALSE;
}
/*以下代码沿用上一节栈的基本功能*/
Status InitStack(SqStack& S)//初始化一个空栈
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack& S, SElemType e)//顺序栈的入栈
{
if (S.top - S.base >= S.stacksize)
{
SElemType* New_ptr = (SElemType*)realloc(S.base, ((S.stacksize) + STACKINCREMENT) * sizeof(SElemType));
if (!New_ptr)
{
exit(OVERFLOW);
}
S.base = New_ptr;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S, SElemType& e)//顺序栈的出栈
{
if (S.top == S.base)
{
return ERROR;
}
e = *--S.top;
return OK;
}
Status StackEmpty(SqStack S)//判断栈是否为空
{
if (S.top == S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
