北邮八皇后数据结构实验报告.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验二栈和队列学生班 级： 班内序号：学 号： 日 期：2013.11.20 1实验要求【实验目的】1、 进一步掌握指针、模板类、异常处理的使用2、 掌握栈的操作的实现方法3、 掌握队列的操作的实现方法4、 学习使用栈解决实际问题的能力5、 学习使用队列解决实际问题的能力【实验内容】 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上 2. 程序分析#include#includeusing namespace std;const int N=8; /皇后的个数static int m=0;/用来计数，使用方法数class Queenpublic:void Print();/输出皇后的排列int Check(int i,int k);/判断位置是否符合要求void Queens(int k);/递归调用private:int qN;/存储每个皇后位置 int num;void main() Queen Q;coutQueen可能的位置:endl;Q.Queens(1);/从第一个皇后开始排cout共有 m 种方法放置QueenN)/如果达到里要求的数量输出皇后排列 Print();else /否则在适当的位置添加一个新皇后for(i=1;i=N;i+)if(Check(i,k) /判断该行中该位置放置皇后是否符合要求qk=i; /记录改行中该点的位置Queens(k+1); /放置下一行的皇后void Queen:Print()cout第+m种：;for(int i=1;i=N;i+)coutendl;for(int j=1;j=N;j+)if(j=qi)coutQ ;else cout* ;coutendl;int Queen:Check(int i,int k)int j;j=1;while(jn)/如果达到里要求的数量输出皇后排列 Print(n);count();else /否则在适当的位置添加一个新皇后for(i=1;i=n;i+)if(Check(i,k) /判断该行中该位置放置皇后是否符合要求qk=i; /记录改行中该点的位置Queens(k+1,n); /放置下一行的皇后算法步骤：（1）.如果输入的k大于皇后的数量，则输出皇后的位置（2）。否则i从1开始递增(3),检测（k，i）上的点是否符合条件，不符合则i自增，符合则转到下一个皇后的排列时间复杂度：O(n)2、判断皇后放置位置是否符合要求int Queen:Check(int i,int k)int j;j=1;while(jk)if(qj=i) | abs(qj-i)=abs(j-k) /判断列，判断斜线return 0; /不符合返回0j+;return 1; /符合返回算法步骤：1. 对于一个坐标，将前面每一个坐标均与这个坐标比较2. 若在同一列或在同一斜线上，则返回0，3. 否则j自增1，面每一个坐标与前面做比较4. 若与前面坐标在同一列5. 最后返回12.3 其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大，最后只显示60种到92种，可以运用输出坐标位置来表示，则可以输出全部解如：void Queen:Print(int n)int i;for(i=1;i=n;i+)cout(i,qi);coutendl;3. 程序运行结果1实验流程图 开始输入n 判断是否满行qk=ik+YN输出结果判断位置（i，k）是否符合要求NYi+2测试条件：无特殊测试条件3.实验结果:4. 总结调试时出现的问题：1. for与if的循环嵌套未能很好掌握，导致几次调试都出现比较严重的错误；且在运用该方法时，未能将八皇后问题的具体思路搞清，没有考虑“如果前次的皇后放置错误导致后面的放置无论如何都不能满足要求，在设计递归算法总是只显示几种，2.如果将92种情形全部打印，则前面的几十种情况将无法显示出，要想看到前面的状态，必须添加一个控制语句，使其能一个一个的输出。总结：这次实验让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没