北邮信通院数据结构实验二八皇后问题实验报告内附源代码完整版文档格式.docx
《北邮信通院数据结构实验二八皇后问题实验报告内附源代码完整版文档格式.docx》由会员分享，可在线阅读，更多相关《北邮信通院数据结构实验二八皇后问题实验报告内附源代码完整版文档格式.docx（12页珍藏版）》请在冰点文库上搜索。
【实验内容】
利用栈结构实现八皇后问题。
八皇后问题19世纪著名的数学家高斯于1850年提出的。
他的问题是：
在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。
请设计算法打印所有可能的摆放方法。
提示：
1、可以使用递归或非递归两种方法实现
2、实现一个关键算法：
判断任意两个皇后是否在同一行、同一列和同一斜线上
2.程序分析
2.1存储结构
存储结构：
栈（递归）
2.2关键算法分析
递归调用摆放皇后
1、关键算法伪代码：
（1）.如果输入的row大于皇后的数量，则输出皇后的位置
（2）否则col从0开始递增
（3）检测（row，col）上的点是否符合条件，不符合则col自增，符合则转到下一个皇后的排列
2、代码详细分析：
voidSeqStack:
:
PlaceQueen（introw）//摆放皇后
{
for（intcol=0;
col<
n;
col++）//遍历0~7，
{
Push（col）;
if（Check（））//判断摆放皇后的位置是否合适
{
if（row<
n-1）//若还没有放到最后一个，则进行下一个皇后的放置
PlaceQueen（row+1）;
else
{
num++;
//计数器加1
Print（n）;
//打印成功的坐标点
}
}
Pop（）;
//若不符合条件则出栈
}
}
3、计算时间复杂度：
O（n²
）
判断皇后位置是否合适：
1、关键算法伪代码：
对于一个坐标，将前面每一个坐标均与这个坐标比较
若在同一列或在同一斜线上，则返回0，
否则j自增1，面每一个坐标与前面做比较
若与前面坐标在同一列
最后返回
2、代码分析：
boolSeqStack:
Check（）
for（inti=0;
i<
top;
i++）//依次检查前面已摆放的皇后位置
if（data[top]==data[i]||（abs（data[top]-data[i]））==（top-i））//判断是否在同一列同一斜线
returnfalse;
returntrue;
3、时间复杂度：
O（n）
2.3其他
说明：
由于输出显示时对话框有限，而程序结果比较多，占用空间大,运用输出坐标位置来表示，则可以输出全部解。
3.程序运行结果
（1）程序框图：
（2）程序代码：
#include<
iostream>
usingnamespacestd;
constintm=1024;
//定义栈的最大高度
intnum=0;
//初始化方案种类计数器
intn;
//摆放的皇后个数
classSeqStack//定义顺序栈
public:
SeqStack（）{top=-1;
}//构造函数，初始化空栈
voidPush（intx）;
//入栈
voidPop（）;
//出栈
voidPlaceQueen（introw）;
//摆放皇后的递归函数
boolCheck（）;
//判断是否在同一行同一列同一斜线
voidPrint（intn）;
//打印以坐标的形式
boolEmpty（）;
//判别栈是否为空
private:
intdata[m];
//定义数组
inttop;
//栈顶指针
};
Push（intx）//入栈操作
if（top>
=m-1）throw"
上溢"
;
top++;
//栈顶指针上移
data[top]=x;
Pop（）//出栈操作
if（Empty（））throw"
下溢"
top--;
//栈顶指针下移
Empty（）
if（top==-1）
returntrue;
else
returnfalse;
}
Print（intn）//将栈的数组形式打印成坐标
inti;
for（i=1;
=n;
i++）
cout<
<
"
（"
"
data[i-1]+1<
）"
cout<
endl;
voidmain（）
{cout<
输入Queen的数目（n>
0）"
cin>
>
n;
if（n<
0||n>
1024）
{cout<
输入错误"
SeqStackQueen;
//定义类的对象
Queen.PlaceQueen（0）;
//从栈底开始赋值
Queen可能的摆放位置种类:
num<
//输出摆放方法的总数
（3）运行结果：
4.总结
调试时出现的问题：
最初由于递归的思想未能很好掌握，导致几次调试都出现比较严重的错误；
且在运用该方法时，未能将八皇后问题的具体思路搞清，没有考虑“如果前次的皇后放置错误导致后面的放置无论如何都不能满足要求，在设计递归算法总是只显示几种，
为了将92种情形全部打印，采用坐标的形式。
使用了栈的存储结构来存储位置的纵坐标，不符合时将其出栈，要注意栈是否为空。
总结：
这次实验让我更好地掌握了栈思想以及函数的嵌套调用等等知识,以及一些书本上没有的东西，让我学会了运用递归算法去解决一些复杂的问题。
另外，在写程序时，要避免由于粗心造成的低级错误，减少调试的次数。
改进：
不仅可以设计放置八皇后，只要修改输入的N，便可显示其他情况的结果。
升级会员 