扬州大学信息工程学院
《数据结构》
---课程设计报告
题目： 迷宫问题 班级： 计科1301 学号： 131404126 姓名： 张艳 指导教师： 王丽爱
1
目 录
1 课程题目
2 需求分析 2.1 功能与数据需求 2.1.1 题目要求的功能 2.1.2 扩展功能 2.2 界面需求 2.3 开发环境与运行需求 3 概要设计 3.1主要数据结构 3.2程序总体结构 3.3各模块函数说明 4 详细设计
4.1算法分析与设计 4.2主要程序段设计 5 测试
6 附程序源代码
2
一、设计题目
迷宫问题
二、需求分析
2.1 功能与数据需求 迷宫求解
问题描述：以一个m×n的长方形表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
2.1.1 题目要求的功能
基本要求：首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1,1,1）, （1,2,2）, （2,2,2）
（3,2,3）, （3,1,2）,?。
测试数据：迷宫的测试数据如下：左上角（1,1）为入口，右下角（9,8）为出口。
2.1.2 扩展功能
1 2 3 4 5 6 7 8 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0
（1）编写递归形式的算法，求得迷宫中所有可能的通路；
（2）以方阵形式输出迷宫及其通路
2.2 界面需求 请求输入进入程序 请求输入起始位置 请求输入终点位置 输出方阵迷宫 输出路径 输出方阵路径
2.3 开发环境与运行需求 Visual C++6.0
3
三、概要设计
3.1主要数据结构
输入起始位置，终点位置 判断首节点 是否为通路 Y 判断路径能N 定义模块 函数模块 否走通 无解迷宫 Y 主函数 对坐标标记 N 选择路径 处是否 到达迷宫出口有解迷宫 输出迷宫 3.3各模块函数说明 typedef struct{
4
Y 左边是 否存在通路下边是 否存在通路右边是 否存在通路上边是 否存在通路 存储路径，将路径入栈
int pos_x[length];//进栈坐标 int pos_y[length]; int top; int base;
}Stack; //新建结构体
void initStack(Stack *p) //初始化栈
Push(Stack *p,int x,int y,int d) //入栈具体操作 Pop(Stack *p,int read[2],int d) //出栈并读出前一步的坐标 initMaze(int Maze[10][9])//建立迷宫
Ways(Stack *p,int Maze[10][9],int rukou_x,int rukou_y,int chukou_x,int chukou_y,int d) //具体路径的求解 menu();//调用菜单函数 main();//实现迷宫求解的主函数
带头结点的单循环链表抽象数据类型SCLinList，其中包括基本操作的函数有：初始化操作函数、插入一个结点操作函数、删除一个结点操作函数、取一个结点数据操作函数和判表是否非空操作函数。该抽象数据类型文件名为SCLinList.h。
JesephRing()函数是实现问题要求的主要函数。
void SCLLDeleteAfter(SCLNode *p)，其功能是删除带头结点的单循环链表中指针p所指结点的下一个结点。
void JesephRing(SCLNode *head, int m)，其功能是对带头结点的单循环链表head,以m为初始报数上限值实现问题要求。
void main(void)，主函数，功能是给出测试数据值，建立测试数据值的带头结点单循环链表，调用JesephRing()函数实现问题要求。 四、详细设计
迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按左、右、上、下4个方向顺序试探下一个位置；如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。
每前进或后退一步，都要进行判断：若前进到了出口处，则说明找到了一条合适的通路；若退回到了入口处，则说明不存在合法的通路到达出口。
用一个二维指针数组迷宫表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。迷宫的入口点在位置（1，1）处，出口点在位置（m,n）处。设计一个模拟走迷宫的算法，为其寻找一条从入口点到出口点的通路。
二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宫的外墙；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宫的入口和出口；假设当前所在位置是（x,y）。沿某个方向前进一步，它可能到达的位置最多有4。
5