1、 存档资料存档资料 成绩：成绩： 课课 程程 设设 计计 报报 告告 书书 所属课程名称所属课程名称 数据结构数据结构 题题 目目 骑士游历骑士游历 分分 院院 电信分院电信分院 专业班级专业班级 学学 号号 学生姓名学生姓名 指导教师指导教师 202013 13 年年 7 7 月月 5 5 日日 目目 录录 第一章第一章 课程设计内容及要求课程设计内容及要求 3 第二章第二章 课程设计的设计分析与功能模块课程设计的设计分析与功能模块 . 1 2.1 2.1 设计分析设计分析 1 (1)(1)设计目的设计目的 1 (2)任务分析任务分析 . 1 1. 要求要求 . 1 2. 2. 输入输入 1
2、 2.2 程序功能模块图程序功能模块图 1 第三章第三章 流程图设计的具体实现流程图设计的具体实现. 3 3.1 马踏遍棋盘流程图马踏遍棋盘流程图 3 3.2 系统测试与调试系统测试与调试 5 第四章第四章 源代码程序设计源代码程序设计 9 4.1 详细设计详细设计. 9 创建创建 9 操作操作 9 显示显示 9 4.2 4.2 源代码源代码 . 10 第五章第五章 课程设计心得课程设计心得 . 13 第六章第六章 参考文献参考文献 . 14 第七章第七章 致谢致谢 15 第一章第一章 课程设计内容及要求课程设计内容及要求 骑士游历问题是一个古老而著名的问题,问题的描述是:在 8 8 格的国际
3、象棋棋盘上,象棋马能否从某个格子出发按照 “马跳 日”的规则跳遍所有 64 个格子最后 再回到出发的那个格子。国 际象棋中的马,英语为 knight,恰好又意指中世纪西方世界的 “骑 士”,因此,这个问题又被称为“骑士游历。 在一个棋盘上（8 行 8 列）放一个“马” ，按“马走日字”的 规则，马要走到棋盘上每一个格子，且每个格子只走一次。 用回溯法深度优先搜索，若寻找到满足要求的解，则输出；否则 推回上一层往下一个方向搜索。 对于当前所在位置（x，y） ，依次枚举 8 个方向搜索，直到找到 一组可行解为止。使用剪枝有 2 处： 第一、使用 Warnsdorffs rule，枚举当前解得时候优
4、先选 择下一步可行步数最少的方向； 第二、若第一点中的方向存在不止一个，则优先选择离中心 位置较远的方向；每次都从中心点开始出发，求出一条合法路径 后再平移映射回待求路径。 第 1 页 第二章第二章 课程设计的设计分析与功能模块课程设计的设计分析与功能模块 2.1 2.1 设计分析设计分析 (1)(1)设计目的设计目的 1.熟练使用 C 语言编写程序，强化模块设计理念。 2.设计一个国际象棋马踏棋盘的演示程序。 3.理解栈的特性“后进先出” 和队列的特性“先进先出” 。 4.初步掌握软件开发过程的问题分析、系统设计、程序编 码、测 试等基本方法和技能。 (2)任务分析任务分析 1. 要求 在国
5、际象棋 88 棋盘上面，按照国际象棋规则中马的 行进规则，实现从任意初始位置，每个方格只进入一次， 走遍棋盘上全部 64 个方格。 编制程序， 求出马的行走路线， 并按求出的行走路线，将数字 1，2，64 依次填入一个 88 的方阵，并输出它的行走路线。 2. 输入 任意一个起始位置；输出：无重复踏遍棋盘的结果， 以数字 1-64 表示行走路线。 2.2 程序功能模块图程序功能模块图 各模块之间的调用关系，如图所示：各模块之间的调用关系，如图所示： 第 2 页 第 3 页 第三章第三章 流程图设计的具体实现流程图设计的具体实现 3.1 马踏遍棋盘流程图马踏遍棋盘流程图 第 4 页 开始 Int i、j i=0 iN Boardij=0 i + 输入棋子起始位置 判断棋子是否出棋盘 Multiplex For 循环 从这个位置开始 结束 第 5 页 3.2 系统测试与调试系统测试与调试 1.程序代码的输入和运行 新建 C 文件并输入代码到工作界面当中，仔细检查，运行 代码，如下图所示，图 3.2-1 表示程序的输入和运行， 图 3.21 图 3.22 2.程序代码的调试 经过请教老师和
