数据结构与算法_马踏棋盘.doc

合肥学院 计算机科学与技术系 课程设计报告 2012 2013 学年第 2 学期 课程课程 数据结构与算法 课程设计名称课程设计名称马踏棋盘 学生姓名学生姓名 学号学号 专业班级专业班级 指导教师指导教师 2013 年 6 月 计科系数据结构课程设计报告 1 目目 录录 数据结构课程设计报告 马踏棋盘 2 问题描述 2 1 问题分析与定义 2 2 数据结构的选择和概要设计 3 数据结构的选择 3 概要设计 3 3 详细设计和编码 4 4 上机调试过程 6 5 测试结果及分析 7 6 用户使用说明 9 7 参考文献 9 附录源程序 10 计科系数据结构课程设计报告 2 数据结构课程设计报告数据结构课程设计报告 马踏棋盘马踏棋盘 题目 题目 问题描述 设计一个国际象棋的马踏遍棋盘的演示程序 要求 将马随机放在国际象棋的 8 8 棋盘 Board 8 8 的某个方格中 马按走棋规则 进行移动 要求每个方格只进入一次 走遍棋盘上全部 64 个方格 编制非递归程序 求出 马的行走路线 并按求出的行走路线 将数字 1 2 64 依次填入一个 8 8 的方阵 输出之 1 1 问题分析与定义 问题分析与定义 走棋规则 马走 3 2 格对角线 简单的说就是走 L 形 棋盘如图所示 将马放在棋盘中的任意一个位置 按照马的走棋规则 我们能够发现 如果没有其他棋子的影响 它最多有 8 个出口 最少有 2 个出口 马所在位置及其出口 算法核心思想 本程序的核心算法是 贪心算法 在每个结点对其子结点进行选取时 优先选择 出口 最小的进行搜索 出口 的意思是在这些子结点中它们的可行子结点的 个数 也就是 孙子 结点越少的越优先跳 为什么要这样选取 这是一种局部调整最优 的做法 如果优先选择出口多的子结点 那出口少的子结点就会越来越多 很可能出现 死 结点 顾名思义就是没有出口又没有跳过的结点 这样对下面的搜索纯粹是徒劳 这样会浪费很多无用的时间 反过来如果每次都优先选择出口少的结点跳 那出口少的结 点就会越来越少 这样跳成功的机会就更大一些 01234567 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 计科系数据结构课程设计报告 3 2 2 数据结构的选择和概要设计 数据结构的选择和概要设计 数据结构的选择 栈 本程序可以利用栈的知识来解决 当然 栈也包括链栈和顺序栈 由于本程序数 据有限 并且顺序栈较链栈简单 所以该程序最终选择使用顺序栈来解决 贪心算法 在 算法中采用逐步构造最优解 在每个阶段 都作出一个看上去最优的决策 在一定的标准 下 决策一旦作出就不可再更改 概要设计 主程序模块 void main 定义变量 接受命令 处理命令 退出 起始坐标函数模块 马儿在棋盘上的起始位置 探寻路径函数模块 马儿每个方向进行尝试 直到试完整个棋盘 输出路径函数模块 输出马儿行走的路径 流程图如下 输入的初始位置是否正确 否 是 主程序模块 起始坐标函数模 块 探寻路径函数模 块 输出路径函数模 块块 结束 计科系数据结构课程设计报告 4 3 3 详细设计和编码 详细设计和编码 下图显示了马位于方格 2 3 时 8 个可能的移动位置 一般来说 当马位于位置 i j 时 可以走到下列 8 个位置之一 01234567 081 172 2H 373 454 5 6 7 i 2 j 1 i 1 j 2 i 1 j 2 i 2 j 1 i 2 j 1 i 1 j 2 i 1 j 2 i 2 j 1 但是 如果 i j 靠近棋盘的边缘 上述有些位置可能超出棋盘范围 成为不允许的 位置 8 个可能位置可以用两个一维数组 Htry1 0 7 和 Htry2 0 7 来表示 0 1 2 3 4 5 6 7 Htry1 2 1 1 2 2 1 1 2 0 1 2 3 4 5 6 7 Htry2 1 2 2 1 1 2 2 1 位于 i j 的马可以走到的新位置是在棋盘范围内的 i Htry h j Htry2 h 其中 h 0 1 2 7 每次在多个可走位置中选择其中一个进行试探 其余未曾试探过的可走位置必须用 适当结构妥善管理 以备试探失败时的 回溯 悔棋 使用 计科系数据结构课程设计报告 5 流程图如下 开始 Int i j i 0 i N Board i j 0 i 输入棋子起始位置 判断棋子是否出棋盘 Multiplex For 循环 从这个位置开始 结束 计科系数据结构课程设计报告 6 4 4 上机调试过程 上机调试过程 1 本次实验的主要目的是在于掌握和理解栈的特性和它的应用 在编制该程序中 遇到了很多问题 首先 在开始刚编制程序的时候遇到的问题是 程序编译都通不过 主 要在一些细节的问题上 还有在程序的返回值在刚开始时也没有正确返回 经过编译慢慢 调试 编译都能通过 没有错误和警告 2 虽然编译都能通过 但是运行时却出错 程序不能终止 只有通过人工方式结 束程序 可能是在某些地方出现了无限死循环了 然后在仔细检查代码 发现没有标记马 儿尝试的方向 director 这样的话 马儿回溯的时候 下一次又有可能走那个方向 这样 就出现了死循环 3 标记好马儿尝试的方向后 编译运行 但是运行结果却不符合程序所要求的结 果 说明在算法上肯定有错误 检查发现 马儿走的坐标没有控制后 它的横纵坐标必须 控制 0 到 7 之间 否则的话马儿就会踏出棋盘以外 这样输出的结果就不对 还有就是棋 盘走过的位置要标记一下 以便下次走不重复走 当回溯的时候的记得把标记给清掉 这 个地方有时候也很容易混淆 5 5 测试结果及分析 测试结果及分析 输入数据 1 根据要求重新输入马的初始位置 9 9 由于输入数据不再要求范围之 内 程序要求用户重新输入 图 1 计科系数据结构课程设计报告 7 输入数据 2 根据要求重新输入马的初始位置 1 1 结果如下 图 2 图 3 计科系数据结构课程设计报告 8 测试结果 如图 1 所示 当输入马的坐标为 9 9 时 由于该坐标不在 8 8 的棋盘内 所以 程序提示要求重新输入 如图 2 所示 重新输入数据位 1 1 满足棋盘要求 得到在 该位置的马踏棋盘的结果 如图 3 所示 当位置选定为 4 4 时的结果 结果分析 如图 3 所示 以数字递增顺序表示马的下一个出口位置 如图中 1 表 示初始位置 按照国际象棋中马的走棋规则并选择最优位置 即为 2 位置 3 表示 2 位置 的马的下一个出口位置 以此循环下去 直到数字遍及整个棋盘 注 马 的走棋路线即为图中白线标记部分 仅标记了前 4 个位置 测试数据 1 输入马的初始位置 9 9 由于不符合要求 程序要求重新输入 6 6 用户使用说明 用户使用说明 用户需将源程序清单输入可运行 C 的编辑平台 例如 vc c Builder 等等 然 后进行编译 然后用户根据提示输入马的初始位置 程序会提示所输入马的初始位置必须 在 1 8 之间 否则需要重新输入 直至输入的位置符合要求为止 输入正确之后 程序会 输入马儿踏遍整个棋盘的具体执行步骤 注 阿拉伯数字 1 2 3 4 62 63 64 下一个数字所在位置即为上一个位置马 儿的出口 7 7 参考文献 参考文献 1 王昆仑 李红 数据结构与算法 北京 铁道工业出版社 2007 年 6 月第一版 2 徐孝凯 魏荣 数据结构 北京 机械工业出版社 1996 年 3 徐孝凯 数据结构简明教程 北京 清华大学出版社 1995 年 4 陈文博 朱青 数据结构与算法 北京 机械工业出版社 1996 年 5 许卓群 张乃孝 杨冬青 唐世渭 数据结构 高等教育出版社 1988 年 6 李廉治 姜文清 郭福顺 数据结构 大连理工大学出版社 1989 年 计科系数据结构课程设计报告 9 附录附录 源程序源程序 1 定义头文件和预定义 include define MAXSIZE 100 define N 8 2 数据类型定义 int board 8 8 定义棋盘 int Htry1 8 1 1 2 2 2 1 1 2 存储马各个出口位置相对当前位置行下标的增量数组 int Htry2 8 2 2 1 1 1 2 2 1 存储马各个出口位置相对当前位置列下标的增量数组 struct Stack 定义栈类型 int i 行坐标 int j 列坐标 int director 存储方向 stack MAXSIZE 定义一个栈数组 int top 1 栈指针 3 函数声明 void InitLocation int xi int yi 马儿在棋盘上的起始位置坐标 int TryPath int i int j 马儿每个方向进行尝试 直到试完整个棋盘 void Display 输出马儿行走的路径 4 起始坐标函数模块 void InitLocation int xi int yi int x y 定义棋盘的横纵坐标变量 top 栈指针指向第一个栈首 stack top i xi 将起始位置的横坐标进栈 stack top j yi 将起始位置的纵坐标进栈 计科系数据结构课程设计报告 10 stack top director 1 将起始位置的尝试方向赋初值 board xi yi top 1 标记棋盘 x stack top i 将起始位置的横坐标赋给棋盘的横坐标 y stack top j 将起始位置的纵坐标赋给棋盘的纵坐标 if TryPath x y 调用马儿探寻函数 如果马儿探寻整个棋盘返回 1 否则返 回 0 Display 输出马儿的行走路径 else printf 无解 5 探寻路径函数模块 int TryPath int i int j int find director number min 定义几个临时变量 int i1 j1 h k s 定义几个临时变量 int a 8 b1 8 b2 8 d 8 定义几个临时数组 while top 1 栈不空时循环 for h 0 h 0k 0 记录条数 a h number 将条数存入数组 a 8 中 for h 0 h 8 h 根据可行路径条数小到大按下表排序放入数组 d 8 中 min 9 for k 0 ka k min a k d h k 将下表存入数组 d 8 中 s k a s 9 director stack top director if top 63 如果走完整个棋盘返回 1 return 1 find 0 表示没有找到下一个位置 for h director 1 h 0 表示找到下一个位置 break if find 1 如果找到下一个位置进栈 stack top director director 存储栈结点的方向 top 栈指针前移进栈 stack top i i stack top j j stack top director 1 重新初始化下一栈结点的尝试方向 board i j top 1 标记棋盘 else 否则退栈 board stack top i stack top j 0 清除棋盘的标记 top 栈指针前移退栈 return 0 6 输出路径函数模块 void Display int i j for i 0 i N i for j 0 j N j printf t d board i j 输出马儿在棋盘上走