《数据结构课程设计N皇后八皇后》由会员分享，可在线阅读，更多相关《数据结构课程设计N皇后八皇后（39页珍藏版）》请在金锄头文库上搜索。
1、精品文档上 海 电 机 学 院 课 程 设 计 报 告课设课题： 数 据 结 构 N皇后八皇后 学 院： 电 子 信 息 学 院 1专 业： 计 算 机 科 学 与 技 术 1姓 名： 1班 级： 1指导老师： 1报告日期： 年 月 制目 录一、设计目的4二、课程设计根本要求4三、课程设计内容及安排4四、八皇后背景知识5五、八皇后问题的实现65.1、递归方法解八皇后问题6、递归介绍7、使用到的函数和变量8、具体运行结果10、算法流程图11、递归算法代码12、算法分析135.2、回溯法解决八皇后问题13、回溯法介绍13、使用到的函数与变量14、具体运行结果15、算法流程图16、回溯算法代码17、
2、算法分析185.3、堆栈法解八皇后问题18、堆栈法介绍18、使用到的函数与变量19、具体运行过程20、算法流程图21、堆栈法实现的源代码21、算法分析255.4、三种算法的比拟255.5、八皇后问题所有输出结果26六、N皇后问题的实现306.1、N皇后问题介绍306.2、使用到的函数与变量306.3、具体的执行316.4、算法流程图316.5、N皇后的源代码326.6、算法分析32七、经验和体会32八、参考文献32九、附录33附录一：递归算法代码34附录二：回溯算法代码34附录三：堆栈法的源代码36附录四：N皇后的源代码39一、设计目的?数据结构?是一门实践性较强的软件根底课程，为了学好这门课
3、程，必须在掌握理论知识的同时，加强上机实践。本课程设计的目的就是要到达理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养根本的、良好的程序设计技能。二、课程设计根本要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般标准进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、设计的题目要求到达一定工作量300行以上代码
4、，并具有一定的深度和难度。6、编写出课程设计说明书，说明书不少于10页代码不算。三、课程设计内容1、问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？而不是怎么做？限制条件是什么？ 2、逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原那么划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个根本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3、详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简
5、单和易于调试，抽象数据类型的实现尽可能做到数据封装，根本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和根本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4、程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时参加一些注解和断言，使程序中逻辑概念清楚；5、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6、结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果
6、。算法的时间、空间复杂性分析；7、编写课程设计报告；四、八皇后背景知识国际象棋中皇后威力很大，它可以象“车一样沿直线上下或左右移动；也可以如同“象那样沿着斜线移动。双方的皇后是不能在同一行或同一列或同一斜线上对持的。那么，在一张空白的国际象棋盘上最多可以放上几个皇后并且不让它们互相攻击呢？这个问题是伟大数学家高斯在十九世纪中期提出来的，并作了局部解答。高斯在棋盘上放下了八个互不攻击的皇后，他还认为可能有76种不同的放法，这就是有名的“八皇后问题。现在我们已经知道八皇后问题有92个解答。那么你能试着找出几种方法吗？如果你动手试试，就一定会发现开头几颗皇后很容易放置，越到后来就越困难。由于我们的记
7、忆有限，很可能在某个位置放过子后来证明不行取消了，但是以后又重新放上子去试探，这样就会不断地走弯路，花费大量的精力。因此，必须找到一个简易有效、有条不紊的法那么才行。让我们先从四皇后谈起。假设要在如图1所示的44棋盘中，放置四个互不攻击的皇后，可以如下从上到下逐行地考虑：当然在每行中只能放置一个而且必须放置一个皇后，问题是每行中的皇后应放在第几列？图1 图2如果第一行的皇后放置在第一列，第二行的皇后就不能放置在第一、二列，只能放置在第三列或第四列。如果第二行的皇后放置在第三列，那第三行的皇后就没有安身之处了。那么暂且把第二行的皇后放在第四列，看看情况如何。这时，第三行的皇后可以放在第二列见图2
8、。然而，第四行的皇后仍然无家可归！要放置好第四个皇后，必须对前几个皇后的位置予以修正。前面已经说过，第三行以至于第二行的所有位置均已考虑过了，只得考虑让第一行的皇后挪一下。如果把第一行的皇后放在第二列，第二行的皇后放在第四列上，第三行的皇后放在第一列上，第四行的皇后放在第三列上，正好四个皇后互不攻击见图3a。如果继续这样逐行逐列地考虑下去，还可以找到四皇后问题地另一个解答见图3b。图3对于八皇后问题，也可如此解决：从上到下每行放一个皇后；在每一行中均从左至右逐列试放。能放那么放继续考虑下一行不能放那么换列数加1换不成那么退退回前一行，让前一皇后所在列数加1后继续考虑，这就是探索八皇后解答的途径
9、。为了记住在探索过程中每行皇后放置的位置就需要用栈。我们可用数组T来作栈；在T(P)中存放第P行皇后所在的列数。例如在第1行的皇后放在第3列，那么可置T(1)=3。对于八皇后问题，如此安排后，数组T只需有八个分量就够了。由于我们在每行中只放一个皇后，故而皇后之间保证不会左右相互攻击了；那么如何检查它们是否在上下或斜线方向相互攻击呢？我们用一个数组C来记录每一列上是否放了皇后，不管在哪一行上的第1列上放了一个皇后，就令C(1)=1，.。假设把放在第1列上的皇后取走放到别的位置上去了，那么再令C(1)=0,.。这样，只要查看C(I)是否为零，就可以知道第I列上是否可以放置皇后了！显然，八皇后问题中
10、的数组C也只需八个分量就可以了。在88的国际象棋棋盘上，有15条从左上走向右下的斜线，称为主斜线如图4中左图；同样有15条从右上走向左下的斜线，称为副斜线。由于每放一个皇后，它所在的两条斜线上就不能再放皇后了。我们可以如同前面所述的那样，再引进两个数组S,M(每个数组有15个分量，分别记录相应的主斜线和副斜线上是否已经放下了皇后。在图4中右图，假设在第2行第3列放了一个皇后，那么应令S(7)=1,M(4)=1,表示第7条主斜线，第4条副斜线上已有皇后，以后不能再放置了。因为，主对角线数7可由8行数列数8+2-3=7计算得到，副斜线数4可由行数列数12+3-14计算得到。所以一般地说，在第P行，第T(P)列放置皇后以后，应该令：C(T(P)=1；S(8+P-T(P)=1；M(P+T(P)-1)=1。有了以上准备知识，就能为八皇后问题写算法了五、八皇后问题的实现5.1、递归方法解八皇后问题、递归的介绍调用子程序的含义：在过程和函数的学习中，我们知道调用子程序的一般形式是：主程序调用子程序A，子程序A调用子程序B，如图如示，这个过程实际上是：当主程序执行到调用子程序A语句时，系统保存一些必要的现场数据，跳转到子程序A为了说得简单些，我这里忽略了参数传递这个过
