数据结构实验报告--八皇后

1．实验要求

实验目的：利用栈结构实现八皇后问题

八皇后问题如下：八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是，在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行，同一列，同一斜线上。

实验内容：利用所学的栈结构用递归或非递归解决八皇后问题。

2. 程序分析

程序使用程序最主要只是在主函数用了一个递归函数Queen。

Queen函数使用了三个参数m,flag[][],chess[][]。其中m是行数，flag[][]是判断二维数组何处可以放置皇后，chess[][]是存储字符串的二维数组。

主函数中对Queen函数中的形参数组flag[][],chess[][]进行初始化，在Queen函数中再进行各种操作。

Queen函数执行代码，首先行数m为0，当m小于7时，通过if…else…语句，利用Queen(m+1,f,c)重新执行递归函数到下一行。

2.1 存储结构

存储结构：数组存储。

flag[][]数组存储数字判断输出和储能放置皇后,chess[][]数组存储字符串即皇后和

非皇后的形状。

2.2 关键算法分析

1、关键算法： a．

for(i=0;i<8;i++)

for(j=0;j<8;j++) { f[i][j]=0;

c[i][j]='*'; 说明：对棋盘进行初始化 未放置皇后的为“*” b．

for(i=0;i<8;i++)

for(j=0;j<8;j++) { c[i][j]=chess[i][j]; f[i][j]=flag[i][j];

}

说明：对c[][]，f[][]进行初始化。 c．

for(i=0;i<8;i++)

for(j=0;j<8;j++) {

if(f[i][j]==0 && (i+j==m+k || m==i || k==j || m-k==i-j)) f[i][j]=-1;

}

c[m][k]='#';

说明：已放置皇后的行、列以及对角线都不能再放置皇后。

已放置皇后的显示为“#”。 d.

if(m==7)

{ cout<<\"算法的第\"<<++count<<\"个解为：\"<else Queen(m+1,f,c); 说明：首先判断是否已执行到最后一行

每输出一个算法，count计数器加1

若没有执行到最后一行，m+1继续执行Queen函数

2.3 其他

要求程序在一开始创建一个统计算法解个数的加法器。

3. 程序运行结果

1、 测试主函数流程：流程图如图所示

2、 测试结论：输出解决算法的个数及八皇后问题的图解。

4. 总结

一．问题及解决办法

1.一开始编的时候对同一行，同一列以及同一斜行不能排皇后的算法不能准确编写，后来通过画图发现了这三个情况数组行标和列标的特点，从而解决了这个问题。

2.程序只能输出从65至99的解，其他解不显示，后来发现是因为界面太小的原因。 二．心得体会

对于刚学的栈表以及递归函数一定要多用才能熟悉，才能知道实现的具体细节问题。对一些出现的错误一点要仔细分析，明白以后就会掌握的很牢固。对于递归函数一定要充分理解它的意义才能用好它。

在编写代码中如果对于一些抽象的算法构思感到困难，可以通过画图，在纸上先进行演算推导出各变量之间的关系，再进行编写可能会使问题变得简单明了一些。 三．改进

递归算法解决八皇后问题比较简单明了，下次可以尝试不使用递归而用非递归编写算法，这样可能会更牢固更好的掌握栈的思想，巩固已学的知识。