数据结构课程设计--迷宫问题(队列).pdf

数据结构课程设计--迷宫问题(队列)--第1页

h

合肥学院

计算机科学与技术系

课程设计报告

2012～2013学年第二学期

课程数据结构与算法

课程设计名称迷宫问题（队列）

学生姓名朱鹏飞

学号1104011011

专业班级计算机科学与技术11级（3）班

指导教师李红

2013年3月

题目：迷宫问题（队列）

以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，

h

数据结构课程设计--迷宫问题(队列)--第1页

数据结构课程设计--迷宫问题(队列)--第2页

h

对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

h

数据结构课程设计--迷宫问题(队列)--第2页

数据结构课程设计--迷宫问题(队列)--第3页

h

要求：首先实现一个以链表作存储结构的队列，然后编写一个求解迷宫的非递归程序。

求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示

走到下一坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），

（1,2,2）,(3,2,3),(3,1,2),…。

测试数据：迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。

选做内容：（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式

输出迷宫及其通路

一、问题分析和任务定义：

从题目可知，迷宫问题主要是考察队列操作和图的遍历算法。

可以分解成以下几个问题：

1.迷宫的构建，若是一个个的将数据输入，那么一个m*n的二维数组要想快速的输入

进去是很麻烦的，那么就应该让计算机自动生成一个这样的迷宫。

2.题目要求以链表作存储结构的对列来对访问过的通路结点进行存储，这样就会遇到一

个比较大的问题。那就是，在寻找的过程当中，当前队尾节点的其余三个方向上均都是墙，

这样就无法再走下去了，必须要返回。由于是用队列存储的，不能直接将队尾元素删除，那

就应该让其他元素从队头出队构成另外一条队列。这样，就可以将该结点从队列当中删除了。

3.在题目中提出，要输出经过结点的方向，对于任意的一个位置有四个方向，所以对于

队列中的么每一个结点设置一个方向的标记量，表示走向下一结点的方向，当前加到队尾的

元素的方向设置为0，一旦有新元素入队，就对队尾元素的方向进行修改。

4.确定没有通路的思路：因为当沿着每个方向前进到某一位置时，不再有通路之后，就

会把该节点从队列中删除，同时会将该位置上的值修改，从而保证下次改位置上的结点不会

再入队。