数据结构实验报告：迷宫问题.doc

成绩：存档资料 武汉大学东湖分校计算机科学学院课 程 设 计 报 告 课程名称 数据结构课程设 题 目 深度与广度优先搜索 迷宫问题 专业班级 计算机应用(1)班 学 号 学生姓名 指导教师 2012 年 01 月 03 日武汉大学东湖分校计算机科学学院课程设计任务书（由指导教师填写）课程名称： 数据结构课程设计 设计题目： 深度与广度优先搜索：迷宫问题 专 业： 计算机应用 班 级： （1） 完成时间： 2012.1.14 指导教师： 专业负责人： 许先斌 主要内容利用图的邻接矩阵存储方法和深度、广度优先遍历算法实现设计一个程序：（1）能自动或者手动生成一个88的矩阵，针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。（2）如果不能，请输出提示；如果能，请输出每一步所经过的结点坐标。基本要求（1）完成程序所要实现的功能，得到正确的运行结果。（2）做好程序的功能测试，测试能走到和不能走到两种情况，程序均能得到正确结果。（3）严格按照课程设计报告的步骤和内容要求撰写报告，做到有文字描述，有图表说明。（4）严格按照课程设计报告的格式要求调整报告格式，包括字体、字体大小等。（5）要求上交源代码。参考资料数据结构（第3版） 李春葆 清华大学出版社数据结构课程设计 何钦铭 浙江大学出版社武汉大学东湖分校计算机科学学院课程设计成绩评价表课程名称数据结构课程设计题 目深度与广度优先搜索：迷宫问题学生姓名学号指导教师姓名职称助教 序 号评价项目指 标满分评分1工作量、工作态度和出勤率按期圆满的完成了规定的任务，难易程度和工作量符合教学要求，工作努力，遵守纪律，出勤率高，工作作风严谨，善于与他人合作。202课程设计质量课程设计选题合理，计算过程简练准确，分析问题思路清晰，结构严谨，文理通顺，撰写规范，图表完备正确。453创新工作中有创新意识，对前人工作有一些改进或有一定应用价值。54答辩能正确回答指导教师所提出的问题。30总 分评 语：指导教师： 年 月 日【软件课程设计报告目录】1、需求分析1.1 自动或者手动生成一个M*M的矩阵，针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。若能到达终点，输出路径上的各个结点,若不能到达,则输出失败标志;要实现这个程序,首先要考虑如何表示这个迷宫.在示例程序中使用二维数组mazeM+2M+2来表示这个迷宫，其中M（2-39）为迷宫的行、列数。用mazeM+2M+2来表示迷宫，而不是使用mazeMM来表示迷宫式防止当遍历到迷宫边界是可能跳出迷宫，而是用mazeM+2M+2就可以吧迷宫的外面加一层“墙”即“1”；找出路时，在每一点都有8中方向可以走：右下，右，下，右上，左下，上，左，左上，在找出路时，最近的路线为对角线，所以设置方向的次序由左下到右上的顺序可尽量减少查找的次数；方向如图：753614201.2 输入的形式和输入值的范围:输入型形式分为两种：一种手动输入8*8的矩阵，第二种为有程序自动生成随机数 （rand()函数）；输入值的范围 “0”或“1”分别表示可以走的地方和墙;1.3 输出形式：输出迷宫，以及程序的运行结果；结果包括有路径和无路径，有路径时输出路径上的各点，并将路劲以箭头的方式在矩阵上指出；1.4 程序所能达到的功能:判断输入的矩阵是否有路径由起点到终点，若有路径输出具体路径，若无则输出失败标志；1.5 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。输入迷宫规模是范围不当,输出错误,且要求重新输入; 选择输入方式是错误时，输出选择错误，且要求重新输入；输入矩阵错误时，提示某点输入错误，且要求重新输入；2、概要设计2.1 类型的定义：typedef struct int row;/行int col;/列int dir;/方向element;element stackMAX_STACK_SIZE;/存储走过的位置typedef struct int vert;水平方向增量int horiz;垂直方向增量offsets; /记录八个方向（右下，右，下，右上，左下，上，左，左上）offsets move8; /八个方向int mazeN+2N+2; /迷宫int markN+2N+2; /记录maze数组上的元素是否别访问过int EXIT_ROW,EXIT_COL;/定义找到出口时的行和列主函数path（）del（）add（）2.2 关系：下图为path（）函数的流程图3、详细设计 第 12页 （共 12页）void path()int row,col,next_row,next_col,dir,found=FALSE;/分别为：当前位置行、列号，下一位置行、列号，遍历方向element position;int top=0;mark11=1; /标记初始位置stack0.row=1； /初始位置行号stack0.col=1; /初始位置列号stack0.dir=0; /定义初始位置遍历方向move0.vert=1;move0.horiz=1;/八个方向具体设置move1.vert=0;move1.horiz=1;move2.vert=1;move2.horiz=0;move3.vert=-1;move3.horiz=1;move4.vert=1;move4.horiz=-1;move5.vert=-1;move5.horiz=0;move6.vert=0;move6.horiz=-1;move7.vert=-1;move7.horiz=-1;while (栈不为空且没找到路径)position =del(&top); /栈顶元素出栈/将出栈元素作为当前位置row=position.row;col=position.col;dir=position.dir;while(八个方向没走完且没找到出路)next_row=row+movedir.vert; /下一位置行号next_col=col+movedir.horiz; /下一位置列号if(下一位置为终点)found=TRUE;当前位置入栈；终点入栈；else if(下一位置非墙且没走过)/标记“下一位置；”“当前位置”入栈；“当前位置”改为“下一位置”初始方向设为第一方向即（dir=0）else 遍历下一方向即（dir+）if(found)/int count=0; /记录节点为输出路径上的第几个节点输出 ：找到路径!路径坐标如下：for(int i=0;i=top;i+)count+;/计数输出该节点坐标；if(count%5=0)printf(n);printf(nnn);int flag; /记录最后遍历方向的下一方向printf(具体路径为：n);for(i=1;iN+1;i+)for(int j=1;jN+1;j+)flag=-1; /初值if(栈中有该点坐标)flag=1;if(flag=-1)printf(%2d,mazeij);/该点不在路径上，输出else 输出栈中存储的上一方向printf(n);printf(nn);else printf( 未找到路径!nnnn);printf(-n);4、使用说明、测试分析及结果（1）使用说明：依次按照文字提示输入，输入迷宫的方式：手动，自动随机产生，手动输入“0”或“1”分别代表路和墙，输入完成，即可生成结果；（2）测试结果与分析；错误测试结果矩阵输入数值不当（3）调试过程中遇到的问题是如何解决提以及对设计与实现的回顾讨论和分析；（4）运行界面。没有找到路径：找到路径：5、课程设计总结 由于以前的知识学习的不算扎实，所以该课程设计对于我来说还是很有难度的。在编写程序的时候，经常要去看教科书，或者向同学请教。程序写好之后，花了4个小时注释，悲剧的是运行之后，出现了N多错误，只好又逐字逐句的检查，实在找不出来就只能自己慢慢调试。就这样磕磕绊绊弄了5天程序代码以及流程图才勉强完成。 总的来说，这次设计报告很