课程设计——数据结构课程设计(八皇后问题).doc

一 设计目的1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二 设计内容求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线8个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉，也就是下一个皇后不能放的位置。 12345678××××××××××Q×××××××××××××××图2-1：摆放示意图根据这个规则，我们可以利用一个函数来判断某个位置是否安全，安全的位置说明它所在的同一行、同一列或两条线上都没有放置过皇后，因此不会出现皇后互相攻击的情况；否则该位置不安全。其具体实现过程是找出所有放置的皇后，将他们的位置与该位置进行比较判断。又注意到同一行只能放一个皇后，因此，只需要对前面的各行逐行扫描皇后，就可以找出所有皇后的位置。下图是其中一种摆放皇后的方法：QQQQQQQQ图2-2：一种摆放皇后的方法三 设计要求1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。5.程序调试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。7.编写课程设计说明书。四 设计过程1.算法思想分析这道题可以用递归循环的方法来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题。（1）冲突（包括行、列、两条对角线） 列：规定每一列放一个皇后，不会造成列上的冲突。 行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。 对角线：对角线有两个方向。在同一对角线上的所有点（设下标为（i,j），要么（i+j）是常数，要么（i-j）是常数。因此，当第i个皇后占领了第j列后，要同时把以（i+j）、（i-j）为下标的标记置为被占领状态。（2）数据结构 解数组A，Ai表示第i个皇后放置的列，范围为18。 行冲突标记数组B，Bj=0 表示第j行空闲，Bj=1 表示第j行被占领，范围为18。 对角线冲突标记数组C、D。Ci-j=0 表示第（i-j）条对角线空闲，Ci-j=1 表示第（i-j）条对角线被占领，范围-77。Di+j=0 表示第（i+j）条对角线空闲，Di+j=1 表示第（i+j）条对角线被占领，范围216。2.算法描述与实现利用JudgeQueen（）函数来实现对皇后摆放位置的确定，并用回溯法来完成对所有皇后的摆放。void JudgeQueen1(int i)void JudgeQueen2(int i)ai表示第i个皇后放置的列，范围为18。行冲突标记数组b，bj=0 表示第j行空闲，bj=1 表示第j行被占领，范围为18ci-j=0 表示第（i-j）条对角线空闲，ci-j=1 表示第（i-j）条对角线被占领，范围-77。Di+j=0 表示第（i+j）条对角线空闲，di+j=1 表示第（i+j）条对角线被占领，范围216。利用if (bj=0) &&(ci+j=0)&& (di-j=0)语句来判断摆放位置是否冲突。利用JudgeQueen1(i+1)的函数调用来实现当8个皇后没有摆完，递归摆放下一皇后的操作。bj=0；ci+j=0；di-j=0；这三个语句来进行回溯。编写程序主函数，在main( )中调用各个功能函数实现八皇后问题的要求，其中运用switch( )函数实现八皇后问题的操作，并调用上述的JudgeQueen（）函数。算法流程A、 数据初始化。B、 从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置（n，m）是否等于0（未被占领）。如果是，摆放第n个皇后，并宣布占领（记得要横列竖列斜列一起设置），接着进行递归；如果不是，测试下一个位置（n，m+1），但是如果当n<=8，m=8时，发现此时已无法摆放时，便要进行回溯。从问题的某一种可能出发，搜索从这种情况能出发，继续搜索，这种不断“回溯”的寻找解的方法，称为“回溯法”。C、 当n>8时，便打印出结果。流程图如4-1所示：图4-1：程序流程图数据初始化测试下个位置m=m+1开始从n列开始摆放第n个皇后当前位置（n，m）是否被占领摆放皇后，并宣布占领n=n+1是否n<=8&m=8进行回溯打印结果3.系统测试（1）由于对八个皇后放置的位置不能一次确定，而且前一个皇后的放置位置直接影响着后面的放置位置，使程序调试时要花费不少时间。（2）本程序有些代码重复出现，显得程序的有些代码看起来很杂乱。（2）本程序模块划分比较合理，且利用指数组存储棋盘，操作方便。（4）算法的时空分析。该算法的运行时间和和皇后的放置方法成正比，在最好情况下的时间和空间复杂度均为O（1），在最差情况下均为O（n2），平均情况在它们之间，即（1+ n2）/2。主界面在Dos下运行程序，出现如下主界面。可以通过输入数字0、1、2加回车实现不同的目的，在此界面中可以得到位置标明法和视图显示法两种表示出所计算出的八皇后的摆放分布。图如4-2所示：图4-2：运行时主界面子界面1在主界面下输入数字1可以进入如下的子界面。下图为按每一行皇后所摆放的列的位置输出的结果的部分截图，如4-3所示：图4-3：子界面子界面2在主界面输入2时所进入的子界面。以视图的方式按矩阵方式输出八皇后摆放所得的结果。如图4-4所示：图4-4：按矩阵方式打印五设计总结通过该题的练习，使我们学会了由递归到非递归的转换以及回溯法的思想，而且可以分析它们的效率高低，什么时候用递归合理，什么时候不能用，这都是通过这次课程设计学到的。八皇后的问题经过小组讨论分析之后，我们便有了设计的思路，最终成功的设计出来。这次课设也让我懂得了编程时候一定要思维严谨。但这次的设计同时也有一些不足之处，如算法不算太简洁，还有一些基本的知识没有完全掌握等等，这些为我以后的学习提供了教训，相信以后我能够做得更好。参考文献1数据结构程序设计题典李春葆等编 清华大学出版社2数据结构(C语言版) 黄国瑜 叶乃菁编 清华大学出版社3数据结构课程设计苏仕华 等编 机械工业出版社附录#include<iostream>using namespace std;int a8,b24,c24,d24;int i, k,g1=0,g2=0;void print1() g1+;cout<<"t第"<<g1<<"种情况: "for (k=1;k<9;k+)cout<<" "<<" "<<ak;cout<<"n"void print2() int t,n;g2+;cout<<"t第"<<g2<<"种情况: nt"for (k=1;k<9;k+) n=ak; for(t=1;t<n;t+)cout<<"0 " cout<<"1 " t+; for(t;t<9;t+)cout<<"0 " cout<<"nt"cout<<"n"void JudgeQueen1(int i)int j;for (j=1;j<9;j+)/每个皇后都有8种可能位置if (bj=0) &&(ci+j=0)&& (di-j=0)/判断位置是否冲突ai=j;/摆放皇后bj=1;/宣布占领第J行ci+j=1;/占领两个对角线di-j=1;if (i<8) JudgeQueen1(i+1);/8个皇后没有摆完，递归摆放下一皇后else print1();/完成任务，打印结果bj=0;/回溯ci+j=0;di-j=0;void JudgeQueen2(int i)int j ,e=1;for (j=1;j<9;j+)/每个皇后都有8种可能位置if (bj=0) &&(ci+j=0)&& (di-j=0)/判断位置是否冲突ai=j;/摆放皇后bj=1;/宣布占领第J行ci+j=1;/占领两个对角线di-j=1;if (i<8) JudgeQueen2(i+1);/8个皇后没有摆完，递归摆放下一皇后elseprint2();/完成任务，打印结果bj=0;/回溯ci+j=0;di-j=0;e+;void main()int choice,e=1;char ch;cout<<"nnt * 欢迎使用八皇后问题查询软件 *nn"for( k=0;k<24;k+)/数据初始化 bk=0;ck=0;dk=0;ch='y'while(ch='y'|ch='Y') cout<<"nt 查 询 菜 单n" cout<<"nt*" cout<<"nt* 1-位置标明法 *" cout<<"nt* 2-视图显示法 *" cout<<"nt* 0-退 出 *" cout<<"nt*" cout<<"nn请选择菜单号(0-2)：" cin>>choice; switch(choice) case 1:cout<<"nt每一行皇后放置的列数的情况nn"JudgeQueen1(1);/从第1个皇后开始放置break; case 2:cout<<"nt使用回车查看下一种情况（共92种）nn"JudgeQueen2(1);/从第1个皇后开始放置break; case 0:ch='n'break; default:cout<<"ntt菜单选择错误，请重新输入!n"