数据结构课程设计报告

淮阴工学院

数据结构课程设计报告

选题名称: 八皇后问题 系（院）: 数理学院 专 业: 信息与计算科学 班 级: 计科1091班 姓 名:刘红斌 学 号: 1094101109 指导教师: 周海岩 学年学期: 2010 ~ 2011 学年 第 2 学期

2011年6月20日

设计任务书

课题 名称 八皇后 1、调研并熟悉八皇后的基本功能、数据流程与工作规程； 设计 2、学习八皇后相关的算法和VC++集成环境的编程技术； 目的 3、通过实际编程加深对基础知识的理解，提高实践能力； 4、学习开发资料的收集与整理，学会撰写课程设计报告。 ； 实验 1、微型电子计算机（PC）环境 2、安装Windows2000以上操作系统，VisualC++6.0开发工具。 1、利用课余时间去图书馆或上网查阅课题相关资料，深入理解课题含义及设计要求，注意材料收集与整理； 2、在第19周之前完成预设计，并请指导老师审查，通过后方可任务 进入下一步工作； 要求 3、本课题要求编写程序实现将八个皇后放置在国际象棋棋盘的无冲突的位置上的算法，并给出所有的解； 4、结束后，即使提交设计报告（含纸质稿、电子稿），要求格式规范、内容完整、结论正确。 工作进度计划 序号 1 2 3 4 起止日期 2011.06.20~2011。06.20 2011.06.21~2011.06.23 2011.062.4~2011.06.25 2011.06.25~2011.06.26 工 作 内 容 在预设计的基础上，进一步查阅资料，完善设计方案，形成书面材料。 设计总体方案，构建、绘制流程框图，编写代码，上机调试。 测试程序，优化代码，增强功能，撰写设计报告。 提交软件代码、设计报告，参加答辩，根据老师反馈意见，修改、完善设计报告。 指导教师： 2011 年 6 月 10 日

摘要：

八皇后问题要求在一个8*8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后所攻击。按国际象棋的规则，一个皇后可以攻击与之处在同一行或同一列或同一斜线上的其他任何棋子。因此，八皇后问题等于要求八个皇后中的任意两个不能放在同一行或同意列或同意斜线上。而本课程设计本人的目的也是通过而本课程设计本人的目的也是通过用C++平台将一个8*8的棋盘上放上8个皇后，使得每一个皇后既攻击不到另外七个皇后，也不被另外七个皇后攻击的92种结构予以实现，使用回溯算法最终将其问题变得一目了然，更加易懂。

关键词：八皇后；C++；回溯法

目录

一、 需求分析 .................................................................................................................1

1.1 选题理由 .................................................................................................................1

1.2 涉及到的知识点 .......................................................................................................1 1.3 功能要求 .................................................................................................................3 二、 概要设计 .................................................................................................................3

2.1 数据结构 .................................................................................................................3

2.2 抽象数据类型的定义 ................................................................................................3 2.3 算法流程 .................................................................................................................4 三、

详细设计 .................................................................................................................6

四、 调试分析及测试 ..................................................................................................... 12

4.1 遇到的问题及解决方法 .......................................................................................... 12 4.2 算法的时空分析 ..................................................................................................... 13 4.3 程序模块构架 ........................................................................................................ 13

4.4 算法的改进 ............................................................................................................ 13 4.5 程序使用说明 ........................................................................................................ 13 4.6 测试结果 ............................................................................................................... 14 总结 .................................................................................................................................... 17 致谢 .................................................................................................................................... 18 参考文献 ............................................................................................................................. 19