第 3 章栈和队列（顺序栈，算法 3.3）

1. 背景说明：

若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条存放在栈中(从栈底到栈顶)，并返回 TRUE；否则返回 FALSE，注意，该解并非最优解，

最优解需要求得最短路径且可能并非一条。

迷宫示意图：

输入文本：

2. 示例代码

1) status.h

/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H/* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define INFEASIABLE    		   	2			/* 返回值未知 */
#define ERR_MEMORY     		   	3			/* 访问内存错 */
#define ERR_NULL_PTR   			4			/* 空指针错误 */
#define ERR_MEMORY_ALLOCATE		5			/* 内存分配错 */
#define ERR_NULL_STACK			6			/* 栈元素为空 */
#define ERR_PARA				7			/* 函数参数错 */
#define ERR_OPEN_FILE			8			/* 打开文件错 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */#endif // !STATUS_H

2) sqStack.h

/* 栈的顺序存储表示头文件 */#ifndef SQSTACK_H
#define SQSTACK_H#include "status.h"#define STACK_INIT_SIZE 10 		/* 存储空间初始分配量 */
#define STACKINCREMENT 2 		/* 存储空间分配增量 *//* 迷宫位置坐标 */
typedef struct {int x;int y;
} MazePosition;/* 定义栈元素类型 */
typedef struct {int order;					/* 通道块在路径上的序号 */int direction;				/* 下一块路径的方向，取值为 0 ~ 3, 分别表示上下左右 */MazePosition pos;			/* 当前通道块在迷宫中的坐标位置 */
} SElemType;typedef struct SqStack {SElemType* base; 			/* 在栈构造之前和销毁之后，base的值为NULL */SElemType* top; 			/* 栈顶指针 */int stackSize; 				/* 当前已分配的存储空间，以元素为单位 */
} SqStack; 						/* 顺序栈 *//* 构造一个空栈 S */
Status InitStack(SqStack* S);/* 销毁栈 S */
void DestroyStack(SqStack* S);/* 把 S 置为空栈 */
void ClearStack(SqStack* S);/* 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE */
Status StackEmpty(SqStack S);/* 返回 S 的元素个数，即栈的长度 */
int StackLength(SqStack S);/* 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR */
Status GetTop(SqStack S, SElemType* e);/* 插入元素 e 为新的栈顶元素 */
Status Push(SqStack* S, SElemType e);/* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR */
Status Pop(SqStack* S, SElemType* e);/* 从栈底到栈顶依次对栈中每个元素调用函数 visit() */
void StackTraverse(SqStack S, void(*Visit)(SElemType));#endif

3) sqStack.c

/* 栈的顺序存储表示源文件 */#include "sqStack.h"
#include "status.h"
#include <stdlib.h>
#include <stdio.h>/* 构造一个空栈 S */
Status InitStack(SqStack* S)
{(*S).base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!(*S).base) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}(*S).top = (*S).base;(*S).stackSize = STACK_INIT_SIZE;return RET_OK;
}/* 销毁栈 S */
void DestroyStack(SqStack* S)
{free((*S).base);(*S).base = NULL;(*S).top = NULL;(*S).stackSize = 0;
}/* 把 S 置为空栈 */
void ClearStack(SqStack* S)
{(*S).top = (*S).base;
}/* 若栈 S 为空栈，则返回 TRUE，否则返回 FALSE */
Status StackEmpty(SqStack S)
{return (S.top == S.base) ? TRUE : FALSE;
}/* 返回 S 的元素个数，即栈的长度 */
int StackLength(SqStack S)
{return (int)(S.top - S.base);
}/* 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR */
Status GetTop(SqStack S, SElemType* e)
{if (S.top > S.base) {*e = *(S.top - 1);return RET_OK;}printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_NULL_STACK);return ERR_NULL_STACK;
}/* 插入元素 e 为新的栈顶元素 */
Status Push(SqStack* S, SElemType e)
{if (((*S).top - (*S).base) == (*S).stackSize) {(*S).base = (SElemType*)realloc((*S).base, (unsigned long long)(((*S).stackSize) + STACKINCREMENT) * sizeof(SElemType));if (!(*S).base) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}(*S).top = (*S).base + (*S).stackSize;(*S).stackSize += STACKINCREMENT;}*((*S).top)++ = e;return RET_OK;
}/* 若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK；否则返回 ERROR */
Status Pop(SqStack* S, SElemType* e)
{if ((*S).top == (*S).base) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}*e = *(--(*S).top);return RET_OK;
}/* 从栈底到栈顶依次对栈中每个元素调用函数 visit() */
void StackTraverse(SqStack S, void(*Visit)(SElemType))
{while (S.top > S.base) {Visit(*S.base++);}
}

4) algorithm.h

/* 算法定义头文件 */
#ifndef ALGORITHM_H
#define ALGORITHM_H#include "sqStack.h"
#include "status.h"#define MAXLENGTH 25			/* 设迷宫最大行列为 25 *//* 定义墙元素值为 0,可通过路径为 -2, 不能通过路径为 -1 */
typedef int MazeType[MAXLENGTH][MAXLENGTH];/* 算法 3.3, 若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得第一条路径存放在栈中(从栈底到栈顶)，并返回 TRUE；否则返回 FALSE */
Status MazePath(MazePosition start, MazePosition end, MazeType* maze, int* totalStep);/* 如果存在路径，输出求得的迷宫的解 */
void PrintMazePath(int row, int col, MazeType* maze);#endif // !ALGORITHM_H

5) algorithm.c

/* 算法实现源文件 */#include "algorithm.h"
#include <string.h>
#include <stdio.h>/*  定义墙元素值为 0,可通过路径为 -2, 不能通过路径为 -1,通过路径为足迹当迷宫 maze 的 curPos 点的序号为 -2(可通过路径)，return OK; 否则，return FALSE */
static Bollean PassPos(MazePosition curPos, MazeType* maze)
{return ((*maze)[curPos.x][curPos.y] == -2) ? TRUE : FALSE;
}/* 使迷宫 maze 的 curPos 点的序号变为足迹 totalStep */
static void FootPrint(MazePosition curPos, MazeType* maze, int* totalStep)
{(*maze)[curPos.x][curPos.y] = *totalStep;
}/* 根据当前位置及移动方向，返回下一位置 */
static MazePosition NextPos(MazePosition curPos, int direction)
{	/* 上下左右四个方向的行、列增量 */MazePosition direc[4] = { { -1, 0 }, { 1 , 0 }, { 0, -1 }, { 0, 1 } };curPos.x += direc[direction].x;curPos.y += direc[direction].y;return curPos;
}/* 使迷宫 maze 的 curPos 点的序号变为 -1(不能通过的路径) */
static void MarkPrint(MazePosition curPos, MazeType* maze)
{(*maze)[curPos.x][curPos.y] = -1;
}/* 判断两个位置是否相同，相同返回 TRUE, 否则返回 FALSE */
static Bollean PostionSame(MazePosition pos1, MazePosition pos2)
{return ((pos1.x == pos2.x) && (pos1.y == pos2.y)) ? TRUE : FALSE;
}/* 算法 3.3, 若迷宫 maze 中存在从入口 start 到出口 end 的通道，则求得一条存放在栈中(从栈底到栈顶)，并返回 TRUE；否则返回 FALSE */
Status MazePath(MazePosition start, MazePosition end, MazeType* maze, int* totalStep)
{SqStack S = { 0 };InitStack(&S);MazePosition curPos = { 0 };(void)memcpy_s(&curPos, sizeof(MazePosition), &start, sizeof(MazePosition));SElemType sE = { 0 };do {if (PassPos(curPos, maze)) {FootPrint(curPos, maze, totalStep);sE.order = *totalStep;sE.pos.x = curPos.x;sE.pos.y = curPos.y;sE.direction = 0;++(*totalStep);Push(&S, sE);if (PostionSame(curPos, end)) {return TRUE;}curPos = NextPos(curPos, sE.direction);} else {if (!StackEmpty(S)) {Pop(&S, &sE);--(*totalStep);while ((sE.direction == 3) && (!StackEmpty(S))) {MarkPrint(sE.pos, maze);Pop(&S, &sE);--(*totalStep);}if (sE.direction < 3) {++(sE.direction);Push(&S, sE);++(*totalStep);curPos = NextPos(sE.pos, sE.direction);}}}} while (!StackEmpty(S));return FALSE;
}/* 如果存在路径，输出求得的迷宫的解 */
void PrintMazePath(int row, int col, MazeType* maze)
{for (int i = 0; i < row; ++i) {for (int j = 0; j < col; ++j) {printf("%3d", (*maze)[i][j]);}printf("\n");}
}

6) main.c

/* 入口程序源文件 */#include "status.h"
#include "algorithm.h"
#include <stdio.h>int main(void)
{printf("Please input the row and col of the maze: ");int row = 0, col = 0;scanf_s("%d%d", &row, &col);MazeType maze = { 0 };for (int i = 0; i < col; ++i) {maze[0][i] = 0;maze[row - 1][i] = 0;}for (int i = 1; i < row - 1; ++i) {maze[i][0] = 0;maze[i][row - 1] = 0;}for (int i = 1; i < row - 1; ++i) {for (int j = 1; j < col - 1; ++j) {maze[i][j] = -2;}}printf("Please input the num of the wall: ");int wallNum = 0;scanf_s("%d", &wallNum);printf("Please input the position of the wall(x, y): \n");int x = 0, y = 0;for (int i = 0; i < wallNum; ++i) {scanf_s("%d%d", &x, &y);maze[x][y] = 0;}printf("The structure of the maze is:\n");PrintMazePath(row, col, &maze);MazePosition start = { 0 }, end = { 0 };printf("Please input the position of the start point(x, y):");scanf_s("%d%d", &start.x, &start.y);printf("Please input the position of the end point(x, y):");scanf_s("%d%d", &end.x, &end.y);int totalStep = 1;if (MazePath(start, end, &maze, &totalStep)) {printf("Use %d steps, one of the path from start to end of the maze is:\n", --totalStep);PrintMazePath(row, col, &maze);} else {printf("There is no way to the end.\n");}return 0;
}

3. 输出示例：