《推箱子的最短路径-数据结构与C语言综合训练报告》由会员分享，可在线阅读，更多相关《推箱子的最短路径-数据结构与C语言综合训练报告（10页珍藏版）》请在金锄头文库上搜索。
1、数据结构与C语言综合训练实习报告信息工程学院数据结构与C语言综合训练报告 （20122013学年第 二学期）报告题目：_推箱子的最短路径_ _ 姓 名：_ _ _ 专 业： 软件工程 年级班级：_2012级2班_ 指导教师： 完成日期： 2013年7月21号 一、综合训练目的和要求本综合训练是计算机科学与技术、信息管理与信息系统、软件工程、电子商务专业重要的实践性环节之一，是在学生学习完程序设计语言(C)、数据结构课程后进行的一次全面的综合练习。本课综合训练的目的和任务：1. 巩固和加深学生对C语言、数据结构课程的基本知识的理解和掌握2. 掌握C语言编程和程序调试的基本技能3. 利用C语言进行
2、基本的软件设计4. 掌握书写程序设计说明文档的能力5. 提高运用C语言、数据结构解决实际问题的能力二、综合训练任务内容1.题目要求：推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个55的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.同时，房间里头还有若干障碍物（用阴影部分表示）。现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.2. 扩展实现的内容：绘制图形界面，通过按钮实现
3、推箱子的整个过程，整个过程中可以动态的看到箱子的移动。游戏界面如下图：游戏动态移动的过程图如下：三、总体设计所用算法主要是根据广度优先搜索，纪录路径，然后利用回溯法实现最短路径的查找并纪录保存下来。所用的数据结构主要为顺序结构。返回开始界面进行游戏开 始开始进入游戏界面进行选择选择游戏开始，进行游戏选择游戏说明，了解游戏规则选择关卡，或者返回游戏开始关卡（1）关卡（2）关卡（3）按空格键进行游戏返回游戏开始后，可以单机鼠标右键退出游戏返回游戏开始，单机鼠标右键可以退出游戏四、详细设计说明1、推箱子游戏具有的功能（1）能够显示主菜单和界面游戏需要提供主菜单进行选择，同时能够把地图文件中的信息转换
4、成为图像显示到游戏界面上。（2）能够实现键盘操作功能能够接收到空格键信息，按照软件内部实现的箱子移动到相应的位置。（3） 能够进行关卡选择功能进入开始游戏的界面时，可以进行游戏的关卡的选择，然后利用空格键进行箱子的移动。（4） 提供游戏说明功能进入游戏说明界面时，可以了解游戏的一些规则，及如何进行游戏。2、 程序结构设计运用C+语言，以及VS2010开发环境（1）、typedef struct Pnode int row; int col;int weight;struct Pnode* back_man;Pnode, * Position;某一点的坐标表示，当用来实现箱子的最短路径的搜索时，
5、back_man 用来存储箱子移动一个位置后，人所在的位置。（2）、typedef struct Mnode int mrow; int mcol; char mazeMAX_ROWMAX_COL;MNode, *MazeType;用来存储地图的信息 （3） 、算法的实现主要有两个类，第一个类是class ShortestPath ；第二个类是class ManBoxStep: public ShortestPath ；A、第一个类class ShortestPath 是用来实现地图中任意两点之间的最短路径，成员函数及其功能如下：Position NextPosition(Position &
6、curpos, int di);用来计算当前点在四个方向下的移动一格得到的下一点的坐标位置，并返回；bool CanArrive( vector list &vec);数据成员有start，end，此函数是判断在地图中能否从 start 到 end ，并利用广度优先搜索搜索从start 到end 的路径，并把所有搜索过的位置全部记录在顺序容器 vec 中，veci 表示存储一系列与start 位置相距i 个格子的被搜索的点的位置；void RecordWay( vector list &vec, vector &way);此函数根据 vec 中所存储的数据，利用回溯法进行往回搜索，找到从 st
7、art 到 end 的最短路径， 并把路径存到容器 way 中；B、第二个类class ManBoxStep 是利用第一个类中的函数实现人和箱子一起从起点到箱子应到的位置的最短路径，其中的成员函数及其功能如下：Position NextState(Position box, int di);此函数的功能是纪录当人能够移动箱子的情况下，纪录移动后箱子和人的位置；MazeType UpdateMaze(MazeType mymaze, Position curpos, Position newpos);此函数的功能是每当在搜索下一步时，及时的更新所在的地图（即改变人和箱子的位置），并每次都将地图纪
8、录下来；bool BFSCanArrive( vector list &AllWay, vector vector &man_way, vector &maze_state);此函数的功能是，可以说是有条件的进行广度优先搜索，即每次搜索四个方向中的一个方向时，都要利用第一个类中的 CanArrive 函数判断是否能从人的当前位置移动到推箱子的位置，并记录最短的路径，并保证箱子前面不是墙，AllWay 是用于存储有条件的广度优先搜索中所搜索到的位置，AllWay i 是用来存储从开始走i 个格子的所有被搜索到的位置，man_way 是用来存储人走过的所有的路径，man_wayi 存储走过的某条路
9、径所经过的点的位置；maze_state 用来存储搜索过程中所更新的所有的地图的状态；void RecordBestWay( vector list &AllWay, vector &bestWay, vector vector &man_way,vector &man_bestway);此函数是根据 AllWay 的数据往回进行回溯法找到箱子可以移动的最短的路径，同理，man_bestway 是根据 man_way 来找到人整个过程中所走过的最短的路径；（4） 、界面及图形的绘制此软件的界面设计主要是利用 Easyx 中的函数进行绘画的，游戏的主界面以及一些按钮时利用绘图函数实现的，并且根据
10、所画按钮的坐标范围，来控制鼠标，从而来实现界面中按钮的控制，游戏过程中的箱子、墙、人均是利用函数所插入的图片，移动的时候，在不同的位置插入不同的图片来显示动态的过程；插入图片的函数loadimage(&img0, _T(F:VStestpushboxs.jpg);loadimage(&img1, _T(F:VStestpushboxw.jpg);loadimage(&img2, _T(F:VStestpushboxm.jpg);loadimage(&img3, _T(F:VStestpushboxb.jpg);loadimage(&img4, _T(F:VStestpushboxd.jpg);
11、loadimage(&img5, _T(F:VStestpushboxbd.jpg);绘制按钮：ellipse(580,440,740,490);/画椭圆RECT r2 = 580,440,740,490;drawtext(_T(游戏说明), &r2, DT_CENTER | DT_VCENTER | DT_SINGLELINE);鼠标的响应：MOUSEMSG m;while(true)m = GetMouseMsg();switch(m.uMsg)case(WM_LBUTTONDOWN):.(5) 地图的获得const char Wall = w;/表示墙const char Space =
12、 s;/表示通道const char Man_Start = m;/表示人开始时的位置const char Box_Start = b;/表示箱子初始时的位置const char Destination = d;/箱子需要到达的目的地根据这些字符的表示含义，将不同关卡的地图存放在不同的 .txt 文件中，在进行游戏时，读取文件，在根据坐标插入相应的图片在界面中显示出来，如下：ifstream infile;infile.open(F:VStestpushboxtest1.txt);int R_C2;for(int i = 0; i R_Ci;mymaze-mrow = R_C0;mymaze-
13、mcol = R_C1;（6） 、结合数据与界面根据所搜索到的最短路径的数据，利用坐标，将数据结合图片的动态移动来表示走过的路径。五、软件使用说明进入开始的界面后就可以进行游戏了，然后选择关卡，然后开始游戏，利用空格键使人和箱子根据计算好的路径进行移动，如下的游戏相邻的两张时的界面：六、 调试与测试编写核心算法的代码时，在一个头文件中实现，并进行测试，测试一般还不是利用文件的输入，直接键盘输入，测试成功后，在分几个文件进行管理，继续调试以及测试，有时出现一些自己不能解决的问题的时候，就咨询辅导老师，帮忙解决，程序执行过程中经常出现的错误就是内存的错误，这样边测试变完善代码；七、 工作日志7月12号 ：主要开始进行程序框架的设计；7月13号 ：开始根据网上的一些资料，思索其中的核心算法广度优先搜 索；7月14号 ：开始编写核心算法的代码，并进行调试；7月15号 ：继续调试核心算法的代码，分几个文件管理，并咨询老师帮助解 决一些调试中的问题；7月16号 ：开始进行界面的框架设计，即图形的绘制；7月18号 ：在界面中添加一些文字，以及相应一些鼠标操作；7月19号 ：开始在主程序中读取文件，实现最短路径的数
