实验二——利用栈结构实现八皇后问题.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验二利用栈结构实现八皇后问题学生姓名： 班 级：班内序号：学 号：日 期：实验要求实验目的：通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力实验内容：1、 利用栈结构实现八皇后问题。2、 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。3、 提示：1.可以使用递归或非递归两种方法实现2. 实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1 存储结构 存储结构：栈2.2 关键算法分析2.2.1皇后摆放位置可行性的判断 判断任意两个皇后是否在同一行、同一列和同一斜线上 for(int i=0;itop;i+) if(queentop=queeni|(abs(queentop-queeni)=(top-i)return false;return true;1. 对于一个坐标，将前面每一行的皇后列标与本行的皇后列标比较 ，若列标相同或列标想减的绝对值与行标相减的值相同，返回false2. 否则i自增13. 列标i=8，即未发现冲突，循环结束，返回true222插入皇后算法void SeqStack:SetQueen(int r) / 设置皇后 for (int i=1;i=StackSize;i+) Push(i);if (Feasible() if (rStackSize-1) SetQueen(r+1);elseCount+; Print(); Pop(); 算法步骤：（1） 判断列标在（0，8）范围内（2） 将列标入栈（3） 判断在该行列坐标下，皇后位置是否可行 （4） 若可行，判断插入列表所在行是否为最后一行，若是，打印列标；否则，开始下一行的皇后位置的选择。 时间复杂度 O（n2） 2.3 其他程序代码：#include using namespace std;const int StackSize=8; /设置皇后数组template class SeqStack public:SeqStack()top=-1; /构造函数 void Push(T x); /入栈操作 void Pop(); /出栈操作 void SetQueen(int row); /设置皇后位置 bool Feasible(); /判断皇后可行性 void Print(); /打印 bool Empty()if(top=-1) return true;else return false; /判断栈是否为空 private:T queenStackSize; int top; ;template void SeqStack:Push(T x) /入栈操作if(top=StackSize-1) throw 栈满;top+; queentop=x;template void SeqStack:Pop() if(Empty() throw 栈下溢;top-; int Count=0;template void SeqStack:SetQueen(int r) /设置皇后 for (int i=1;i=StackSize;i+) Push(i);if (Feasible() /判断是否可以摆放皇后 if (rStackSize-1) SetQueen(r+1);elseCount+; Print(); Pop(); template bool SeqStack:Feasible() /可行性判断for(int i=0;itop;i+) if(queentop=queeni|(abs(queentop-queeni)=(top-i) /判断皇后不在同一列或对角线上return false;return true;template void SeqStack:Print() coutCount:endl; for(int i=0;iStackSize;i+)cout第i+1行：; coutqueeni ; coutendl;void main() /主函数SeqStack Queen; Queen.SetQueen(0); 3. 程序运行结果 测试主函数流程：流程图如图所示开始执行设置皇后算法结束 打印摆放皇后的坐标 1、 测试条件：初始Queen8作为棋盘的各行分别确定各行的列标2、 测试结论通过递归算法，程序成功的打印了八皇后的所有可能性。4. 总结本次实验我掌握了利用栈的存储结构，熟悉栈的出入栈操作，利用递归算法实现了八皇后的摆放，实验的过程使我学到了许多书本上没有的知识，更加深了我对于栈的存储结构的理解，同时也让我理解了，数组与栈的内在联系。在程序调试过程中，主要的问题是：1总会有丢分号之类的小错误2. for与if的循环嵌套未能很好掌握，在编写设置皇后的递归算法时，循环和判断使用思路很混乱，导致皇后放置判断时，若判断到本行所有位置均不合适的时候，不能改变上一行皇后