数据结构八皇后问题(1).doc

目目 录录 一 需求分析 1 1 1 程序的功能 1 1 2 程序的输入输出要求 1 二 概要设计 3 2 1 程序的主要模块 3 2 2 程序涉及 3 三 详细设计 4 3 1 相关代码及算法 4 3 1 1 定义相关的数据类型如下 4 3 1 2 主模块类 C 码算法 4 3 1 3 画棋盘模块类 C 码算法 5 3 1 4 画皇后模块类 C 码算法 5 3 1 5 八皇后摆法模块 递归法 6 3 1 6 初始化模块 7 3 1 7 输出摆放好的八皇后图形 动态演示 7 3 2 相关流程图 8 四 调试分析 10 五 设计体会 11 六 附录 12 七 参考文献 16 0 一 需求分析 1 11 1 程序功能程序功能 八皇后问题是一个古老而著名的问题 该问题是十九世纪著名的数学家高斯 1850 年提出的 八皇后问题要求在一个 的棋盘上放上 个皇后 使得每一 个皇后既攻击不到另外七个皇后 也不被另外七个皇后所攻击 按照国际象棋的规 则 一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子 问 有多少种不同的摆法 并找出所有的摆法 因此 八皇后问题等于要求八个皇后中 的任意两个不能被放在同一行或同一列或同一斜线上 本程序通过对子函数 void qu int i 的调用 将八皇后的问题关键通过数据结构的思想予以了实现 虽然题 目以及演算看起来都比较复杂 繁琐 但在实际中 只要当一只皇后放入棋盘后 在横与列 斜线上没有另外一只皇后与其冲突 再对皇后的定位进行相关的判断 即可完成 如果在这个程序中 我们运用的是非递归的思想 那么将大量使用 if 等语句 并通过不断的判断 去推出答案 而且这种非递归的思想 大大的增加了 程序的时间复杂度 如果我们使用了数据结构中的算法后 那么程序的时间复杂度 以及相关的代码简化都能取得不错的改进 这个程序 我运用到了数据结构中的栈 数组 以及树和回溯的方法 特别是在对于树以及二叉树的学习 更是为八皇后的 问题提供了科学的解决方案 通过对树的分析 把八皇后的问题看成了树 而在衍 生第一个变化后 上面的第一层八个变化就变成了八个结点 而这八个结点再继续 的衍生 这样比较形象的将八皇后的问题简单化了 然后再通过回溯法进行设 计 回溯法是设计递归过程的一个重要的方法 它的求解过程实质上是一个先序遍 历一棵 状态树 的过程 在这个程序设计中 它先进行判断 棋盘上是否已经得 到一个完整的布局 即棋盘是否已经摆上 8 个棋子 如果是 则输出布局 如果 不是则依次先根遍历满足约束条件的各棵子树 流程即是 判断该子树根的布局是否合法 如果合法的话 则先根遍历该子树 如果不合 法的话 则剪去该子树的分支 1 21 2 程序的输入输出要求 程序的输入输出要求 用 TC 软件进行编译以及调试 调试正确之后 运行结果如下图 输出结果如下图所示 1 第 1 种情况 第 92 种情况 2 二 概要设计 2 12 1 主要模块 主要模块 这个程序主要由 4 个模块组成 分别是画棋盘模块 画皇后模块 输出皇后摆法模 块 和解决如何摆置皇后模块 这 4 个模块隶属于主函数模块 既主函数通过对这 4 个模块的合理调用解决 8 皇后问题 同时这 4 个模块之间也互有调用 2 22 2 程序设计的数据结构及其关系 程序设计的数据结构及其关系 数据结构的实现 数组 a i a i 表示第 i 个皇后放置的列 i 的范围 1 8 对角 线数组 b j 主对角线 c j 从对角线 根据程序的运行 去决定主从对角线是否 放入皇后 然后进行数据的初始化 从 n 列开始摆放第 n 个皇后 因为这样便可以符合 每一竖列一个皇后的要求 先测试当前位置 n m 是否等于 未被占领 如果是 摆 放第 n 个皇后 并宣布占领 切记要横列竖列斜列一起来 接着进行递归 如果不是 测试下一个位置 n m 1 但是如果当 n 8 m 8 时 却发现此时已经无法摆放时 便要 进行回溯 三 详细设计 3 13 1 定义相关的数据类型 定义相关的数据类型 3 1 13 1 1 定义的相关数据类型 定义的相关数据类型 int A 21 B 21 C 21 Y 8 void buff1 buff2 3 1 23 1 2 设计思想 设计思想 本程序通过对子函数 void qu int i 的调用 将八皇后的问题关键通过数据结 构的思想予以了实现 虽然题目以及演算看起来都比较复杂 繁琐 但在实际中 只 要当一只皇后放入棋盘后 在横与列 斜线上没有另外一只皇后与其冲突 再对皇后 的定位进行相关的判断 即可完成 如果在这个程序中 我们运用的是非递归的思想 3 那么将大量使用 if 等语句 并通过不断的判断 去推出答案 而且这种非递归的思想 大大的增加了程序的时间复杂度 如果我们使用了数据结构中的算法后 那么程序的 时间复杂度 以及相关的代码简化都能取得不错的改进 这个程序 我运用到了数据 结构中的栈 数组 以及树和回溯的方法 特别是在对于树以及二叉树的学习 更是 为八皇后的问题提供了科学的解决方案 通过对树的分析 把八皇后的问题看成了树 而在衍生第一个变化后 上面的第一层八个变化就变成了八个结点 而这八个结点再 继续的衍生 这样比较形象的将八皇后的问题简单化了 然后再通过回溯法进行 设计 回溯法是设计递归过程的一个重要的方法 它的求解过程实质上是一个先序遍 历一棵 状态树 的过程 在这个程序设计中 它先进行判断 棋盘上是否已经得到 一个完整的布局 即棋盘是否已经摆上 8 个棋子 如果是 则输出布局 如果不是则 依次先根遍历满足约束条件的各棵子树 流程即是 判断该子树根的布局是否合法 如果合法的话 则先根遍历该子树 如果不合法的话 则剪去该子树的分支 3 23 2 相关代码及算法相关代码及算法 3 2 13 2 1 主模块主模块 C C 码算法 码算法 void main void Queen Q int gdriver DETECT gmode initgraph SetQueen setcolor YELLOW QueenPic cleardevice setcolor LIGHTGREEN settextstyle 0 0 3 outtextxy 180 10 Eight Queens setcolor WHITE settextstyle 0 0 1 outtextxy 250 400 2009 11 8 3 30pm 4 QueenRe getch closegraph 3 2 23 2 2 棋盘模块棋盘模块 C C 码算法码算法 void Checker void 画棋盘函数 int i k for k 0 k 8 k for i 0 i7 return for x 0 xA x 7 放置皇后 Q A x 7 1 标记下次这里不能放置皇后 6 Q B x y 7 1 标记下次这里不能放置皇后 Q C x y 7 1 标记下次这里不能放置皇后 if y 7 PrintQueen Q 调用输出图形函数 QueenRe Q y 1 进入下一层递归 Q A x 7 0 如果上次摆法导致后面不能继续摆放则重置标记为 0 Q B x y 7 0 Q C x y 7 0 3 2 53 2 5 初始化模块初始化模块 C C 码码 void SetQueen Queen Q 初始化 int i for i 0 iA i 0 Q B i 0 Q C i 0 初始化为 0 表示可以放置皇后 for i 0 iY i 1 3 2 63 2 6 图形输出 图形输出 void PrintQueen Queen t 图形输出函数 int k char str 20 static total 0 total setviewport 240 80 400 260 1 设置窗口 sprintf str NO d total setcolor GREEN settextstyle 0 0 1 outtextxy 0 0 str Checker for k 0 kY k 2 0 k 2 0 else putimage t Y k 20 20 k 20 buff2 COPY PUT getch if getch 27 exit 0 clearviewport void QueenRe Queen Q int y 八皇后的递归算法 int x if y 7 return for x 0 xA x 7 Q A x 7 1 Q B x y 7 1 Q C x y 7 1 if y 7 PrintQueen Q QueenRe Q y 1 进入下一层递归 Q A x 7 0 Q B x y 7 0 Q C x y 7 0 8 3 33 3 相关流程图相关流程图 Mian 函数 QueenRe Qu een Q int y 函数 PrintQueen Queen t 函 数 Checker void 函数 QueenPic v oid 函数 SetQueen Queen Q 函数调用图 9 皇后模块流程图 10 11 START 行循环遍 历完毕 吗 列循环遍 历 当前位置可 否放置皇后 放置皇后 并且 标记下次该列 主次对角线不能 放皇后 回朔 重置 Y N列遍历 完毕 输出图形 End N Y N Y 皇后模块流程图 四 调试分析 通过编译连接后 程序基本上把八皇后的 92 种摆法的都进行了演示 但程序运 行中也出现了以下缺点 因为八皇后的表现方法甚多 输出后虽能全部显示 但未能使屏幕停留 把一个一 个的将其显示出来 但是这样便使得操作步骤太多 也会造成不必要的麻烦 所以只画 出了第一种和最后一种的输出结果 演示如图所示 正确输出结果如下 12 五 设计体会 本课程设计本人的目的也是通过用 WIN TC 程序设计平台将一个 的棋盘上放上 个皇后 使得每一个皇后既攻击不到另外七个皇后 也不被另外七个皇后所攻击的 92 种结构予以实现 最终将其问题变得一目了然 更加易懂 六 用户使用说明 6 16 1 程序的使用平台 程序的使用平台 系统要求 windows2000 以上操作系统 语言开发平台 WIN TC 6 26 2 源代码分析 源代码分析 首先对程序中的函数头文件进行引入 定位 在这个程序中 与其他 C 的程序一 样 都是引入 include 然后开始定义里面的函数所需要的数组 其 中 setviewport 240 80 400 260 1 是对总的棋盘状态数进行定位 记录 接着 进入了主函数 在主函数中 先对棋盘进行初始化 并规定了在程序输出时 的情况 然后 对行列 对角线也进行了初始化 并在对这些元素初始后 对子函数 进行调用 进入子函数后 便马上对皇后放入的位置进行判断 通过语句的判断 如 果没有冲突的话 则放下皇后 并标记 在下一次的时候 不再放入皇后 并在主从 对角线进行判断 标记 然后再通过 if 语句判断 如果行还没有遍历完 进入下一行 接着通过放入一个 for 语句进行分析 如果前次的皇后放置导致后面的放置无论如 13 何都不能满足要求 则回溯 重置 当所有工作完成后 无冲突后 就返回主函数 并通过编译后对结果进行展示 七 附录 include include include include include void buff1 buff2 typedef struct int A 21 B 21 C 21 Y 8 Queen void SetQueen Queen Q 初始化 int i for i 0 iA i 0 Q B i 0 Q C i 0 for i 0 iY i 1 void QueenPic void 画皇后图象 然后存储到缓冲区 int size polypoints1 10 9 1 11 1 20 20 1 20 9 1 polypoints2 10 29 1 31 1 40 20 21 20 29 1 setfillstyle SOLID FILL LIGHTBLUE 画淡蓝色棋格 setcolor LIGHTBLUE rectangle 1 1 20 20 floodfill 10 10 LIGHTBLUE 14 setfillstyle SOLID FILL WHITE 画白色棋格 setcolor WHITE rectangle 21 1 40 20 floodfill 30 10 WHITE setfillstyle SOLID FILL DARKGRAY setcolor YELLOW drawpoly 5 polypoints1 drawpoly 5 polypoints2 floodfill 10 10 YELLOW floodfill 30 10 YELLOW size imagesize 1 1 20 20 计算缓冲区大小 然后存储 buff1 void malloc size buff2 void malloc size getimage 1 1 20 20 buff1 getimage 21 1 40 20 buff2 cleardevice void Checker void 画棋盘函数 int i k for k 0 k 8 k for i 0 i 8 i if k 2 0 setcolor LIGHTBLUE rectangle i 20 20 k 20 i 1 20 20 k 1 20 floodfill i 20 10 20 k 20 10 LIGHTBLUE else setfillstyle SOLID FILL WHITE setcolor WHITE rectangle i 20 20 k 20 i 1 20 20 k 1 20 floodfill i 20 10 20 k 20 10 WHITE void PrintQueen Queen t 图形输出函数 int k char str 20 static total 0 total setviewport 240 80 400 260 1 设置窗口 sprintf str NO d total 15 setcolor GREEN settextstyle 0 0 1 outtextxy 0 0 str Checker for k 0 kY k 2 0 k 2