八皇后实验报告.doc

数据结构实验报告
实验名称: 实验二——八皇后问题
学生姓名: 姜山
班级: 2011211106
班内序号: 14
学号: 2011210167
日期: 2012年11月16日
实验要求
【实验目的】
1、进一步掌握指针、模板类、异常处理的使用
2、掌握栈的操作的实现方法
3、掌握队列的操作的实现方法
4、学习使用栈解决实际问题的能力
5、学习使用队列解决实际问题的能力
【实验内容】
利用栈结构实现八皇后问题。
在8*8的棋盘上放置8个皇后,要求使其不能互相攻击,即任意的两个皇后都不能处于同一行、同一列或同一斜线上。请设计算法打印所有可能的摆放方法。要使用栈结构。
2. 程序分析
存储结构
利用栈存储结构。
关键算法分析
1、关键算法:
判断该位置能否放置:
bool SeqStack<T>::Judgement()
{
for(int i=0;i<top;i++) if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))
return false;
return true;
}
用for循环,data[top]=data[i]判断是否在同一列,abs(data[top]-data[i])=(top-i)判断是否在同一斜线。当既不在同一斜线也不再同一列时即可放置
打印棋盘:
void SeqStack<T>::Output()
{
for(int i=0;i<StackSize;i++)
{
for(int j=0;j<data[i];j++)
cout<<"□";
cout<<"▓";
for(int j=StackSize-1;j>data[i];j--)
cout<<"□";
cout<<endl;
}
在data[i]表示的位置打印皇后,其余位置则打印空格。
递归法放置皇后:
void SeqStack<T>::PlaceQueen(int row)
{
for (int col=0;col<StackSize;col++)
{
Push(col);
if(Judgement())
{
if (row<StackSize-1)
PlaceQueen(row+1);
else
{
count++;
Output();
}
}
Pop();
}
每一行都是从列号0开始循环,依次进行判断,如果if(Judgement)的值为真,也就是该位置可以放置棋子,则进入下一层if语句,若满足row<StackSize-1则进入递归,下一行元素的列号入栈,满足条件则继续列举,直到找到8个皇后,计数器+1,打印该情况,然后栈顶元素出栈,进入下一层for循环,放置完全8个皇后位置则打印,直到最终第一行的列号循环完毕,穷尽了所有的情况,打印所有可能的情况的棋盘,问题解决。
2、代码详细分析:
判断函数:
for(int i=0;i<top;i++) //依次检查前面各行的皇后位置
if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))