二． 概要设计
为了实现上述操作，以栈为存储结构。
本程序包含三个模块：
（1） 主程序模块:实现人机交互。
（2） 迷宫生产模块：随机产生一个12×12的迷宫。
（3） 路径查找模块：实现通路的查找。
（4） 求解迷宫中一条通路的伪代码：
《用栈解决迷宫问题的实验报告》
一、需求分析
在本次实验中，我们需要设计一个程序来解决迷宫问题。迷宫采用结构体Maze进行表示，其中包括以下关键属性：
1. pos：用于标记该位置是否存在障碍，通常用0表示通路，非0表示障碍。
2. freq：记录该位置被访问的次数，用于优化路径查找。
3. move：是一个长度为4的数组，表示当前位置的四个可能方向（北、东、南、西），用于记录下一步的移动方向。
迷宫的大小设定为12×12，用字符'H'表示障碍，空字符表示通路。起点设为左上角，终点设为右下角。程序的目标是找出一条从起点到终点的可行路径。
二、概要设计
为实现这个功能，程序采用栈作为主要的数据结构，分为三个主要模块：
1. 主程序模块：负责与用户交互，包括迷宫的显示和路径的查找。
2. 迷宫生产模块：生成一个随机的12×12迷宫。
3. 路径查找模块：实现从起点到终点的路径搜索。
路径查找的伪代码大致如下：
1. 当当前位置可通行时，将其压入栈，并检查是否为出口。若是出口，则结束搜索；否则，更新当前位置为东邻方块。
2. 如果当前位置不可通行，且栈非空，尝试沿顺时针方向寻找未探索的相邻块。如果找不到，删除栈顶元素，重复此过程直到找到可通行的相邻块或栈为空。
三、详细设计
栈的实现采用链表结构，定义如下：
```c
typedef struct Node {
int x;
int y;
struct Node *next;
} Node;
typedef struct {
Node *base;
Node *top;
int length;
} Stack;
```
栈的常用操作包括初始化、打印、销毁、出栈和入栈：
1. `initstack()` 初始化栈。
2. `printstack(Stack *s)` 打印栈中元素。
3. `destroy(Stack *s)` 销毁整个栈。
4. `deltop(Stack *s)` 出栈。
5. `pushelem(Stack *s, int x, int y)` 入栈，将坐标(x, y)压入栈。
主程序模块：
```c
int main() {
// ...
Maze a[N][N];
makemaze(a);
// ...
findpath(a);
// ...
}
```
迷宫生成模块：
```c
void makemaze(Maze (*p)[N]) {
// ...
srand((int)time(NULL));
for (int conter = 0; conter < 20; ++conter) {
int i = rand() % (N - 2);
int j = rand() % (N - 2);
(*(p + i) + j)->pos = 'X';
if (i == 1 && j == 1 || i == N - 1 && j == N - 1)
(*(p + i) + j)->pos = 0;
}
printmaze(p);
}
```
路径查找模块：
```c
Maze *testnewpos(Maze (*p)[N], Stack *s, int *i, int *j) {
// ...
for (; q == NULL && select < 4; ++select) {
switch (select) {
case 0:
if ((*p + s->top->x) + s->top->y)->move[0] != 1) {
((*p + s->top->x) + s->top->y)->move[0] = 1;
q = *p + s->top->x + 1;
*i = s->top->x + 0;
// ...
}
// ...
}
}
// ...
}
```
四、算法解析
在路径查找过程中，采用了深度优先搜索（DFS）策略，通过栈进行递归回溯。当当前位置可通行时，将其压入栈并检查是否到达终点。若未到达，尝试向四个方向之一移动。如果当前位置不可通行，检查栈中是否有未探索过的相邻位置，若有则继续搜索，否则回溯至上一步。
总结，本实验报告详细阐述了如何使用栈来解决迷宫问题，涵盖了从需求分析到详细设计的全过程，以及关键数据结构栈的实现。通过迷宫生成、路径查找等模块，展示了如何利用栈进行深度优先搜索来解决实际问题。
