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

《数据结构与算法_马踏棋盘.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计科系数据结构课程设计报告学院计算机科学与技术系课程设计报告2012～2013学年第2学期课程数据结构与算法课程设计名称马踏棋盘学生学号专业班级指导教师-14-计科系数据结构课程设计报告2013年6月目录数据结构课程设计报告————马踏棋盘-2-问题描述-2-1、问题分析与定义-2-2、数据结构的选择和概要设计-3-数据结构的选择-3-概要设计-3-3、详细设计和编码-4-4、上机调试过程-6-5、测试结果及分析-7-6、用户使用说明-9-7、参考文献-9-附录源程序-10--14-计科系数据结构课程设计报告数据结构课程设计报告————马踏棋盘题目：【问题描述】设计一个国际象棋的马踏遍棋盘的演

2、示程序。要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。1、问题分析与定义走棋规则：马走3×2格对角线，简单的说就是走L形棋盘如图所示，将马放在棋盘中的任意一个位置，按照马的走棋规则，我们能够发现，如果没有其他棋子的影响，它最多有8个出口，最少有2个出口。 012345670  8 1   1 7   2  2   H    3 6   3  4  5 4   5        6    

3、    7        马所在位置及其出口算法核心思想：本程序的核心算法是“贪心算法”。-14-计科系数据结构课程设计报告在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。2、数据结

4、构的选择和概要设计数据结构的选择栈：本程序可以利用栈的知识来解决，当然，栈也包括链栈和顺序栈，由于本程序数据有限，并且顺序栈较链栈简单，所以该程序最终选择使用顺序栈来解决。贪心算法：在算法中采用逐步构造最优解。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出就不可再更改。概要设计Ⅰ、主程序模块：voidmain(){定义变量；接受命令；处理命令；退出；}Ⅱ、起始坐标函数模块——马儿在棋盘上的起始位置；Ⅲ、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；Ⅳ、输出路径函数模块——输出马儿行走的路径；流程图如下：主程序模块输入的初始位置是否正确否是起始坐标函数模块探

5、寻路径函数模块-14-计科系数据结构课程设计报告输出路径函数模块块结束3、详细设计和编码下图显示了马位于方格（2，3）时，8个可能的移动位置。一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一012345670811722H373454567(i-2,j+1)、（i-1,j+2）、(i+1,j+2)、(i+2,j+1)(i+2,j-1)、(i+1,j-2)、(i-1,j-2)、(i-2,j-1)但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘围，成为不允许的位置。8个可能位置可以用两个一维数组Htry1[0..7]和Htry2[0..7]来表示：01234567Htry1

6、-2-11221-1-201234567Htry21221-1-2-2-1-14-计科系数据结构课程设计报告位于(i,j)的马可以走到的新位置是在棋盘围的(i+Htry[h],j+Htry2[h]),其中h=0,1,2,…,7。每次在多个可走位置中选择其中一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。流程图如下：-14-计科系数据结构课程设计报告开始Inti、ji=0i

7、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。（2）、虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，然后在仔细检查代码，