北邮信通院数据结构实验二--八皇后问题实验报告(内附源代码完整版)

1、数据结构实验报告实验名称：实验八ill后冋题学生姓名：班 级：班闪序号：学 号：闩 期：2014年11只27円1. 实验要求【实验h的】> 进一步掌握指针、模板类、异常处理的使用> 掌握栈的操作的实现方法> 掌握队列的操作的实现方法> 学4使川栈解决实际问题的能力> 学使川队列解决实际问题的能力 【实验内容】利川栈结构实现八皇p问题。八皇p问题19世纪著名的数学家高斯于1850年捉出的。他的闷题是：在8*8的棋盘匕 放置8个皇后，使其不能互和攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线 上。请设计算法打印所冇可能的摆放方法。提示.1、可以使川递归或非递归

2、两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析2.1存储结构存储结构：栈（递归）s(l:10)1cm9toptl_> s*3 7 6 5 43 一 2 一bottomypxpdptoo*-1bottoms(b>插入x与y卮的栈10,9&6 5如1432e<ek(c)退出一个元素卮的梭2.2关键算法分析递归调用摆放皇后1、关键算法伪代码：(1) .如果输入的row大于皇后的数量，则输出皇后的位置(2) 否则col从0开始递增(3) 检测(row, col)上的点是否符合条件，不符合则col tl增，符则转到下 一个皇后的

3、排列2、代码详细分析：void seqstack:placequeen(int row)/摆放皇后for (int col=0;col< n;col+)/遍历 07，push (col);if (check ()/判断摆放皇后的位置足否合适if (row< n-1)/若还没有放到敁a个，则进行下一个皇后的放置placequeen(row+1);num+; print (n)elsepop ();/计数器加1/打印成功的坐标点/若不符合条件则出栈3、计算时间复杂度：0(n2)判断皇后位置是否合适：1、关键算法伪代码：对于一个少标，将前面每一个华标均与这个华标比较卷在同一列或决同一斜线

4、上，则返回0，否则j自增1，面每一个少标与前面做比较若与前而坐标在同一列 最后返回2、代码分析：bool seqstack:check()for(int i=0;i<top;i+)/依次检查前面已摆放的皇后位置if(datatop=datalij|(abs(datatopj-datai)=(top-i)/判断是否在同一列同一斜线return false;return true;3、时间复杂度：0(n)2.3其他说明：由于输出显示时对话框冇限，而程序结果比较多，占用空间人，运用输出坐标位置来 表示，则可以输出全部解。3. 程序运行结果(1 )程序框图:/定义栈的最人/初始化方案/摆放的皇r

5、/定义顺/构造函/入栈 /出栈/摆放阜盾/判断是否在(2)程序代码: includeiostream using namespace std;const int m=1024;高度int num=0;种类计数器 int n;个数class seqstack序栈public:seqstack() top=-1;数，初始化空栈void push(int x); void pop();void placcquccn(int row); 的递归函数bool check();同一行同一列同一斜线void print(int n);/打印以坐标的形式bool empty();/判别栈是为空private:

6、int datafml;/定义数组int top;/栈顶指针;void scqstack:push(int x)/入栈揀作if(top>= m-1) throw "上溢"top+;/栈顶指针上移datatopl=x;void seqstack:pop()/出栈操作if(empty() throw "下溢"；top-;/桟顶棺针下移void seqstack:placequeen(int row)for (int col=0;col< n;col+)push(col); if (check()后的位a是否合适if (row< n-1)后一

7、个，则进行下一个皇后的放置placequeen(row+1);elsenum+;器加1/摆放皇活/遍历07,/判断摆放呈/农还没冇放到鉍/计数print ;/打印成功的坐标点popo; 合条件则岀栈/芯不符bool seqstack:empty() if(top=-l)return true;elsereturn false;bool seqstack:check()for(int i=0;i<top;i+)前面己摆放的皇后位sif(datatop=datai|(abs(datatop-datafi)=(top-i)一斜线return false; return true;/依次检查/判

8、断是否在同一列同void seqstack:print(int n)形式打印成坐标int i;for(i=l;i<=n;i+)cout«h(h«i«,'；,«datai-1 +1 «”)n; cout«endl;/将栈的数组void main() cout«”输入 queen 的数目(n0) "«endl; cin»n;if(n<0|n>1024)cout«"输入错误,endl;seqstack queen;queen.placequeen(o);/

9、定义类的对象/从栈底开始赋值cout«" queen可能的搜放位置种类:n«num«endl;/输出技放力*法的总数（3）运行结果：e:vc十十microsoft visual studiomyproects谈若二debugv 呈后 exe<1，4<2.?<3,3<4,8<5,2x6,s<?,1<8,6 <1,4<2，？<3,5<4,2<5,6<6,1<?,3<8,8 <1,42.?<3,5(4,3<s,1<6,6<?,8<8.2

10、 <1,4<2,8<3,1<4,3<s,6<6,2<?.?<8.s <1,4x2.8x3.1x4.5x5.7x6.2x7.6x8.3> <1,4<2,8<3,s4,3<s,1x6,?<?,2<8,6 <1,5<2.1<3,4<4,6<5,8<6,2<?.?<8.3 <1.5 ><2.1x3.8 x4.4x5.2 ><6.7x7.3x8.6> <1.5x2,13,8<4,6<s,3<6,?？，2

11、<8,4 <1,5><2.2><3.4><4.6><5.8><6.3><7.1><8.?> <1.5 ><2.2x3.4x4.7x5.3x6.8x7.6x8.1 > <1.5x2.2x3.6x4.1 x5.7x6.4x7.8x8.3> <1.5x2.2x3.8 ><4,1x5.4x6,7x7.3x8.6> <1.5 ><2.3x3.1x4.6x5.8x6.2x7.4x8.?> <1.5x2.3 >&

12、lt;3.1x4.7x5.2x6.8x7.6x8.4> <1.5x2.3x3.8x4.4x5.7x6.1x7.6x8.2> <1,52.?3,14,3<5,8<6,6？.4<8.2 <1.5 ><2.7x3.1 x4.4x5.2x6.8x7.6x8.3> <1.5x2.7x3.2x4.4x5.8x6.1x7.3x8.6> <1.5><2.7><3,2><4.6><5.3><6,1><7.4><8.8> <1.5x2.

13、7x3.2x4.6x5.3x6.1x7.8x8.4> <1.5x2.7x3.4x4.1x5.3x6.8x7.6x8.2> <1,5<2,8<3,4<4,1<5,3<6,6<?,2<8,? <1,5 ><2.8 ><3.4x4.1x5.7x6.2x7.6x8.3> <1.6><2.1><3.5><4.2><5.8)<6.3><7.7><8.4>"e:vc+microsoft visual studiomyprojects读验二debugv違后.exe"_回!4. 总结凋试吋出现的问题：最初山于递归的思想未能很好掌握，导致儿次调试都出现比较严 重的错误；且a运用该方法时，未能将八皇后问题的其体思路搞清，没有考虑“如果前次的 皇p放置错误导致后側的放置无论如何都不能满妃要求，在设