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

一 设计目的 1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉，也就是下一个皇后不能放的位置。 1 2 3 4 5 6 7 8 × × × × × × × × × × Q × × × × × × × × × × × × × × × 图2-1：摆放示意图 根据这个规则，我们可以利用一个函数来判断某个位置是否安全，安全的位置说明它所在的同一行、同一列或两条线上都没有放置过皇后，因此不会出现皇后互相攻击的情况；否则该位置不安全。其具体实现过程是找出所有放置的皇后，将他们的位置与该位置进行比较判断。又注意到同一行只能放一个皇后，因此，只需要对前面的各行逐行扫描皇后，就可以找出所有皇后的位置。 下图是其中一种摆放皇后的方法： Q Q Q Q Q Q Q Q 图2-2：一种摆放皇后的方法 三 设计要求 1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ 2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚5.程序调试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析7.编写课程设计这道题可以用递归循环的方法来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题。 （1冲突（包括行、列、两条对角线） 列：规定每一列放一个皇后，不会造成列上的冲突。 行：当第i行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以i为下标的标记置为被占领状态。 对角线：对角线有两个方向。在同一对角线上的所有点（设下标为（i,j）），要么（i+j）是常数，要么（i-j）是常数。因此，当第i个皇后占领了第j列后，要同时把以（i+j）、（i-j）为下标的标记置为被占领状态。 （2）数据结构 解数组A，A[i]表示第i个皇后放置的列，范围为1~8。 行冲突标记数组B，B[j]=0 表示第j行空闲，B[j]=1 表示第j行被占领，范围为1~8。 对角线冲突标记数组C、D。C[i-j]=0 表示第（i-j）条对角线空闲，C[i-j]=1 表示第（i-j）条对角线被占领，范围-7~7。D[i+j]=0 表示第（i+j）条对角线空闲，D[i+j]=1 表示第（i+j）条对角线被占领，范围2~16。void JudgeQueen1(int i) void JudgeQueen2(int i) a[i]表示第i个皇后放置的列，范围为1~8。行冲突标记数组，[j]=0 表示第j行空闲，[j]=1 表示第j行被占领，范围为1~8[i-j]=0 表示第（i-j）条对角线空闲，[i-j]=1 表示第（i-j）条对角线被占领，范围-7~7。D[i+j]=0 表示第（i+j）条对角线空闲，[i+j]=1 表示第（i+j）条对角线被占领，范围2~16。c[i+j]=0；d[i-j]=0；这三个语句