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

数据结构实验报告实验名称： 学生姓名： 班 级： 班内序号： 学 号：日 期： 实验要求实验目的进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力 实验内容利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。 具体要求1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1 存储结构利用栈的存储结构2.2 关键算法分析2.2.1 判断算法分析：判断第i行的皇后与前i-1行的皇后是否在同一列或者同一对角线上。判断是否在同一列上只需比较栈内存的数是否相等；判断是否在同一对角线上只需比较行差和列差是否相等。代码实现：bool stack::check()//bool型{for(int i=0;itop;i++)if(data[top]==data[i]||abs(data[top]-data[i])==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(data[top]-data[i])==top-i)，而我却把绝对值漏掉了，导致最后出现了2113种放置方法；看到棋盘后我才知道我漏掉了另一种情况。我还遇到的另外一个问题是结果显示不完全，只能看到第64到第92种方案，经过查资料后才知道是屏幕缓冲区的高度设置不够。适当增加高度后即可显示全部的方案。2.心得体会通过本次实验，我对栈结构有了进一步的理解。解决这类摆放问题，充分运用了栈“后入先出”的特点，用栈来保存放置的位置；以及使用了递归函数对问题进行了简化。下附本程序所有源代码：#includeiostream#includewindows.husing namespace std;const int stacksize=8;int num=0;//静态变量num用于计数class stack//建立一个栈类解决问题{private:int data[stacksize];//定义数组，data[i]保存皇后在第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上溢;else{top++;data[top]=x;}}void stack::pop(){if(Empty())//异常处理throw下溢;elsetop--;}bool stack::check()//bool型{for(int i=0;itop