文档介绍：合肥学院
计算机科学与技术系
课程设计报告
2012 ~2013 学年第二学期
课程
数据结构与算法
课程设计名称
迷宫问题(队列)
学生姓名
朱鹏飞
学号
专业班级
计算机科学与技术11级(3)班
指导教师
李红
2013 年 3 月
题目:迷宫问题(队列)
以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
要求:首先实现一个以链表作存储结构的队列,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出,其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向,如:对于下列数据的迷宫,输出的一条通路为:(1,1,1),(1,2,2),(3,2,3),(3,1,2),…。
测试数据:迷宫的测试数据如下:左下角(1,1)为入口,右下角(8,9)为出口。
选做内容:(1)编写递归形式的算法,求得迷宫中所有可能的通路;(2)以方阵形式输出迷宫及其通路
问题分析和任务定义:
从题目可知,迷宫问题主要是考察队列操作和图的遍历算法。
可以分解成以下几个问题:
,若是一个个的将数据输入,那么一个 m*n的二维数组要想快速的输入进去是很麻烦的,那么就应该让计算机自动生成一个这样的迷宫。
,这样就会遇到一个比较大的问题。那就是,在寻找的过程当中,当前队尾节点的其余三个方向上均都是墙,这样就无法再走下去了,必须要返回。由于是用队列存储的,不能直接将队尾元素删除,那就应该让其他元素从队头出队构成另外一条队列。这样,就可以将该结点从队列当中删除了。
,要输出经过结点的方向,对于任意的一个位置有四个方向,所以对于队列中的么每一个结点设置一个方向的标记量,表示走向下一结点的方向,当前加到队尾的元素的方向设置为0,一旦有新元素入队,就对队尾元素的方向进行修改。
:因为当沿着每个方向前进到某一位置时,不再有通路之后,就会把该节点从队列中删除,同时会将该位置上的值修改,从而保证下次改位置上的结点不会再入队。如果不存在通路,必然会一直返回到初始状态(队列为空)。
,所以一旦找到终点,就可以结束需找了。
数据结构的选择和概要设计:
(一)数据结构的选择:(根据实验的要求)
:
typedef struct
{
int x;
int y;
}Weizhi;//迷宫中每一个结点的位置
:
typedef struct
{
Weizhi wz;
int fangxiang;//对方向的选定,对不同的方向设置不同的数值
}Yuansu;//队列当中元素
:
typedef struct Node
{
Yuansu data;
struct Node *next;
}Jiedian;//链队列中的结点数据类型
:
typedef struct
{
Jiedian *front;//队头指针
Jiedian *rear;//队尾指针
}Liandui;
(二)概要设计:
设计思路:
首先构建一个空队列,同时由计算机产生一个迷宫;在判断迷宫的指定出入口是否存在,若不存在,则结束这次查找并输出提示信息;若存在,则进行下一步,搜索通路,有通路直至到达终点,无通路就退回到起点。收索过程中,遇到前面不再有出口的时候,就要使当前队尾结点出队,于是就要对当前队列从队头到倒数第二个结点依次转移,释放出队尾结点。
从完成的功能上看,
实现程序与用户操作的界面设计;
用非递归算法实现以链队列来存储访问过的通路结点,找出通路;
构建迷宫,显示迷宫。
于是,就构建出以下几个模块之间的关系架构:
主模块
队列存储功能迷宫搜索功能

建空对列出队、入队、修改队列构建、输出迷宫从迷宫的起点开始寻找通路
图1. 模块间的关系
详细设计和编码:
从上面的概要设计可以看出,要具体的实现这些功能,为实现方便构造以下几个全局变量:
int m=0,n=0;//用来设置长方阵迷宫的大小
int a[12][12];//用来存放迷宫中每一个结点的信息
Liandui *S;//存放结点信息的队列
同时,必须要构造这些相应的函数:
队列操作
1. //建空队列(仅有一个头结点)
void Jiankong(Liandui *t)
申请头结点(为其分配内存):t->front=(Jiedian *)malloc(