潍坊网站建设中公,1688网站特色,诸暨建设局网站,做电影网站许可证1. 背景说明#xff1a;
若迷宫 maze 中存在从入口 start 到出口 end 的通道#xff0c;则求得一条存放在栈中(从栈底到栈顶)#xff0c;并返回 TRUE#xff1b;否则返回 FALSE#xff0c;注意#xff0c;该解并非最优解#xff0c;
最优解需要求得最短路径且可能并非…1. 背景说明
若迷宫 maze 中存在从入口 start 到出口 end 的通道则求得一条存放在栈中(从栈底到栈顶)并返回 TRUE否则返回 FALSE注意该解并非最优解
最优解需要求得最短路径且可能并非一条。
迷宫示意图 输入文本 10 10181 3
1 7
2 3
2 7
3 5
3 6
4 2
4 3
4 4
5 4
6 2
6 6
7 2
7 3
7 4
7 6
7 7
8 11 18 8
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.hint 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. 输出示例
