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

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

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

2、法打印所有可能的摆放方法。3、提不：1.可以使用递归或非递归两种方法实现2.实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.程序分析2.1存储结构存储结构：栈Queenm<^4OD=7aueen(61Qutenl61aueenl61aueenfSIaueenfSIaueen(51aueenf41aueen(41Queen

3、41aueen(31aueenf31aueenr31aueen(21aueen(21aueen

4、21QueenfllQueen⑴aueenfllqueen[0]queen[0]queen[

5、0]緬入S后，Push元索入Mbtop++若MlttS后位■不合授，PopWt,top-2.2关键算法分析2.2.1皇后摆放位置可行性的判断判断任意两个皇后是否在同一行、同一列和同一斜线上for(inti=0;i

6、

7、(abs(queen[top]-queen[i]))==(top-i))returnfalse;returntrue;1.对于一个坐标，将前而每一行的皇后列标与本行的皇后列标比较，若列标相冋或列标想减的绝对值与行标相减的值相同，返回false2.否则i自

8、增13.列标i=8，即未发现冲突，循环结束，返回true2.2.2插入皇后算法//设置皇后voidSeqStack::SetQueen(intr)for(inti=l;i<=StackSize;i++){Push(i);if(Feasible()){if(r〈StackSize-l)SetQueen(r+1);else{Count+十；Print0;}}Pop();}}算法步骤：(1)判断列标在(0,8)范围内(2)将列标入栈(3)判断在该行列坐标下，皇后位置是否可行(4)若可行，判断插入列表所在行是否为最后一行，若是，打

9、印列标；否则，开始下一行的皇后位置的选择。时间复杂度0(n2)2.3其他程序代码：//没置皇后数组#includeusingnamespacestd;constintStackSize=8;template〈classT>classSeqStackSeqStack(){top=-l:}//构造函数voidPush(Tx);//入栈操作voidPop();//出栈操作voidSetQueen(introw);//设置皇后位置boolFeasible0;//判断皇后可行性voidPrint();"打印boolEm

10、pty(){if(top==-l)returntrue;elsereturnfaprivate:public://判断栈是否为空Tqueen[StackSize];inttop;）；templatevoidScqStack::Push(Tx)//入栈操作{if(top>=StackSize-l)throw"栈满〃；top++;queen[top]=x:)template〈classT>voidSeqStack::Pop(){if(Empty())throw〃栈下溢"；top一一；)intCount=0

11、;templatevoidScqStack::SetQueen(intr)//设置呈后{for(inti=l;i<=StackSize;i++){Push⑴；if(Feasible0)//判断是否可以摆放皇后{if(rboolSeqStack::Feasible()//可行性判断{for(inti=0;i〈top;i++)//判断皇后不在if(queen[top]=

12、=queen[i]

13、(abs(queen[top]-queen[i]))==(top-i))同一列或对角线上returnfalse;returntrue;template〈classT>voidSeqStack::Print(){cout〈〈C()unt<