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

合肥学院计算机科学与技术系课程设计报告2012 2013 学年第 二 学期课程数据结构与算法课程设计名称迷宫问题（队列）学生姓名朱鹏飞学号1104011011专业班级计算机科学与技术11级（3）班指导教师李红2013 年 3 月题目：迷宫问题（队列）以一个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 NodeYuansu data;struct Node *next;Jiedian;/链队列中的结点数据类型4.链队列：typedef struct Jiedian *front;/队头指针Jiedian *rear;/队尾指针Liandui;（二）概要设计：设计思路：首先构建一个空队列，同时由计算机产生一个迷宫；在判断迷宫的指定出入口是否存在，若不存在，则结束这次查找并输出提示信息；若存在，则进行下一步，搜索通路，有通路直至到达终点，无通路就退回到起点。收索过程中，遇到前面不再有出口的时候，就要使当前队尾结点出队，于是就要对当前队列从队头到倒数第二个结点依次转移，释放出队尾结点。从完成的功能上看，1. 实现程序与用户操作的界面设计；2. 用非递归算法实现以链队列来存储访问过的通路结点，找出通路；3. 构建迷宫，显示迷宫。于是，就构建出以下几个模块之间的关系架构： 主模块 队列存储功能 迷宫搜索功能建空对列 出队、入队、修改队列 构建、输出迷宫 从迷宫的起点开始寻找通路 图1. 模块间的关系三、 详细设计和编码：从上面的概要设计可以看出，要具体的实现这些功能，为实现方便构造以下几个全局变量：int m=0,n=0;/用来设置长方阵迷宫的大小int a1212;/用来存放迷宫中每一个结点的信息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(%d,&aij);四周栅栏全设为1。2. /输出迷宫(矩阵)void Shuchu()这个函数只需要用两层for循环直接将其输出。3/寻找通路的过程int Xunzhao(Liandui *t)说明：这个函数是这个程序的核心部分，是重要功能的实现部分。本函数中应用到自身的内部变量有：Jiedian *p;/作为中间过渡的结点指针Liandui *s;/作为调整的过渡队列指针Jiedian *x;/作为搜索是的过渡结点指针int i=1,j=1;/位置（1）首先，要判断该迷宫的出入口是否均是通路，是通路即进行后续操作：（2）将第一个结点（入口结点）入队，同时为了防止，在广度搜索遍历的过程中往回走，将访问过的通路结点设置为2，即：ap-data.wz.xp-data.wz.y=2;（3）用while循环执行后续操作，条件是在：队列不是空的（要求对列不是空的是为了后续判断，因为一开始必然会有一个结点，而后来是空的情况，就只有是没有通路，一直返回到了最初状态）或者是已经到达了终点（达到终点就可以确定是有通路了）。满足循环条件的时候，就对该结点的四个方向上的结点的数据进行判断，设定向右、向下、向左、向上的方向分别是1,2,3,4.四个方向判断的代码特点（以向右为例）：if(at-rear-data.wz.xt-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;/新结点入队at-rear-data.wz.xt-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=NULL;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直接跳出循环。（三） 主函数模块：说明：主函数模块的功能仅仅是完成以上函数的调用和参数的传递，以及对一些返回值进行判断处理。思路是：创建迷宫，建空对列-判断出入口是否存在-存在出入口，就输出行走路径，同时把修改之后的迷宫输出。（四） 其他模块（提示列表）为了程序的易于使用，用一个Tishi( )函数把一些要求说明的信息，都用put( )函数输出到显示界面上。四、 上机调试过程：1. 图2.调试窗口1显示的警告是：程序的第193行的寻找函数没有返回值，在后面加上return 0；之后该警告就没了。当调试无误之后，运行时有异常终止情况出现:1.程序异常终止：测试时弹出如下窗口： 图3.调试窗口2按“确定”之后，提示贯标指示到：测试数据是： 图4.测试图1经过检查，不是所指示的位置出错，而是逻辑错误，该队列中仅一个元素出队，不需要按一般情况来出队的，于是添加了一个处理操作，错误消失了。2.程序异常：当输入以下数据时， 图5.测试图2运行到的位置是： 图6.测试图3错误指示的位置是：分析程序的前后，发现while结束条件不正确。调试之后能够运行。五、测试结果及分析：测试数据一： 图7.运行图1分析：这组数据测试的迷宫是有通路的，按照遍历的顺序，依次范文通路结点的相邻节点，于是得到了通路的路径，同时也产生了访问过程中留下来的痕迹。最终程序正常的执行结束，即终止。测试数据二： 图8.运行图2分析：这组测试数据：是程序的出入口虽然存在但是没有通路，所以访问到连接起点的所有通路结点，最后还是返回到初始位置，程序结束。六、用户使用说明：1.在输入迷宫矩阵的长、宽的时候，数值要再0到10之间，两个数字之间用空格分开。2.在输入举证的时候，只能输入0和1这两种数字，输入的个数之和要是m*n的值。3.运行的结果是在当前界面上直接显示。4.该程序每次只可以测试一组数据。七、参考文献：1 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2007年5月。八、附录：#include#include#include#include/*思想：将能够走出迷宫所经过的某一条路径用一个链队列存储*/*从顶点开始依次对二维数组中的每一个元素的所有的邻接点进行访问，若访问过的节点是通路则入队；否则，不入队。*/全局变量int m=0,n=0;/用来设置长方阵迷宫的大小int a1212;/用来存放迷宫中每一个结点的信息/*-结构体的定义-*/typedef struct int x;int y;Weizhi;/迷宫中每一个结点的位置typedef structWeizhi wz;int fangxiang;/对方向的选定，按a,b,c,d值的大小依次选定Yuansu;/队列当中元素typedef struct NodeYuansu data;struct Node *next;Jiedian;/链队列中的结点数据类型typedef struct Jiedian *front;Jiedian *rear;Liandui;/链队列Liandui *S;/存放结点信息的队列/*-子函数-*/提示菜单：void Tishi()puts(-迷宫中结点的规定如下-n);puts(-0：表示未访问过的通路结点-n);puts(-1：表示墙结点-n);puts(-2：表示访问过的通路节点-n);puts(-3：表示边界的栅栏-n);/创建迷宫(矩阵)void CHangJian()int i,j;printf(请输入长方形矩阵迷宫的长度与宽度(均不超过10):n);scanf(%d%d,&m,&n);printf(输入这些数值(0/1):n);srand(time(NULL);/计算机自动读取自身的时间(真正实现产生随机数)/迷宫四周用栅栏围住,用2表示for(i=0;i=n+1;i+)/i代表列a0i=3;am+1i=3;for(j=1;j=m+1;j+)/j代表行aj0=3;ajn+1=3;for(i=1;i=m;i+)for(j=1;j=n;j+)scanf(%d,&aij);/输出迷宫(矩阵)void Shuchu()int i,j;for(i=0;i=m+1;i+)for(j=0;jfront=(Jiedian *)malloc(sizeof(Jiedian);/为队头指针申请内存 t-rear=t-front;t-front-data.fangxiang=-1;t-front-data.wz.x=-1;t-front-data.wz.y=-1;t-front-next=NULL;/队列置空/判断队列是否为空int Pankong(Liandui *t)if(t-front=t-rear)return -1;return 0;/表示该链队列不是空的/寻找通路的过程int Xunzhao(Liandui *t)/起点是a11,终点是amnJiedian *p; /作为入队时的过渡指针 Liandui *s;/作为队列调整时的链队指针Jiedian *x;/作为搜索时的查找指针int i=1,j=1;/坐标位置变量if(a11=0&amn=0)Jiankong(t);/建立一个空队列/将入口结点入队p=(Jiedian *)malloc(sizeof(Jiedian);p-data.wz.x=1,p-data.wz.y=1;p-data.fangxiang=1;/初始方向假定向右ap-data.wz.xp-data.wz.y=2;/标记为访问过的通路结点p-next=NULL;t-rear-next=p;t-rear=p;/向空队列中插入一个结点while(Pankong(t)=0|(t-rear-data.wz.x!=m&t-rear-data.wz.y!=n)/链队列非空并且没有搜索到终点 if(at-rear-data.wz.xt-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;at-rear-data.wz.xt-rear-data.wz.y=2;/访问的相邻结点是通路结点else if(at-rear-data.wz.x+1t-rear-data.wz.y=0)/向下行驶的方向定为2p=(Jiedian *)malloc(sizeof(Jiedian);p-data.wz.x=t-rear-data.wz.x+1;p-data.wz.y=t-rear-data.wz.y;p-data.fangxiang=0;p-next=NULL;t-rear-data.fangxiang=2;t-rear-next=p;t-rear=p;at-rear-data.wz.xt-rear-data.wz.y=2;/访问的相邻结点是通路结点else if(at-rear-data.wz.xt-rear-data.wz.y-1=0)/向下行驶的方向定为3p=(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=3;t-rear-next=p;t-rear=p;at-rear-data.wz.xt-rear-data.wz.y=2;/访问的相邻结点是通路结点else if(at-rear-data.wz.x-1t-rear-data.wz.y=0)/向上行驶的方向定为4p=(Jiedian *)malloc(sizeof(Jiedian);p-data.wz.x=t-rear-data.wz.x-1;p-data.wz.y=t-rear-data.wz.y;p-data.fangxiang=0;p-next=NULL;t-rear-data.fangxiang=4;t-rear-next=p;t-rear=p;at-rear-data.wz.xt-rear-data.wz.y=2;/访问的相邻结点是通路结点else/将该节点从队尾删除(调整链队列)s=(Liandui *)malloc(sizeof(Liandui);s-front=(Jiedian *)malloc(sizeof(Jiedian);s-front-next=NULL;s-rear=s-front;x=t-front-next;free(t-front);t-front=x;if(x-next=NULL)/仅一个结点t-front=t-rear; free(x);break;while(x-next-next!=NULL)/从循环中找到倒数第二个结点/不只一个结点s-rear-next=x;s-rear=x;/把收索到的结点放入新队列的的队尾x=x-next;free(x-next);x-next=NULL;s-r