数据结构课程设计(皇后问题)

《数据结构课程设计(皇后问题)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计报告课程名称数据结构课程设计课题名称皇后问题专业信息与计算科学班级信息科学1201学号201210010115姓名宋康指导教师　刘长松陈华光陈多2014年6月15日课程设计任务书课程名称数据结构课程设计课题皇后问题专业班级信息科学1201学生姓名宋康学号201210010115指导老师刘长松陈华光陈多审批任务书下达日期：2014年6月16日任务完成日期：2014年6月28日一、设计内容与设计要求1．设计内容：1）问题描述在N*N的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。 2）实现提示算法基

2、本思想：    从第1行起逐行放置皇后，每放置一个皇后均需要依次对第1.2，…，n列进行试探，并尽可能取小的列数。若当前试探的列位置是安全的，即不由于回溯求解的规则是“后进先出”，因此要用到栈。 2．设计要求：l课程设计报告规范1)需求分析a.程序的功能。b.输入输出的要求。2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计a.采用C语言定义相关的数据类型。b.写出各模块的类

3、C码算法。c.画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录a.参考书目b.源程序清单（带注释）l考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中

4、等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：①平时出勤（占10%）②系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）③程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）④设计报告（占30%）、注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。⑤独立完成情况（占10%）。l课程验收要求①运行所设计的系统。②回答有关问题。③提交课程设计报告纸质稿。④提交源程序、设计报告文档电子稿。⑤依内容的创新程度，完善程序情况及对程序讲解情况打分。二、进度

5、安排17周周一下午14：30-18：30信科1101.1102E51317周周三上午8：00-11：30信科1101.1102E51317周周五上午8：00-11：30信科1101.1102E513目录一、课题叙述61.1课题的来源61.2面对的问题6二、需求分析62.1功能需求6三、概要设计6四、详细设计和实现74.1算法描述及详细流程图74.2算法流程图8五、运行结果8六、结果分析99八、附录（源程序）10一、课题综述1.1课题的来源 八皇后问题是一个古老而著名的问题，该问题是十九世纪著名的数学家高斯1850年提出的。在国

6、际象棋中，皇后是最有权利的一个棋子；只要别的棋子在它的同一行或同一列或同一斜线（正斜线或反斜线）上时，它就能把对方棋子吃掉。所以高斯提出了一个问题：在8*8的格的国际象棋上摆放八个皇后，使其不能相互攻击，即任意两个皇后都不能处于同一列、同一行、或同一条斜线上面，问共有多少种解法。计算机发明后，将8后演变成n后，可以想到n的最小值应为4。 1.2 面对的问题1）   解决冲突问题：这个问题包括了行，列，两条对角线；列：规定每一列放一个皇后，不会造成列上的冲突；行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把

7、以I为下标的标记置为被占领状态；2） 使用数据结构的知识，用回溯法解决问题。 二、需求分析2.1功能需求    当运行程序时，在屏幕上显示每一种方法n个皇后的相对位置，要用比较直观 的界面显示。三、概要设计      最容易想到的方法就是有序地从第1列的第1行开始，尝试放上一个皇后，然后再尝试第2列的第几行能够放上一个皇后，如果第2列也放置成功，那么就继续放置第3列，如果此时第3列没有一行可以放置一个皇后，说明目前为止的尝试是无效的（即不可能得到最终解），那么此时就应该回溯到上一步（即第2步），将上一步（第2步）所放置的皇后的

8、位置再重新取走放在另一个符合要求的地方…如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。四、详细设计和实现4.1 算法描述及详细流程图1）编写限界函数boolPLACE(intk,intx[])，用以确定在k列上能否放置皇后；2）编写voidNQUEENS(intn)函数