数据结构课程设计之八皇后问题.pdf

《数据结构课程设计之八皇后问题.pdf》由会员分享，可在线阅读，更多相关《数据结构课程设计之八皇后问题.pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 1 课 程 设 计 报 告 课程名称 数据结构课程设计 课题名称 八皇后问题演示 专 业 通信工程 班 级 通信工程 1081 学 号 *姓 名 刘献文 指导教师 田娟秀 郭芳 2012 年 7 月 6 日 2 湖南工程学院 课 程 设 计 任 务 书 课程名称 数据结构 课 题 八皇后问题演示 专业班级 通信工程 1081 学生姓名 刘献文 学 号 *指导老师 田娟秀 郭芳 审 批 任务书下达日期 2012 年 7 月 1 日 任务完成日期 2012 年 7 月 6 日 3 1 设计内容与设计要求 1.1 设计内容（4）课题四：八皇后问题演示 八皇后问题是一个古老而著名的问题，是回溯算法的

2、典型例题。该问题是十九世纪著名的数学家高斯 1850 年提出：在 88 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76 种方案。1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解，后来有人用图论的方法解出 92 种结果。设计思路：解决 8 皇后时，在安放第 i 行皇后时，需要在列的方向从 1 到 n 试探(j=1,n)：首先在第 j 列安放一个皇后，如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。如果没有出现攻击，在第j 列安放的皇后不动，递归安放第 i+1 行皇

3、后。对于八皇后问题的实现，如果结合动态的图形演示，则可以使算法的描述更形象、更生动。要求用 Turbo C 或 VC6.0 MFC 实现的八皇后问题的图形程序，能够演示全部的 92 组解。1.2 选题方案：所选题目根据学号确定，学号模 6 加 1，即（学号%6+1）。如你的学号为 9，则所选题目号为：9%6+1（题目 4）。注意，所有的课题都要求用图形方式演示步骤和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。1.3 设计要求：1.3.1 课程设计报告规范（1）需求分析 a.程序的功能。b.输入输出的要求。（2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、

4、各模块的调用关系；每个模块的功能。4 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计 a.采用 C 语言定义相关的数据类型。b写出各模块的类 C 码算法。c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会 a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。（5）使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式 a.设计报告要求用A4 纸打印

5、成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录 源程序清单（带注释）1.3.2 考核方式 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占 10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占 10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占 40%）（4）设计报告（占 30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，

6、成绩为零分。（5）独立完成情况（占 10%）。1.3.3 课程验收要求（1）运行所设计的系统。5 （2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2 进度安排 第 20 周：星期一 8：0012：00 上课 星期二 8：0012：00 上机 星期三 14：3018：30 上机 星期四 8：0012：00 上机 附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4 大小的图纸及程序清单）。正文的格式:一级标题用 3 号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为 22。正文的

7、内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在 5000 字以上（不含程序原代码）。6 目录 一、需求分析.7 1.1 功能要求.7 1.2 涉及到的知识点.7 二、概要设计.7 2.1 数据结构.7 2.2 抽象数据类型的定义.8 2.3 算法流程.8 三、详细设计.9 四、调试分析及测试.13 4.1 遇到的问题及解决方法.13 4.2 程序使用说明.13 4.3 测试结果.13 五、总结与体会.16 六、评分表.17

8、七、附录（源程序）.18 7 一、需求分析 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯 1850年提出的,并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有 76 种不同的放法，这就是有名的“八皇后”问题。在国际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在 8*8 的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。现在我们已经知道八皇后问题有 92 个解答。1.1 功能要求 当

9、运行程序时，在屏幕上显示一个比较直观选择界面。进入界面后，就会提示输入字符的输入形式，在八皇后求解程序中，只要你选择输出解的格式，选择 1 则显示为每一列皇后的放置的行数，选择 2 则显示的是以矩阵形式形象的显示皇后的放置位置，选择 0 则退出程序的调试。在调试结果中，的位置也就表示了该皇后应该所在的位置，代表了空位置。1.2 涉及到的知识点 本次课程设计中，用到的主要知识有：递归法的应用,for 语句的灵活运用，数据结构中树知识的灵活运用、栈及数组的掌握.二、概要设计 2.1 数据结构.1.数组 gEightQueen，存放第 i 行皇后所在的列；2.cont 为存放皇后问题解的个数，men

10、t 为皇后问题解矩形形式显示的解的个数；3.对 角 线 标 记 为qj-i与(j-k)，i 为 列，j为 行，当(qj=i)或 者(abs(qj-i)=abs(j-k)，则表示第 i 列皇后是否已在第 j 行存在或 qj-i 与(j-k)为 8 对角线冲突；2.2 抽象数据类型的定义 print1()/打印每一行皇后放置的列数的情况 print2()/打印以矩阵形式形象的显示皇后的放置位置 find()/寻找可以放置皇后的位置 place1()、place2()/递归调用，存入所有每一行皇后所在的列 Sleep(i)/缓冲 i/1000s 显示下一个矩阵形式皇后位置 void main()/主

11、函数调用 2.3 算法流程 1.当 n8 时，便打印出结果。算法流程图如下:Y N N 开始 从 n 行开始摆放第 n 个皇后 把第 n 个皇后所在的列存入 qk中 n=8 打印结果 n+9 三、详细设计/位置标明法打印 void print1(int n)int i;cont+;printf(第%d 个解:,cont);for(i=1;i=n;i+)printf(%d,qi);printf(n);/矩阵表示法打印 void print2()/输出一个解 ment+;/输出的解的个数 int i=0;printf(第%d 个解:n,ment);Sleep(300);for(i=1;i9;i+)

12、/i 为行 for(int d=1;d8)print1(8);else for(int i=1;i8)print2();else for(int i=1;i=8;i+)if(find(i,k)qk=i;place2(k+1);/主函数调用 void main()11 int choice;char ch;printf(nnt*欢迎进入八皇后问题*nn);ch=y;while(ch=y|ch=Y)printf(nt 查 询 菜 单n);printf(nt*);printf(nt*No.1-每一行皇后放置的列数的情况 *);printf(nt*No.2-视图矩阵形式显示皇后的位置 *);print

13、f(nt*No.0-退 出 *);printf(nt*);printf(nt 请选择菜单号(No.0-No.2)：);scanf(%d,&choice);switch(choice)case 1:printf(nt 每一行皇后放置的列数的情况nn);place1(1);/从第 1 个皇后开始放置 break;case 2:place2(1);/从第 1 个皇后开始放置 break;case 0:ch=n;break;default:printf(ntt 菜单选择错误，请重新输入!n);12 各函数的调用关系图、主要函数的流程图 1 2 0 2 开始 退出 判断输入 调用 place2 函数 显

14、示视图矩阵形式显示皇后的位置 调用 place1 函数 显示每一行皇后放置的列数的情况 13 四、调试分析及测试 4.1 遇到的问题及解决方法(1)由于对八个皇后放置的位置不能一次确定，而且前一个皇后的放置位置直接影响着后面的放置位置，使程序调试时要花费不少时间。（2）由于开始编程时没有设置时间缓冲，所以输出 92 种矩阵形式显示皇后的位置时dos 窗口只能显示出第 64 个以后的解，求教老师后，在显示前插入一个 Sleep（），使每一个矩形形式解都能在 dos 窗口中很明显的看到。4.2 程序使用说明（1）本程序的运行环境为 DOS 操作系统（2）进入演示程序后即显示文本方式的用户界面（3）

15、进入界面后，就会提示输入字符的输入形式，在八皇后求解程序中，只要你选择输出解的格式，选择 1 则显示为每一列皇后的放置的行数，选择 2 则显示的是以矩阵形式形象的显示皇后的放置位置，选择 0 则退出程序的调试。在调试结果中，的位置也就表示了该皇后应该所在的位置，代表了空位置。4.3 测试结果 初步运行界面 14 选择输入为“1”时的显示，位置标明每一行皇后放置的列数 15 选择输入为“2”时的显示，视图矩阵形式显示皇后位置 16 选择输入为“0”时的显示，即将退出 dos 窗口 五、总结与体会 通过这次的课程设计，我从中得到了许多经验和软件设计的一些新思路；从这个八皇后问题设计以及分析中，本人

16、从中理解到了数据结构对于软件设计的重要性，它的使用，可以改变软件的运行周期，思路从繁化简，并且都能够通过其相关引导，将本身以前编程思想进行扩充，发展.这也是在这次课程设计中我所掌握得到的。但在这次的课设中也遇了一些问题，如，八皇后在变成初期由于没真正体会到“树”在里面的运用,不自觉的采用了非递归的算法，结果大大增加了程序的复杂程度。并且也让整个程序的时间复杂度变得更大；在重温了树的回溯，以及二叉树的遍历后，最终将程序进行了一次较大的改造。并且通过思考，再将以前的知识加以运用才最终解决了这个问题，整个程序的算法的可看性也有了较大的改进。总结一下自己，发现自己虽然在不仅在理论上没有掌握牢固，并且在

17、实践的时候也遇到了问题，所以自己还是远远的不足，不管是在数据结构课程的设计上，还是其他专业课上，在以后的一段学习时间里必须坚持自己思考，自己多动脑，多动手，这样才能脱离理论，让自己的学习更上一层楼。参考文献 1.数据结构教程/李春葆等编著.3 版北京：清华大学出版社,2009.3 2.数据结构教程（第三版）上机实验教程/李春葆等编著.北京：清华大学出版社,2009.3 17 六、评分表 应用技术学院课程设计评分表 课程名称：数据结构课程设计 项 目 评 价 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量 答辩陈述与回答问题情况 课程设计周表现情况 综合成绩 教师签名：日 期：（注：

18、1此页附在课程设计报告之后；2综合成绩按优、良、中、及格和不及格五级评定。）18 七、附录（源程序）#include#include#include const int N=20;int qN;int cont=0,ment=0;void print1(int n)int i;cont+;printf(第%d 个解:,cont);for(i=1;i=n;i+)printf(%d,qi);printf(n);void print2()/输出一个解 ment+;/输出的解的个数 int i=0;printf(第%d 个解:n,ment);Sleep(300);for(i=1;i9;i+)/i为行

19、for(int d=1;d9;d+)/d为列 if(d=qi)/如果此行中d为存入皇后的列 printf();/标记输出 else printf();/此行中其他列输出 19 printf(n);/一行输出完成，换行 int find(int i,int k)int j;/定义 j 为行 j=1;while(j8)print1(8);else for(int i=1;i8)print2();else for(int i=1;i=8;i+)if(find(i,k)qk=i;place2(k+1);void main()int choice;char ch;printf(nnt*欢迎进入八皇后问题

20、*nn);ch=y;while(ch=y|ch=Y)printf(nt 查 询 菜 单n);printf(nt*);printf(nt*No.1-每一行皇后放置的列数的情况 *);printf(nt*No.2-视图矩阵形式显示皇后的位置 *);printf(nt*No.0-退 出 *);printf(nt*);printf(nt 请选择菜单号(No.0-No.2)：);scanf(%d,&choice);switch(choice)21 case 1:printf(nt 每一行皇后放置的列数的情况nn);place1(1);/从第 1 个皇后开始放置 break;case 2:place2(1);/从第 1 个皇后开始放置 break;case 0:ch=n;break;default:printf(ntt 菜单选择错误，请重新输入!n);