数据结构实习报告-国际象棋中马及遍历.doc

数据结构与VC编程实习实习报告 学生姓名：学 号：专业班级：指导教师：2012年7月14日实习题目在国际象棋棋盘上实现马的遍历一、任务描述及要求国际象棋的棋盘有8864个格子，给它们规定坐标（1，1）到（8，8）。马在这64个格子的某一个格子上，它的跳动规则是：如果它现在在（x，y）位置，它下一步可以跳到（x1，y2）或（x2，y1）（所有的“”之间没有相关性）。一般来说它下一步可以有八种跳法，但是它不能跳出这64个格子。设计算法使它不管从哪出发都可以跳遍所有的格子（每个格子只能路过一次）最后回到起点。1.基本要求： 合理设计界面，自行设计国际象棋棋盘，用鼠标选择马的起始位置，起始位置选定后，按“开始”按钮演示马的每一步行走路线。棋盘和马的显示尽量美观逼真。功能菜单或按钮自行设计，以合理为目的。2.扩展要求： 对算法进行优化，根据j.c.Warnsdorff规则设计算法，该规则是在所有可跳的方格中,马只可能走这样一个方格:从该方格出发,马能跳的方格数为最少；如果可跳的方格数相等,则从当前位置看,方格序号小的优先。二、概要设计1抽象数据类型本次实习中，我主要采用图的深度遍历知识和贪心算法来解决在国际象棋棋盘上实现马的遍历问题。棋盘上将64个格子视为64个点，将马从一个格子跳到另一个格子视为一条边，则共有168条边，那么可以将棋盘视为一个无向图，马在棋盘上按c.Warnsdorff规则跳动可视为图的深度遍历过程中的一步。 为了实现图的存储，需要建立顶点顺序表和邻接表，这个过程是在图的构造函数里实现的。图的操作主要包括：给出顶点vertex在表中的位置，给出顶点位置为 v 的第一个邻接顶点的位置，给出顶点v的邻接顶点w的下一个邻接顶点的位置，给出顶点位置为 v 的最优邻接顶点的位置。图的遍历算法是在视图类里面实现的。 图的抽象数据类型为： ADT Graph数据：顶点顺序表关系: 邻接表表示了顶点之间的邻接关系操作： 给出顶点vertex在表中的位置 给出顶点位置为 v 的第一个邻接顶点的位置 给出顶点v的邻接顶点w的下一个邻接顶点的位置 给出顶点位置为 v 的最优邻接顶点的位置由于贪心算法有时不能得到整体最优解，所以我设计了另一种遍历算法。由于要求遍历完所有点后要回到起点，则这是一条哈密顿回路，故可以事先找出这样的一种遍历序列并将其用点数组记录下来，以后在每次遍历时不论从哪个点出发都走这条路线，则一定能回到起点。此种遍历易于理解，下面不再详细介绍。2整个程序包含功能模块及模块间的调用关系 整个程序包含的主要功能模块：更换棋盘颜色，遍历起点的定位（鼠标定位、坐标定位和默认起点），在窗口的状态栏右边可以显示鼠标当前所处的坐标值以协助顶点的定位，棋盘上遍历过程的动态显示（图片（可更换）或路线），遍历顶点序列的打印，两种遍历方式（规则遍历（基于c.Warnsdorff规则的图的深度遍历）和固定遍历（按固定的路线遍历），重新遍历。 模块间的调用关系：每次开始遍历之前可以更换棋盘的颜色、选择遍历过程的动态显示方式和遍历起点，然后选择规则遍历或固定遍历。开始遍历之后可以动态显示遍历过程，并打印遍历的顶点序列。在下一次遍历之前要选择重新遍历，并重新选择起点和遍历方式。实际上整个遍历是在开始动态显示遍历过程之前完成的，在遍历时将遍历序列用一维数组记录下来，遍历完之后利用此数组记录的序列来控制遍历过程的动态显示和遍历顶点序列的打印。三、详细设计1虚拟实现（即数据结构的C+语言描述） 规则遍历中图的抽象数据类型的C+类定义为：class Edge /边结点的定义public: int dest; /边的另一顶点位置，即下标 Edge *link; /下一条边结点的指针public: Edge (int num=-1,Edge *ptr=NULL): dest (num),link (ptr) /构造函数;struct Vertex /顶点的定义 E data; /顶点的名字int numEdge; /此顶点当前关联的可走边数bool ver; /标记此顶点是否被访问过Edge *adj; /边链表的头指针;class Graph /图的类定义public: Vertex *NodeTable; /顶点顺序表 (各边链表的头结点)int numVertices; /顶点个数public: Graph (); /构造函数 Graph();/析构函数int getVertexPos (const E vertx);/给出顶点vertex在表中的位置 int getFirstNeighbor (int v); /给出顶点位置为 v 的第一个邻接顶点的位置 int getNextNeighbor (int v, int w);/给出顶点v的邻接顶点w的下一个邻接/顶点的位置int GetPriNeighbor(int v); /给出顶点位置为 v 的最优邻接顶点的位置; 固定遍历中存储点的数组的定义：CPoint arr64; /存储马的固定行走回路路径，共64步2抽象数据类型中定义的操作算法实现（用伪代码描述）此处只介绍求顶点位置为 v 的最优邻接顶点的位置的函数和图的深度遍历算法的伪代码： int GetPriNeighbor(int v)的伪代码： 若v存在则执行以下操作,否则返回-1；令min=9,w2=-1，w2记录最优邻接点； 令w1为v的第一个邻接顶点的位置；当邻接顶点w1存在时执行以下操作:若 w1未被访问，则转到，否则转到；若min大于w1当前关联的可走边数numEdge则令min= numEdge，令w2=w1；若min等于w1当前关联的可走边数numEdge，如果w2w1则令w2=w1； 令w1为v的邻接顶点w1的下一个邻接顶点的位置，转到； 返回w2；具体实现代码如下：int Graph:GetPriNeighbor(int v) /给出顶点位置为 v 的最优邻接顶点的位置, 如果找不到, 则函数返回-1 if (v != -1)/顶点v存在int min=9,w2=-1; /w2记录最优邻接点 int w1 = getFirstNeighbor (v); /获取第一个邻接顶点的位置while (w1 != -1) /若邻接顶点w存在 if ( !NodeTablew1.ver ) /w1未被访问if(minNodeTablew1.numEdge)min=NodeTablew1.numEdge;/记录v的最优邻接顶点的当前关联的边数 w2=w1; /从该方格出发,马能跳的方格数为最少else if(min=NodeTablew1.numEdge) if(w2w1) w2=w1; /如果可跳的方格数相等,则从当前位置看,方格序号小的优先else w1 = getNextNeighbor (v, w1); /获取下一个邻接顶点return w2; return -1; void DFS(Graph & G,E & v)的伪代码：若开始遍历且起点在棋盘内则令常变量m为起始点v的下标，令loc=m,v=loc；令v的访问标记ver为true；若k=0且k=1 & v=0 & k=64) hk+=v; /标记序号,存储下标G.NodeTablev.numEdge-; /起始点被访问过则将其边数减1 if(k=64) G.NodeTablem.ver=false; /k=64时将起始点标记为未被遍历,以便回到起始点int w = G.getFirstNeighbor (v); /获取第一个邻接顶点的位置while (w != -1) /若邻接顶点w存在 /if ( !G.NodeTablew.ver ) /w未被访问G.NodeTablew.numEdge-; /顶点各邻接点的边数都应减1w = G.getNextNeighbor (v, w); /获取下一个邻接顶点int pw=G.GetPriNeighbor(v); /给出顶点位置为 v 的最优邻接顶点的位置, 如果找不到, 则函数返回-1if(pw!=-1) dfs(G,pw,m); /若最优邻接顶点存在, 递归访问顶点pw3函数之间的调用关系 运行程序后调用视图类的OnDraw()函数在窗口中绘制棋盘。 在菜单栏的“操作”中点击“黄绿相间” 、“黑白相间” 、“恢复默认”菜单后分别调用视图类的OnMenuitemby()、OnMenuitembw()、OnSyschMenuitem()函数，在此函数中调用了Invalidate()函数，它自动调用OnDraw函数重新绘制窗口。 点击“图片” 、“路线”菜单后分别调用视图类的OnMaMenuitem()、OnRouteMenuitem()函数。 点击“更换图片”菜单调用视图类的OnDialog3()函数以弹出对话框，在对话框上点击单选按钮选择图片后，若点击“确定”按钮调用Dialog3类的OnOk3Button()函数，若点击“缺省设置”按钮则调用Dialog3类的OnPicsysButton()函数。 点击“鼠标定位”、“坐标定位”菜单后分别调用视图类的OnMouselocation()、OnMenuitemsys()函数，点击“坐标定位” 后弹出OnDialog2()对话框，设置起点后，若点击对话框上的“确定”“按钮后调用OnDialog2()类的OnOk2Button() 函数，在此函数中调用了UpdateData(TRUE)函数以刷新控件的值到对应的变量，若点击“缺省值”按钮则调用OnDialog2()类的OnSysButton()函数 关闭对话框后调用视图类的OnDialog2()函数。 点击“规则遍历”菜单或工具栏中的“J”图标后调用视图类的OnMenuitemstart()函数，此函数中调用了Graph类的构造函数Graph ()来建立图，也调用了视图类的图的深度遍历函数DFS()和显示图片或路线和遍历序列listnumber()函数。在DFS()中调用了Graph类的getVertexPos()和视图类的dfs ()函数，在dfs ()中又调用了Graph类的getFirstNeighbor()、getNextNeighbor ()、GetPriNeighbor()函数，也调用了它本身来形成深度遍历，也用到了遍历序列存储数组h65。在listnumber()中调用了视图类的picture()和route()函数和延时函数Sleep()，用以动态显示遍历过程，之后打印顶点的遍历序列并提示遍历成功与否。 点击“固定遍历”菜单或工具栏中的“S”图标后调用视图类的OnSolidMenuitem()和listnumber()函数, 也用到了存储固定路径的点数组arr64和遍历序列存储数组h65。 点击“重新遍历”菜单或工具栏中的“T”图标后视图类的OnStopMenuitem()函数，在此函数中对遍历序列存储数组h65和全局变量进行了初始化，也调用了Invalidate()函数，它自动调用OnDraw函数重新绘制窗口。 四、调试分析1程序在调试过程中出现的问题及解决方法我个人认为我在写程序之前时考虑得比较仔细，所以需要调试的地方比较少。以下是我在调试过程中出现的问题及解决方法： 实习期间的前几天我一直认为利用c.Warnsdorff规则设计出的图的深度遍历算法自己设计出算法后，通过窗口右侧显示的遍历序列发现算法不正确。为了解决这个问题，我先仔细得把程序读了几遍，觉得算法设计得不缜密，尤其是对当前遍历点和其邻接点的边数减少问题的考虑和对获取最优邻接点的函数的设计。经过改进后，还是不能得到理想的结果。于是我认为还是算法设计得有问题，所以我对程序进行了调试。经过反复地调试和改进，我觉得算法没有问题了，可是对于某些起始点遍历结果还是不正确。于是我开始怀疑利用c.Warnsdorff规则设计出的算法是不是一定能遍历到所有点并回到起点。在网上查询资料并与老师交流后发现自己前期的想法是错误的，实际上利用c.Warnsdorff规则在大多数情况下能够实现遍历，但并不能确保成功。经过再次深究自己设计的算法，我认为算法是正确的。 与老师探讨自己设计的算法后，老师要求我重新设计一种算法使得从任何一个点出发都可以遍历到所有点并回到起点，即利用事先已知的固定路线来遍历。在这个算法的设计过程中，也出现了遍历序列不正确的问题，序列的前一部分正确，后一部分错误。经过调试，发现在存储遍历序列的过程中用来控制点数组元素从arr63转到arr0的变量出了问题，修改之后，问题顺利解决。2算法的时间复杂度分析 图的深度遍历算法的时间复杂度分析：设第i（1=i=64）个点的邻接点个数为Di,图的边数为e。则遍历算法第i个点的各邻接点的边数都减1的循环的时间代价是Di，获取最优邻接顶点的函数的时间代价也是Di，故深度遍历算法的总时间代价为2(D1+D2+D63+D64+Dj)=2 O(e)+2Dj，其中Dj是起点的邻接点个数。 固定路线遍历算法的时间复杂度分析：设数组元素个数为n,则遍历算法中for循环、while循环和listnumber()函数的时间复杂度都为O(n),故固定路线遍历算法的时间复杂度为O(n)。五、测试结果根据一组提供的测试数据得到什么样的结果？ 图的深度遍历算法的测试数据为：坐标值（7，8） 遍历序列：63，48，31，16，6，12，2，17，11，1，18，3，9，26，41，58，52，62，56，46，40，55，61，51，57，42，25，10，4，14，8，23，13，7，24，39，29，19，34，49，59，44，27，33，50，35，20，5，15，21，36，30，45，60，54，64，47，32，22，37，43，28，38，53，63遍历结果正确！ 固定路线遍历算法的测试数据为：坐标值（1，4）遍历序列：25，10，4，14，8，23，6，16，31，48，63，53，59，49，34，17，2，12，29，19，9，3，13，7，24，39，56，62，47，64，54，60，50，33，18，1，11，5，15，32，22，28，38，21，27，44，61，55，40，46，52，37，43，58，41，26，20，35，45，30，36，51，57，42，25遍历结果正确！六、心得体会为期九天的数据结构实习，感觉比平常的一个月都要漫长。这不仅仅是因为在考完试后的这九天中我依然早起晚睡，每天的工作量不亚于考前复习每天的工作量，每天对着电脑思考一些复杂的问题，更重要的是因为这九天我坚持下来了，学到了很多知识，锤炼了自己多方面的能力，增强了自己的毅力和信心，为以后的学习和工作奠定了很好的基础。实习前我并没有做充分的准备，实习开始时老师只说了相关事项，并没有说怎么去做。所以，一切工作都得靠自己，自己利用网络和书籍去解决编程中遇到的问题，请教老师和同学也是很好的一种解决问题的方式，此时我才体会到了“书到用时方恨少”的含义。实习前期主要是对题目加以分析，设计实习作品的预期效果，查找资料并学习相关知识。由于缺乏独立解决问题的经验，以前接触的很少，所以这个阶段感觉比较费力。由于时间有限，所以实习中期知识基本上都是现学现用，而且还得自己设计算法解决相关问题。然而自己设计的算法并不一定正确，需要反复改进并反复测试，经过多次修改后结果还不正确时，自己会感到很失望，并且会动摇自己的信心，甚至想放弃。更令人头疼的是编程过程中会遇到很多错误，有时需要查阅相关资料，有时需要调试程序，所以这个阶段感觉相当费力，当然这个阶段多与老师和同学沟通是非常有必要的，在沟通中常常会有意想不到的收获。但当每一个问题得到解决时，都会令自己信心大增，都会展现出最灿烂的笑容，吃饭都觉得胃口好，睡觉也睡得安稳，于是更加坚定地接着做下去。实习后期主要是对程序进行优化，添加一些功能，验收程序并撰写实习报告。实习期间一次次的失望对自己是一个很大的考验，但一次次的看到希望对自己则是莫大的肯定。当自己独立完成整个作品时，再回首整个实习期间遇到的问题和经受的苦难，感觉那也不算什么，并且觉得自己的付出是非常值得的，因为这是大学期间乃至整个人生中的一笔宝贵的财富。指导教师评语及成绩姓名学号评价项目评 价 内 容得 分（百分制）平时表现(30%)学习、工作态度(30%)纪律性(30%)综合运用知识能力(40%)实习成果(70%)开题报告书写水平(15%)实习总结报告书写水平(15%)成果(70%)总分评语：指导教师（签名）：年 月 日