一、栈
1.名词2.栈的实现
栈元素的结构：初始化栈入栈出栈 二、迷宫问题
1.定义迷宫类型2.迷宫分析
1.迷宫的初始化2.迷宫显示3.迷宫寻路 3.运行结果 三.全部程序和参考书籍
一、栈栈又是线性表，但是它是一个受限制的线性表。线性表可以自由得删除或插入节点，但栈只能在栈顶删除（出栈）或插入（入栈）。（见下图）
顺序表的插入与删除：
栈的入栈与出栈：
-
栈
- 栈就像是一个堆放积木的盒子，与盒子等大的积木就像是栈元素，先放进去的积木总是最后才能被取出来，它只能依次从盒子顶端开始取。 栈顶
- 最后入栈的 下一个元素，是栈的最上面的元素 栈底
- 最开始（第一个）入栈的元素，是栈的最下面的元素 栈顶指针
- 指向栈顶元素 栈底指针
- 指向栈底元素 空栈和初始栈
- 栈顶指针指向栈顶指针，表示该栈可能是空栈（初始化的栈是空栈）
typedef int SElemType;
// 顺序栈元素结构
typedef struct {
SElemType* base; // 栈底指针
SElemType* top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} SqStack;
其中
SElemType* base; // 栈底指针 //栈底指针，主要用于接收动态分配空间的首地址。 SElemType* top; // 栈顶指针 //栈顶指针，主要用于入栈和出栈。初始化栈
"->"是指针式访问结构体成员
typedef int Status;
Status InitStack(SqStack* S) {
if(S == NULL) {
return ERROR;
}
//分配栈空间
S->base = (SElemType*) malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(S->base == NULL) {
exit(1);//非正常结束当前进程
}
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return OK;
}
入栈
Status Push(SqStack* S, SElemType e)
{
if (S->base == NULL || S == NULL)
return ERROR;
//若栈满了，则增加空间
if (S->top - S->base >= S->stacksiaze)
{
S->base = (SElemType*)realloc(S->base,(S->stacksiaze + STACKINCREMENT) * sizeof(SElemType));
if (S->base == NULL)
exit(1);//分配失败
S->top = S->base + S->stacksiaze;
S->stacksiaze += STACKINCREMENT;
}
//将e压入栈（先入栈，栈顶指针再自增）
*(S->top++) = e;
return OK;
}
出栈
Status Pop(SqStack* S, SElemType* e)
{
if (S->base == NULL || S == NULL || S->base == S->top)
return ERROR;
//栈顶指针先递减
*e = *(--(S->top));//当前栈顶指针所指的地址都默认是不用地址，栈顶的前一个地址（--(S->top)）才是有用地址
return OK;
}
二、迷宫问题
迷宫一般来讲都是有外墙、迷宫内墙、通路、死胡同、方向（东南西北）、迷宫的方位（x、y坐标）、迷宫大小等等。
1.定义迷宫类型typedef int MazeType[M][N]; // 迷宫类型
//迷宫类型
typedef enum {
Wall, // 外墙
Obstacle, // 迷宫内部的障碍
Way, // 通路
Impasse, // “死胡同”
East, South, West, North // 当前探索方向：东南西北
} MazeNode;
//通道信息
typedef struct {
int x;
int y;
int di;//下一个访问的位置
}SElemType;
//迷宫栈
typedef struct {
SElemType* base; // 栈底指针
SElemType* top; // 栈顶指针
int stacksize; // 当前已分配的存储空间，以元素为单位
} SqStack;
typedef int MazeType[M][N]; // 迷宫类型
常见的类型定义是：
typedef int** MazeType; // 迷宫类型
二者类似但第一种是为二位数组分配了大小的二维数组，第二个是暂未分配大小的二位数组大小。（第一个已经为二位数组初始化元素为0，第二种是未初始化的二维数组）
2.迷宫分析 1.迷宫的初始化在初始化阶段将迷宫的外形确定下来，包括迷宫的外轮廓（外墙）、迷宫内的障碍（内墙）确定并打印在终端上，为了保证迷宫的不确定性和迷宫寻路的自主性，迷宫的内墙由系统的随机数发生器随机的生成内墙的位置。迷宫的墙壁都是由枚举类型来给定的，这样做的好处是代码阅读方便容易理解。迷宫的坐标是由二维数组的下标表示。
如下所示是一个4*4大小的迷宫二维数组，数组中存储的就是迷宫的类型（外墙、内墙、通路、死胡同，方向），假设1是墙壁，0是通路：
| 0 | 1 | 1 | 1 |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
代码如下：
void InitMaze(MazeType maze, PosType* start, PosType* end)
{
int tmp;
srand((unsigned)time(NULL)); //初始化随机数发生器
for (int i=0;i < M;i++)
{
for (int j = 0;j < N;j++)
{
//墙壁生成
if (i == 0 || j == 0 || i == M - 1 || j == N - 1)
maze[i][j] = Wall;//外墙
else
{
tmp = rand() % X;
if (tmp == 0)
maze[i][j] = Obstacle;//内墙
else
maze[i][j] = Way;//通路
}
}
}
//入口
start->x = 1;
start->y = 0;
//出口
end->x = M - 2;
end->y = N - 1;
//开放入口和出口
maze[1][0] = maze[M - 2][N - 1] = Way;
//提高寻路成功率
maze[1][1] = maze[M - 2][N - 2] = Way;
// 显示迷宫的初始状态
PrintMaze(maze);
}
2.迷宫显示
利用switch函数判断迷宫类型二位数组maze的类型，根据其类型打印迷宫。
其关键点：
在每一行的结束位置输出回车符。每次进入打印函数，先清屏再打印。 3.迷宫寻路
- 首先判断当前位置是否可以通过，判断依据是当前坐标位置是不是通路；
- 若当前位置可以通过，则默认先向东访问并在该坐标下留在访问的方向标记（东南西北和死胡同）；
- 打印当前坐标的迷宫类型到终端，并且将当前位置压入栈中；
代码如下：
Status MazePath(MazeType maze, PosType start, PosType end)
{
SqStack S;
PosType curPos;
SElemType e;
InitStack(&S);
curPos = start;//设置当前位置是入口位置
do {
//如果当前位置是可以通过的（该位置是从未曾探索过的通道块）
if (Pass(maze, curPos))
{
//留下足迹（留下向东访问的标记）
FootPrint(maze, curPos);
e = Construct(curPos,East);//构造一个通道块信息并返回
Push(&S, e);//将通道块压入栈
if (Equals(curPos, end))
{
printf("n寻路成功！！nn");
return TRUE;
}
curPos = NextPos(curPos, East);//获取下一个要探索的位置
}
else
{
if (!StackEmpty(S))
{
Pop(&S, &e);//退回上一个位置
while (e.di == North && !StackEmpty(S))
{
MarkPrint(maze, e.seat, Impasse);//留下死胡同印记
Pop(&S, &e);//继续退回
}
if (e.di < North)
{
++e.di;//改变探索方向，按东南西北方向轮询
MarkPrint(maze, e.seat, e.di);//在迷宫下留下访问标记，用来观察迷宫的状态
Push(&S, e);//从新将该位置加入到路径只能
curPos = NextPos(e.seat, e.di);
}
}
}
} while (!StackEmpty(S));
printf("n寻路失败nn");
return FALSE;
}
3.运行结果
8：向北方向
4：向西方向
6：向东方向
2：向南方向
0：死胡同
*：墙壁
下载程序
参考书籍：严蔚敏，吴伟民 《书籍结构（C语言版）》 清华大学出版社（第52页算法3.3） 书号：9787302147510
