数据结构实习报告——国际象棋中马的遍历

《数据结构实习报告——国际象棋中马的遍历》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与VC编程实习实习报告学生姓名：学号：专业班级：指导教师：2012年7月14日实习题目在国际象棋棋盘上实现马的遍历一、任务描述及要求国际象棋的棋盘有8×8＝64个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可以跳到（x±1，y±2）或（x±2，y±1）（所有的“±”之间没有相关性）。一般来说它下一步可以有八种跳法，但是它不能跳出这64个格子。设计算法使它不管从哪出发都可以跳遍所有的格子（每个格子只能路过一次）最后回到起点。1.基本要求：合理设计界面，自行设计国际象棋

2、棋盘，用鼠标选择马的起始位置，起始位置选定后，按“开始”按钮演示马的每一步行走路线。棋盘和马的显示尽量美观逼真。功能菜单或按钮自行设计，以合理为目的。2.扩展要求：对算法进行优化，根据j.c.Warnsdorff规则设计算法，该规则是在所有可跳的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数为最少；如果可跳的方格数相等,则从当前位置看,方格序号小的优先。二、概要设计1．抽象数据类型本次实习中，我主要采用图的深度遍历知识和贪心算法来解决在国际象棋棋盘上实现马的遍历问题。棋盘上将64个格子视为64个点，将马从一个格子跳到另一个格子视为一条边，则共

3、有168条边，那么可以将棋盘视为一个无向图，马在棋盘上按c.Warnsdorff规则跳动可视为图的深度遍历过程中的一步。为了实现图的存储，需要建立顶点顺序表和邻接表，这个过程是在图的构造函数里实现的。图的操作主要包括：给出顶点vertex在表中的位置，给出顶点位置为v的第一个邻接顶点的位置，给出顶点v的邻接顶点w的下一个邻接顶点的位置，给出顶点位置为v的最优邻接顶点的位置。图的遍历算法是在视图类里面实现的。图的抽象数据类型为：ADTGraph{数据：顶点顺序表关系:邻接表表示了顶点之间的邻接关系操作：①给出顶点vertex在表中的位置②给出顶点位置为v的第

4、一个邻接顶点的位置③给出顶点v的邻接顶点w的下一个邻接顶点的位置④给出顶点位置为v的最优邻接顶点的位置}由于贪心算法有时不能得到整体最优解，所以我设计了另一种遍历算法。由于要求遍历完所有点后要回到起点，则这是一条哈密顿回路，故可以事先找出这样的一种遍历序列并将其用点数组记录下来，以后在每次遍历时不论从哪个点出发都走这条路线，则一定能回到起点。此种遍历易于理解，下面不再详细介绍。2．整个程序包含功能模块及模块间的调用关系⑴整个程序包含的主要功能模块：更换棋盘颜色，遍历起点的定位（鼠标定位、坐标定位和默认起点），在窗口的状态栏右边可以显示鼠标当前所处的坐标值以

5、协助顶点的定位，棋盘上遍历过程的动态显示（图片（可更换）或路线），遍历顶点序列的打印，两种遍历方式（规则遍历（基于c.Warnsdorff规则的图的深度遍历）和固定遍历（按固定的路线遍历）），重新遍历。⑵模块间的调用关系：每次开始遍历之前可以更换棋盘的颜色、选择遍历过程的动态显示方式和遍历起点，然后选择规则遍历或固定遍历。开始遍历之后可以动态显示遍历过程，并打印遍历的顶点序列。在下一次遍历之前要选择重新遍历，并重新选择起点和遍历方式。实际上整个遍历是在开始动态显示遍历过程之前完成的，在遍历时将遍历序列用一维数组记录下来，遍历完之后利用此数组记录的序列来控制

6、遍历过程的动态显示和遍历顶点序列的打印。三、详细设计1．虚拟实现（即数据结构的C++语言描述）⑴规则遍历中图的抽象数据类型的C++类定义为：classEdge{//边结点的定义public:intdest;//边的另一顶点位置，即下标Edge*link;//下一条边结点的指针public:Edge(intnum=-1,Edge*ptr=NULL):dest(num),link(ptr){}//构造函数};structVertex{//顶点的定义Edata;//顶点的名字intnumEdge;//此顶点当前关联的可走边数boolver;//标记此顶点是否被访

7、问过Edge*adj;//边链表的头指针};classGraph{//图的类定义public:Vertex*NodeTable;//顶点顺序表(各边链表的头结点)intnumVertices;//顶点个数public:Graph();//构造函数~Graph();//析构函数intgetVertexPos(constEvertx);//给出顶点vertex在表中的位置intgetFirstNeighbor(intv);//给出顶点位置为v的第一个邻接顶点的位置intgetNextNeighbor(intv,intw);//给出顶点v的邻接顶点w的下一个邻接

8、//顶点的位置intGetPriNeighbor(intv);//