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