迷宫问题(队列)
- 格式：doc
- 大小：1.34 MB
- 文档页数：20
软件综合课程设计迷宫问题（队列）数制转换问题二〇一四年六月二、迷宫问题（队列）1、问题陈述要求：首先实现一个链表作存储结构的队列，然后编写一个求解迷宫的非递归程序。
求得的通路以三元组（i,j,d）的形式输出，其中，（i,j）指示迷宫中的一个坐标，d表示走到下一个坐标的方向，如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（3，2，3），（3，1，2），…测试数据：迷宫的测试数据如下：迷宫的测试数据如下：左下角（1，1）为入口，右下角（8，9）为出口。
2、需求分析用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立自己的迷宫；或者使用程序中提供的迷宫。
其中用队列的基本操作完成迷宫问题的求解。
从题目可知：迷宫问题主要考察队列操作和图的遍历算法。
可以分解成为以下几个问题：(1)迷宫的构建，若是一个个的将数据输入，那么一个m*n的二维数组要想快速的输入进去是很麻烦的，那么就应该让计算机自动生成一个这样的迷宫。
(2)题目要求以链表作存储结构的对列来对访问过的通路节点进行存储，这样就会遇到一个比较大的问题。
那就是，在寻找的过程当中，当前队尾节点的其余三个方面上均都是墙，这样就无法再走下去了，必须要返回。
由于是用队列存储的，不能直接将队尾元素删除，那就应该让其他元素从队头出队构成另外一条队列。
这样，就可以讲该结点从队列当中删除了。
(3)在题目中提出，要输出经过结点的方向，对于任意的一个位置有四个方向，所以对于队列中的每一个结点设置一个方向的标志量，表示走向下一个结点的方向，当前加到队尾的元素的方向设置为0，一旦有新元素入队，就对队尾元素的方向进行修改。
(4) 确定没有通路的思路：因为当沿着每个方向前进都某一位置的时候，不再有通路之后，就会把该节点从队列中删除，同时会将该位置上的值修改，从而保证下次改位置的节点不会再入队。
如果不存在通路，必然会一直返回到初始状态（队列为空）(5) 因只需要找一条通路就可以了，所以一旦找到终点，就可以结束查找了。
3、概要设计（一）、数据结构的选择（根据实验的要求）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)构建迷宫，显示迷宫。
于是，就构建了以下几个模块之间的关系架构：主模块队列存储功能迷宫搜索功能建空队列出队、入队、修改队列构建、输出迷宫从迷宫的起点寻找通路4、详细设计和编码：从上面的概要设计可以看出，要具体的实现这些功能，为实现方便构造以下几个全局变量：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;这里，为了让头结点能够方便后面的操作，给其数据域赋一些特殊值。
//判断队列是否为空int Pankong(Liandui *t)条件是当： if(t->front==t->rear)成立，即为空，返回一个标志量，否则返回另一个量。
由于考虑到队列的调整是在迷宫寻找的过程中进行的，所以不再单独设置成一个函数，而是将其作为迷宫查找函数中的一个模块。
（2）迷宫操作//创建迷宫（矩阵）void CHangJian()由于创建一个手动输入，比较麻烦，容易出错，可以调用srand(time(NULL));这个函数获得系统时间，在用rand()%2来得到0,1的随机数在两层for循环中构造出这样一个迷宫矩阵。
为了测试各种情况，可以手动输入构建迷宫。
即用:scanf("%d",&a[i][j]);四周栅栏全设为1.//输出迷宫（矩阵）void Shuchu（）这个函数只需要用两层for循环直接将其输出。
//寻找通路的过程int Xunzhao(Liandui *t)说明：这个函数是这个程序的核心部分，是重要功能的实现部分。
本函数中应用到自身的内部变量有：Jiedian *p; //作为中间过渡的结点指针Liandui *s; //作为调整的过渡队列指针Jiedian *x; //作为搜索时的过渡结点指针int i=1,j=1; //位置首先，要判断该迷宫的出入口是否均是通路，是通路即进行后续操作；将第一个结点（入口结点）入队，同时为了防止，在广度搜索遍历的过程中往回走，将访问过的通路结点设置为2,即：a[p->data.wz.x][p->data.wz.y]=2;用while循环执行后续操作，条件是在：队列不是空的（要求队列不是空的是为了后续判断，因为一开始必然会有一个结点，而后来是空的情况，就只有是没有通路，一直返回了最初状态）或者是已经到达了终点（到达终点就可以确定是有通络了）。
满足循环条件的时候，就对该结点的四个方向上的结点的数据进行判断，设定向右、向下、向左、向上的方向分别都是1,2,3,4.四个方向判断的代码特点（以向右为例）：if(a[t->rear->data.wz.x][t->rear->data.wz.y+1]==0){//向右行驶的方向定为1p=(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;//访问的相邻结点是通路结点}当四个方向判断都没有通路的时候，就要将当前的队尾结点从队列中删除。
删除操作如下（链队列调整）：此时要分为两种情况，第一种是队尾节点也是队头结点；if(x->next==NULL)//仅一个结点{ t->front=t->rear; free(x);break;}其他情况就要进行队列的调整：生成新的空队列，同时把要调整的队列的空队头给删除，移动过渡指针调整原队列的队头指针：s=(Liandui *)malloc(sizeof(Liandui));s->front=(Jiedian*)malloc(sizeof(Jiedian));s->front->next=N ULL;s->rear=s->front;x=t->front->next;free(t->front);t->front=x;对于队列要是找到最后一个结点反而无法删除，所以找到倒数第二个结点就结束搜索。
即：while（x->next->next!=NULL)在没达到结束条件，循环体执行的操作时：s->rear->next=x; s->rear=x;//把收索到的结点放入新队列的队尾x=x->next;//继续移动搜索指针循环结束，也即是找到了倒数第二个结点，那就可以把其尾结点删除了，free(x->next);由于是队列，所以要把当前队尾结点的指针域赋空：x->next=NULL;不能忘了，还要把x这个结点入队：s->rear->next=x; s->rear=x;调整结束之后，将队列恢复成t的新队列：t->front=s->front;t->rear=s->rear;其后还要在外层循环中对队列尾元素判断是否是终点，要是终点就结束，返回“0”表示有通路。
最后，就是对队列进行判断，如果是空的，就返回“-2”。
为了消除程序无返回值的警告，可以再函数体尾部加上“return 0；”事实上是不会执行。
4、//若存在通路，即输出该通路void Putout(Liandui *t)该函数就是将队列输出，在搜索指针未指向空的时候，一直执行循环体。
但是这样会有一个错误，经调试之后，发现当t指向尾节点，就不需要再循环了，可以用break直接跳出循环。
（3）主函数模块说明：主函数模块的功能仅仅是完成以上函数的调用和参数的传递，以及对一些返回值进行判断处理。
思路是：创建迷宫，建空队列——>判断出入口是否存在——>存在出入口，就输入行走路径，同时把修改之后的迷宫输出。
（4）其他模块（提示列表）为了程序的易于使用，用一个Tishi（）函数把一些要求说明的信息，都用put（）函数输出到显示界面上。
5、程序代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<time.h>/*思想：将能够走出迷宫所经过的某一条路径用一个链队列存储*//*从顶点开始依次队二维数组中的每一个元素的邻接点进行访问，若访问过的节点通过路则入队；否则，不入队。
