数据结构 八皇后问题 报告

数据结构实验报告

实验名称：实验2 利用栈结构实现八皇后问题

学生姓名： 廖宁

班 级： 2009211114

班内序号： 18

学 号： 09210411

日 期： 2010年11月18日

1．实验要求

八皇后问题是19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。

提示：

（1）可以使用递归或非递归两种方法实现。

（2）实现一个关键算法，判断任意两个皇后是否在同一行、同一列和同一斜线上。

2. 程序分析

程序工程包含一个模板类函数实现定义的源文件forthelove.cpp和测试源文件sbsuowang.cpp。

2.1 存储结构

存储结构为栈。

2.2 关键算法分析

(1)

判断在第row行第column列摆放皇后是否非法,采取定行不定列的方法，列相等的算法为position[i]=colume，对角线相等有两种情况：一是position在上则

row-i=colume-position[i];

二是position在下，row-i=position[i]-colume.加入能放皇后，列和对角线上值都不能相等。 具体代码如下：

int IsIllegal(int row, int column, const int* position)

{/

int i;

for (i=1; i < row; ++i)

{

if ((position[i] == column)

|| (row - i == column - position[i])

|| (row - i == position[i] - column))

{

return TRUE;

}

}

return FALSE;

}

（2）

我采用定行尝试列的方法来遍历，记录皇后位置的数组可以和栈数组合二为一，而栈顶指针也可以和行坐标合二为一，这样一来栈帧只要一个列坐标就可以了。

1.伪代码：

while(栈不空）

{

if ( 行(即栈顶) <= n && 列 <= n )

{

if ( 当前位置不能放皇后 )

{

列++;

}

else

{

列入栈(隐含着"行++");

列 = 1;

}

}

else

{

if ( 行(即栈顶) > n )

{

输出位置数组(即栈数组);

}

列退栈(隐含着"行--");

列++;

}

}//end while

具体实现代码：

void Queens(int n, void (* Visit)(const int* position))

{

//position[n]数组:position[0]为棋盘大小，即n

//position[1]~position[n]：下标为行坐标，值为列坐标

int* stack = NULL; //栈

int top; //栈顶

int column; //列

stack = (int*)malloc((n + 1) * sizeof(int));

stack[0] = n;

top = column = 1;

while(top > 0)

{

if ((top <= n) && (column <= n))

{

if (IsIllegal(top, column, stack))

{

++column;

}

else

{

stack[top++] = column;

column = 1;

}

}

else

{

if (top > n)

{

(* Visit)(stack);

}

column = stack[--top];

++column;

}

}//end while

free(stack);

return;

}

3. 程序运行结果

程序实现八皇后问题：

经过测试，程序运行良好，无明显错误。

4. 总结

（1）这次上机实验，用栈结构实现了八皇后问题，总体上程序没有很大毛病，基本上运行良好。

（2）这个程序不仅解决了八皇后的问题，求出了八皇后的摆放方法数，并有效的输出，同时推广到n皇后问题上，只要n的数值不是很大，都能正确的得出结果，这是不错的提升。

（3）对栈结构有了深刻的认识，数据结构的东西，必须是经过上机去体会的，不能拘泥于课本，课本的东西还是比较基础的，有时候需要实用的知识的时候，多参考查询网上的知识是非常有益的。

（4）最后衷心感谢老师和同学在我做这个程序过程中的关心和帮助。

本文来源：https://www.bwwdw.com/article/6su1.html