王小丫数据结构课程设计报告

王小丫数据结构课程报告 课设课题: 数 据 结 构 ?? N皇后(八皇后) 学 院: 电 子 信 息 学 院 专 业: 计 算 机 科 学 与 技 术 姓 名: 班 级: 指导老师: 报告日期: 年 月 制 数据结构课程设计??N皇后/八皇后 目 录 一、设计目的„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„4 二、课程设计基本要求„„„„„„„„„„„„„„„„„„„„„„„„„„„„„4 三、课程设计内容及安排„„„„„„„„„„„„„„„„„„„„„„„„„„„„4 四、八皇后背景知识„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„5 五、八皇后问题的实现„„„„„„„„„„„„„„„„„„„„„„„„„„„„„6 5.1、递归方法解八皇后问题„„„„„„„„„„„„„„„„„„„„„„„„„6 5.1.1、递归介绍„„„„„„„„„„„„„„„„„„„„„„„„„„„„7 5.1.2、使用到的函数和变量„„„„„„„„„„„„„„„„„„„„„„„8 5.1.3、具体运行结果„„„„„„„„„„„„„„„„„„„„„„„„„10 5.1.4、算法流程图„„„„„„„„„„„„„„„„„„„„„„„„„„11 递归算法代码„„„„„„„„„„„„„„„„„„„„„„„„„12 5.1.5、 5.1.6、算法分析„„„„„„„„„„„„„„„„„„„„„„„„„„„13 5.2、回溯法解决八皇后问题„„„„„„„„„„„„„„„„„„„„„„„„„13 5.2.1、回溯法介绍„„„„„„„„„„„„„„„„„„„„„„„„„„13 5.2.2、使用到的函数与变量„„„„„„„„„„„„„„„„„„„„„„14 5.2.3、具体运行结果„„„„„„„„„„„„„„„„„„„„„„„„„15 5.2.4、算法流程图„„„„„„„„„„„„„„„„„„„„„„„„„„16 5.2.5、回溯算法代码„„„„„„„„„„„„„„„„„„„„„„„„„17 5.2.6、算法分析„„„„„„„„„„„„„„„„„„„„„„„„„„„18 5.3、堆栈法解八皇后问题„„„„„„„„„„„„„„„„„„„„„„„„„„18 5.3.1、堆栈法介绍„„„„„„„„„„„„„„„„„„„„„„„„„„18 5.3.2、使用到的函数与变量„„„„„„„„„„„„„„„„„„„„„„19 5.3.3、具体运行过程„„„„„„„„„„„„„„„„„„„„„„„„„20 5.3.4、算法流程图„„„„„„„„„„„„„„„„„„„„„„„„„„21 5.3.5、堆栈法实现的源代码„„„„„„„„„„„„„„„„„„„„„„21 龚辉 2 数据结构课程设计??N皇后/八皇后 5.3.6、算法分析„„„„„„„„„„„„„„„„„„„„„„„„„„„25 5.4、三种算法的比较„„„„„„„„„„„„„„„„„„„„„„„„„„„„25 5.5、八皇后问题所有输出结果„„„„„„„„„„„„„„„„„„„„„„„„26 六、N皇后问题的实现„„„„„„„„„„„„„„„„„„„„„„„„„„„„„30 6.1、N皇后问题介绍„„„„„„„„„„„„„„„„„„„„„„„„„„„„30 6.2、使用到的函数与变量„„„„„„„„„„„„„„„„„„„„„„„„„„30 6.3、具体的执行„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„31 6.4、算法流程图„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„31 6.5、N皇后的源代码„„„„„„„„„„„„„„„„„„„„„„„„„„„„32 6.6、算法分析„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„32 七、经验和体会„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„32 八、参考文献„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„32 九、附录„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„33 附录一:递归算法代码„„„„„„„„„„„„„„„„„„„„„„„„„„„34 附录二:回溯算法代码„„„„„„„„„„„„„„„„„„„„„„„„„„„34 附录三:堆栈法的源代码„„„„„„„„„„„„„„„„„„„„„„„„„„36 附录四:N皇后的源代码„„„„„„„„„„„„„„„„„„„„„„„„„„39 龚辉 3 数据结构课程设计??N皇后/八皇后 一、设计目的 《数据结构》是一门实践性较强的软件基础课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 二、课程设计基本要求 1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力; 2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力; 4、训练用系统的观点和软件开发一般进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5、设计的题目要求达到一定工作量(300行以上代码)，并具有一定的深度和难度。 6、编写出课程设计说明书，说明书不少于10页(代码不算)。 三、课程设计内容 1、问题分析和任务定义:根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么,(而不是怎么做,)限制条件是什么, 2、逻辑设计:对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图; 3、详细设计:定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架; 4、程序编码:把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚; 龚辉 4 数据结构课程设计??N皇后/八皇后 5、程序调试与测试:采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果; 6、结果分析:程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析; 7、编写课程设计报告; 四、八皇后背景知识 国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动;也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢,这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后”问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗,如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。 让我们先从四皇后谈起。若要在如图1所示的4×4棋盘中，放置四个互不攻击的皇后，可以如下从上到下逐行地考虑:当然在每行中只能放置一个而且必须放置一个皇后，问题是每行中的皇后应放在第几列, 图1 图2 如果第一行的皇后放置在第一列，第二行的皇后就不能放置在第一、二列，只能放置在第三列或第四列。如果第二行的皇后放置在第三列，那第三行的皇后就没有安身‎‎之处了。那么暂且把第二行的皇后放在第四列，看看情况如何。这时，第三行的皇后可以放在第二列(见图2)。然而，第四行的皇后仍然无家可归～要放置好第四个皇后，必须对前几个皇后的位置予以修正。 前面已经说过，第三行以至于第二行的所有位置均已考虑过了，只得考虑让第一行的皇后挪一下。如果把第一行的皇后放在第二列，第二行的皇后放在第四列上‎‎，第三行的皇后放在第一列上，第四行的皇后放在第三列上，正好四个皇后互不攻击(见图3a)。如果继续这样逐行逐列地考虑下去，还可以找到四皇后问题地另一个解答(见图3b)。 龚辉 5 数据结构课程设计??N皇后/八皇后 图3 对于八皇后问题，也可如此解决:从上到下每行放一个皇后;在每一行中均从左至右逐列试放。能放则放(继续考虑下一行)不能放则换(列数加1)换不成则退(退回前一行，让前一皇后所在列数加1后继续考虑)，这就是探索八皇后解答的途径。 为了记住在探索过程中每行皇后放置的位置就需要用栈。我们可用数组T来作栈;在T(P)中存放第P行皇后所在的列数。例如在第1行的皇后放在第3列，则可置T(1)=3。对于八皇后问题，如此安排后，数组T只需有八个分量就够了。 由于我们在每行中只放一个皇后，故而皇后之间保证不会左右相互攻击了;那么如何检查它们是否在上下或斜线方向相互攻击呢, 我们用一个数组C来每一列上是否放了皇后，不管在哪一行上的第1列上放了一个皇后，就令C(1)=1，...。若把放在第1列上的皇后取走放到别的位置上去了，那么再令C(1)=0,...。这样，只要查看C(I)是否为零，就可以知道第I列上是否可以放置皇后了～显然，八皇后问题中的数组C也只需八个分量就可以了。 在8×8的国际象棋棋盘上，有15条从左上走向右下的斜线，称为主斜线(如图4中左图);同样有15条从右上走向左下的斜线，称为副斜线。由于每放一个皇后，它所在的两条斜线上就不能再放皇后了。我们可以如同前面所述的那样，再引进两个数组S,M(每个数组有15个分量)，分别记录相应的主斜线和副斜线上是否已经放下了皇后。在图4中右图，若在第2行第3列放了一个皇后，则应令S(7)=1,M(4)=1,表示第7条主斜线，第4条副斜线上已有皇后，以后不能再放置了。因为，主对角线数7可由8，行数,列数,8+2-3=7计算得到，副斜线数4可由行数，列数,1,2+3-1,4计算得到。所以一般地说，在第P行，第T(P)列放置皇后以后，应该令:C(T(P))=1;S(8+P-T(P))=1;M(P+T(P)-1)=1。有了以上准备知识，就能为八皇后问题写算法了 五、八皇后问题的实现 5.1、递归方法解八皇后问题 5.1.1、递归的介绍 调用子程序的含义: 龚辉 6 数据结构课程设计??N皇后/八皇后 在过程和函数的学习中，我们知道调用子程序的一般形式是:主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是: 当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，跳转到子程序A(为了说得简单些，我这里忽略了参数传递这个过程)。 当子程序A执行到调用子程序B语句时，系统作法如上，跳转到子程序B。 子程序B执行完所有语句后，跳转回子程序A调用子程序B语句的下一条语句(我这又忽略了返回值处理) 子程序A执行完后，跳转回主程序调用子程序A语句的下一条语句 主程序执行到结束。 做个比较:我在吃饭(执行主程序)吃到一半时，某人叫我(执行子程序A)，话正说到一半，电话又响了起来(执行子程序B)，我只要先接完电话，再和某人把话说完，最后把饭吃完 认识递归函数 我们在高中时都学过数学归纳法，例: 求 n～ 我们可以把n～这么定义 也就是说要求3～，我们必须先求出2～，要求2～，必须先求1～，要求1～，就必须先求 0～，而0!=1，所以1!=0!*1=1，再进而求2!，3!。分别用函数表示，则如图: 我们可以观察到，除计算0～子程序外，其他的子程序基本相似，我们可以设计这么一个子程序: int factorial(int i){ int res; res=factorial(I-1)*i; 龚辉 7 数据结构课程设计??N皇后/八皇后 return res; } 那么当执行主程序语句s=factorial(3)时，就会执行factorial(3),但在执行factorial(3)，又会调用factorial(2)，这时大家要注意，factorial(3)和factorial(2)虽然是同一个代码段，但在内存中它的数据区是两份～而执行factorial(2)时又会调用factorial(1)，执行factorial(1)时又会调用factorial(0)，每调用一次factorial函数，它就会在内存中新增一个数据区，那么这些复制了多份的函数大家可以把它看成是多个不同名的函数来理解; 但我们这个函数有点问题，在执行factorial(0)时，它又会调用factorial(,1)。。。造成死循环，也就是说，在factorial函数中，我们要在适当的时候保证不再调用该函数，也就是不执行res=factorial(I-1)*i;这条调用语句。所以函数要改成: int factorial(int i){ int res; if (I>0) res=factorial(I-1)*i; else res=1; return res; } 那么求3!的实际执行过程如图所示: 5.1.2、使用到的函数和变量 在这个算法中共有六个函数， 除了Main()主函数，还有IsVa lid(int n)，Output()，Queen(int n)， 变量icount，Site这些组成程序， 龚辉 8 数据结构课程设计??N皇后/八皇后 红框圈出的是递归函数的应用，既自己调用自己在Queen(int n)中调用queen是典型的 递归调用。 编译没有错误 龚辉 9 数据结构课程设计??N皇后/八皇后 5.1.3、具体运行结果 龚辉 10 数据结构课程设计??N皇后/八皇后 运行结果表示出有92种可能性 5.1.4、算法流程图 递归的图解演示 龚辉 11 数据结构课程设计??N皇后/八皇后 5.1.5、程序代码见附录一 5.1.6、算法分析 递归是一种很古老的算法，其应用的也十分的广泛，在和多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。 递归的优点是:编写简单，缺点是:消耗资源大。 八皇后问题是一个经典的数据结构问题用递归是最为常见的方法，由于递归是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。 该算法中所有语句的频度之和(即算法的时间耗费)为: 32 T(n)=2n+3n+2n+1 3当n趋向于无穷时，其时间复杂度为O(n)。 5.2、回溯法解决八皇后问题 5.2.1、回溯法介绍 在计算机奥赛中，有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但 因为它花费的时是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，间比较长。 回溯法的基本思想 对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况;从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解(并不一定是完整的，事实上这也就是构造约束函数的意义所在)与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。 回溯法中，首先需要明确下面三个概念: (一)约束函数:约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。 (二)状态空间树:刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。 (三)扩展节点、活结点、死结点:所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点;死结点反之。由此很容易知道死结点是不必求出其子节点的(没有意义)。 深度优先搜索(DFS)和广度优先搜索(FIFO) 在分支界限法中，一般用的是FIFO或最小耗费搜索;其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列。通过遍历这个队列(队列在遍历过程中不断增长)完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径。而在回溯法中，一般都用DFS。为什么呢,这是因为可以通过约束函数杀死一些节点从 龚辉 12 数据结构课程设计??N皇后/八皇后 而节省时间，由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。FIFO理论上也是可以做到这样的，但是通过对比不难发现，DFS在以这种方法解决问题时思路要清晰非常多。 因此，回溯法可以被认为是一个有过剪枝的DFS过程。 利用回溯法解题的具体步骤 首先，要通过读题完成下面三个步骤: (1) 描述解的形式，定义一个解空间，它包含问题的所有解。 (2) 构造状态空间树。 (3) 构造约束函数(用于杀死节点)。 然后就要通过DFS思想完成回溯，完整过程如下: (1) 设置初始化的(给变量赋初值，读入已知数据等)。 (2) 变换方式去试探，若全部试完则转(7)。 (3) 判断此法是否成功(通过约束函数)，不成功则转(2)。 (4) 试探成功则前进一步再试探。 (5) 正确方案还未找到则转(2)。 (6) 已找到一种方案则记录并打印。 (7) 退回一步(回溯)，若未退到头则转(2)。 (8) 已退到头则结束或打印无解。 回溯法的数据结构 回溯法的状态空间树，在计算机上的数据结构有两种表示方法。当用k表示树的节点层数，n表示节点总数，m表示解的总数时: (一) 用m个k元组表示m种不同的解。其中，每组中的元素是[1,n]中的一个元素。在Pascal中，可以这样定义变量: var a:array[1..k,1..m]of integer;(integer可以依n的范围决定) (二) m个n元组表示m种不同的解。因为所有的节点都包含在每个解的表示中，每组中的元素只有两种情况，被选用和不被选用。在Pascal中，可以这样定义变量: var a:array[1..n,1..m]of boolean; 这两种数据结构的解空间最多都含有2n个不同的元组 5.2.2、使用到的函数与变量 回溯发是很好的算法，在所有算发中 空间复杂度是最小的，其只有一个主函数 main()，和一个变量total，就可以成功的解 决八皇后问题，我本人对于这种算法非常 的推崇，也觉的是所有解决了八皇后问题 中最好的。 龚辉 13 数据结构课程设计??N皇后/八皇后 编译没有错误 5.2.3、具体运行结果 龚辉 14 数据结构课程设计??N皇后/八皇后 运行结果如图 5.2.4、算法流程图 回溯算法的图解 龚辉 15 数据结构课程设计??N皇后/八皇后 5.2.5、程序代码见附录二 5.2.6、算法分析 回溯是一个很好的算法，其应用的也十分的广泛，在和多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。 回溯的优点是:编写复杂，缺点是:消耗资源小。 八皇后问题是一个经典的数据结构问题用回溯是最为常见的方法，由于回溯是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。 该算法中所有语句的频度之和(即算法的时间耗费)为: 2+1 T(n)=2n 2+1 分析:当n趋向于无穷时，其时间复杂度为O(n+2)。 5.3、堆栈法解八皇后问题 5.3.1、堆栈法介绍 堆栈的概念 堆栈(Stack)是一种比较重要的线性数据结构，如果对数据结构知识不是很了解的话，我们可以把它简单的看作一维数组。但是对一维数组进行元素的插入、删除操作时，可以在任何位置进行，而对于栈来说，插入、删除操作是固定在一端进行‎‎的，这一端称为栈顶(top)，另一端称为栈底(bottom)，向栈中插入数据的操作称为压入(Push)，从栈中删除数据称为弹出(Pop)。 堆栈的存储方式 二 对栈中元素的操作是按后进先出(Last In First Out,简称LIFO)的原则进行的，即最后压入的元素最先弹出。 在栈的操作过程中，有一个永远指向栈顶的栈顶指针，在压入和弹出数据时，栈顶指针向上或向下移动。当栈顶指针为零时(即指向栈底的后面)，栈为空栈。如果压入的数据过多超出了栈的最大空间，则发生栈上溢。 在程序设计中，我们可以使用一维数组实现对栈的操作。假设用一维数组s[1..arrmax]表示栈，则对于非空栈，s[1]为最早压入栈的元素，同时设栈顶指针top，则s[top]为最后压入栈的元素。当top=arrmax时栈满，若此时有数据入栈将产生“数组越界”的错误，极为栈上溢，反之当top=0,意为栈空。 龚辉 16 数据结构课程设计??N皇后/八皇后 5.3.2、使用到的函数与变量 组成的程序的函数有:DeSetQueen(int row，int col)，DisplayAndSet()，main()，NoConf lict(int row,int col)，Pop()，Push(int row，int col)， Queen()，SetQueen(int row，int col)，变量有: ArrayQueen,OutQueen,Top 。 没有编译错误 5.3.3、具体运行过程 龚辉 17 数据结构课程设计??N皇后/八皇后 运行结果放在queen.txt文件中 八皇后问题的源代码 运行在queen.txt文件中的92种结果 龚辉 18 数据结构课程设计??N皇后/八皇后 5.3.4、算法流程图 5.3.5、程序代码见附录三 5.3.6、算法分析 堆栈是一个很好的算法，其应用的也十分的广泛，在和多复杂的程序中也是经常性的使用，虽然其的程序编写相对的简单，但其确消耗很多的资源，在没有好的算法的前提下，这是相对能够运行的算法，当然这也是在编程着能够拥有一定的编写能力的基础上的。 堆栈的优点是:算法比较的平均，运行十分的复杂。 八皇后问题是一个经典的数据结构问题用递归是最为常见的方法，由于递归是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。 该算法中所有语句的频度之和(即算法的时间耗费)为: n T(n)=2n+1 2 分析:当n趋向于无穷时，其时间复杂度为O(n+1)。 龚辉 19 数据结构课程设计??N皇后/八皇后 5.4、三种算法的比较 递归简单，但消耗资源。 回溯比较的复杂，但消耗资源少。 堆栈比较的平均 5.5、八皇后问题所有输出结果为(8×8棋盘): 第1种情况: 第2种情况: 第3种情况: Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * * * * * * * Q * * * * * Q * * * * Q * * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * Q * * * * * * * * * * Q * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * 第4种情况: 第5种情况: 第6种情况: Q * * * * * * * * * * * * Q * * * * * Q * * * * * * * * Q * * * Q * * * * * * * Q * * * * * * * * * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * * Q * * * Q * * * * * * * * * * * * * Q * * Q * * * * * * * * * * * * Q * Q * * * * * * * * * * * * Q * * * Q * * * * * * * * * * * Q * * Q * * * * * * * * * * * * Q * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * 第7种情况: 第8种情况: 第9种情况: * * * * Q * * * * * Q * * * * * * * * * Q * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * Q * * * Q * * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * Q * * * * * 龚辉 20 数据结构课程设计??N皇后/八皇后 第10种情况: 第11种情况: 第12种情况: * * * * * * Q * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * * * * * Q * * * * * Q * * * * * * * * * Q * * * * * Q * * * * Q * * * * * * * * * * Q * * * * * Q * * * * * * * * * * Q * * * Q * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * Q * * * * * * Q * * * * * Q * * * * * * 第13种情况: 第14种情况: 第15种情况: * Q * * * * * * * * * * Q * * * * * * * * * * Q * * * * * Q * * * * Q * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * * Q * * * * Q * * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * Q * * * * 第16种情况: 第17种情况: 第18种情况: * * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * Q * * * * * * * Q * Q * * * * * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * Q * * * * * * * * * Q * * * 第19种情况: 第20种情况: 第21种情况: * * * * Q * * * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * * * * Q * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * * * Q * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * Q * * * 龚辉 21 数据结构课程设计??N皇后/八皇后 第22种情况: 第23种情况: 第24种情况: * * * * * * * Q * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * Q * * * * * * * * Q * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * Q * * * * * 第25种情况: 第26种情况: 第27种情况: * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * Q * * * * * * Q * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * * * * Q * * * * * * Q * * * * * * * * * Q * * * * Q * * * * * * * * * * Q * Q * * * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * * 第28种情况: 第29种情况: 第30种情况: * * * * Q * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * Q * * * * * * * * * * Q Q * * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * Q * * * * Q * * * * * * Q * * * * * * * * * Q * * * * * * * * Q * * Q * * * * * * * * * Q * * * * * * * Q * * * * 第31种情况: 第32种情况: 第33种情况: * * * * * Q * * * * * * * * Q * * * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * Q * * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * Q * * * * * * * Q * * 龚辉 22 数据结构课程设计??N皇后/八皇后 第34种情况: 第35种情况: 第36种情况: * * * * Q * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * Q * * * * * * Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * Q * * * * Q * * * * * * * Q * * * * * 第37种情况: 第38种情况: 第39种情况: * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * Q * * * * * * * * Q * * * * * * * Q * * * * Q * * * * * * * Q * * * * * 第40种情况: 第41种情况: 第42种情况: * * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * * Q * * * * * * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * * * Q * * * * Q * * * * * * * * * * * Q * * * * * * * * Q * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q 第43种情况: 第44种情况: 第45种情况: * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * Q Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * * Q * * * Q * * * * * * * * * Q * * * * * * Q * * * * * * * * * Q * * Q * * * * * * * * * * * * Q * * * * * Q * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * 龚辉 23 数据结构课程设计??N皇后/八皇后 第46种情况: 第47种情况: 第48种情况: * * * * Q * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * Q * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * * * Q * * * Q * * * * * * * * * * * Q * * * * * Q * * * * * * * * Q * * * * * * Q * * * Q * * * * * * * * * * Q * * * * * Q * * * * * 第49种情况: 第50种情况: 第51种情况: * Q * * * * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * Q * * * * * * Q * * * * * * * * * * Q * * Q * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * * * Q * * * Q * * * * * * Q * * * * * * * * * Q * * * * * * * * Q * * 第52种情况: 第53种情况: 第54种情况: * * * Q * * * * * * * Q * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * * * * Q * * * * * * Q * * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * * Q * * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * * * * Q * * * * * * Q * * * Q * * * * * * * * * Q * * * 第55种情况: 第56种情况: 第57种情况: * * Q * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * * * Q * * * Q * * * * * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * * Q * * * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * 龚辉 24 数据结构课程设计??N皇后/八皇后 第58种情况: 第59种情况: 第60种情况: * * Q * * * * * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * * * Q * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * * * * * Q 第61种情况: 第62种情况: 第63种情况: * * * * * Q * * * * * Q * * * * * * * Q * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * Q * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * * * * Q * * * Q * * * * * * 第64种情况: 第65种情况: 第66种情况: * * * Q * * * * * Q * * * * * * * * * Q * * * * * * * * * Q * * * * * Q * * * * * Q * * * * * * * * * * * * * Q * * * * * Q * * * * * * Q * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * * * * Q * * * Q * * * * * * Q * * * * * * * * * * Q * * * * * * * * * Q * 第67种情况: 第68种情况: 第69种情况: * * * Q * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * * Q * * * * * * * * * * Q Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * Q * * * * 龚辉 25 数据结构课程设计??N皇后/八皇后 第70种情况: 第71种情况: 第72种情况: * * Q * * * * * * * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * Q * * * * * * * Q * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * * Q * * * Q * * * * * * * * * * * Q * * * Q * * * * * * * * * * * Q * * * Q * * * * 第73种情况: 第74种情况: 第75种情况: * * * * * * Q * * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * * Q * * * Q * * * * * * * * * * * Q * * * * * Q * * * * * * * * * Q Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * * Q * * 第76种情况: 第77种情况: 第78种情况: * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * Q * * * * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * Q * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * * * Q * * * * * * Q * * * * Q * * * * * * * * * Q * * * * * * Q * * * * * * * * * * * Q 第79种情况: 第80种情况: 第81种情况: * * * Q * * * * * * * * Q * * * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * Q * * * * * * Q * * * * * * * * * Q * * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * * * * * * * Q Q * * * * * * * Q * * * * * * * * * * * Q * * * * * Q * * * * * * * * * * Q * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * 龚辉 26 数据结构课程设计??N皇后/八皇后 第82种情况: 第83种情况: 第84种情况: * * * Q * * * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * Q * * * * * Q * * * * * * * * Q * * * * * * * * * * Q * * * * * * * * * Q * * * * * Q * * * * * * * * * Q * * * * * Q * * * * * * * * * Q * * Q * * * * * * * * Q * * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * * * Q * * * * * * * * * Q * * * * * Q * * * 第85种情况: 第86种情况: 第87种情况: * * * * * Q * * * * * * * Q * * * * * * * Q * * * * * Q * * * * * * Q * * * * * * * Q * * * * * * Q * * * * * * * * * * * * Q * * * * * * * Q * * * * * * * * Q * Q * * * * * * * Q * * * * * * * * * * Q * * * * * * Q * * * * * * * * * * * Q * * * * * * Q * * * * * * * * Q * * * * Q * * * Q * * * * * * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * * Q * * * * * * Q * * * * 第88种情况: 第89种情况: 第90种情况: * * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * Q * * Q * * * * * * * Q * * * * * * * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * * * * Q * * Q * * * * * * * * * * * Q * * Q * * * * * * * * * * * Q * * * * Q * * * * * * * * * Q * * * * * * * * * * Q * * * * * * * Q Q * * * * * * * * * * * Q * * * * * * * * Q * * * * * * * Q * * Q * * * * * * * Q * * * * * * * 第91种情况: 第92种情况: * * Q * * * * * * * Q * * * * * * * * * Q * * * * * * * * Q * * * Q * * * * * * * * * Q * * * * * * * * * * * Q * Q * * * * * * * * * * * Q * * * * * * * * * Q * * * Q * * * * * * * * Q * * * * * * * * * Q * * * * * * * Q * Q * * * * * * * Q * * * * * * * 龚辉 27 数据结构课程设计??N皇后/八皇后 六、N皇后问题的实现 6.1、N皇后问题介绍 国际象棋中皇后威力很大，它可以象“车”一样沿直线上下或左右移动;也可以如同“象”那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢,这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了部分解答。高斯在棋盘上放下了N个互不攻击的皇后，他还认为可能有N种不同的放法，这就是有名的“N皇后”问题。现在我们已经知道N皇后问题有N个解答。那么你能试着找出几种方法吗,如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记忆有限，很可能在某个‎‎位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法则才行。 6.2、使用到的函数和变量 有函数:IsOK(int n)，main()，Queen(int n), 变量:count,queen,site 6.3、具体的执行 龚辉 28 数据结构课程设计??N皇后/八皇后 没有编译错误 在界面中输入皇后的数目 龚辉 29 数据结构课程设计??N皇后/八皇后 4皇后的执行结果 5皇后的执行结果 6皇后的执行结果 龚辉 30 数据结构课程设计??N皇后/八皇后 7皇后的执行结果 10皇后的执行结果 龚辉 31 数据结构课程设计??N皇后/八皇后 对于N皇后: 皇后 N 4 5 6 7 8 9 10 方案数 2 10 4 40 N 352 724 6.5、程序代码见附录四 6.6、算法分析 皇后问题是一个经典的数据结构问题用递归是最为常见的方法，由于递归是自己套自己，把八皇后问题的调用函数在代码界面上融合到了一个函数中。 该算法中所有语句的频度之和(即算法的时间耗费)为: 32 T(n)=2n+3n+2n+1 3当n趋向于无穷时，其时间复杂度为O(n+1)。 七、经验和体会 课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，单片机已经成为当今计算机应用中空前活跃的领域， 在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握单片机的开发技术是十分重要的。 回顾起此次数据结构课程设计，至今我仍感慨颇多，的确，从选题到定稿，从理论到实践，在整整两星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，一定把以前所学过的知识重新温故。 经过两个星期的上机实践学习，使我对数据结构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进;再有对数据结构的一些库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对数据结构中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。 通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习数据结构，还是其它的课程，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。 这次课程设计终于顺利完成了，在设计中遇到了很多编程问题，最后在张艳老师的辛勤指导下，终于游逆而解。同时，在老师的身上我学得到很多实用的知识，在次我表示感谢～同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢～ 龚辉 32 数据结构课程设计??N皇后/八皇后 八、参考文献 [1] 严蔚敏 吴伟民编著 《数据结构》 清华大学出版社，2000 [2] 黄国瑜 叶乃菁编著 《数据结构》 清华大学出版社，2001 [3] 胡学钢编著 《数据结构算法设计指导》 清华大学出版社，1999 [4] 王士元编著 《数据结构与数据库系统》 南开大学出版社，2000 [5] 李强根主编 《数据结构,C++ 描述,》 中国水利水电出版社， 2001 [6] 杨正宏编著 《数据结构》 中国铁道出版社，2002 [7] 胡学钢编著 《数据结构算法设计指导》 清华大学出版社，1999 [8] 殷人昆 徐孝凯编著 《数据结构习题解析》 清华大学出版社，2002 [9] 李春葆编著 《数据结构习题与解析》 清华大学出版社，2001 [10] 咨讯教育小组编著 《数据结构数据结构版》 中国铁道出版社，2002 九、附录 附录一:递归算法代码: #include include # #include #include #include #define QUEENS 8 int iCount = 0; //!记录解的序号的全局变量。 int Site[QUEENS]; //!记录皇后在各列上的放置位置的全局数组。 void Queen(int n); //!递归求解的函数。 void Output();//!输出一个解。 int IsValid(int n); //!判断第n个皇后放上去之后，是否有冲突。 void main() /*----------------------------Main:主函数。----------------------------*/ { system("title 龚辉——递归算法八皇后问题 "); Queen(0); //!从第0列开始递归试探。 getch();//!按任意键返回。 } void Queen(int n) /*-----------------Queen:递归放置第n个皇后，程序的核心!----------------*/ { int i; if(n == QUEENS) //!参数n从0开始，等于8时便试出了一个解，将它输出并回溯。 { Output(); return; } for(i = 1 ; i <= QUEENS ; i++) //!n还没到8，在第n列的各个行上依次试探。 龚辉 33 数据结构课程设计??N皇后/八皇后 { Site[n] = i; //!在该列的第i行上放置皇后。 if(IsValid(n)) //!如果放置没有冲突，就开始下一列的试探。 Queen(n + 1); } } int IsValid(int n) /*------IsValid:判断第n个皇后放上去之后，是否合法，即是否无冲突。------*/ { int i; for(i = 0 ; i < n ; i++) / /!将第n个皇后的位置依次于前面n,1个皇后的位置比较。 { if(Site[i] == Site[n]) //!两个皇后在同一行上，返回0。 return 0; if(abs(Site[i] - Site[n]) == (n - i)) //!两个皇后在同一对角线上，返回0。 return 0; } return 1; //!没有冲突，返回1。 } void Output()/*------------Output:输出一个解，即一种没有冲突的放置方案。------------*/ { int i; printf("No.%-5d" , ++iCount); //!输出序号。 for(i = 0 ; i < QUEENS ; i++)//!依次输出各个列上的皇后的位置，即所在的行数。 printf("%d " , Site[i]); printf("\n"); } 附录二:回溯算法代码 #include # include using namespace std; int total = 0; //方案计数 void main(){ int queen[8]; int i, j, k; for (i=0;i<8;i++) queen[i] = 0; //八皇后全放在第0列 for (i=1;;){ //首先安放第0行皇后 if(queen[i]<8){ //皇后还可调整 k=0; //检查与第k个皇后是否互相攻击 while(k #include /*===定义栈与操作==------------------*/ struct Stack { Stack *top; int row; int col; }*Top; void Push(int row,int col); void Pop(); /*=====栈的定义完毕==---------------*/ #define MAXQUEEN 8 /*=======三个冲突数组确定是否能放置皇后 **///0表示无冲突，1表示有冲突 static int a[MAXQUEEN];//列冲突 static int b[MAXQUEEN*2-1];//主对角线冲突 static int c[MAXQUEEN*2-1];//副对角线冲突 static int d[MAXQUEEN]; 龚辉 35 数据结构课程设计??N皇后/八皇后 /*======**/ void SetQueen(int row,int col);//放置皇后后在该处设置冲突 void DeSetQueen(int row,int col); bool NoConflict(int row,int col);//判断该位置放置皇后 //是否与其他皇后冲突 // char ArrayQueen[MAXQUEEN][MAXQUEEN]; ofstream outQueen;//定义一个输出文件流 void DisplayAndSet(); // bool Queen(); // void main() { Top = new Stack; Top->top=NULL; outQueen.open("queen.txt",ios::out,filebuf::openprot); for(int x=0;x0)//控制结束 return true; if(precolrow[0]==MAXQUEEN) return false; } return true; } void SetQueen(int row,int col) { a[col]=1; b[row+col]=1; c[row-col+MAXQUEEN-1]=1; d[row]=1; 龚辉 37 数据结构课程设计??N皇后/八皇后 } void DeSetQueen(int row,int col) { a[col]=0; b[row+col]=0; c[row-col+MAXQUEEN-1]=0; d[row]=0; } bool NoConflict(int row,int col) { if(a[col]!=1&&b[row+col]!=1&&c[row-col+MAXQUEEN-1]!=1&&d[row]!=1) return true; return false; } void DisplayAndSet() { Stack *temp=Top->top; for(int x=0;xtop) ArrayQueen[temp->row][temp->col]='Q'; for( x=0;xtop; for(x=0;xtop) ArrayQueen[temp->row][temp->col]='*'; } void Push(int row,int col) { Stack *s = new Stack; s->row = row; s->col = col; s->top = Top->top; Top->top = s; } 龚辉 38 数据结构课程设计??N皇后/八皇后 void Pop() { if(Top->top!=NULL) { Stack *temp=Top->top; Top->top = temp->top; delete temp; } } : 附录四:N皇后的源代码 #include #include #include #include int *site; //每行的棋子所放置的位置，注意下标从0开始 int queen; //皇后的数目 int count=0; //第几种放置的可能性 //判断第n+1行的放置是否合适 int IsOk(int n) { int i; for(i=0;i