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

《实验二——利用栈结构实现八皇后问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、北京邮电大学信息与通信工程学院数据结构实验报告实验名称：实验二——利用栈结构实现八皇后问题学生姓名：班级：班内序号：学号：日期：实验要求实验目的：通过选择下面五个题目之一进行实现，掌握如下内容：Ø进一步掌握指针、模板类、异常处理的使用Ø掌握栈的操作的实现方法Ø掌握队列的操作的实现方法Ø学习使用栈解决实际问题的能力Ø学习使用队列解决实际问题的能力实验内容：1、利用栈结构实现八皇后问题。2、八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇

2、后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。3、提示：1.可以使用递归或非递归两种方法实现2.实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上第7页北京邮电大学信息与通信工程学院2.程序分析2.1存储结构存储结构：栈2.2关键算法分析2.2.1皇后摆放位置可行性的判断判断任意两个皇后是否在同一行、同一列和同一斜线上for(inti=0;i

3、

4、(abs(queen[top]-queen[i]))==(t

5、op-i))returnfalse;returntrue;1.对于一个坐标，将前面每一行的皇后列标与本行的皇后列标比较，若列标相同或列标想减的绝对值与行标相减的值相同，返回false2.否则i自增13.列标i=8，即未发现冲突，循环结束，返回true第7页北京邮电大学信息与通信工程学院2．2．2插入皇后算法voidSeqStack::SetQueen(intr)//设置皇后{for(inti=1;i<=StackSize;i++){Push(i);if(Feasible()){if(r

6、-1)SetQueen(r+1);else{Count++;Print();}}Pop();}}算法步骤：（1）判断列标在（0，8）范围内（2）将列标入栈（3）判断在该行列坐标下，皇后位置是否可行（4）若可行，判断插入列表所在行是否为最后一行，若是，打印列标；否则，开始下一行的皇后位置的选择。时间复杂度O（n2）2.3其他程序代码：#includeusingnamespacestd;constintStackSize=8;//设置皇后数组template第7页北京邮电大学信息

7、与通信工程学院classSeqStack{public:SeqStack(){top=-1;}//构造函数voidPush(Tx);//入栈操作voidPop();//出栈操作voidSetQueen(introw);//设置皇后位置boolFeasible();//判断皇后可行性voidPrint();//打印boolEmpty(){if(top==-1)returntrue;elsereturnfalse;};//判断栈是否为空private:Tqueen[StackSize];inttop;};templ

8、atevoidSeqStack::Push(Tx)//入栈操作{if(top>=StackSize-1)throw"栈满";top++;queen[top]=x;}templatevoidSeqStack::Pop(){if(Empty())throw"栈下溢";top--;}intCount=0;templatevoidSeqStack::SetQueen(intr)//设置皇后{for(inti=1;i<=StackSize;i++){Pus

9、h(i);if(Feasible())//判断是否可以摆放皇后{if(rboolSeqStack::Feasible()//可行性判断{for(inti=0;i

10、

11、(abs(queen[top]-queen[i]))==(top-i))//判断皇后不在同一列或对

12、角线上returnfalse;returntrue;}templatevoidSeqStack::Print(){cout<