数据结构实验报告利用栈结构实现八皇后问题.doc

北京邮电大学信息与通信工程学院数据结构实验报告实验名称： 实验二利用栈结构实现八皇后问题学生姓名： 班 级： 班内序号： 学 号： 日 期： 2013年11月21日1 实验要求（1）实验目的通过选择下面五个题目之一进行实现，掌握如下内容： 进一步掌握指针、模板类、异常处理的使用 掌握栈的操作的实现方法 掌握队列的操作的实现方法 学习使用栈解决实际问题的能力 学习使用队列解决实际问题的能力（2）实验内容 利用栈结构实现八皇后问题。 八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。可以使用递归或非递归两种方法实现实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线。（3）代码要求必须要有异常处理，比如删除空链表时需要抛出异常；保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能递归程序注意调用的过程，防止栈溢出 2. 程序分析2.1 存储结构 栈（递归）： 2.2 关键算法分析(1) 递归void SeqStack:PlaceQueen(int row) /在栈顶放置符合条件的值的操作,即摆放皇后for (int col=0;colStackSize;col+) /穷尽7，即穷尽列Push(col); if (Judgement() /判断摆放皇后的位置是否安全 if (rowStackSize-1) /若还没有放到第八个皇后，则进行下一个皇后的放置PlaceQueen(row+1);elseans+; Output(); Pop(); /若不符合条件则出栈时间复杂度:O(n)(2) 判断皇后放置位置是否符合要求bool SeqStack:Judgement()for(int i=0;itop;i+) /依次检查前面各行的皇后位置，if(datatop=datai|(abs(datatop-datai)=(top-i) /判断是否在同一 列同一斜线return false;return true;算法步骤： 对于一个坐标，将前面每一个坐标均与这个坐标比较 若在同一列或在同一斜线上，则返回0， 否则j自增1，面每一个坐标与前面做比较 若与前面坐标在同一列 最后返回true or false.2.3 其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大，最后只显示60种到92种，这需要适当的设置对话框，设置步骤为：属性屏幕缓冲区高度设为相对大些的值（1000或其他），即可显示所有结果。也可适当完善代码将结果输出到一个文档里，便于观察分析。3. 程序运行结果 实验流程图：开始输入n 判断是否满行qk=ians+YN输出结果判断位置是否符合要求NYrow+实验结果：4. 总结总结：这次实验让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西，让我学会了运用递归