数据结构课程设计--迷宫问题（队列）

《数据结构课程设计--迷宫问题（队列）》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥学院计算机科学与技术系课程设计报告2012～2013学年第二学期课程数据结构与算法课程设计名称迷宫问题（队列）学生姓名朱鹏飞学号专业班级计算机科学与技术11级（3）班指导教师李红2013年3月题目：迷宫问题（队列）以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。要求：首先实现一个以链表作存储结构的队列，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向，如：对于下

2、列数据的迷宫，输出的一条通路为：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。测试数据：迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。选做内容：（1）编写递归形式的算法，求得迷宫中所有可能的通路；（2）以方阵形式输出迷宫及其通路一、问题分析和任务定义：从题目可知，迷宫问题主要是考察队列操作和图的遍历算法。可以分解成以下几个问题：1.迷宫的构建，若是一个个的将数据输入，那么一个m*n的二维数组要想快速的输入进去是很麻烦的，那么就应该让计算机自动生成一个这样的迷宫。2.题目要求以链表作存储结构的对列来对访问过的通

3、路结点进行存储，这样就会遇到一个比较大的问题。那就是，在寻找的过程当中，当前队尾节点的其余三个方向上均都是墙，这样就无法再走下去了，必须要返回。由于是用队列存储的，不能直接将队尾元素删除，那就应该让其他元素从队头出队构成另外一条队列。这样，就可以将该结点从队列当中删除了。3.在题目中提出，要输出经过结点的方向，对于任意的一个位置有四个方向，所以对于队列中的么每一个结点设置一个方向的标记量，表示走向下一结点的方向，当前加到队尾的元素的方向设置为0，一旦有新元素入队，就对队尾元素的方向进行修改。4.确定没有通路的思路：因为当沿着每个方向前进到某一位置时，不

4、再有通路之后，就会把该节点从队列中删除，同时会将该位置上的值修改，从而保证下次改位置上的结点不会再入队。如果不存在通路，必然会一直返回到初始状态（队列为空）。5.因只需要找到一条通路就可以了，所以一旦找到终点，就可以结束需找了。二、数据结构的选择和概要设计：（一）数据结构的选择：（根据实验的要求）1.点的坐标类型：typedefstruct{intx;inty;}Weizhi;//迷宫中每一个结点的位置2.带方向的点：typedefstruct{Weizhiwz;intfangxiang;//对方向的选定，对不同的方向设置不同的数值}Yuansu;//

5、队列当中元素3.队列当中的节点的类型：typedefstructNode{Yuansudata;structNode*next;}Jiedian;//链队列中的结点数据类型4.链队列：typedefstruct{Jiedian*front;//队头指针Jiedian*rear;//队尾指针}Liandui;（二）概要设计：设计思路：首先构建一个空队列，同时由计算机产生一个迷宫；在判断迷宫的指定出入口是否存在，若不存在，则结束这次查找并输出提示信息；若存在，则进行下一步，搜索通路，有通路直至到达终点，无通路就退回到起点。收索过程中，遇到前面不再有出口的时

6、候，就要使当前队尾结点出队，于是就要对当前队列从队头到倒数第二个结点依次转移，释放出队尾结点。从完成的功能上看，1.实现程序与用户操作的界面设计；2.用非递归算法实现以链队列来存储访问过的通路结点，找出通路；3.构建迷宫，显示迷宫。于是，就构建出以下几个模块之间的关系架构：主模块队列存储功能迷宫搜索功能建空对列出队、入队、修改队列构建、输出迷宫从迷宫的起点开始寻找通路图1.模块间的关系一、详细设计和编码：从上面的概要设计可以看出，要具体的实现这些功能，为实现方便构造以下几个全局变量：intm=0,n=0;//用来设置长方阵迷宫的大小inta[12][1

7、2];//用来存放迷宫中每一个结点的信息Liandui*S;//存放结点信息的队列同时，必须要构造这些相应的函数：（一）队列操作1.//建空队列(仅有一个头结点)voidJiankong(Liandui*t)申请头结点（为其分配内存）：t->front=(Jiedian*)malloc(sizeof(Jiedian));建空：t->rear=t->front;t->front->next=NULL;这里，为了让头结点能够方便后面的操作，给其数据域赋一些特殊值。2．//判断队列是否为空intPankong(Liandui*t)条件是当：if(t->fro

8、nt==t->rear)成立，即为空，返回一个标志量，否则返回另一个量。由于考虑到队列的调整是