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