数据结构 迷宫问题(栈、C)

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

2、、 问题分析和任务定义此程序可以用二维数组存储迷宫数据，设定入口点的下标为（1，1），出口点的下标为（m,n）。为处理方便起见，在迷宫的四周加一圈障碍。对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通，并默认以东、南、西、北的顺序进行搜索路线。将走过的路线放入链栈中，当走出迷宫时，栈中及走出迷宫的路线；当走不出时，栈为空。实现本程序需要解决以下几个问题：1. 如何通过二维数组建立并存储迷宫。2. 如何进行路径搜索。3. 按一个方向搜索不到出路时怎么办？4. 将符合条件的路线存储。5. 搜索到出路时按顺序输出路线。首先，可以用二维数组存储迷宫，0和1分别表示迷宫中的通路和障碍,为处理方便

3、起见，建立迷宫时在迷宫四周加一圈障碍。例如一个5*5的迷宫用二维数组可表示为：int maze77= 1,1,1,1,1,1,1, 1,0,0,0,0,0,1, 1,1,1,1,1,0,1, 1,0,0,0,0,0,1, 1,0,1,1,1,1,1, 1,0,0,0,0,0,1, 1,1,1,1,1,1,1;路径搜索时，需要知道出口和入口的坐标，本程序默认为（1,1）、（m，n）。定义一个移动坐标(xc,yc），用以记录搜索路线时当前位置的坐标。搜索时默认按照东、南、西、北的优先顺序进行查找，其中，向东搜索用“1”表示，向南、向西、向北分别用“2”、“3”、“4”表示，“0”表示方向未知。当向

4、东无路时，再向西查找当某位置为通路时（mazeij=0），则将这一步的信息放入栈中。同时，将此步设置为障碍，防止下一步搜索时出现“回头”的现象。若为障碍时，此时，将栈中元素出去，即沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。将栈中的元素输出，即寻找到的出迷宫的路线。假如所有可能的通路都探索到而未能到达出口，则所设的迷宫没有通路。如上面的例子中，最后输出的路线为：（1，1,1）、（1,2,1）、（1,3,1）、（1,4,1）、（1,5,2）、（2,5,2）、（3,5,3）、（3,4,3）、（3,3,3）、（3,2,3）、（3,1,2）、（4,1,2）、（5,1,1）、（5,2,

5、1）、（5,3,1）、（5,4,1）、（5,5,0）。2、 数据结构的选择和概要设计 迷宫数据用二维数组int mazeSIZE+2SIZE+2来存储即可(迷宫四周加障碍，所以行列数加2)，在定义了迷宫的行列数后，利用两个for循环即可用键盘录入迷宫信息，并在迷宫周围加围墙。存储搜索路线按题目要求采用链栈的数据结构，用非递归的方法求解路线。图（1）为程序的流程图。3、 详细设计和编码首先建立迷宫。用户自定义迷宫的行列数m、n，利用嵌套循环将迷宫信息存储于数组mazem+2n+2中：for(i=0;i<m+2;i+) for(j=0;j<n+2;j+) if(i=0|i=m+1|j=

6、0|j=n+1) /在迷宫周围加障碍mazeij=1; else scanf("%d",&mazeij); 在对迷宫探索时，每一步都有四个方向可以搜索，为实现这一操作，可建立一个移动数组move8。向东搜索时坐标变化为横坐标不变，纵坐标加一，向南搜索时坐标变化为横坐标加一，纵坐标不变，向西搜索时坐标变化为横坐标不变，纵坐标减一，向北搜索时坐标变化为横坐标减一，纵坐标不变。这样就完成了向四个方向的搜索操作。建立链栈用于存储路线信息。链栈的数据域为包含了i，j，d的结构体，这样就能将路线的每一步信息存储下来。再建立一个移动坐标，以记录搜索过程中变化方向时坐标的变化。路线

7、搜索：1. 先将入口信息入栈，当栈不为空时，转2，否则转7；2. 将当前位置信息（item->x、item->y、item->d）赋给动态变量（x、y、d）；3. 此位置是否有方向可搜索，是则移动到下一方向，并判断是否为通路，若为通路，转4，若不为通路，换个方向继续搜索，否则转6；4. 则将此位置信息入栈，同时将此位置设置为障碍，避免下一步搜索时返回原路，并判断此位置是否为出口，是则转8，不是转5；5. 初始化搜索方向，转3；6. 执行出栈，判断栈是否为空，是则转，不是则取栈顶元素并转3；7. 迷宫无出路；8. 逆置栈中元素，输出迷宫路线。如对上面提到的迷宫maze77进行路

8、线搜索时，入口maze11的信息为x=1、y=1、d=0（暂时不知道下一步的移动方向，故d的值为0），将其入栈。此时栈不为空，按照东、南、西、北的优先搜索顺序进行路径查找。Maze11向东有方向可搜索，移动坐标变化i=x+move1.xc、j=y+move1.yc并且mazeij=0，即此位置可到达。将此位置信息入栈。以此类推，当到maze15时，向东不可再搜索时，开始向南搜索。移动坐标变化i=x+move2.xc、j=y+move2.yc并且mazeij=0，此位置可到达，将此位置信息入栈，同时要初始化搜索方向最终，将搜索到出口maze55，输出出迷宫路线，程序结束。4、 上机调试过程1.

9、语法错误及修改由于本程序运用了链栈的数据结构，并要求用非递归算法求解，所以在设计过程中遇到了不少语法错误。在建立链栈的过程中无错误，但关于链栈类型的子函数的返回值问题是有一些问题。在链栈的逆置时，由于不可使用递归算法，产生了一些麻烦，同时增加了时间和空间的复杂度。在遇到语法错误时，经过反复的调试分析后，所有的语法错误均得到了很好的解决。2. 逻辑错误在编写本程序之前，本人阅读了一些参考材料，充分的了解了迷宫问题的核心思想，同时也想到了图的深度优先搜索遍历与此题的思想极为相似，所以在编写程序的过程中，未遇到逻辑错误，大多问题都是语法错误。Main()建立移动数组用户自定义迷宫行列数和布局出口和入

10、口是否有障碍 是初始化链栈并将入口信息入栈 否栈是否为空 是当前坐标四周是否有方向可搜索 否删除栈中此步信息 是坐标移动栈是否为空此步有无障碍换方向搜索 是 否 是迷宫无出路此步信息入栈此步是否为出口 否 栈逆置并输出路线 是结束 图（1） 流程图5、 调试结果及其分析图（2） 调试结果上面三张图是程序的运行结果，分别在有出路和无出路的情况下进行了调试。由于在建立迷宫的过程中，程序会自动加一圈障碍，所以用户只需输入迷宫布局即可。6、 用户使用说明1. 本程序设计源代码重要的语句均有相应的注释，用户可根据注释加以阅读和理解；2. 本程序设计源代码要求迷宫行列数不大于10，用户可根据需要加以修改行

11、列数的最大值SIZE。3. 用户使用程序时，需要先输入行列数（注意范围），再建立与之对应的迷宫数据（0和1分别表示迷宫中的通路和障碍），回车后，即可看到搜索结果。7、 参考文献1 王昆仑、李红 数据结构与算法 北京：中国铁道出版社 2006年5月2 严蔚敏、吴伟民 数据结构 北京：北京大学出版社，2007年5月8、 附录程序源代码：#include <stdio.h>#include <malloc.h>#define SIZE 10typedef struct/位置信息，x、y为坐标，d为下一步的移动方向int x,y,d;elemtype;typedef struc

12、t node/链栈结点类型elemtype data; struct node *next;Linkstack;typedef structint xc,yc;Change; int mazeSIZE+2SIZE+2;/二维数组，存储迷宫信息void Createmove(Change move8)/移动数组move1.xc=0;move1.yc=1;move2.xc=1;move2.yc=0;move3.xc=0;move3.yc=-1;move4.xc=-1;move4.yc=0;Linkstack *Initstack()/初始化栈 Linkstack *L;L=(Linkstack *

13、)malloc(sizeof(Linkstack);L->next=NULL;return L; Linkstack *Push(Linkstack *L,elemtype *item)/入栈Linkstack *temp=L;L=(Linkstack*)malloc(sizeof(Linkstack); L->data =*item; L->next=temp;return L;void GrainPop(Linkstack *L,elemtype *item)/取栈顶元素*item=L->data; Linkstack *DeletePop(Linkstack *L

14、)/出栈if(L=NULL) printf("栈已清空！n");return NULL;else Linkstack *temp=L;L=L->next;free(temp);/释放内存return L;void Createmaze(int m,int n)/建立迷宫 int i,j;printf("建立迷宫：n");for(i=0;i<m+2;i+) for(j=0;j<n+2;j+) if(i=0|i=m+1|j=0|j=n+1)/迷宫周围加障碍mazeij=1; else scanf("%d",&ma

15、zeij); printf("迷宫打印为：n"); for(i=0;i<m+2;i+) for(j=0;j<n+2;j+) printf("%3d",mazeij); printf("n"); int Stackempty(Linkstack *L)/ 判断栈是否为空if(L=NULL)return 0;elsereturn 1; int Searchpath(Linkstack *L,int mazeSIZE+2SIZE+2,Change move8,int m,int n,Linkstack *p)/路线搜索 int

16、x,y,d,i,j;elemtype *item;item=(elemtype *)malloc(sizeof(elemtype);item->x=1;/入口信息入栈，0表示方向未知item->y=1;item->d=0;maze11=1;/标记L=Push(L,item);while(Stackempty(L) x=item->x; y=item->y; d=item->d+1;while(d<5) /1东2南3西4北 i=x+moved.xc; j=y+moved.yc; if(mazeij=0)/此位置为通路 L->data.d=d; it

17、em->x=i; item->y=j; L=Push(L,item); mazexy=1; x=i; y=j; if(x=m&&y=n)/判断是否到达出口*p=L;return 1; else d=1;/初始化搜索方向 else d+;/变化搜索方向 L=DeletePop(L);/将不存在出路的结点删除if(!L)GrainPop(L,item);/取栈顶elsereturn 0; *p=L;return 0; void Printpath(Linkstack *L)/路线输出Linkstack *p,stack100;int i=-1;p=L;while(p!=

18、NULL)/栈逆置stacki+.data=p->data;p=p->next;while(i>-1)/输出三元组i-;printf("(%2d,%2d,%2d)n",stacki.data.x,stacki.data.y,stacki.data.d);/*void Printpath(Linkstack *s)/递归算法输出 if(s)Printpath(s->next);printf("(%2d,%2d,%2d)n",s->data.x,s->data.y,s->data.d); */void main()int m,n; Change move8;Linkstack *L=NULL; Linkstack *pL