北邮信通院数据结构实验二--八皇后问题实验报告(内附源代码完整版)

《北邮信通院数据结构实验二--八皇后问题实验报告(内附源代码完整版)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构实验报告实验名称：实验~八Ill后冋题学生姓名：班级：班闪序号：学号：闩期：2014年11只27円1.实验要求【实验H的】>进一步掌握指针、模板类、异常处理的使用>掌握栈的操作的实现方法>掌握队列的操作的实现方法>学4使川栈解决实际问题的能力>学使川队列解决实际问题的能力【实验内容】利川栈结构实现八皇P问题。八皇P问题19世纪著名的数学家高斯于1850年捉出的。他的闷题是：在8*8的棋盘匕放置8个皇后，使其不能互和攻击，即任意两个皇后都不能处于同一行、同一列、同一•斜线上。请设计算法打印所冇可能的摆放方法。提示.•1、可

2、以使川递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2.程序分析2.1存储结构存储结构：栈（递归）S(l:10)1CM9^toptL_>S*37^6^5^4^3一2一bottom^YpXpDptoo*-1bottoms(b>插入X与Y卮的栈10,9^&6^5如14^3^2^E

3、合条件，不符合则coltl增，符☆则转到下一个皇后的排列2、代码详细分析：voidSeqStack::PlaceQueen(introw)//摆放皇后{for(intcol=0;col

4、②判断皇后位置是否合适：1、关键算法伪代码：对于一个少标，将前面每一个华标均与这个华标比较卷在同一列或决同一斜线上，则返回0，否则j自增1，面每一个少标与前面做比较若与前而坐标在同一列最后返回2、代码分析：boolSeqStack::Check(){for(inti=0;i

5、

6、(abs(data[topJ-data[i]))==(top-i))//判断是否在同一列同一斜线returnfalse;returntrue;}3、时间复杂度：0(

7、n)2.3其他说明：由于输出显示时对话框冇限，而程序结果比较多，占用空间人，运用输出坐标位置来表示，则可以输出全部解。1.程序运行结果(1)程序框图://定义栈的最人//初始化方案//摆放的皇r//定义顺//构造函//入栈//出栈//摆放阜盾//判断是否在(2)程序代码:^include〈iostream〉usingnamespacestd;constintm=1024;高度intnum=0;种类计数器intn;个数classSeqStack序栈{public:SeqStack(){top=-1;}数，初始化空栈voidPush

8、(intx);voidPop();voidPlaccQuccn(introw);的递归函数boolCheck();同一行同一列同一斜线voidPrint(intn);//打印以坐标的形式boolEmpty();//判别栈是为空private:intdatafml;//定义数组inttop;//栈顶指针};voidScqStack::Push(intx)//入栈揀作{if(top>=m-1)throw"上溢";top++;//栈顶指针上移data[topl=x;}voidSeqStack::Pop()//出栈操作{if(Empty

9、())throw"下溢"；top-;//桟顶棺针下移voidSeqStack::PlaceQueen(introw){for(intcol=0;col

10、op==-l)returntrue;elsereturnfalse;boolSeqStack::Check(){for(inti=0;i

11、

12、(abs(data[top]-datafi