课程设计迷宫问题

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

2、宫，这样迷宫的每一个位置都可以用其行列号来唯一指定，但是二维数组不能动态定义其大小，我们可以考虑先定义一个较大的二维数组mazemaxsizemaxsize,然后用它的前m行n列来存放元素，即可得到一个m×n的二维数组。 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 *s

4、ecret(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

5、->next=null;/置空top=p;/将p的值赋给top j=1;/方向 do while(j<=4) m=0; x=top->vex_x; y=top->vex_y; switch(j) case 1:if(y+1<=a.maze_y&&!a.mazexy+1&&!found(x,y+1,top)/右/并判断新路口的下一个点 p=(point *)malloc(sizeof(point); p->vex_x=x;p->vex_y=y+1;/控制行列 p->next=top;/调整新出口 top->di

6、rection=j;/调整下一步方向 top=p;m=1; break; case 2:if(x+1<=a.maze_x&&!a.mazex+1y&&!found(x+1,y,top)/下/并判断新路口的下一个点 p=(point *)malloc(sizeof(point); p->vex_x=x+1;p->vex_y=y;/控制行列 p->next=top;/调整新出口 top->direction=j;/调整方向 top=p;m=1; break; case 3:if(y-1<=a.maze_y&&!a.

7、mazexy-1&&!found(x,y-1,top)/左/并判断新路口的下一个点 p=(point *)malloc(sizeof(point); p->vex_x=x;p->vex_y=y-1;/控制行列 p->next=top;/调整新出口 top->direction=j;/调整方向 top=p;m=1; break; case 4:if(x-1<=a.maze_x&&!a.mazex-1y&&!found(x-1,y,top)/上/并判断新路口的下一个点 p=(point *)malloc(sizeof(p

8、oint); p->vex_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(j>4)/控制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|to

9、p->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. 了解数据结构在编写比较复杂的程序的重要作用.七参考文献数

10、据结构-c语言描述 耿国华 数据结构案例精编-清华大学出版社c语言程序设计-科学出版社 王曙燕八附录：源代码（电子版）#include<stdio.h>#include<malloc.h>#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指向下一个结点

11、 point;maze creat()/创建迷宫数组 int 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;j<=a.maze_y;j+) scanf(&qu

12、ot;%d",&a.mazeij); return a;/返回迷宫a的值int found(int x,int y,point *head)/ point *p=head;/定义头指针 while(p)/p不等于零、执行循环条件 if(x=p->vex_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;/j表示四个方向;m用来辅助j的循环判断条件 p=(point

13、 *)malloc(sizeof(point);/申请空间存放p p->vex_x=1; p->vex_y=1;/初始化行列数值 p->next=null;/置空top=p;/将p的值赋给top j=1;/方向 do while(j<=4) m=0; x=top->vex_x; y=top->vex_y; switch(j) case 1:if(y+1<=a.maze_y&&!a.mazexy+1&&!found(x,y+1,top)/右/并判断新路口的下一个点 p=(point *)malloc(sizeof(poin

14、t); p->vex_x=x;p->vex_y=y+1;/控制行列 p->next=top;/调整新出口 top->direction=j;/调整下一步方向 top=p;m=1; break; case 2:if(x+1<=a.maze_x&&!a.mazex+1y&&!found(x+1,y,top)/下/并判断新路口的下一个点 p=(point *)malloc(sizeof(point); p->vex_x=x+1;p->vex_y=y;/控制行列 p->next=top;/调整新出口 top->dir

15、ection=j;/调整方向 top=p;m=1; break; case 3:if(y-1<=a.maze_y&&!a.mazexy-1&&!found(x,y-1,top)/左/并判断新路口的下一个点 p=(point *)malloc(sizeof(point); p->vex_x=x;p->vex_y=y-1;/控制行列 p->next=top;/调整新出口 top->direction=j;/调整方向 top=p;m=1; break; case 4:if(x-1<=a.maze_x&&!a.maze

16、x-1y&&!found(x-1,y,top)/上/并判断新路口的下一个点 p=(point *)malloc(sizeof(point); p->vex_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(j>4)/控制j的值和控制跳出条件 if(top!=null) top=top->next; if(top=null)return null; j=t

17、op->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 *stackmaxsize;/输出的数组 if(p=null) printf("

18、您输入的迷宫不能到达出口!n"); return 0; else printf("输出路径<三元组表示>:n"); while(p!=null)/入栈 stacktop+=p; p=p->next; while(top>0)/出栈 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)/路径图 int i,j; char mmaxsizemaxsize;/路径图数组 printf("路径图是:n"); for(i=1;i<=road.maze_x;i+) for(j=1;j<=road.maze_y;j+) if(r