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

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验二八皇后问题学生姓名： 班 级： 班内序号： 学 号： 日 期： 2014年11月27日1 实验要求【实验目的】Ø 进一步掌握指针、模板类、异常处理的使用Ø 掌握栈的操作的实现方法Ø 掌握队列的操作的实现方法Ø 学习使用栈解决实际问题的能力Ø 学习使用队列解决实际问题的能力【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计

2、算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现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

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

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

5、ace std;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); /摆放皇后的递归函数bool check(); /判断是否在同一行同一列同一斜线void print(int n); /打印以坐标的形式bool empty(); /判别栈是否为空 private:int dat

6、am; /定义数组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

7、 (row< n-1) /若还没有放到最后一个，则进行下一个皇后的放置placequeen(row+1);elsenum+; /计数器加1print(n); /打印成功的坐标点pop(); /若不符合条件则出栈bool seqstack:empty()if(top=-1) return true;elsereturn false; bool seqstack:check()for(int i=0;i<top;i+) /依次检查前面已摆放的皇后位置if(datatop=datai|(abs(datatop-datai)=(top-i) /判断是否在同一列同一斜线return fals

8、e;return true; void seqstack:print(int n) /将栈的数组形式打印成坐标 int i;for(i=1;i<=n;i+)cout<<"("<<i<<","<<datai-1+1<<")"cout<<endl;void main() cout<<"输入queen的数目（n>0）"<<endl; cin>>n;if(n<0|n>1024)cout<

9、<"输入错误"<<endl;seqstack queen; /定义类的对象queen.placequeen(0); /从栈底开始赋值cout<<" queen可能的摆放位置种类:"<<num<<endl; /输出摆放方法的总数（3）运行结果：4. 总结 调试时出现的问题： 最初由于递归的思想未能很好掌握，导致几次调试都出现比较严重的错误；且在运用该方法时，未能将八皇后问题的具体思路搞清，没有考虑“如果前次的皇后放置错误导致后面的放置无论如何都不能满足要求，在设计递归算法总是只显示几种，为了将92种情形全部打印，采用坐标的形式。使用了栈的存储结构来存储位置的纵坐标，不符合时将其出栈，要注意