马踏棋盘 正式作业

1、 数据结构与算法分析 课程设计报告设计题目:马踏棋盘专 业 计算机科学与技术 学 号姓 名年 月 日<<马踏棋盘 >>数据结构课程设计概要设计功能模块化分析通过对问题描述的分析, 可知马踏棋盘问题所要求实现的功能大致由三个部 分组成:接收用户输入的马的起始位置;从起始位置开始在棋盘上标记马按问题描述中的行走规则访问棋盘中每 个格子的顺序;输出棋盘上标记的访问顺序。系统结构的总体设计输入模块:提示用户输入数据,接收用户输入的数据,即马的起始位置, 并判断该位置是否在棋盘内。 若该起始位置在棋盘内, 则接着执行下一模块的功 能;若该起始位置不在棋盘内,则提示用户输入无效,并

2、要求用户再次输入; 初始化模块:初始化所有的数据结构中的数据;棋盘遍历模块:采用特定算法, 按照马的行走规则对棋盘进行遍历, 每次 访问一个格子时,要测试该格子是否在棋盘范围内,保存马的访问顺序; 位置测试模块:接收格子的 x 和 y 坐标, 判断该格子是否在棋盘内, 然后 根据该格子是否在棋盘内返回不同的信号;输出模块:将棋盘遍历模块中保存下来的讯号进行输出, 输出格式遵从棋盘格式;总控模块:负责调用个处理模块,完成马踏棋盘问题的求解。处理方式设计针对问题和核心模块,采用深度优先遍历思想和回溯算法的非递归形式。 深度优先遍历的基本思想深度优先遍历可以从任意顶点开始访问图的顶点, 然后把该顶点

3、标记为已访 问。 在每次迭代的时侯, 该算法紧接着处理与当前顶点邻接的未访问顶点。 如果 有若干个这样的顶点, 可以任意选择一个顶点。 凡在实际应用中, 选择哪一个邻 接的未访问候选顶点主要是由表示图的数据结构决定的。回溯算法的基本思想回溯法是穷举查找技术的一个变种。 它每次只构造解的一个分量, 然后按照 下面的方法来评估这个部分构造解。 如果一个部分构造解可以进一步构造而不会 违反问题的约束, 我们就接受对解的下一个分量所做的第一个合法选择。 如果无 法对下一分量进行合法的选择, 就不必对剩下的任何分量再做任何选择了。 在这 种情况下, 该算法进行回溯, 把部分构造解的最后一个分量替换为它的

4、下一个选 择。详细设计详细设计的主要任务是根据概要设计对每个模块的定义进行设计, 以实现 其功能算法和外部接口所要求的模块内部的数据结构和程序的逻辑结构。 详细设计的目标有两个:实现模块功能的算法要逻辑上正确和算法描 述要简明易懂。设计主要采用的工具是程序流程图。全局数据结构 dx 和 dy :两个长度为 8的一维数组,分别存储马 8个选择的方向的 x 位移(即行位移和 y 位移(即列位移 ; st_chess:这是一个结构体, 该结构体内有标记棋盘上该位置是否被访问 过的 visited 整型变量,存储马的访问次序的 route 整型变量,马在访问该位置 时的前驱位置的 x 坐标的 prex

5、 整型变量,马在访问该位置时的前驱位置的 y 坐 标的 prey 整型变量,马下次回溯到该位置时应该从哪个方向开始试探的 direction 变量。 并生成该结构体的一个实例 chess1010, 存储棋盘上的各种 标记信息。 startx 和 starty :这是两个整型变量,表示起始位置的 x 坐标和 y 坐标, 用于接收和存放用户输入的数据。测试模块接口:接收上级模块传送的两个整型变量 x 和 y ;核心函数:test(;测试模块的程序流程图如图所示。 输入模块接口:不接受任何数据;数据结构:使用已经定义的全局整型变量 startx 和 starty ; 核心函数:start_pos(;

6、输入模块的程序流程图如图所示。 初始化模块接口:不接受任何数据;核心函数:init(;操作:将全局数据结构 chess 中的所有标记信息均标记为 0。 棋盘遍历模块接口:不接受任何数据;核心函数：horse_chess(； 棋盘遍历模块的程序流程图如图所示。 开始 num = 64; cnt = 1; x= startx;y = starty; num != 0 i = chessxxyy. Direction; xx = x + dxi; yy = y + dyi; i+; test(xx,yy, = 1 and chessxxyy.visited = 0; T x = xx; y = yy

7、; num-; i<8 F a=chessxy.prex; b=chessxy.prey; x=a; y=b; F T 结束 确认测试 测试用例设计： 输入数据 (8,8 预期输出 “输入无效！请重新输入！” 01 64 60 34 03 36 19 22 61 54 02 37 20 23 04 17 63 59 33 47 35 18 21 10 53 48 38 58 24 11 16 05 (0,0 62 32 46 49 39 26 09 12 55 52 57 25 43 15 06 27 31 45 50 40 29 08 13 42 51 56 30 44 14 41 2

8、8 07 64 61 47 42 37 15 02 11 48 43 38 45 40 12 17 14 60 46 41 36 16 01 10 03 57 49 44 39 34 18 13 08 62 59 35 30 51 09 04 19 54 55 50 33 28 22 07 24 58 63 29 52 31 25 20 05 56 53 32 27 21 06 23 26 (2,5 测试结果：经过测试，实际结果符合预期结果。 、 算法性能分析 在马踏棋盘这一实际问题中，可以将整个棋盘抽象成一个图，并依据马的在 图上的行走规则，构造出一颗解的空间树。这颗空间树以马的起始位置为根

9、，它 将有 8 颗子树分别对应着从这一点出发，马走一步可能到达的位置，然后对这颗 树用深度优先遍历的思想进行遍历，可以得到马对棋盘的访问顺序。根据问题描 述的规则，由于该棋盘上每一个格子都会被访问，且仅被访问一次，因此该算法 的时间效率为 n*n 级，其中 n 为棋盘一列（或一行）的格子数；在该算法中， 需要对整个棋盘的每一个格子进行标记，需要使用多个 n*n 的二维数组，因此 该算法的空间效率也是 n*n 级的。 课程设计总结 本次课程设计是围绕数据结构进行。 根据问题描述可知， 需要解决问题并不复杂， 整个问题只需要实现一个功能， 那就是输出马按特定规则在棋盘上的遍历顺序。但是，为了实现该

10、单一功能，却 需要优秀的算法和数据结构以保证实现的时间和空间效率。 由于所有的操作都是 在棋盘上进行，因此，我们理所当然会想到将整个棋盘抽象成一个数据结构 二维数组， 但是一个二维数组不足以存储马的遍历过程需要保存的诸如访问标 记、前驱访问节点等等信息，因此我采用了一个结构体，结构体设置几个简单的 整型变量来保存各种信息。基本的数据结构设计好后，我们还需要基于该数据结 构的好的算法来实现。之前，我使用了广度优先搜索对马的路径进行搜索，但由 于输出结果依然难以辨认马的行走路径，因此，我改换成深度优先搜索和回溯法 来寻找马的路径，将回溯是需要的信息保存在棋盘的数据结构中，这就相当于， 用深度搜索遍历一个由马的行走路径所构成的一颗解的空间树， 马的行走路径实 际上就是从这颗解空间树的根节点到叶子节点过程中经过的所有节点所组成的 路径。 心得体会 经过这次数据结构课程设计，我们不仅及时巩固的了数据结构、算法、以 及软件工程的知识， 并对数据结构和算法的配合对于程序时间和空间性能的影响 以及软件工程提供的开发流程和工具对于实现特定功能程序的重要意义。 当我们面对一个实际问题，应该迅速根据问题性质和特点抽象成特定的数 据结构，当然每个问题都有可能能够抽象成多种数据结构，每种数据结构适应于 不同的算法，例如，马踏棋盘问题就可