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

1、北京邮电大学电信工程学院数据结构实验报告实验名称：实验二一一利用栈结构实现八皇后问题学生姓名：班级：班内序号：学号：日期：2022年11月21日1.实验要求(1)实验目的通过选择下面五个题目之一进行实现,掌握如下内容：?进一步掌握指针、模板类、异常处理的使用?掌握栈的操作的实现方法?掌握队列的操作的实现方法?学习使用栈解决实际问题的水平?学习使用队列解决实际问题的水平(2)实验内容利用栈结构实现八皇后问题.八皇后问题19世纪著名的数学家高斯于1850年提出的.他的问题是： 在8*8的棋盘上放置8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列、同一斜线上.请设计算法打印所有可能

2、的摆放方法.可以使用递归或非递归两种方法实现实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线.(3)代码要求必须要有异常处理,比方删除空链表时需要抛出异常；保持良好的编程的风格：?代码段与段之间要有空行和缩近?标识符名称应该与其代表的意义一致?函数名之前应该添加注释说明该函数的功能?关键代码应说明其功能递归程序注意调用的过程,预防栈溢出2.程序分析2.1存储结构栈(递归)for(intcol=0;colStackSize;col+)(top*1小9&75 54 4箪2bottomsbottoms工工$(1:10)$(1:10)$(1:10)$(1:10)国3(1:3(1

3、:1010ItkItk1 110+10+卡/riri/卜tOEtOE.8+JL8+J8+J十X-mu-mu-w wXP口.川向F/w w及加?n.D.Eko白o.加&*BbottomsbottomsBP3cittom3cittom+ +产?即却C)有6个元素的栈fb)插入工与后的栈(c)退出一个玩素后的栈2.2关键算法分析void(1)递归SeqStack:PlaceQueen(introw)/在栈顶放置符合条件的值的操作,即摆放皇后(2)Push(col);if(Judgement()(if(rowStackSize-1)/判断摆放皇后的位置是否平安假设还没有放到第八个皇后,那么进行

4、下一个皇后的放置PlaceQueen(row+1);else(ans+;Output();)Pop();)/假设不符合条件那么出栈时间复杂度：O(n2)判断皇后放置位置是否符合要求boolSeqStack:Judgement()(for(inti=0;itop;i+)/if(datatop=datai|(abs(datatop卜datai)=(top-i)/列同一斜线returnfalse;returntrue;)依次检查前面各行的皇后位置,判断是否在同一欢送下载穷尽7,即穷尽列/算法步骤：对于一个坐标,将前面每一个坐标均与这个坐标比拟2假设在同一列或在同一斜线上,那么返回0,3否那么j自增1,面每一个坐标与前面做比拟假设与前面坐标在同一列5最后返回trueorfalse.2.3其他说明：由于输出显示时对话框有限,而程序结果比拟多,占用空间大,最后只显示60种到92种,这需要适当的设置对话框,设置步骤为：属性一屏幕缓冲区高度设为相对大些的值1000或其他,即可显示所有结果.也可适当完善代码将结果输出到一个文档里,便于观察分析.3 .程序运行结果实验流程图:欢送下载实验结果:4 .总结总结：这次实验让我更好地掌握了栈思想以及一维数组等等知识,以及一些书本上没有的东西,让我