题目：迷宫问题（队列）
以一个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）以方阵形式输出迷宫及其通路
一、问题分析和任务定义：
从题目可知，迷宫问题主要是考察队列操作和图的遍历算法。 可以分解成以下几个问题：
1.迷宫的构建，若是一个个的将数据输入，那么一个 m*n的二维数组要想快速的输入进去是很麻烦的，那么就应该让计算机自动生成一个这样的迷宫。
2.题目要求以链表作存储结构的对列来对访问过的通路结点进行存储，这样就会遇到一个比较大的问题。那就是，在寻找的过程当中，当前队尾节点的其余三个方向上均都是墙，这样就无法再走下去了，必须要返回。由于是用队列存储的，不能直接将队尾元素删除，那就应该让其他元素从队头出队构成另外一条队列。这样，就可以将该结点从队列当中删除了。
3.在题目中提出，要输出经过结点的方向，对于任意的一个位置有四个方向，所以对于队列中的么每一个结点设置一个方向的标记量，表示走向下一结点的方向，当前加到队尾的元素的方向设置为0，一旦有新元素入队，就对队尾元素的方向进行修改。
4.确定没有通路的思路：因为当沿着每个方向前进到某一位置时，不再有通路之后，就会把该节点从队列中删除，同时会将该位置上的值修改，从而保证下次改位置上的结点不会再入队。如果不存在通路，必然会一直返回到初始状态（队列为空）。
5.因只需要找到一条通路就可以了，所以一旦找到终点，就可以结束需找了。 二、数据结构的选择和概要设计： （一）数据结构的选择：（根据实验的要求）
1.点的坐标类型： typedef struct {
int x; int y;
}Weizhi;//迷宫中每一个结点的位置 2.带方向的点： typedef struct {
Weizhi wz;
int fangxiang;//对方向的选定，对不同的方向设置不同的数值
}Yuansu;//队列当中元素 3.队列当中的节点的类型：
typedef struct Node {
Yuansu data;
struct Node *next;
}Jiedian;//链队列中的结点数据类型 4.链队列：
typedef struct {
Jiedian *front;//队头指针 Jiedian *rear;//队尾指针 }Liandui;
（二）概要设计：
设计思路：
首先构建一个空队列，同时由计算机产生一个迷宫；在判断迷宫的指定出入口是否存在，若不存在，则结束这次查找并输出提示信息；若存在，则进行下一步，搜索通路，有通路直至到达终点，无通路就退回到起点。收索过程中，遇到前面不再有出口的时候，就要使当前队尾结点出队，于是就要对当前队列从队头到倒数第二个结点依次转移，释放出队尾结点。
从完成的功能上看，
1. 实现程序与用户操作的界面设计；
2. 用非递归算法实现以链队列来存储访问过的通路结点，找出通路； 3. 构建迷宫，显示迷宫。
于是，就构建出以下几个模块之间的关系架构：
主模块
队列存储功能 迷宫搜索功能
建空对列 出队、入队、修改队列 构建、输出迷宫 从迷宫的起点开始寻找通路 图1. 模块间的关系 三、详细设计和编码：
从上面的概要设计可以看出，要具体的实现这些功能，为实现方便构造以下几个全局变量：
int m=0,n=0;//用来设置长方阵迷宫的大小
int a[12][12];//用来存放迷宫中每一个结点的信息 Liandui *S;//存放结点信息的队列 同时，必须要构造这些相应的函数： （一） 队列操作
1. //建空队列(仅有一个头结点) void Jiankong(Liandui *t)
申请头结点（为其分配内存）：t->front=(Jiedian *)malloc(sizeof(Jiedian)); 建空：t->rear=t->front; t->front->next=NULL;
这里，为了让头结点能够方便后面的操作，给其数据域赋一些特殊值。 2．//判断队列是否为空 int Pankong(Liandui *t)
条件是当：if(t->front==t->rear)成立，即为空，返回一个标志量，否则返回另一个量。
由于考虑到队列的调整是在迷宫寻找的过程中进行的，所以不再单独设置成一个函数，而是将其作为迷宫查找函数中的一个模块。 （二） 迷宫操作：
1. //创建迷宫(矩阵) void CHangJian( )
由于创建一个手动输入，比较麻烦，容易出错，可以调用srand(time(NULL));这个函数获得系统时间，在用rand( )%2来得到0,1的随机数在两层for循环中构造出这样一个迷宫矩阵。为了测试各种情况，可以手动输入构建迷宫。即用：scanf(\四周栅栏全设为1。
2. //输出迷宫(矩阵) void Shuchu()
这个函数只需要用两层for循环直接将其输出。 3．//寻找通路的过程 int Xunzhao(Liandui *t)
说明：这个函数是这个程序的核心部分，是重要功能的实现部分。 本函数中应用到自身的内部变量有： Jiedian *p;//作为中间过渡的结点指针 Liandui *s;//作为调整的过渡队列指针 Jiedian *x;//作为搜索是的过渡结点指针 int i=1,j=1;//位置
（1）首先，要判断该迷宫的出入口是否均是通路，是通路即进行后续操作：
（2）将第一个结点（入口结点）入队，同时为了防止，在广度搜索遍历的过程中往回走，将访问过的通路结点设置为2，即： a[p->data.wz.x][p->data.wz.y]=2;
（3）用while循环执行后续操作，条件是在：队列不是空的（要求对列不是空的是为了后续判断，因为一开始必然会有一个结点，而后来是空的情况，就只有是没有通路，一直返回到了最初状态）或者是已经到达了终点（达到终点就可以确定是有通路了）。
满足循环条件的时候，就对该结点的四个方向上的结点的数据进行判断，设定向右、向下、向左、向上的方向分别是1,2,3,4.
四个方向判断的代码特点（以向右为例）：
if(a[t->rear->data.wz.x][t->rear->data.wz.y+1]==0) {//向右行驶的方向定为1
p=(Jiedian *)malloc(sizeof(Jiedian));
p->data.wz.x=t->rear->data.wz.x;p->data.wz.y=t->rear->data.wz.y+1; p->data.fangxiang=0;//对新结点分量赋值 p->next=NULL;t->rear->data.fangxiang=1; t->rear->next=p;t->rear=p;//新结点入队
a[t->rear->data.wz.x][t->rear->data.wz.y]=2;//访问的相邻结点是通路结点
数据结构课程设计报告-迷宫问题(队列)
