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