北邮数据结构实验2八皇后

《北邮数据结构实验2八皇后》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、同一行、同一列和同一斜线上2.程序分析2.1存储结构存储结构：栈2.2关键算法分析设计思想:由于八皇后问题，可以分解成算法相同的子问题，所以使用递归的方法伪代码:1.输入皇后个数n2.i=13.判断i是否大于n4.是：打印一组可能5.否：循环行位置1~n6.判断该位置是否符合要求，若符合记录data[i]7.i+1重复关键算法:1、递归算法步骤： 1.如果输入的row大于皇后的数量，则输出皇后的位置 2.否则row从0开始递增3.检测（row，col）上的点是否符合条件，不符合则row自增，符合则转到下一个皇后的排列时间复杂度：O(n²)2、判断皇后放置位置是否符合要求for(in

3、ti=0;i

4、

5、(data[top]-data[i])==(top-i)

6、

7、(data[i]-data[top])==(top-i))算法步骤： 1.对于一个坐标，将前面每一个坐标均与这个坐标比较;2.若在同一列或在同一斜线上，则返回false;3.否则i自增1，面每一个坐标与前面做比较 4.若都不相等，则返回true时间复杂度：O(n)2.3其他源代码：#includeusingnamespacestd;constintNumOfQ=8;//numberofqueenin

8、tnumber=0;//方案计数templateclassSeqStack{public:SeqStack(){top=-1;}voidPush(Tx);voidPop();voidQueen(introw);//放置皇后boolCheck();//判断是否可以放置皇后voidprint();//打印boolEmpty(){if(top==-1)returntrue;elsereturnfalse;};//判别栈是否为空private:Tdata[NumOfQ];inttop;};templatevoidSeqStack::Push(Tx)//

9、入栈{if(top>=NumOfQ-1)throw"上溢";top++;data[top]=x;}templatevoidSeqStack::Pop()//出栈{if(Empty())throw"下溢";top--;}templateboolSeqStack::Check(){for(inti=0;i

10、

11、(data[top]-data[i])==(top-i)

12、

13、(data[i]-data[top])==(top-i))//判断是否可以放置皇后re

14、turnfalse;}returntrue;}templatevoidSeqStack::print()//将栈的数组形式打印成棋盘形式{cout<<"NO."<<++number<<":"<data[i];j--)cout<<"*";cout<void

15、SeqStack::Queen(introw)//在栈顶放置符合条件的值的操作,即摆放皇后{for(intcol=0;col