课程设计迷宫问题

西安邮电学院数据结构设计报告题目：迷宫问题院系名称：计算机学院专业名称：软件工程班级：1002班学生姓名：吴云汉学号（8位）：04103071指导教师：王燕设计起止时间：2011年11月28日~2011年12月11日 一：设计目的仅仅认识到队列是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解队列的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法二.设计内容1.迷宫的建立：迷宫中存在通路和障碍，为了方便迷宫的创建，可用0表示通路，用1表示障碍，这样迷宫就可以用0、1矩阵来描述，2.迷宫的存储：迷宫是一个矩形区域，可以使用二维数组表示迷宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组Maze[maxsize][maxsize],然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组。3.迷宫路径的搜索：首先从迷宫的入口开始，如果该位置就是迷宫出口，则已经找到了一条路径，搜索工作结束。否则搜索其上、下、左、右位置是否是障碍，若不是障碍，就移动到该位置，然后再从该位置开始搜索通往出口的路径；若是障碍就选择另一个相邻的位置，并从它开始搜索路径。为防止搜索重复出现，则将已搜索过的位置标记为2，同时保留搜索痕迹，在考虑进入下一个位置搜索之前，将当前位置保存在一个队列中，如果所有相邻的非障碍位置均被搜索过，且未找到通往出口的路径，则表明不存在从入口到出口的路径。这实现的是广度优先遍历的算法，如果找到路径，则为最短路径三．概要设计1．功能模块图mazecreat()intfound(intx,inty,Point*head)Point*secret(mazea)intprint(Point*p)printmazepath(Point*p,mazeroad)voidmain()2.各个模块详细的功能描述mazecreat()//创建迷宫数组intfound(intx,inty,Point*head)Point*secret(mazea)//寻找迷宫出路函数intprint(Point*p)//输出迷宫路径printmazepath(Point*p,mazeroad)//路径图 voidmain()//主函数部分四．详细设计1．功能函数的调用关系图 2．重点设计及编码寻找迷宫出路函数Point*secret(mazea)//{Point*top,*p;//定义top入口、p为出口intj,m,x,y;//j表示四个方向;m用来辅助j的循环判断条件p=(Point*)malloc(sizeof(Point));//申请空间存放pp->vex_x=1;p->vex_y=1;//初始化行列数值p->next=NULL;//置空top=p;//将p的值赋给topj=1;//方向do{while(jvex_x;y=top->vex_y;switch(j){case1:if(y+1vex_x=x;p->vex_y=y+1;//控制行列p->next=top;//调整新出口top->direction=j;//调整下一步方向top=p;m=1;}break;case2:if(x+1vex_x=x+1;p->vex_y=y;//控制行列p->next=top;//调整新出口top->direction=j;//调整方向 top=p;m=1;}break;case3:if(y-1vex_x=x;p->vex_y=y-1;//控制行列p->next=top;//调整新出口top->direction=j;//调整方向top=p;m=1;}break;case4: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;}elsej++;}//whileif(j>4)//控制j的值和控制跳出条件{if(top!=NULL){top=top->next;if(top==NULL)returnNULL;j=top->direction+1;top->direction=j;}}}while(top->vex_x!=a.maze_x||top->vex_y!=a.maze_y);//do……while探索条件if(top->vex_x==a.maze_x&&top->vex_y==a.maze_y)top->direction=0;//判断是否到达顶点returntop; }五．测试数据及运行结果1．正常测试数据和运行结果2．异常测试数据及运行结果 六．调试情况，设计技巧及体会1．改进方案在调试过程中，首先使用的是栈进行存储，但是产生的路径是多条或不是最短路径，所以改用其他算法。2．体会1.对栈的理解还不够透彻，有些地方的改进是请教同学帮忙实现的.2.了解数据结构在编写比较复杂的程序的重要作用.七．参考文献《数据结构----C语言描述》耿国华《数据结构案例精编》---清华大学出版社《C语言程序设计》-----科学出版社王曙燕八．附录：源代码（电子版）#include#include#definemaxsize100//迷宫的最大行列数typedefstruct{intMaze[maxsize][maxsize];//迷宫数组intmaze_x,maze_y;//迷宫的行和列}maze;typedefstructpoint{intvex_x,vex_y;intdirection;//方向structpoint*next;//递归定义point指向下一个结点}Point;mazecreat()//创建迷宫数组{inti,j;mazea;//用a表示迷宫数组mazeprintf("迷宫的行数和列数:");//迷宫的行数和列数scanf("%d%d",&a.maze_x,&a.maze_y);printf("||用0表示迷宫中的通路、1表示迷宫中的障碍!||\n");for(i=1;ivex_y)return1;p=p->next;}return0;}Point*secret(mazea)//寻找迷宫出路函数{Point*top,*p;//定义top入口、p为出口intj,m,x,y;//j表示四个方向;m用来辅助j的循环判断条件p=(Point*)malloc(sizeof(Point));//申请空间存放pp->vex_x=1;p->vex_y=1;//初始化行列数值p->next=NULL;//置空top=p;//将p的值赋给topj=1;//方向do{while(jvex_x;y=top->vex_y;switch(j){case1:if(y+1vex_x=x;p->vex_y=y+1;//控制行列 p->next=top;//调整新出口top->direction=j;//调整下一步方向top=p;m=1;}break;case2:if(x+1vex_x=x+1;p->vex_y=y;//控制行列p->next=top;//调整新出口top->direction=j;//调整方向top=p;m=1;}break;case3:if(y-1vex_x=x;p->vex_y=y-1;//控制行列p->next=top;//调整新出口top->direction=j;//调整方向top=p;m=1;}break;case4: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;} elsej++;}//whileif(j>4)//控制j的值和控制跳出条件{if(top!=NULL){top=top->next;if(top==NULL)returnNULL;j=top->direction+1;top->direction=j;}}}while(top->vex_x!=a.maze_x||top->vex_y!=a.maze_y);//do……while探索条件if(top->vex_x==a.maze_x&&top->vex_y==a.maze_y)top->direction=0;//判断是否到达顶点returntop;}intprint(Point*p)//输出迷宫路径{inti=0,top=0;Point*stack[maxsize];//输出的数组if(p==NULL){printf("您输入的迷宫不能到达出口!\n");return0;}else{printf("输出路径:\n");while(p!=NULL)//入栈{stack[top++]=p;p=p->next;}while(top>0)//出栈{top--;printf("(%d,%d,%d)",stack[top]->vex_x,stack[top]->vex_y,stack[top]->direction);i++;if(i%8==0)printf("\n");}}printf("\n");return1;} voidprintmazepath(Point*p,mazeroad)//路径图{inti,j;charm[maxsize][maxsize];//路径图数组printf("路径图是:\n");for(i=1;ivex_x][p->vex_y]=15;break;//到达case1:m[p->vex_x][p->vex_y]=26;break;//→case2:m[p->vex_x][p->vex_y]=25;break;//↓case3:m[p->vex_x][p->vex_y]=27;break;//←case4:m[p->vex_x][p->vex_y]=24;break;//↑}p=p->next;}for(i=1;i