推箱子的最短路径数据结构与C语言综合训练报告Word格式文档下载.docx
《推箱子的最短路径数据结构与C语言综合训练报告Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《推箱子的最短路径数据结构与C语言综合训练报告Word格式文档下载.docx（12页珍藏版）》请在冰点文库上搜索。
本综合训练是计算机科学与技术、信息管理与信息系统、软件工程、电子商务专业重要的实践性环节之一，是在学生学习完《程序设计语言（C）》、《数据结构》课程后进行的一次全面的综合练习。
本课综合训练的目的和任务：
1.巩固和加深学生对C语言、数据结构课程的基本知识的理解和掌握
2.掌握C语言编程和程序调试的基本技能
3.利用C语言进行基本的软件设计
4.掌握书写程序设计说明文档的能力
5.提高运用C语言、数据结构解决实际问题的能力
二、综合训练任务内容
1.题目要求：
推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个5×
5的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.同时，房间里头还有若干障碍物（用阴影部分表示）。
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.
2.扩展实现的内容：
绘制图形界面，通过按钮实现推箱子的整个过程，整个过程中可以动态的看到箱子的移动。
游戏界面如下图：
游戏动态移动的过程图如下：
三、总体设计
所用算法主要是根据广度优先搜索，纪录路径，然后利用回溯法实现最短路径的查找并纪录保存下来。
所用的数据结构主要为顺序结构。
四、详细设计说明
1、推箱子游戏具有的功能
（1）能够显示主菜单和界面
游戏需要提供主菜单进行选择，同时能够把地图文件中的信息转换成为图像显示到游戏界面上。
（2）能够实现键盘操作功能
能够接收到空格键信息，按照软件内部实现的箱子移动到相应的位置。
（3）能够进行关卡选择功能
进入开始游戏的界面时，可以进行游戏的关卡的选择，然后利用空格键进行箱子的移动。
（4）提供游戏说明功能
进入游戏说明界面时，可以了解游戏的一些规则，及如何进行游戏。
2、程序结构设计
运用C++语言，以及VS2010开发环境
（1）、typedefstructPnode{
introw;
intcol;
intweight;
structPnode*back_man;
}Pnode,*Position;
某一点的坐标表示，当用来实现箱子的最短路径的搜索时，back_man用来存储箱子移动一个位置后，人所在的位置。
（2）、typedefstructMnode{
intmrow;
intmcol;
charmaze[MAX_ROW][MAX_COL];
}MNode,*MazeType;
用来存储地图的信息
（3）、算法的实现
主要有两个类，第一个类是classShortestPath；
第二个类是classManBoxStep:
publicShortestPath；
A、第一个类classShortestPath是用来实现地图中任意两点之间的最短路径，成员函数及其功能如下：
PositionNextPosition（Position&
curpos,intdi）;
用来计算当前点在四个方向下的移动一格得到的下一点的坐标位置，并返回；
boolCanArrive（vector<
list<
Position>
>
&
vec）;
数据成员有start，end，此函数是判断在地图中能否从start到end，并利用广度优先搜索搜索从start到end的路径，并把所有搜索过的位置全部记录在顺序容器vec中，vec[i]表示存储一系列与start位置相距i个格子的被搜索的点的位置；
voidRecordWay（vector<
vec,vector<
way）;
此函数根据vec中所存储的数据，利用回溯法进行往回搜索，找到从start到end的最短路径，并把路径存到容器way中；
B、第二个类classManBoxStep是利用第一个类中的函数实现人和箱子一起从起点到箱子应到的位置的最短路径，其中的成员函数及其功能如下：
PositionNextState（Positionbox,intdi）;
此函数的功能是纪录当人能够移动箱子的情况下，纪录移动后箱子和人的位置；
MazeTypeUpdateMaze（MazeTypemymaze,Positioncurpos,Positionnewpos）;
此函数的功能是每当在搜索下一步时，及时的更新所在的地图（即改变人和箱子的位置），并每次都将地图纪录下来；
boolBFSCanArrive（vector<
AllWay,
vector<
vector<
man_way,
MazeType>
&
maze_state）;
此函数的功能是，可以说是有条件的进行广度优先搜索，即每次搜索四个方向中的一个方向时，都要利用第一个类中的CanArrive函数判断是否能从人的当前位置移动到推箱子的位置，并记录最短的路径，并保证箱子前面不是墙，AllWay是用于存储有条件的广度优先搜索中所搜索到的位置，AllWay[i]是用来存储从开始走i个格子的所有被搜索到的位置，man_way是用来存储人走过的所有的路径，man_way[i]存储走过的某条路径所经过的点的位置；
maze_state用来存储搜索过程中所更新的所有的地图的状态；
voidRecordBestWay（vector<
bestWay,
&
man_way,
man_bestway）;
此函数是根据AllWay的数据往回进行回溯法找到箱子可以移动的最短的路径，同理，man_bestway是根据man_way来找到人整个过程中所走过的最短的路径；
（4）、界面及图形的绘制
此软件的界面设计主要是利用Easyx中的函数进行绘画的，游戏的主界面以及一些按钮时利用绘图函数实现的，并且根据所画按钮的坐标范围，来控制鼠标，从而来实现界面中按钮的控制，游戏过程中的箱子、墙、人均是利用函数所插入的图片，移动的时候，在不同的位置插入不同的图片来显示动态的过程；
插入图片的函数
loadimage（&
img[0],_T（"
F:
\\VS\\test\\pushbox\\s.jpg"
））;
loadimage（&
img[1],_T（"
\\VS\\test\\pushbox\\w.jpg"
img[2],_T（"
\\VS\\test\\pushbox\\m.jpg"
img[3],_T（"
\\VS\\test\\pushbox\\b.jpg"
img[4],_T（"
\\VS\\test\\pushbox\\d.jpg"
img[5],_T（"
\\VS\\test\\pushbox\\bd.jpg"
绘制按钮：
ellipse（580,440,740,490）;
//画椭圆
RECTr2={580,440,740,490};
drawtext（_T（"
游戏说明"
）,&
r2,DT_CENTER|DT_VCENTER|DT_SINGLELINE）;
鼠标的响应：
MOUSEMSGm;
while（true）
{
m=GetMouseMsg（）;
switch（m.uMsg）
{
case（WM_LBUTTONDOWN）:
......
}
（5）地图的获得
constcharWall='
w'
;
//表示墙
constcharSpace='
s'
//表示通道
constcharMan_Start='
m'
//表示人开始时的位置
constcharBox_Start='
b'
//表示箱子初始时的位置
constcharDestination='
d'
//箱子需要到达的目的地
根据这些字符的表示含义，将不同关卡的地图存放在不同的.txt文件中，在进行游戏时，读取文件，在根据坐标插入相应的图片在界面中显示出来，如下：
ifstreaminfile;
infile.open（"
\\VS\\test\\pushbox\\test1.txt"
）;
intR_C[2];
for（inti=0;
i<
2;
i++）
infile>
>
R_C[i];
mymaze->
mrow=R_C[0];
mcol=R_C[1];
（6）、结合数据与界面
根据所搜索到的最短路径的数据，利用坐标，将数据结合图片的动态移动来表示走过的路径。
五、软件使用说明
进入开始的界面后就可以进行游戏了，然后选择关卡，然后开始游戏，利用空格键使人和箱子根据计算好的路径进行移动，如下的游戏相邻的两张时的界面：
六、调试与测试
编写核心算法的代码时，在一个头文件中实现，并进行测试，测试一般还不是利用文件的输入，直接键盘输入，测试成功后，在分几个文件进行管理，继续调试以及测试，有时出现一些自己不能解决的问题的时候，就咨询辅导老师，帮忙解决，程序执行过程中经常出现的错误就是内存的错误，这样边测试变完善代码；
七、工作日志
7月12号：
主要开始进行程序框架的设计；
7月13号：
开始根据网上的一些资料，思索其中的核心算法——广度优先搜索；
7月14号：
开始编写核心算法的代码，并进行调试；
7月15号：
继续调试核心算法的代码，分几个文件管理，并咨询老师帮助解决一些调试中的问题；
7月16号：
开始进行界面的框架设计，即图形的绘制；
7月18号：
在界面中添加一些文字，以及相应一些鼠标操作；
7月19号：
开始在主程序中读取文件，实现最短路径的数据的存储；
7月20号：
根据所得的数据进行联系界面中图片的插入，并调试代码；
7月21号：
开始进行代码的优化，继续调试，并且书写实习报告；
八、综合训练心得与体会
感觉通过这次综合的实习，可以将自己所学到的东西真正的利用到了实践当中，使自己对项目开发有了一个大致的流程，在实际问题中解决问题的能力得以提高，并且通过这次实习提高了我编程的能力，以及调试代码的能力，此外，通过这次的实习，使我学习到了利用Easyx进行绘画以及界面的设计，扩大了自己的知识范围；
九、意见和建议
希望刚开始实习时，能有多点辅导老师，因为我们基本上选的题目刚开始都是一片模糊，不知道其中的意思，需要老师的讲解与开导；
还就是以后有时间可以进行多些这样的综合性的实习，这样可以锻炼我们运用理论知识到实践中的能力。
升级会员 