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

数据结构实验报告实验名称：实验二一一八皇后问题学生姓名：班级：班内序号：学号：日期：2014年11月27日.实验要求实验目的】进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力实验内容】利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：可以使用递归或非递归两种方法实现实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上程序分析voidSeqStack::PlaceQueen(introw) voidSeqStack::PlaceQueen(introw) 〃摆放皇后2.1存储结构存储结构：栈（递归）5(1:10)S10,5(1:10)S10,P1:10^—9-—却HPton：_卜8，——的_■itot]*4PXp6+K— Z0+-!Fp5TE*EJ4DP4吉丁DP3-◎■1Ototiom£"BPbottam+Jd►A'(b)播A.X与Y后的栈 <c）退出一乍元素启的榜22关键算法分析①递归调用摆放皇后1、关键算法伪代码：.如果输入的3大于皇后的数量，则输出皇后的位置（2）否则col从°开始递增（3）检测（r0w，c°l）上的点是否符合条件，不符合则向自增，符合则转到下一个皇后的排列2、代码详细分析：for(intcol=0;col<n;col++)//遍历0~7,Push(col);if(Check())if(Check())//判断摆放皇后的位置是否合适if(row<n-1)//若还没有放到最后一个，则进行下一个皇后的放置PlaceQueen(row+1);elsenum++;Print(n);Pop()；〃计数器加1〃打印成功的坐标点〃若不符合条件则出栈3、计算时间复杂度：0(n2)②判断皇后位置是否合适:1、关键算法伪代码：对于一个坐标，将前面每一个坐标均与这个坐标比较若在同一列或在同一斜线上，则返回0,否则j-自增1,面每一个坐标与前面做比较若与前面坐标在同一列最后返回2、 代码分析：boolSeqStack::Check(){for(inti=0;i<top;i++)次检查前面已摆放的皇后位置if(data[top]==data[i]||(abs(data[top]_data[i]))==(top_i))在同一列同一斜线returnfalse;returntrue;}3、时间复杂度：0(n)2.3其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大来表示，则可以输出全部解。3.程序运行结果(1)程序框图：//依//判断是否运用输出坐标位置classSeqStack classSeqStack //定义开始输入nNN判断是否满行判断位置q[row]q[row]=cofrow++输出结果COH+⑵程序代码:#include<iostream>usingnamespacestd;constintm=1024大高度intnum=0;案种类计数器intn;个数〃定义栈的最〃初始化方〃摆放的皇后voidSeqStack::Push(intx) voidSeqStack::Push(intx) //入栈操作顺序栈public:SeqStack(){top=T;}〃构造函数，初始化空栈voidPush(intx);//入栈voidPop();//出栈voidPlaceQueen(introw);//摆放皇后的递归函数boolCheck();〃判断是否在同一行同一列同一斜线voidPrint(intn);//打印以坐标的形式boolEmpty();//判别栈是否为空private:intdata[m];//定义数组inttop;//栈顶指};if(top>=m-1)throw上溢top++;//栈顶if(Empty())throw//栈顶if(Empty())throw"下溢"//出栈操作指针上移data[top]=x;}voidSeqStack::Pop()////栈顶top--;指针下移//摆放皇后voidSeqStack::PlaceQueen(introw){II遍历II遍历o~7,{Push(col);if(Check())//判断摆放皇后的位置是否合适{if(row<n-1) //若还没有放到最后一个，则进行下一个皇后的放置PlaceQueen(row+1);else{num++; //计数器加1Print(n); //打印成功的坐标点}}Pop()； //若不符合条件则出栈}boolSeqStack::Empty(){if(top==-1)returntrue;

elsereturnfalse;}boolSeqStack::Check(){for(inti=O;i<top;i++) //依次检查前面已摆放的皇后位置if(data[top]==data[i川(abs(data[top]_data[i]))==(top_i)) 〃判断7E口在F0一列同一斜线returnfalse;returntrue;//将栈的数}//将栈的数组形式打印成坐标inti;for(i=1;i<=n;i++)cout<<"("<<i<<","<<data[i-1]+1<<")";cout<<endl;

voidmain(){""输入Queen的数目(口>0)"<<endl;cin»n;if(n<0||n>1024)做a<<"输入错误"<<endl;}SeqStackQueen;Queen.PlaceQueen(0);//SeqStackQueen;Queen.PlaceQueen(0);//定义类的对象//从栈底开始赋值cout<<"Queen可能的摆放位置种类："<<num<<endl;//始赋值cout<<"Queen可能的摆放位置种类："<<num<<endl;//输出摆放方法的总数(3)运行结果：r"E:\vcicroscftV,：5Lp-3Stwdic,MyProjects\^S§—\Debjg\l\3S.exe撇入Qu.wn的数目金>gjP<1>1><2,5><3>8><4,6><5.3><6.?><7.2><8,4><1,1><2,6><3,8><4.3><5,?><6,4)<?.2><8,5><1.1X2,7X3,4X4,6X5,8X6,2X7,5X8,3><1.1X2,7X3,SX4,«>C5,2X6,4X7,fi>CB„3>«.2)<2,4><3,6><4.«><5,3><6.1><7.7><8.5><1,2X2,5><3,7X4,1X5,3X6,BX7,6X8,4><1,2><2f5><3,7><4,4>C5,1><6,8X7,G><8,3><1,2><2,6><3.1><4,7><5,4><6,8><7.3><8,5><1>2><2_7><3>3><4.6><5,8><&^><7.1><8.4><1,2><2,?><3>5><4,8><5,1><6,4><7,6><8,3><1,2><2,8><3,6><4,1><5,3><6,5><7,?><8,4><1,3X2,1X3,7X4,5X5,8X6,2><7>4X8,6><1.3X2,5><3,2X4,8X5,1X6,7X7,4X8,6><1,3><2>5><3,2><4,»><5,6><6,4><7>?><8>1><1.3X2,5 ><5,4X6,2X7,3X8<1,3X2F5><3,8X4,4X5,1X6,7X7,2X8,6><1,3><2,6><3,.2><4,5><5,8><6,1><?,7><8,4><1.3X2,6>0,2X4.7X5,1><6,4><?,8X8,5><1,3><2,6><3,2><4,7)<5,5><&,1><7,8><8,4><1«3><2>0<3>4><4.1><5^6><6.5><?.7>(8,2)<1,3><2,6><3,8><4.1i<5,4><6>7><7.5><8±2>"E:\vc++\Micro&oftVisualStudio'MyP同 超二\DebcigVV3JS\exg<1,3X2.5 4X5,1><6,7X7,2><»,6><1^3X2,6X3,2X4,5>C5,9><6,1X7,7X8,4><1,3X2.6X3,2X4,?>C5,G><6,IX?,8X8,4?<1,3><2>6><3.4><4.1><5,8><6,5><7>?><8,2><1,3X2,6X3,4X4.2X5,8)<G,5X7,7X8,1?(33)(2*6X3.8>《4」》<5,4)<6m7X7.5X82)<1,3X2,6><3,8X4,1X5,5X6,7X7,2X8.4><1,3X2,6X3,8><4.2><5,4><6a><7,7><8,5><1,3X2,7X3,2X4,8><5,5X6,1X7,4X8,6><1,3X2,7X3,2><4,8>C5,6><6„4><7A>«,5>KL3M2*83£3』>《4.7X5/X6IX7*2>£«.5>'<1,4><2,1><3,5><4,8><5,2><6.?><?,3><8,6><1,4><2,1><3,5><4^«><5,6><6,3><7^7><8#2><1,4><2,2><3.7><4.3><5,6><6,8><7.1><8,5><1,4X2,2><3,7X4,3X5,6X6.BX7,5X8J>(l^><2F2)OJ.?><4Jp5>C5Jkl>C6A8>C7,6>(B<3><1^><2,2><3,8X4,5X5,7X6,1><7,3X8,6><1,4><2,2><3,8><4,6><5,1><6,3><7,5><8,?><1,4><2,6><3,1><4,5><5,2><6,8><7,3><8,?><1,4><2,6><3,8><^,2><5,?><6.1><7,3><8,5><1a4><2f6X3.B><4,3X5 7X7.5X8.2><1.4X2,?X3>1><4,8><5,5X6,2X7.6><«,3><l,4><2r7><3,3><4,ft>C5,3J<6,5><7,l>C8,fr>

»“E\vc++\MicH3MftVisualStudicAMyProjects侯验=\Debug\A皇氐Eire<14.4><2,7><3,5><4,2><5,&><64.1><7,3><8,9> <1,4><2,7><3,5><4,3><5,1><6,6><7,8><8,2>Cl,4X2,8X3,1X4,3><5,6><6,2X7,7X8,5><1,4X2,8X3,1X4,5><5,7X6,2X7,6X8,3>Cl,4X2,8X3,5X4^35<5」>C6,7><7八2X8,6><1,5><2,1><3,8><4,4>(5>2><6,?>(?,3><8,6><1,5X2,2X3,4X4,6X5,8>C6,3X7,1X8<l,5><22><3.6X4a>C5,7><6H><7.e><B.3><1,5X2,<1,5><2,1><3,8><4,4>(5>2><6,?>(?,3><8,6><1,5X2,2X3,4X4,6X5,8>C6,3X7,1X8<l,5><22><3.6X4a>C5,7><6H><7.e><B.3><1,5X2,3X3,f>C\6X5,8><6,2x7,4X8,7>Cl,<5,7X6,1X7,6X8,2>(l«5X2,7><3pl><4,4>C5i2>C6.S>C7.G><8,3>7>RCl,5X2,l><3,8>C4,fi><5,3><6,7><7,2><8,4><1,5><2,2><3,4>(47X5,3>C6,B><7,6><8,1><1,5><2,2><3,BX[1f><5,4>C6,?><7,3><8,6>5X2,3X3,1X4,7X5,2><6,8X7,6X8,4><1,5X2,3X3,8X4.4?ajp5><2,7>Oj.l><4,3><5,B><6jp6><7j.4><fl,2>_ ——————————<1,5><2,7><3,2><4,6><5,3><6,1><7J4><8,8><1,5X2,7X3,2X4,6X5,3><6,1X7,8X8,4><1,5X2,7?<3,4>(41?<5,3><6,8X7,6X8,2>———————- F<1,5X2,B><3.4><,l>C5,3>C6p6><7,2><a,7>Kl,5><2,a><3,4X4,lJ<5,7>C6,2><7,6><8,3><1,6><2,1><3,5><4,2><5,8><6,3><7,7><8,4>E:\vc++\^icrosoftVisualStudio\MyPreject bugVVft&.exe<1<1.6X2,2X3,7X4,1>C5,4X6,8X7,5X8,3><1^><2.3><3,1><4,7><5,5><6,8><7,2><8,4><1,&><2,3X3,1>C4,8><5,4>C6,2><7,7><8,5>ki,8X2P3><3,1X4.8X5,5)C6.2X7,4X8,?><1,6X2.3X3,5><4,7><5,1>(6^><7,2><8,8><1^6X2,3><3^?><4,2><5,4X6,8><7,1X8,S><1^6><2,3><3,7>«2>C5,8>C6>5X7rl><e,4><1a6><2.3)《3・7X4.4〉<S」>46.H><7,2><8,5>《1fG《2p4X3f1"4通,《54》《32X7">《*f”(1,6X2,4X3.7X4,1X5.3)C6,5><7,2X8,8><1,