数据结构课程设计--求解迷宫问题
- 格式：doc
- 大小：266.00 KB
- 文档页数：21
数据结构课程设计--求解迷宫问题
0 / 21
课程设计(论文)
题 目 名 称 迷宫求解
课 程 名 称 数据结构课程设计
学 生 姓 名
学 号
系 、专 业 信息工程系、电气信息类（信息类）
指 导 教 师 申寿云
2010年 1 月 3 日 数据结构课程设计--求解迷宫问题
1 / 21 摘 要
设计一个简单迷宫程序，从入口出发找到一条通路到达出口。编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。
首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。用“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。可以用二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n，n）。为处理方便起见，可在迷宫的四周加一障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。
关键词：迷宫；栈；链表；二维数组 数据结构课程设计--求解迷宫问题
2 / 21 目 录
1 问题描述 ............................................................................................................ 1
2 需求分析 ............................................................................................................ 1
3 概要设计 ............................................................................................................ 1
3．1抽象数据类型定义 ............................................................................... 1
3．2模块划分 ................................................................................................ 2
4 详细设计 ............................................................................................................ 2
4．1数据类型的定义 ................................................................................... 2
4．2主要模块的算法描述 ........................................................................... 3
5 测试分析 ............................................................................................................ 6
6 课程设计总结 .................................................................................................... 7
参考文献 ................................................................................................................. 7
附录（源程序清单） ............................................................................................ 9
数据结构课程设计--求解迷宫问题
1 问题描述
迷宫是一个M行N列的0-1矩阵，其中0表示无障碍，1表示有障碍。设入口为(1，1)出口为(M，N)每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元，编制程序给出一条通过迷宫的路径或报告一个“无法通过”的信息。
2 需求分析
（1）首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出，其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。否则报告一个无法通过的信息。
（2）建立InitStack函数，用于构造一个空栈。
（3）建立DestroyStack函数，用于销毁栈。
（4）建立Pop函数，用于删除栈顶元素，返回栈顶元素的值。
（5）建立Push函数，用于插入新的栈顶元素。
（6）建立NextPos函数，用于定位下一个位置。
3 概要设计
3．1抽象数据类型定义
（1）栈的抽象数据类型定义
InitStack( LStack *S )
操作结果：构造一个空栈S。
DestroyStack( LStack *S )
操作结果：栈S被销毁。
Pop( LStack *S，ElemType *e )
操作结果：删除S的栈顶元素。用e返回栈顶元素的值。若栈为空则返回0。
Push( LStack *S，ElemType e ) 数据结构课程设计--求解迷宫问题
2 / 21 操作结果：在栈顶之上插入元素e为新的栈顶元素。若栈S为空栈，则返回0。
（2）迷宫的抽象数据类型定义
NextPos(unsigned *x，unsigned *y，short di)
操作结果：找到下一个位置。
3．2模块划分
本程序包括三个模块：
（1）主程序模块
void main()
{
初始化；
构造迷宫；
迷宫求解；
迷宫输出；
}
（2）栈模块——实现栈的抽象数据类型
（3）迷宫模块——实现迷宫的抽象数据类型
4 详细设计
4．1数据类型的定义
（1）迷宫类型
typedef struct {
unsigned ord, x, y；
short di；
} ElemType；
unsigned x, y, curstep,i=0；
char maze[10][10]；
（2）栈类型
typedef struct Node {
ElemType data； 数据结构课程设计--求解迷宫问题
3 / 21 struct Node* next；
} Node, *LinkList；
typedef struct {
LinkList top；
unsigned length；
} LStack；
LinkList q；
LStack S,T；
ElemType e；
4．2主要模块的算法描述
4.1函数寻找下一个位置流程图
此函数的功能是寻找下一个位置。首先判断di的值，如果di=1，指针x++，退出。如果di=2，指针y++，退出。如果di=3，指针x--，退出。如果di=4，指针y--，退出。如果di为其它值，则直接退出。见图4.1。
Y N
Y N
Y Y N
N di=1
di=2
di=3
di=4
Break； 指针x自增；
Break；
指针y自增；
Break；
指针x自减；
Break；
指针y自减；
Break； 开始
结束 数据结构课程设计--求解迷宫问题
4 / 21
图4.1 函数寻找下一个位置流程图
4.2 函数销毁栈流程图
此函数的功能是销毁栈，首先建立单链表q，判断top指针是否为空，若为空则释放s的空间，否则出栈，直到top指针为空，释放s的空间。见图4.2。
图4.2 函数销毁栈流程图
4.3 函数出栈流程图
此函数的功能是出栈。首先建立单链表q，如果栈s为空则返回0，若栈s不为空，则出栈，修改指针。返回1。见图4.3。
Y N LinkList q；
栈s为空
出栈；
Return 1； Return 0； 开 始 Y N LinkList q；
判断栈的top
释放栈s的空间； 出栈； 开 始
结 束 数据结构课程设计--求解迷宫问题
5 / 21
图4.3 函数出栈流程图
4.4 函数入栈流程图
此函数的功能是入栈。首先在链表中生成结点p，判断p是否为空。若为空则返回0，若非空，则入栈，修改指针，返回0。见图4.4。
图4.4 函数入栈流程图
4.5 主函数流程图
主函数实现了求解迷宫，首先建立栈s和t，输出迷宫图形，然后探索路径，实现迷宫求解，最后输出出迷宫顺序。如果有完整路径则输出完整路径，如果没有完整路径则输出无法通过信息。见图4.5。
Y N 生成结点p；
!p
入栈；
Return 1； Return 0； 开 始
结 束
建立栈S和T；
输出迷宫图形；
迷宫求解；
输出出迷宫顺序； 开 始
