北邮信通院数据结构实验二__八皇后问题实验报告(内附源代码完整版)

1、.数据结构实验报告实验名称 ： 实验二 八皇后问题学生姓名 ：班级：班内序号 ：学号：日期： 2014年11月27日1实验要求【实验目的 】进一步掌握指针、模板类 、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力【实验内容 】利用栈结构实现八皇后问题。八皇后问题19 世纪著名的数学家高斯于1850 年提出的 。 他的问题是 ：在 8*8 的棋盘上放置8 个皇后 ，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列 、同一斜线上 。 请设计算法打印所有可能的摆放方法。提示 ：1、可以使用递归或非递归两种方法实现2、实现

2、一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析.专业 .专注.2.1 存储结构存储结构 ：栈（递归）2.2 关键算法分析递归调用摆放皇后1、关键算法伪代码：（ 1 ） .如果输入的 row 大于皇后的数量 ，则输出皇后的位置（ 2 ） 否则 col 从 0 开始递增(3)检测 （ row ， col ）上的点是否符合条件，不符合则col 自增 ，符合则转到下一个皇后的排列2、代码详细分析：void SeqStack:PlaceQueen(int row)/ 摆放皇后.专业 .专注.for (int col=0;col n;col+)/ 遍历 07 ，Push(co

3、l);if (Check()/ 判断摆放皇后的位置是否合适if (row n-1)/ 若还没有放到最后一个，则进行下一个皇后的放置PlaceQueen(row+1);elsenum+;/ 计数器加1Print(n);/ 打印成功的坐标点Pop();/ 若不符合条件则出栈3、计算时间复杂度： O(n2) 判断皇后位置是否合适：1、 关键算法伪代码：.专业 .专注.对于一个坐标 ，将前面每一个坐标均与这个坐标比较若在同一列或在同一斜线上，则返回 0，否则 j 自增 1 ，面每一个坐标与前面做比较若与前面坐标在同一列最后返回2、 代码分析 ：bool SeqStack:Check()for(inti

4、=0;itop;i+)/ 依次检查前面已摆放的皇后位置if(datatop=datai|(abs(datatop-datai)=(top-i)/ 判断是否在同一列同一斜线return false;return true;3、 时间复杂度 ： O(n)2.3 其他说明 ：由于输出显示时对话框有限，而程序结果比较多，占用空间大,运用输出坐标位置来表示 ，则可以输出全部解。3. 程序运行结果（ 1）程序框图 ：.专业 .专注.开始输入 nY判断是否满行输出结果N判断位置 qrowNcol+是否符合要求Yqrow=colrow+(2)程序代码 ：#include using namespace std

5、;const int m=1024;/ 定义栈的最大高度int num=0;/ 初始化方案种类计数器int n;/ 摆放的皇后个数class SeqStack/ 定义.专业 .专注.顺序栈public:SeqStack()top=-1;/ 构造函数，初始化空栈void Push(int x);/ 入栈void Pop();/ 出栈void PlaceQueen(int row);/ 摆放皇后的递归函数boolCheck();/ 判断是否在同一行同一列同一斜线void Print(int n);/ 打印以坐标的形式bool Empty();/ 判别栈是否为空private:int datam;/

6、 定义数组int top;/ 栈顶指针;void SeqStack:Push(int x)/ 入栈操作.专业 .专注.if(top= m-1) throw 上溢 ;top+;/ 栈顶指针上移datatop=x;void SeqStack:Pop()/ 出栈操作if(Empty() throw 下溢 ;top-;/ 栈顶指针下移void SeqStack:PlaceQueen(int row)/ 摆放皇后for (int col=0;col n;col+)/ 遍历 07 ，Push(col);if (Check()/ 判断摆放皇.专业 .专注.后的位置是否合适if(rown-1)/ 若还没有放到

7、最后一个 ，则进行下一个皇后的放置PlaceQueen(row+1);elsenum+;/ 计数器加 1Print(n);/ 打印成功的坐标点Pop();/ 若不符合条件则出栈bool SeqStack:Empty()if(top=-1)return true;.专业 .专注.elsereturn false;bool SeqStack:Check()for(inti=0;itop;i+)/ 依次检查前面已摆放的皇后位置if(datatop=datai|(abs(datatop-datai)=(top-i)/ 判断是否在同一列同一斜线return false;return true;void

8、SeqStack:Print(int n)/ 将栈的数组形式打印成坐标int i;for(i=1;i=n;i+)cout(i,datai-1+1);coutendl;.专业 .专注.void main() cout0 ）n;if(n1024)cout 输入错误 endl;SeqStack Queen;/ 定义类的对象Queen.PlaceQueen(0);/ 从栈底开始赋值coutQueen可能的摆放位置种类:numendl;/ 输出摆放方法的总数（ 3）运行结果 ：.专业 .专注.专业 .专注.专业 .专注.4. 总结调试时出现的问题： 最初由于递归的思想未能很好掌握，导致几次调试都出现比较严重的错误 ；且在运用该方法时，未能将八皇后问题的具体思路搞清，没有考虑 “如果前次的皇后放置错误导致后面的放置无论如何都不能满足要求，在设计递归算法总是只显示几种，为了将 92 种情形全部打印，采用坐标的形式。使用了栈的存储结构来存储位置的纵坐标，不符合时将其出栈，要注意栈是否为空。总结 ：这次实验让我更好地掌