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

湖南商学院计电学院数据结构课程设计 目录 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 页 共 15 页 马踏棋盘马踏棋盘数据结构课程设计数据结构课程设计 1.1. 课程设计任务与要求课程设计任务与要求 1.11.1 课程设计目的课程设计目的 数据结构是计算机专业一门重要的专业技术基础课程。本课程较系统地介绍 了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查 找和排序技术。本课程将为整个专业的学习以及软件设计水平的提高打下良好的基础。 为了学好数据结构，必须掌握编写一些在特定数据结构上的算法，并通过上机调 试，更好地掌握各种数据结构及其特点，此次数据结构课程设计目的正在于此。 经过本次课程设计，我们对于数据结构基本理论和存储结构及算法设计将有更加 深入的理解，并提高我们在实际设计操作中系统分析、结构确定、算法选择、数学建 模和信息加工的能力，提高我们的 C/C+语言程序设计能力，以及培养学我们编写程 序设计文档的能力。 1.21.2 问题描述问题描述 问题说明 将马随机放在国际象棋的 8*8 棋盘 Bord88的某个方格中，马按走棋规则进行移 动。马的走棋规则为“日”字，每次可以向 8 个方向走，若某一方向的落点是马的路 径中已经经过的点，则放弃这一方向，即要求每个方格上只进入一次，走遍棋盘上全 部 64 个方格。 输入要求 由用户指定,可自行指定一个马的初始位置； 输出要求 马的行走路线，即根据马对棋盘上每个格子的访问顺序，输出该序号； 具体要求 根据题目描述编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数 字 1，2，64 依次填入一个 8*8 的方阵，输出之。 湖南商学院计电学院数据结构课程设计 第 2 页 共 15 页 2.2. 概要设计概要设计 2.12.1 功能模块化分析功能模块化分析 通过对问题描述的分析，可知马踏棋盘问题所要求实现的功能大致由三个部分组 成： 接收用户输入的马的起始位置； 从起始位置开始在棋盘上标记马按问题描述中的行走规则访问棋盘中每个格子 的顺序； 输出棋盘上标记的访问顺序。 2.22.2 系统结构的总体设计系统结构的总体设计 根据问题的性质，使用结构化设计方法。 结构化设计方法(Structured Design, SD)是一种面向数据流的设计方法，是基于模 块化、自顶向下、逐层细化、结构化程序设计等程序设计技术基础的设计方式，它需 要明确数据处理的类型。 根据对问题的分析可知，马踏棋盘问题是属于变换型数据处理问题。因此，可以 将整个问题划分为 6 个大模块。输入模块、初始化模块、棋盘遍历模块、位置测试模 块、输出模块、总控模块。 输入模块：提示用户输入数据，接收用户输入的数据，即马的起始位置，并判 断该位置是否在棋盘内。若该起始位置在棋盘内，则接着执行下一模块的功能；若该 起始位置不在棋盘内，则提示用户输入无效，并要求用户再次输入； 初始化模块：初始化所有的数据结构中的数据； 棋盘遍历模块：采用特定算法，按照马的行走规则对棋盘进行遍历，每次访问 一个格子时，要测试该格子是否在棋盘范围内，保存马的访问顺序； 位置测试模块：接收格子的 x 和 y 坐标，判断该格子是否在棋盘内，然后根据 该格子是否在棋盘内返回不同的信号； 输出模块：将棋盘遍历模块中保存下来的讯号进行输出，输出格式遵从棋盘格 式； 湖南商学院计电学院数据结构课程设计 第 3 页 共 15 页 总控模块：负责调用个处理模块，完成马踏棋盘问题的求解。马踏棋盘问题的 软件结构图如图 1。 总控模块 输入模块 棋盘遍历 模块 输出模块 测试模块 图 1 马踏棋盘软件结构图 2.32.3 处理方式设计处理方式设计 针对问题和核心模块，采用深度优先遍历思想和回溯算法的非递归形式。 深度优先遍历的基本思想 深度优先遍历可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。 在每次迭代的时侯，该算法紧接着处理与当前顶点邻接的未访问顶点。如果有若干个 这样的顶点，可以任意选择一个顶点。凡在实际应用中，选择哪一个邻接的未访问候 选顶点主要是由表示图的数据结构决定的。 回溯算法的基本思想 回溯法是穷举查找技术的一个变种。它每次只构造解的一个分量，然后按照下面 的方法来评估这个部分构造解。如果一个部分构造解可以进一步构造而不会违反问题 的约束，我们就接受对解的下一个分量所做的第一个合法选择。如果无法对下一分量 进行合法的选择，就不必对剩下的任何分量再做任何选择了。在这种情况下，该算法 进行回溯，把部分构造解的最后一个分量替换为它的下一个选择。 算法性能分析 在马踏棋盘这一实际问题中，我们可以将整个棋盘抽象成一个图，并依据马的在 图上的行走规则，构造出一颗解的空间树。这颗空间树以马的起始位置为根，它将有 湖南商学院计电学院数据结构课程设计 第 4 页 共 15 页 8 颗子树分别对应着从这一点出发，马走一步可能到达的位置，当然可以根据该到达位 置是否在棋盘上对树进行剪枝。然后对这颗树用深度优先遍历的思想进行遍历，可以 得到马对棋盘的访问顺序。根据问题描述的规则，由于该棋盘上每一个格子都会被访 问，且仅被访问一次，因此该算法的时间效率为 n*n 级，其中 n 为棋盘一列（或一行） 的格子数；在该算法中，需要对整个棋盘的每一个格子进行标记，需要使用多个 n*n 的二维数组，因此该算法的空间效率也是 n*n 级的。 3 3 详细设计详细设计 详细设计的主要任务是 根据概要设计对每个模块的定义进行设计，以实现其功能 算法和外部接口所要求的模块内部的数据结构和程序的逻辑结构。 详细设计的目标有两个：实现模块功能的算法要逻辑上正确和算法描述要简明 易懂。 传统软件开发方法的详细设计主要是用结构化程序设计法。详细设计的表示工 具有图形工具和语言工具。图形工具有程序流程图、PAD（Problem Analysis Diagram）图、NS（由 Nassi 和 Shneidermen 开发，简称 NS）图。语言工具有伪 码和 PDL（Program Design Language）等。本次设计主要采用的工具是程序流程图。 3.13.1 全局数据结构全局数据结构 dx和 dy：两个长度为 8 的一维数组，分别存储马 8 个选择的方向的 x 位移 （即行位移）和 y 位移（即列位移） ； st_chess：这是一个结构体，该结构体内有标记棋盘上该位置是否被访问过的 visited 整型变量，存储马的访问次序的 route 整型变量，马在访问该位置时的前驱位置 的 x 坐标的 prex 整型变量，马在访问该位置时的前驱位置的 y 坐标的 prey 整型变量， 马下次回溯到该位置时应该从哪个方向开始试探的 direction 变量。并生成该结构体的 一个实例 chess1010，存储棋盘上的各种标记信息。 startx 和 starty：这是两个整型变量，表示起始位置的 x 坐标和 y 坐标，用于接收 和存放用户输入的数据。 湖南商学院计电学院数据结构课程设计 第 5 页 共 15 页 3.23.2 测试模块测试模块 接口：接收上级模块传送的两个整型变量 x 和 y； 核心函数：test()； 测试模块的程序流程图如图 2 所示。 开始 读入x，y x = 0 and x = 0 and y 8 返回1返回2 结束 T F 图 2 测试模块程序流程图 3.33.3 输入模块输入模块 接口：不接受任何数据； 数据结构：使用已经定义的全局整型变量 startx 和 starty； 核心函数：start_pos()； 输入模块的程序流程图如图 3 所示。 湖南商学院计电学院数据结构课程设计 第 6 页 共 15 页 开始 提示并输入 chx,chy 调用测试 模块 返回1 提示用户输 入无效 结束 F T startx=chx-0; starty=chy-0; 图 3 输入模块程序流程图 3.43.4 初始化模块初始化模块 接口：不接受任何数据； 核心函数：init()； 操作：将全局数据结构 chess中的所有标记信息均标记为 0。 3.53.5 棋盘遍历模块棋盘遍历模块 接口：不接受任何数据； 核心函数：horse_chess()； 棋盘遍历模块的程序流程图如图 4 所示。 湖南商学院计电学院数据结构课程设计 第 7 页 共 15 页 开始 num = 64; cnt = 1; x= startx;y = starty; i = chessxxyy. Direction; xx = x + dxi; yy = y + dyi; x = xx; y = yy; num-; num != 0 test(xx,yy,) = 1 and chessxxyy.visited = 0; i = 0 取值为真为 T1，否则为T1; 若条件 x = 0 取值为真为 T3，否则为T3; 若条件 y = 0 /在，则返回 1 else return 0;/不在，则返回 0 void start_pos()/由用户随即指定吗的起始位置 char chx, chy; while(1) 湖南商学院计电学院数据结构课程设计 第 13 页 共 15 页 printf(请输入马的起始位置(07,07,中间应有一个空格):n); chx = getchar();/用户输入起始位置的 x 坐标 getchar();/获取输入中的空格 chy = getchar();/用户输入起始位置的 x 坐标 startx = chx - 0; starty = chy - 0; if(test(startx, starty) = 0 )/如果用户输入的其实位置不再指定的棋盘内则提示用户重新输 入 printf(输入无效！请重新输入！); else break; return; void init()/初始化棋盘上各种标记信息 int i, j; for(i = 0; i 8; i+) for(j = 0; j 8; j+) chessij.visited = 0; chessij.route = 0; chessij.direction = 0; chessij.prex = 0; chessij.prey = 0; void horse_chess() int i, cnt, x, y, xx, yy, num, a, b; num = 64; cnt = 1; chessstartxstarty.visited = 1; chessstartxstarty.prex = -1; chessstartxstarty.prey = -1; chessstartxstarty.route = cnt+; x = startx; y = starty; 湖南商学院计电学院数据结构课程设计 第 14 页 共 15 页 num-; while(num)/循环处理 64 次，即棋盘上的 64 个格子 for(i = chessxy.direction; i = 8)/若从该点出发已经没有任何路径可以试探，则从该点回溯一个点 a = chessxy.prex; b = chessxy.prey; x = a; y = b; return; void print()/打印棋盘上的序号 int i, j; for(i = 0; i 8; i+) for(j = 0; j 8; j+) if(