搜索
北京邮电大学信息与通信工程学院第1页数据结构实验报告实验名称：实验二——八皇后问题学生姓名：班级：班内序号：学号：日期：2014年11月27日1．实验要求【实验目的】进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力【实验内容】利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.程序分析2.1存储结构存储结构：栈（递归）北京邮电大学信息与通信工程学院第2页2.2关键算法分析①递归调用摆放皇后1、关键算法伪代码：（1）.如果输入的row大于皇后的数量，则输出皇后的位置（2）否则col从0开始递增(3)检测（row，col）上的点是否符合条件，不符合则col自增，符合则转到下一个皇后的排列2、代码详细分析：voidSeqStack::PlaceQueen(introw)//摆放皇后{for(intcol=0;coln;col++)//遍历0~7，{Push(col);if(Check())//判断摆放皇后的位置是否合适{if(rown-1)//若还没有放到最后一个，则进行下一个皇后的放置PlaceQueen(row+1);else{num++;//计数器加1Print(n);//打印成功的坐标点}}Pop();//若不符合条件则出栈}}北京邮电大学信息与通信工程学院第3页3、计算时间复杂度：O(n²)②判断皇后位置是否合适：1、关键算法伪代码：对于一个坐标，将前面每一个坐标均与这个坐标比较若在同一列或在同一斜线上，则返回0，否则j自增1，面每一个坐标与前面做比较若与前面坐标在同一列最后返回2、代码分析：boolSeqStack::Check(){for(inti=0;itop;i++)//依次检查前面已摆放的皇后位置if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否在同一列同一斜线returnfalse;returntrue;}3、时间复杂度：O(n)2.3其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大,运用输出坐标位置来表示，则可以输出全部解。3.程序运行结果北京邮电大学信息与通信工程学院第4页（1）程序框图：(2)程序代码：#includeiostreamusingnamespacestd;constintm=1024;//定义栈的最大高度intnum=0;//初始化方案种类计数器intn;//摆放的皇后个数classSeqStack//定义顺序栈{public:SeqStack(){top=-1;}//构造函数，初始化空栈voidPush(intx);//入栈voidPop();//出栈voidPlaceQueen(introw);//摆放皇后的递归函数boolCheck();//判断是否在同一行同一列同一斜线开始输入n判断是否满行q[row]=colrow++YN输出结果判断位置q[row]是否符合要求NYcol++北京邮电大学信息与通信工程学院第5页voidPrint(intn);//打印以坐标的形式boolEmpty();//判别栈是否为空private:intdata[m];//定义数组inttop;//栈顶指针};voidSeqStack::Push(intx)//入栈操作{if(top=m-1)throw上溢;top++;//栈顶指针上移data[top]=x;}voidSeqStack::Pop()//出栈操作{if(Empty())throw下溢;top--;//栈顶指针下移}voidSeqStack::PlaceQueen(introw)//摆放皇后{for(intcol=0;coln;col++)//遍历0~7，{Push(col);if(Check())//判断摆放皇后的位置是否合适{if(rown-1)//若还没有放到最后一个，则进行下一个皇后的放置PlaceQueen(row+1);else{num++;//计数器加1Print(n);//打印成功的坐标点北京邮电大学信息与通信工程学院第6页}}Pop();//若不符合条件则出栈}}boolSeqStack::Empty(){if(top==-1)returntrue;elsereturnfalse;}boolSeqStack::Check(){for(inti=0;itop;i++)//依次检查前面已摆放的皇后位置if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否在同一列同一斜线returnfalse;returntrue;}voidSeqStack::Print(intn)//将栈的数组形式打印成坐标{inti;for(i=1;i=n;i++)cout(i,data[i-1]+1);coutendl;}voidmain(){cout输入Queen的数目（n0）endl;cinn;if(n0||n1024){cout输入错误endl;}SeqStackQueen;//定义类的对象Queen.PlaceQueen(0);//从栈底开始北京邮电大学信息与通信工程学院第7页赋值coutQueen可能的摆放位置种类:numendl;//输出摆放方法的总数}（3）运行结果：北京邮电大学信息与通信工程学院第8页北京邮电大学信息与通信工程学院第9页4.总结调试时出现的问题：最初由于递归的思想未能很好掌握，导致几次调试都出现比较严重的错误；且在运用该方法时，未能将八皇后问题的具体思路搞清，没有考虑“如果前次的皇后放置错误导致后面的放置无论如何都不能满足要求，在设计递归算法总是只显示几种，为了将92种情形全部打印，采用坐标的形式。使用了栈的存储结构来存储位置的纵坐标，不符合时将其出栈，要注意栈是否为空。总结：这次实验让我更好地掌握了栈思想以及函数的嵌套调用等等知识,以及一些书本上没有的东西，让我学会了运用递归算法去解决一些复杂的问题。另外，在写程序时，要避免由于粗心造成的低级错误，减少调试的次数。改进：不仅可以设计放置八皇后，只要修改输入的N，便可显示其他情况的结果。