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

《数据结构实验报告：迷宫问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉大学东湖分校计算机科学学院课程设计报告课程名称数据结构课程设题B深度与广度优先搜索迷宫问题专业班级计算机应用（1）班学号学生姓名指导教师2012年01月03日武汉大学东湖分校计算机科学学院课程设计任务书(巾指导教师填写)课程名称：数据结构课程设计设计题目：深度与广度优先搜索：迷宫问题专业：计算机应用班级：m完成时间：2012.1.14指导教师：专业负贵人：许先斌主要内容利用图的邻接矩阵存储方法和深度、广度优先遍历算法实现没计一个程序：(1)能自动或者手动生成一个8X8的矩阵，针对这个矩阵，程序判断是否能从起点经过迷宫走到终点。(2)如果不能

2、，请输岀提示；如果能，请输岀每一步所经过的结点坐标。基本要求(1)完成程序所要实现的功能，得到正确的运行结果。(2)做好程序的功能测试，测试能走到和不能走到两种情况，程序均能得到正确结果。(3)严格按照课程设计报告的步骤和A容要求撰写报告，做到有文字描述，有图表说明。(4)严格按照课程设计报告的格式要求调整报告格式，包括字体、字体大小等。(5)要求上交源代码。参考资料《数据结构(第3版)》李春葆清华大学出版社《数据结构课程没计》何钦铭浙江大学出版社武汉大学东湖分校计算机科学学院课程设计成绩评价表课程名称数据结构课程设计题目深度与广度优先搜索：迷

3、宫问题学生姓名学指导教号师姓名职称助教序号评价项指标满分评分1工作量、工作态度和山勤率按期圆满的完成了规定的任务，难易程度和工作量符合教学要求，工作努力，遵守纪律，山勤率高，工作作风严谨，善于与他人合作。202课程设计质量课程没计选题合理，计算过程简练准确，分析问题思路清晰，结构严谨，文理通顺，撰写规范，图表完备正确。453创新工作屮有创新意识，对前人工作有一些改进或有一定应用价值。54答辩能正确回答指导教师所提出的问题。30总分评语：指导教师：年_月_日【软件课程设计报告目录］1、需求分析1.1自动或者手动生成一个M*M的矩阵，针对这个矩阵，

4、程序判断是否能从起点经过迷宫走到终点。若能到达终点，输出路径上的各个结点，若不能到达，则输出失败标志；要实现这个程序，首先要考虑如何表示这个迷宫.在示例程序中使用二维数组maze[M+2][M+2]来表示这个迷宫,其中M(2-39)为迷宫的行、列数。用maze[M+2][M+2]来表示迷芭，而不是使用maze[M][M]来表示迷宫式防止当遍历到迷宫边界是可能跳出迷宫，而是用maze[M+2][M+2]就可以吧迷宫的外面加一层“墙”即“1”；找出路时，在每一点都有8中方向可以走：右下，右，下，右上，左下，上，左，左上，在找出路时，最近的路线为对角

5、线，所以设置方向的次序由左下到右上的顺序可尽量减少查找的次数：方向如图：753614201.2输入的形式和输入值的范围:输入型形式分为两种：一种手动输入8*8的矩阵，第二种为有程序自动生成随机数(mnd()函数)；输入值的范围“0”或“1”分别表示可以走的地方和墙；1.3输出形式：输出迷宫，以及程序的运行结果；结果包括有路径和无路径，有路径吋输出路径上的各点，并将路劲以箭头的方式在矩阵上指出；1.4程序所能达到的功能:判断输入的矩阵是否有路径由起点到终点，若有路径输出具体路径，若无则输出失败标志；1.5测试数据：包括正确的输入及其输出结果和含有

6、错误的输入及其输出结果。输入迷宫规模是范围不当，输出错误，且要求重新输入；选择输入方式是错误时，输出选择错误，且要求重新输入；输入矩阵错误时，提示某点输入错误,且要求重新输入；2、概要设计2.1类型的定义：typedefstruct{introw;//^yintcol;//列intdir;//方向}element;elementstack[MAX_STACK_SIZE];//存储走过的位置typedefstruct{intvert;水平方向增量inthoriz;垂直方向增量}offsets;//记录八个方向(右下，古，下，石上，左下，上，左，左

7、上)offsetsmove[8]://八个方向intmaze[N+2][N+2];//迷宫intmark[N+2][N+2];//记录maze数组上的元素是否别访问过intEXIT_ROW,EXIT_COL;//定义找到出口时的行和列2.2关系：下图为path()函数的流程图找利dlft和im•入携”摘⑽置入祝rr妫〈幽SnfUWFUKW下—•《祁.也卜一⑽3、详细设计voidpathO{introw,col,next_row,next_col,dir,found=FALSE;//分别为：当前位置行、列号，下一位置行、列号，遍历方向//标记初始

8、位置//初始位置行号//初始位置列号//定义初始位置遍历方向elementpositioninttop=0;mark[l][1]=1;stack[OL