数据结构实验报告-八皇后问题

《数据结构实验报告-八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实验报告实验名称：实验2——八皇后问题学生姓名：高鹏班级：2011211123班内序号：19学号：2011211442口期：2012年11月14口1.实验要求利用栈结构实现八皇后问题。八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上。2.程序分析2.1

2、存储结构采用栈存储，英结构图如下:2.2关键算法分析一：关键算法1、检测是否冲突函数原型:intlsValid(intn);自然语言：检测至笫i行所摆放的第i个皇后和之前的i・l个皇后发生冲突，如是，则返回0；反之，则当前布局合法，返回1.判断两个皇后是否相互攻击的准则是：若两个皇后处于同一行，或处于同一列，或处于同一斜线，就能相互攻击。考虑到数组的每个元素分别代表不同行的皇后,即每行只放置了一个皇后，所以不必考虑“处于同一行的攻击”的情形；处于同一列，则语句：if(queens[i]==queens[n])就能判断出

3、不同行的两个棋子是否同处一列；对于处于同一斜线的情况，他们的斜率为1或者-1,故使用下列语句：if(abs(queons[i]-queons[n])==(n-i))其屮n和i分别代表代表不同行的皇后，即数组queen[8]里不同下标的两个元素。代码：for(inti二0;i

4、turn1;2、放置新棋子函数原型:voidplaceQueen(inti);自然语言：假设前i-1行的皇后棋子已被合法布置，现从第i行开始合法地摆放新棋子。如杲当前的行数i已经大于等于8,则在总数上加1并输出当前的棋盘布局；否则将第i行的皇后放置在第j列，检查当前的布局是否合法，如果合法，则进入下一列，开始放置第i+1行的皇后；否则，移去刚才放置在第i行的皇后，重新放置该位置的皇后。代码：voidQueenPuzzle::placeQueen(inti)for(intj=0;j

5、出结果辻(i==MAX){sum++;cout«"第"《sum〈〈"组解:"《endl;printOut();return;}//放置皇后queens[i]=j;//此位置不能放皇后继续试验下一位置if(IsValid(i))placeQueen(i+1);}}二：代码详细分析1、检测是否冲突intQueenPuzzle::IsValid(intn){//将第n个皇后的位置依次于前面n—个皇后的位置比较。for(inti=0;i

6、return0;//两个皇后在同一对角线上，返回if(abs(queens[i]-queens[n])二二(n-i))return0;//没有冲突，返回。return1;}2、放置新棋子voidQueenPuzzle::placeQueen(inti){for(intj二0;j

7、Valid(i))placeQueen(i+1);}三、计算关键算法的时间、空间复杂度N皇后的时间复杂度为0(Jn),空间复杂度为S()2.3其他本程序中加入函数语句if(getch()='q')exit(0);,本该在编译执行后一次性输出92组结果，但是加入该语句后可以在输出一组结果后通过按Q选择停止输出而退出，或者通过按其他任意键选择继续输出下一组直到92组全部输出为止。每输出一组结果后口动暂停，待用户按键选择程序是否继续输出。3.程序运彳丁结果1.1测试主函数流程:开始输川半前棋盘的布局如果不冲突P继续放崟下一行

8、的皇后如果冲突‘務走刚才放證的皇厉。3.2测试条件：输出八皇后所有可能的情况及一共有多少种情况3.3测试结论c:UsersasusDocuments\/isualStudio2005Projectsliuweiyureleaseliuweiyu.exe回ILrL按q键盘退岀，按其他键继续第92组解0000按q键盘退