数据结构实验报告利用栈结构实现八皇后问题.doc

《数据结构实验报告利用栈结构实现八皇后问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构实验报告实验名称：实验二——利用栈结构实现八皇后问题学生姓名：班级：班内序号：学号：日期：2013年11月21日1．实验要求（1）实验目的通过选择下面五个题目之一进行实现，掌握如下内容：Ø进一步掌握指针、模板类、异常处理的使用Ø掌握栈的操作的实现方法Ø掌握队列的操作的实现方法Ø学习使用栈解决实际问题的能力Ø学习使用队列解决实际问题的能力（2）实验内容利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同

2、一斜线上。请设计算法打印所有可能的摆放方法。①可以使用递归或非递归两种方法实现②实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。（3）代码要求①必须要有异常处理，比如删除空链表时需要抛出异常；②保持良好的编程的风格：Ø代码段与段之间要有空行和缩近Ø标识符名称应该与其代表的意义一致Ø函数名之前应该添加注释说明该函数的功能Ø关键代码应说明其功能③递归程序注意调用的过程，防止栈溢出2.程序分析2.1存储结构栈（递归）：2.2关键算法分析(1)递归voidSeqStack::PlaceQueen(introw)//在栈顶

3、放置符合条件的值的操作,即摆放皇后{for(intcol=0;col::Judgement(){for(int

4、i=0;i

5、

6、(abs(data[top]-data[i]))==(top-i))//判断是否在同一列同一斜线returnfalse;returntrue;}算法步骤：①对于一个坐标，将前面每一个坐标均与这个坐标比较②若在同一列或在同一斜线上，则返回0，③否则j自增1，面每一个坐标与前面做比较④若与前面坐标在同一列⑤最后返回trueorfalse.2.3其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大，最后只显示60种到92种，这

7、需要适当的设置对话框，设置步骤为：属性—屏幕缓冲区高度设为相对大些的值（1000或其他），即可显示所有结果。也可适当完善代码将结果输出到一个文档里，便于观察分析。3.程序运行结果实验流程图：开始输入n判断是否满行q[k]=ians++YN输出结果判断位置是否符合要求NYrow++实验结果：4.总结总结：这次实验让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，让我学会了运用递归算法去解决一些复杂的问题改进：不仅可以设计放置八皇后，也可以是9皇后，10皇后，只要修改N；也可以尝试采用二维数组的思想来实现。