北邮数据结构实验二实验报告皇后问题.docx

数据结构实验报告实验名称： 学生姓名： 班 级： 班内序号： 学 号：日 期： 1 实验要求1.1 实验目的2 进一步掌握指针、模板类、异常处理的使用3 掌握栈的操作的实现方法4 掌握队列的操作的实现方法5 学习使用栈解决实际问题的能力6 学习使用队列解决实际问题的能力1.2 实验内容利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。1.3 具体要求1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1 存储结构利用栈的存储结构2.2 关键算法分析2.2.1 判断算法分析：判断第i行的皇后与前i-1行的皇后是否在同一列或者同一对角线上。判断是否在同一列上只需比较栈内存的数是否相等；判断是否在同一对角线上只需比较行差和列差是否相等。代码实现：bool stack:check() /bool型for(int i=0;itop;i+)if(datatop=datai|abs(datatop-datai)=top-i) /符合列和对角线的点return false;return true;2.2.2 放置皇后代码分析：放置皇后用递归函数实现。从第0行开始放置皇后，穷尽该列。列值入栈，判断皇后位置是否符合放置要求，若不能，则出栈；若能，则判断是否为第8个皇后，若是，则打印棋盘，并且计数器+1；若不是，则进行row+1行递归函数继续。递归终止条件：row=stacksize-1。代码实现：void stack:Queen(int row) /输入的参数为皇后所在行数for(int col=0;colstacksize;col+)push(col);if(check() /判断不同行之间的皇后是否符合要求if(row=stacksize-1) /递归停止条件num+; /计数print(); /打印else Queen(row+1); /递归（将皇后放置到下一行），直到把皇后放完8行为止pop(); /不符合，出栈2.3 其他当棋盘大小为8x8时，共有92种方案，若要研究其他size的棋盘，更改stacksize值即可。3. 程序运行结果3.1 主函数流程图开始row=0入栈出栈合适？ 否row+1 是row=8? 否 是计数器+1棋盘打印结束3.2 程序运行结果4. 总结1.遇到的问题刚开始接触这个题目时，不太懂对判断的皇后是否在同一对角线上的条件，只考虑到了一边对角线，而没有考虑到另外一种情况。正确的条件是：(abs(datatop-datai)=top-i)，而我却把绝对值漏掉了，导致最后出现了2113种放置方法；看到棋盘后我才知道我漏掉了另一种情况。我还遇到的另外一个问题是结果显示不完全，只能看到第64到第92种方案，经过查资料后才知道是屏幕缓冲区的高度设置不够。适当增加高度后即可显示全部的方案。2.心得体会通过本次实验，我对栈结构有了进一步的理解。解决这类摆放问题，充分运用了栈“后入先出”的特点，用栈来保存放置的位置；以及使用了递归函数对问题进行了简化。下附本程序所有源代码：#include#includeusing namespace std;const int stacksize=8;int num=0; /静态变量num用于计数class stack /建立一个栈类解决问题private:int datastacksize; /定义数组，datai保存皇后在第i行的第几个位置int top; /栈顶指针public:stack()top=-1; /默认构造函数void push(int x); /入栈void pop(); /出栈bool Empty(); /判断栈是否为空bool check(); /检查列和斜线是否符合要求void print(); /打印解决方案void Queen(int row); /解决措施;bool stack:Empty()if(top=-1) return true;else return false;void stack:push(int x) if(top=stacksize) /异常处理throw上溢;elsetop+;datatop=x;void stack:pop() if(Empty() /异常处理throw下溢;elsetop-;bool stack:check() /bool型for(int i=0;itop;i+)if(datatop=datai|abs(datatop-datai)=top-i) /符合列和对角线的点return false;return true;void stack:print()cout第num种方案：endl;for(int i=0;istacksize;i+) /按行输出，i表示第i行for(int j=0;jdatai;j+) /皇后前j个空位用表示cout; coutdatai;j-)/皇后后7-j个空位用表示 cout;coutendl;coutendl;void stack:Queen(int row) /输入的参数为皇后所在行数for(int col=0;colstacksize;col+)push(col);if(check() /判断不同行之间的皇后是否符合要求if(row=stacksize-1) /递归停