数据结构与算法_马踏棋盘.doc

合肥学院 计算机科学与技术系 课程设计报告 2012～2013学年第2学期 课程 数据结构与算法 课程设计名称 马踏棋盘 学生姓名 学号 专业班级 指导教师 2013 年6月 目 录 数据结构课程设计报告————马踏棋盘 - 2 - 问题描述 - 2 - 1、问题分析与定义 - 2 - 2、数据结构的选择和概要设计 - 3 - 数据结构的选择 - 3 - 概要设计 - 3 - 3、详细设计和编码 - 4 - 4、上机调试过程 - 6 - 5、测试结果及分析 - 7 - 6、用户使用说明 - 9 - 7、参考文献 - 9 - 附录源程序 - 10 - 数据结构课程设计报告 ————马踏棋盘 题目：【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。 要求将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。 ? 0 1 2 3 4 5 6 7 0 ? ? 8 ? 1 ? ? ? 1 ? 7 ? ? ? 2 ? ? 2 ? ? ? H ? ? ? ? 3 ? 6 ? ? ? 3 ? ? 4 ? ? 5 ? 4 ? ? ? 5 ? ? ? ? ? ? ? ? 6 ? ? ? ? ? ? ? ? 7 ? ? ? ? ? ? ? ? 马所在位置及其出口 算法核心思想：本程序的核心算法是“贪心算法”。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。）…,7。 每次在多个可走位置中选择其中一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。 流程图如下： 4、上机调试过程 （1）、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。 （2）、虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，然后在仔细检查代码，发现没有标记马儿尝试的方向director，这样的话，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。 （3）、标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须控制0到7之间，否则的话马儿就会踏出棋盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。 5、测试结果及分析 输入数据1：根据要求重新输入马的初始位置（9,9），由于输入数据不再要求范围之内,程序要求用户重新输入; 图（1） 输入数据2：根据要求重新输入马的初始位置（1,1），结果如下 图（2） = 图（3） 测试结果 如图（1）所示、当输入马的坐标为（9,9）时，由于该坐标不在8×8的棋盘内，所以程序提示要求重新输入；如图（2）所示，重新输入数据位（1,1）满足棋盘要求，得到在该位置的马踏棋盘的结果。如图（3）所示，当位置选定为（4,4）时的结果。 结果分析：如图（3）所示，以数字递增顺序表示马的下一个出口位置。如图中，1表示初始位置，按照国际象棋中马的走棋规则并选择最优位置，即为2位置；3表示2位置的马的下一个出口位置。以此循环下去，直到数字遍及整个棋盘。 注：马 的走棋路线即为图中白线标记部分（仅标记了前4个位置） 测试数据1:输入马的初始位置(9，9)，由于不符合要求，程序要求重新输入 6、用户使用说明 用户需将源程序清单输入可运行C++的编辑平台，例如vc++, c++ Builder等等，然后进行编译，然后用户根据提示输入马的初始位置，程序会提示所输入马的初始位置必须在1-8之间，否则需要重新输入，直至输入的位置符合要求为止；输入正确之后，程序会输入马儿踏遍整个棋盘的具体执行步骤。 注：