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

《北邮数据结构实验二实验报告皇后问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实验报告实验名称：学生姓名：班级：班内序号：学号：日期：1．实验要求1.1实验目的2进一步掌握指针、模板类、异常处理的使用3掌握栈的操作的实现方法4掌握队列的操作的实现方法5学习使用栈解决实际问题的能力6学习使用队列解决实际问题的能力1.2实验内容利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。1.3具体要求1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个

2、皇后是否在同一行、同一列和同一斜线上2.程序分析2.1存储结构利用栈的存储结构2.2关键算法分析2.2.1判断算法分析：判断第i行的皇后与前i-1行的皇后是否在同一列或者同一对角线上。判断是否在同一列上只需比较栈内存的数是否相等；判断是否在同一对角线上只需比较行差和列差是否相等。代码实现：boolstack::check()//bool型{for(inti=0;i

3、

4、abs(data[top]-data[i])==top-i)//符合列和对角线的点returnfalse;returntrue;}2.2

5、.2放置皇后代码分析：放置皇后用递归函数实现。从第0行开始放置皇后，穷尽该列。列值入栈，判断皇后位置是否符合放置要求，若不能，则出栈；若能，则判断是否为第8个皇后，若是，则打印棋盘，并且计数器+1；若不是，则进行row+1行递归函数继续。递归终止条件：row==stacksize-1。代码实现：voidstack::Queen(introw)//输入的参数为皇后所在行数{for(intcol=0;col

6、递归停止条件{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.遇到的问题刚开始接触这个题目时，不太懂对判断的皇后是否在同一对角线上的条件，只考虑到了一边对角线，而没有考虑到另外一种情况。正确

7、的条件是：(abs(data[top]-data[i])==top-i)，而我却把绝对值漏掉了，导致最后出现了2113种放置方法；看到棋盘后我才知道我漏掉了另一种情况。我还遇到的另外一个问题是结果显示不完全，只能看到第64到第92种方案，经过查资料后才知道是屏幕缓冲区的高度设置不够。适当增加高度后即可显示全部的方案。2.心得体会通过本次实验，我对栈结构有了进一步的理解。解决这类摆放问题，充分运用了栈“后入先出”的特点，用栈来保存放置的位置；以及使用了递归函数对问题进行了简化。下附本程序所有源代码：#include#include

8、ws.h>usingnamespacestd;constintstacksize=8;intnum=0;//静态变量num用于计数classstack//建立一个栈类解决问题{private:intdata[stacksize];//定义数组，data[i]保存皇后在第i行的第几个位置inttop;//栈顶指针public:stack(){top=-1;};//默认构造函数voidpush(intx);//入栈voidpop();//出栈boolEmpty();//判断栈是否为空boolcheck();//检查列和斜线是否符合要求voidprint();//打

9、印解决方案voidQueen(introw);//解决措施};boolstack::Empty(){if(top==-1)returntrue;elsereturnfalse;}voidstack::push(intx){if(top>=stacksize)//异常处理throw"上溢";else{top++;data[top]=x;}}voidstack::pop(){if(Empty())//异常处理throw"下溢";elsetop--;}boolstack::check()//bool型{for(inti=0;i

10、]==data[i]

11、

12、abs(dat