课程设计迷宫问题

1、西安邮电学院数据结构设计报告题 目： 迷宫问题院系名称： 计算机学院 专业名称： 软件工程班 级： 1002班 学生姓名： 吴云汉学号（8位）： 04103071指导教师： 王 燕设计起止时间：2011年11月28日2011年12月11日一：设计目的仅仅认识到队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法二. 设计内容1.迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述，2.迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷

2、宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组Mazemaxsizemaxsize,然后用它的前m行n列来存放元素，即可得到一个mn的二维数组。 3.迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列

3、中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径三概要设计1功能模块图maze creat()int found(int x,int y,Point *head)Point *secret(maze a) int print(Point *p) printmazepath(Point *p,maze road)void main()2. 各个模块详细的功能描述maze creat()/创建迷宫数组int found(int x,int y,Point *head)Point *secret(

4、maze a)/寻找迷宫出路函数int print(Point *p)/输出迷宫路径printmazepath(Point *p,maze road)/路径图void main()/主函数部分四详细设计1功能函数的调用关系图2重点设计及编码寻找迷宫出路函数Point *secret(maze a)/ Point *top,*p;/定义top入口、p为出口 int j,m,x,y;/j表示四个方向;m用来辅助j的循环判断条件 p=(Point *)malloc(sizeof(Point);/申请空间存放p p-vex_x=1; p-vex_y=1;/初始化行列数值 p-next=NULL;/置空

5、top=p;/将p的值赋给top j=1;/方向 do while(jvex_x; y=top-vex_y; switch(j) case 1:if(y+1vex_x=x;p-vex_y=y+1;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整下一步方向 top=p;m=1; break; case 2:if(x+1vex_x=x+1;p-vex_y=y;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整方向 top=p;m=1; break; case 3:if(y-1vex_x=x;p-vex_y=y-1;/控制行列

6、 p-next=top;/调整新出口 top-direction=j;/调整方向 top=p;m=1; break; case 4:if(x-1vex_x=x-1;p-vex_y=y;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整方向 top=p;m=1; break; if(m!=0) j=1;break; else j+; /whileif(j4)/控制j的值和控制跳出条件 if(top!=NULL) top=top-next; if(top=NULL)return NULL; j=top-direction+1;top-direction=j; w

7、hile(top-vex_x!=a.maze_x|top-vex_y!=a.maze_y);/dowhile探索条件 if(top-vex_x=a.maze_x&top-vex_y=a.maze_y)top-direction=0;/判断是否到达顶点 return top;五测试数据及运行结果1 正常测试数据和运行结果2异常测试数据及运行结果六调试情况，设计技巧及体会1改进方案在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以改用其他算法。2体会1. 对栈的理解还不够透彻，有些地方的改进是请教同学帮忙实现的.2. 了解数据结构在编写比较复杂的程序的重要作用.七参考文

8、献数据结构-C语言描述 耿国华 数据结构案例精编-清华大学出版社C语言程序设计-科学出版社 王曙燕八附录：源代码（电子版）#include#include#define maxsize 100/迷宫的最大行列数typedef struct int Mazemaxsizemaxsize;/迷宫数组 int maze_x,maze_y;/迷宫的行和列maze;typedef struct point int vex_x,vex_y; int direction;/方向 struct point *next;/递归定义point指向下一个结点 Point;maze creat()/创建迷宫数组 in

9、t i,j; maze a;/用a表示迷宫数组maze printf(迷宫的行数和列数:);/迷宫的行数和列数 scanf(%d%d,&a.maze_x,&a.maze_y);printf(|用0表示迷宫中的通路、1表示迷宫中的障碍!|n); for(i=1;i=a.maze_x;i+)/创建迷宫、给迷宫赋值 printf(输入第%d行:,i); for(j=1;jvex_x&y=p-vex_y) return 1; p=p-next; return 0;Point *secret(maze a)/寻找迷宫出路函数 Point *top,*p;/定义top入口、p为出口 int j,m,x,y

10、;/j表示四个方向;m用来辅助j的循环判断条件 p=(Point *)malloc(sizeof(Point);/申请空间存放p p-vex_x=1; p-vex_y=1;/初始化行列数值 p-next=NULL;/置空top=p;/将p的值赋给top j=1;/方向 do while(jvex_x; y=top-vex_y; switch(j) case 1:if(y+1vex_x=x;p-vex_y=y+1;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整下一步方向 top=p;m=1; break; case 2:if(x+1vex_x=x+1;p-

11、vex_y=y;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整方向 top=p;m=1; break; case 3:if(y-1vex_x=x;p-vex_y=y-1;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整方向 top=p;m=1; break; case 4:if(x-1vex_x=x-1;p-vex_y=y;/控制行列 p-next=top;/调整新出口 top-direction=j;/调整方向 top=p;m=1; break; if(m!=0) j=1;break; else j+; /whil

12、eif(j4)/控制j的值和控制跳出条件 if(top!=NULL) top=top-next; if(top=NULL)return NULL; j=top-direction+1;top-direction=j; while(top-vex_x!=a.maze_x|top-vex_y!=a.maze_y);/dowhile探索条件 if(top-vex_x=a.maze_x&top-vex_y=a.maze_y)top-direction=0;/判断是否到达顶点 return top;int print(Point *p)/输出迷宫路径 int i=0,top=0; Point *stac

13、kmaxsize;/输出的数组 if(p=NULL) printf(您输入的迷宫不能到达出口!n); return 0; else printf(输出路径:n); while(p!=NULL)/入栈 stacktop+=p; p=p-next; while(top0)/出栈 top-; printf(%d,%d,%d),stacktop-vex_x,stacktop-vex_y,stacktop-direction); i+; if(i%8=0)printf(n); printf(n); return 1;void printmazepath(Point *p,maze road)/路径图 i

14、nt i,j; char mmaxsizemaxsize;/路径图数组 printf(路径图是:n); for(i=1;i=road.maze_x;i+) for(j=1;jdirection)/方向箭头case 0:mp-vex_xp-vex_y=15;break;/到达case 1:mp-vex_xp-vex_y=26;break;/case 2:mp-vex_xp-vex_y=25;break;/case 3:mp-vex_xp-vex_y=27;break;/case 4:mp-vex_xp-vex_y=24;break;/p=p-next;for(i=1;i=road.maze_x;i+)for(j=1;j=road.maze_y