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

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

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

2、放方法。3、提示：1.可以使用递归或非递归两种方法实现2.实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.程序分析2.1存储结构存储结构：栈2.2关键算法分析2.2.1皇后摆放位置可行性的判断判断任意两个皇后是否在同一行、同一列和同一斜线上for(inti=0;i

3、

4、(abs(queen[top]-queen[i]))==(top-i))returnfalse;returntrue;1.对于一个坐标，将前面每一行的皇后列标与本行的皇后列标比较，若列标相同或列标想

5、减的绝对值与行标相减的值相同，返回false2.否则i自增13.列标i=8，即未发现冲突，循环结束，返回true2．2．2插入皇后算法voidSeqStack::SetQueen(intr)//设置皇后{for(inti=1;i<=StackSize;i++){Push(i);if(Feasible()){if(r

6、判断插入列表所在行是否为最后一行，若是，打印列标；否则，开始下一行的皇后位置的选择。时间复杂度O（n2）2.3其他程序代码：#includeusingnamespacestd;constintStackSize=8;//设置皇后数组templateclassSeqStack{public:SeqStack(){top=-1;}//构造函数voidPush(Tx);//入栈操作voidPop();//出栈操作voidSetQueen(introw);//设置皇后位置boolFeasible();//判断皇后可行性

7、voidPrint();//打印boolEmpty(){if(top==-1)returntrue;elsereturnfalse;};//判断栈是否为空private:Tqueen[StackSize];inttop;};templatevoidSeqStack::Push(Tx)//入栈操作{if(top>=StackSize-1)throw"栈满";top++;queen[top]=x;}templatevoidSeqStack::Pop(){if(Empty())throw"栈下溢";top--

8、;}intCount=0;templatevoidSeqStack::SetQueen(intr)//设置皇后{for(inti=1;i<=StackSize;i++){Push(i);if(Feasible())//判断是否可以摆放皇后{if(rboolSeqStack::Feasible()//可行性判断{for(inti=0;i

9、p]==queen[i]

10、

11、(abs(queen[top]-queen[i]))==(top-i))//判断皇后不在同一列或对角线上returnfalse;returntrue;}templatevoidSeqStack::Print(){cout<Queen;Queen.

12、SetQueen(0);}3.程序运行结果测试主函数流程：流程图如图所示开始执行设置皇后算法结束打印摆放皇后的坐标1、测试条件：初始Qu