文档介绍：题目:迷宫问题(队列)以一个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,一旦有新元素入队,就对队尾元素的方向进行修改。:因为当沿着每个方向前进到某一位置时,不再有通路之后,就会把该节点从队列中删除,同时会将该位置上的值修改,从而保证下次改位置上的结点不会再入队。如果不存在通路,必然会一直返回到初始状态(队列为空)。,所以一旦找到终点,就可以结束需找了。数据结构的选择和概要设计:(一)数据结构的选择:(根据实验的要求):typedefstruct{ intx; inty;}Weizhi;//:typedefstruct{ Weizhiwz; intfangxiang;//对方向的选定,对不同的方向设置不同的数值}Yuansu;//:typedefstructNode{ Yuansudata; structNode*next;}Jiedian;//:typedefstruct{ Jiedian*front;//队头指针 Jiedian*rear;//队尾指针}Liandui;(二)概要设计:设计思路:首先构建一个空队列,同时由计算机产生一个迷宫;在判断迷宫的指定出入口是否存在,若不存在,则结束这次查找并输出提示信息;若存在,则进行下一步,搜索通路,有通路直至到达终点,无通路就退回到起点。收索过程中,遇到前面不再有出口的时候,就要使当前队尾结点出队,于是就要对当前队列从队头到倒数第二个结点依次转移,释放出队尾结点。从完成的功能上看,实现程序与用户操作的界面设计;用非递归算法实现以链队列来存储访问过的通路结点,找出通路;构建迷宫,显示迷宫。于是,就构建出以下几个模块之间的关系架构:主模块队列存储功能迷宫搜索功能建空对列出队、入队、修改队列构建、:从上面的概要设计可以看出,要具体的实现这些功能,为实现方便构造以下几个全局变量:intm=0,n=0;//用来设置长方阵迷宫的大小inta[12][12];//用来存放迷宫中每一个结点的信息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->front==t->rear)成立,即为空,返回一个标志量,否则返回另一个量。由于考虑到队列的调整是在迷宫寻找的过程中进行的,所以不再单独设置成一个函数,而是将其作为迷宫查找函数中的一个模块。迷宫操作:1.//创建迷宫(矩阵)voidCHangJian()由于创建一个手动输入,比较麻烦,容易出错,可以调用s