北邮八皇后数据结构实验报告

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

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

2、实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.程序分析#include#includeusingnamespacestd;constintN=8;//皇后的个数第9页北京邮电大学信息与通信工程学院staticintm=0;//用来计数，使用方法数classQueen{public:voidPrint();//输出皇后的排列intCheck(inti,intk);//判断位置是否符合要求voidQueens(intk);//递归调用private:intq[N];//存储每个皇后位置intnum;};voidmain(

3、){QueenQ;cout<<"Queen可能的位置:"<N)//如果达到里要求的数量输出皇后排列{Print();第9页北京邮电大学信息与通信工程学院}else//否则在适当的位置添加一个新皇后{for(i=1;i<=N;i++)if(Check(i,k))//判断该行中该位置放置'皇后'是否符合要求{q[k]=i;//记录改行中该点的位置Queen

4、s(k+1);//放置下一行的'皇后'}}}voidQueen::Print(){cout<<"第"<<++m<<"种：";for(inti=1;i<=N;i++){cout<

5、

6、abs(q[j]-i)==abs(j-k))//判断列，判断斜线是否满足条件return0;//不符合

7、返回0j++;}return1;//符合返回}1，首先声明一个Queen类，包含打印函数，找Queen位置函数以及判断位置是否合理函数；Print()Check(inti,intk)Queens(intk)Queens(intk)函数：从第一个位置开始第9页北京邮电大学信息与通信工程学院2.1存储结构2.1存储结构1、存储结构：栈（递归）2.2关键算法分析1、递归voidQueen::Queens(intk,intn)//计算出皇后的排列，k是当前皇后数量，n是数量上限{inti;if(k>n)//如果达到里要求的数量输出皇后排列{Print(n);count();}else//否

8、则在适当的位置添加一个新皇后{for(i=1;i<=n;i++)if(Check(i,k))//判断该行中该位置放置'皇后'是否符合要求{q[k]=i;//记录改行中该点的位置Queens(k+1,n);//放置下一行的'皇后'}}}算法步骤：（1）.如果输入的k大于皇后的数量，则输出皇后的位置（2）。否则i从1开始递增(3),检测（k，i）上的点是否符合条件，不符合则i自增，符合则转到下一个皇后的排列第9页北京邮电大学信息与通信工程学院时间复杂度：O(n²)2、判断皇后放置位置是否符合要求intQueen::Check(inti,intk){intj;j=1;while(j

9、{if((q[j]==i)

10、

11、abs(q[j]-i)==abs(j-k))//判断列，判断斜线return0;//不符合返回0j++;}return1;//符合返回}算法步骤：1.对于一个坐标，将前面每一个坐标均与这个坐标比较2.若在同一列或在同一斜线上，则返回0，3.否则j自增1，面每一个坐标与前面做比较4.若与前面坐标在同一列5.最后返回12.3其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大，最后只显示60种到92种，可以运用输出坐标位置来表示，