数据结构实验报告八皇后（整理）_数据结构实验报告答案

数据结构实验报告八皇后（整理）由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告答案”。

数据结构实验报告

1．实验要求

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

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

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

2.程序分析

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

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

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

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

2.1 存储结构

存储结构：数组存储。

flag[][]数组存储数字判断输出和储能放置皇后,che[][]数组存储字符串即皇后和非皇后的形状。

2.2 关键算法分析

1、关键算法： a．

for(i=0;i

for(j=0;j

{

f[i][j]=0;

c[i][j]='*';

说明：对棋盘进行初始化 未放置皇后的为“*” b．

for(i=0;i

for(j=0;j

{

c[i][j]=che[i][j];

f[i][j]=flag[i][j];

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

for(i=0;i

for(j=0;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

for(int i=0;i

{

for(int j=0;j

{

cout

}

cout

}

cout

cout

return;

}

else Queen(m+1,f,c);

说明：首先判断是否已执行到最后一行

每输出一个算法，count计数器加1 若没有执行到最后一行，m+1继续执行Queen函数

2.3 其他

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

3.程序运行结果

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

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

4.总结

一．问题及解决办法

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

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

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

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

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