c++利用栈解决八皇后问题数据结构实验报告

X X 级数据结构实验报告 实验名称： 实验二——栈和队列 学生姓名： 班 级： 班内序号： 学 号： 日 期： 1．实验要求 【实验目的】 1、 进一步掌握指针、模板类、异常处理的使用 2、 掌握栈的操作的实现方法 3、 掌握队列的操作的实现方法 4、 学习使用栈解决实际问题的能力 5、 学习使用队列解决实际问题的能力 【实验内容】 利用栈结构实现八皇后问题。 八皇后问题 19 世纪著名的数学家高斯于 1850 年提出的。他的问题是：在 8*8 的棋盘上放置 8 个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 提示： 1、可以使用递归或非递归两种方法实现 2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上 2. 程序分析 2.1 存储结构 存储结构：栈（递归） 2.2 关键算法分析 【设计思想】 由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法 【伪代码】 1、 输入皇后个数 n 2、 k=1 3、 判断 k 是否大于n 3.1 是：打印一组可能 3.2 否：循环行位置 1~n 判断该位置是否符合要求，若符合记录 q[k]的坐标 y 值 k+1 重复 3 【关键算法】 1、递归 void Queen::Queens(int k,int n)//计算出皇后的排列，k 是当前皇后数量，n 是数量上限 { int i; if(k>n)//如果达到里要求的数量输出皇后排列 { Print(n); count(); } else //否则在适当的位置添加一个新皇后 { for(i=1;i<=n;i++) if(Check(i,k)) //判断该行中该位置放置'皇后'是否符合要求 { q[k]=i; //记录改行中该点的位置 Queens(k+1,n); //放置下一行的'皇后' } } } 时间复杂度：O(n²) 2、判断皇后放置位置是否符合要求 int Queen::Check(int i,int k) { int j; j=1; while(j #include using namespace std; #define N 10 class Queen { public: Queen(){num=-1;} void Print(int n);//输出皇后的排列，打出的数字为每个皇后的坐标 int Check(int i,int k);//判断位置是否符合要求 void Queens(int k,int n);//递归调用 int count();//计数 ...