“马踏棋盘”数据结构课程设计.doc

目录 1. 课程设计任务与要求 1 1.1 课程设计目的 1 1.2 问题描述 1 2. 概要设计 2 2.1 功能模块化分析 2 2.2 系统结构的总体设计 2 2.3 处理方式设计 3 3 详细设计 4 3.1全局数据结构 4 3.2测试模块 4 3.3输入模块 5 3.4初始化模块 6 3.5棋盘遍历模块 6 4. 测试 7 4.1 单元测试和集成测试 8 4.2 确认测试 9 5. 课程设计总结 10 5.1 该课程设计的特点 10 5.2 存在的不足 11 5.3 心得体会 11 参考文献 11 附录 12 《马踏棋盘》数据结构课程设计 1. 课程设计任务与要求 1.1 课程设计目的 《数据结构》是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术。本课程将为整个专业的学习以及软件设计水平的提高打下良好的基础。为了学好《数据结构》，必须掌握编写一些在特定数据结构上的算法，并通过上机调试，更好地掌握各种数据结构及其特点，《数据结构》课程设计。 本课程设计对于数据结构基本理论和存储结构及算法设计有更加深入的理解提高在实际设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力提高的C/C++语言程序设计能力培养学编写程序设计文档的能力。将马随机放在国际象棋的8*8棋盘Bord[8][8]的某个方格中，马按走棋规则进行移动。8个方向走，若某一方向的落点是马的路径中已经经过的点，则放弃这一方向，即要求每个方格上只进入一次，走遍棋盘上全部64个方格。由指定,可自行指定一个马的初始位置编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。Structured Design, SD)是一种面向数据流的设计方法，是基于模块化、自顶向下、逐层细化、结构化程序设计等程序设计技术基础的设计方式，它需要明确数据处理的类型。 根据对问题的分析可知，马踏棋盘问题是属于变换型数据处理问题。因此，可以将整个问题划分为6个大模块。输入模块、初始化模块、棋盘遍历模块、位置测试模块、输出模块、总控模块。 ⑴输入模块：提示用户输入数据，接收用户输入的数据，即马的起始位置，并判断该位置是否在棋盘内。若该起始位置在棋盘内，则接着执行下一模块的功能；若该起始位置不在棋盘内，则提示用户输入无效，并要求用户再次输入； ⑵初始化模块：初始化所有的数据结构中的数据； ⑶棋盘遍历模块：采用特定算法，按照马的行走规则对棋盘进行遍历，每次访问一个格子时，要测试该格子是否在棋盘范围内，保存马的访问顺序； ⑷位置测试模块：接收格子的x和y坐标，判断该格子是否在棋盘内，然后根据该格子是否在棋盘内返回不同的信号； ⑸输出模块：将棋盘遍历模块中保存下来的讯号进行输出，输出格式遵从棋盘格式； ⑹总控模块：负责调用个处理模块，完成马踏棋盘问题的求解。马踏棋盘问题的软件结构图如图1。 图1 马踏棋盘软件结构图 2.3 处理方式设计 针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。 ⑴深度优先遍历的基本思想 深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时侯，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点，可以任意选择一个顶点。凡在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数据结构决定的。 ⑵回溯算法的基本思想 回溯法是穷举查找技术的一个变种。它每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。 ⑶算法性能分析 在马踏棋盘这一实际问题中，我们可以将整个棋盘抽象成一个图，并依据马的在图上的行走规则，构造出一颗解的空间树。这颗空间树以马的起始位置为根，它将有8颗子树分别对应着从这一点出发，马走一步可能到达的位置，当然可以根据该到达位置是否在棋盘上对树进行剪枝。然后对这颗树用深度优先遍历的思想进行遍历，可以得到马对棋盘的访问顺序。根据问题描述的规则，由于该棋盘上每一个格子都会被访问，且仅被访问一次，因此该算法的时间效率为n*n级，其中n为棋盘一列（或一行）的格子数；在该算法中，需要对整个棋盘的每一个格子进行标记，需要使用多个n*n的二维数组，因此该算法的空间效率也是n*n级的。 3 详细设计 详细设计的主要任务是详细设计的目标有两个：实现模块功能的