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

《“马踏棋盘”数据结构课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖南商学院计电学院数据结构课程设计目录1.课程设计任务与要求11.1课程设计目的11.2问题描述12.概要设计22.1功能模块化分析22.2系统结构的总体设计22.3处理方式设计33详细设计43.1全局数据结构43.2测试模块43.3输入模块53.4初始化模块63.5棋盘遍历模块64.测试74.1单元测试和集成测试84.2确认测试95.课程设计总结105.1该课程设计的特点105.2存在的不足115.3心得体会11参考文献11附录12湖南商学院计电学院数据结构课程设计《马踏棋盘》数据结构课程设计1.课程设计任务与要求1.1课程设计目的《数据结构》是计算机专业一门重要的

2、专业技术基础课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术。本课程将为整个专业的学习以及软件设计水平的提高打下良好的基础。为了学好《数据结构》，必须掌握编写一些在特定数据结构上的算法，并通过上机调试，更好地掌握各种数据结构及其特点，此次《数据结构》课程设计目的正在于此。经过本次课程设计，我们对于数据结构基本理论和存储结构及算法设计将有更加深入的理解，并提高我们在实际设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力，提高我们的C/C++语言程序设计能力，以及培养学我们编写程序设计文档的能力。

3、1.2问题描述⑴问题说明将马随机放在国际象棋的8*8棋盘Bord[8][8]的某个方格中，马按走棋规则进行移动。马的走棋规则为“日”字，每次可以向8个方向走，若某一方向的落点是马的路径中已经经过的点，则放弃这一方向，即要求每个方格上只进入一次，走遍棋盘上全部64个方格。⑵输入要求由用户指定,可自行指定一个马的初始位置；⑶输出要求马的行走路线，即根据马对棋盘上每个格子的访问顺序，输出该序号；⑷具体要求根据题目描述编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。第15页共15页湖南商学院计电学院数据结构课程设计

4、2.概要设计2.1功能模块化分析通过对问题描述的分析，可知马踏棋盘问题所要求实现的功能大致由三个部分组成：⑴接收用户输入的马的起始位置；⑵从起始位置开始在棋盘上标记马按问题描述中的行走规则访问棋盘中每个格子的顺序；⑶输出棋盘上标记的访问顺序。2.2系统结构的总体设计根据问题的性质，使用结构化设计方法。结构化设计方法(StructuredDesign,SD)是一种面向数据流的设计方法，是基于模块化、自顶向下、逐层细化、结构化程序设计等程序设计技术基础的设计方式，它需要明确数据处理的类型。根据对问题的分析可知，马踏棋盘问题是属于变换型数据处理问题。因此，可以将整个问题划分

5、为6个大模块。输入模块、初始化模块、棋盘遍历模块、位置测试模块、输出模块、总控模块。⑴输入模块：提示用户输入数据，接收用户输入的数据，即马的起始位置，并判断该位置是否在棋盘内。若该起始位置在棋盘内，则接着执行下一模块的功能；若该起始位置不在棋盘内，则提示用户输入无效，并要求用户再次输入；⑵初始化模块：初始化所有的数据结构中的数据；⑶棋盘遍历模块：采用特定算法，按照马的行走规则对棋盘进行遍历，每次访问一个格子时，要测试该格子是否在棋盘范围内，保存马的访问顺序；⑷位置测试模块：接收格子的x和y坐标，判断该格子是否在棋盘内，然后根据该格子是否在棋盘内返回不同的信号；⑸输出模

6、块：将棋盘遍历模块中保存下来的讯号进行输出，输出格式遵从棋盘格式；⑹总控模块：负责调用个处理模块，完成马踏棋盘问题的求解。马踏棋盘问题的软件结构图如图1。第15页共15页湖南商学院计电学院数据结构课程设计图1马踏棋盘软件结构图2.3处理方式设计针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。⑴深度优先遍历的基本思想深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时侯，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个这样的顶点，可以任意选择一个顶点。凡在实际应用中，选择哪一个邻接的未访问候选顶点主要是由表示图的数

7、据结构决定的。⑵回溯算法的基本思想回溯法是穷举查找技术的一个变种。它每次只构造解的一个分量，然后按照下面的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量进行合法的选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。⑶算法性能分析第15页共15页湖南商学院计电学院数据结构课程设计在马踏棋盘这一实际问题中，我们可以将整个棋盘抽象成一个图，并依据马的在图上的行走规则，构造出一颗解的空间树。