数据结构报告分析.doc

课 程 设 计 报 告 题目： 国际跳棋 课程名称： 专业班级： 学 号： 姓 名： 指导教师： 报告日期： 计算机科学与技术学院 任务书 ⑴查阅相关的文献资料； ⑵使用图形界面，要求界面美观，操作方便； ⑶除实现人机对弈功能外，其它功能上可自由发挥。 参考文献 [1] 严蔚敏,吴伟民. 数据结构(C语言版). 北京: 清华大学出版社,1997 [2] 王晓东. 计算机算法设计与分析. 北京: 电子工业出版社, 2007. [3] 蒋浩,郑金华. 国际跳棋游戏中的进化策略.中国人工智能进展(2005) 目录 一、选题背景 1. 课程设计课题的目的与意义…………………………………………………………………1 2. 应解决的主要问题及技术现状………………………………………………………………1 3. 研究与发展概况及存在的问题………………………………………………………………1 4. 本设计的指导思想……………………………………………………………………………1 二、 三、过程(设计或实验)论述 1. 程序总体设计思路2. 数据结构类型…………………………………………………………………………………3 3. 算法详细设计 5. C语言程序实现的简要说明…………………………………………………………………5 四、程序测试复杂度分析五、六、七、附录源程序2 一、选题背景 数据结构是计算机科学技术与信息安全等专业的一门重要专业基础课，牢固掌握数据结构的基础知识，熟练地运用数据结构的思想与技术方法解决实际应用问题是是本课程学习的基本任务与目标。而课程设计是重要组成部分 要成功实现国际跳棋小程序，应该考虑两个方面的问题：内部算法的实现和图形界面的实现与美化。 因为国际跳棋的界面比较简单，所以图形界面写起来不是很复杂。可以用Qt、GTK+或者MFC写图形界面，本次课程设计用的是GTK+3.0 。由于此前没有接触过GTK+3.0，没有任何基础，所以需要查找教程。根据教程提供的范例，图形界面就不难实现了，至于美化则需要细心调整规划。 最重要的是内部算法的实现。要实现算法，那么应该熟悉国际跳棋的下棋规则。国际跳棋的规则不唯一，本次课程设计选择的规则需要注意的地方是：普通棋子跳吃时只能向前，王棋每次只能前进一格，跳吃时同样只能前进一格。算法中最难的部分是电脑下棋算法的实现，采用的是α-β搜索树。 本次课程设计采用的是C语言，发展已经很成熟。使用的是Codeblocks编译器，但由于Codeblocks目前不支持GTK+3.0，所以需要设置环境变量，还要对Codeblocks新建的工程项目进行配置。配置之前需要下载完整的GTK+3.0开发包，否则某些lib库缺失会导致出现运行出错。本次课程设计采用的是自顶向下的设计思路。将整个程序分成玩家下棋和电脑下棋两个大的部分，然后将每个部分的功能分成小模块依次实现。 二、方案论证 本次课程设计采用的是自顶向下的设计方案。将整个程序分成若干子模块依次实现，但是每个模块的核心均是算法的设计。而国际跳棋程序所有算法中，电脑下棋算法是最重要的，也是最难的。通过上网查资料发现，一般电脑下棋算法有两种方案，一是最小最大策略，一是α-β搜索树剪枝。从获取的资料中可知，对于一个结点为N的博弈树，采用α-β剪枝进行搜索，一般可以把搜索的时间复杂度提高到O（），这意味着其搜索深度可以提高到采用最小最大策略算法的2倍，效率更高。 三、过程(设计或实验)论述 根据完成课程设计的过程，可以分成如下几个部分：程序总体设计思路、数据结构类型、算法详细设计、系统工作流程图、C语言程序实现的简要说明。现在分别进行阐述。 程序总体设计思路 采用自顶向下的设计方案，首先将国际跳棋程序的实现分为两大部分：图形界面、下棋算法。 数据结构类型 本次课程设计完全采用数组数据结构。具体实现方法是：定义一个10的按钮数组button，每个按钮表示国际跳棋棋盘的一个格子，再定义一个10的int型数组pos，初始化为或 算法详细设计 设置一个状态变量mode，初始化为 如果mode=1，当玩家第一次点击棋子时，获取被点击棋子的坐标存放在静态变量（x1，y1）中，如果（x1，y1）处pos的值为mode变为 如果mode=2，第二次点击棋子的坐标存放在静态变量（x2，y2）中。 判断x1，x2，y1，y2的关系，如果满足横坐标和纵坐标之差的均为2，y21，执行（） 如果满足横坐标和纵坐标之差的均为22，y21，y12，y22，y22，y22，则回到（）处开始执行；若mode=1，执行（）。若mode=1且y2==0，那么（x2，y2）处pos值变为 如果mode=1，刷新棋盘，并且开始电脑下棋。 电脑下棋的算法借鉴的是网上所查资料提供的α-β剪