实验二八皇后问题.doc

2009级数据结构实验报告实验名称： 实验二 栈和队列学生姓名：班 级：班内序号：学 号：日 期：一、实验要求1实验目的:进一步掌握指针、模板类、异常处理的使用；掌握栈的操作的实现方法；掌握队列的操作的实现方法；培养使用栈解决实际温特的能力；培养使用队列解决实际问题的能力；2实验内容利用栈结构是八皇后问题。八皇后问题：在8X8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。3代码要求 必须有异常处理，保持良好的编程风格，递归程序注意调用的过程，防止栈溢出。二、程序分析1创建棋盘const int MAXSIZE = 8;/棋盘大小int chessMAXSIZEMAXSIZE=0;int row;int col;2解决个行、列、对角线上是否有皇后的方法int Solve() stack stack; int colMAXSIZE = 0, md2 * MAXSIZE - 1 = 0, sd2 * MAXSIZE - 1 = 0;/互斥标志，表示同一列及对角线上是否有皇后， int str, stc, i,j; int scount = 0; Node topNode; for(i = 0; i MAXSIZE; i+) topNode.row = 0; topNode.col = MAXSIZE - 1 - i; topNode.isMarked = false; stack.push(topNode); 以行为单位回溯while(!stack.empty() topNode = stack.top(); str = topNode.row; stc = topNode.col; if(topNode.isMarked=false) / 如果栈顶元素的位置并没有确立 if(colstc | mdstr - stc + MAXSIZE - 1 | sdstr + stc) /如果同一列或同一对角线上已有皇后，则退回*/ stack.pop(); else /占据这个位置，设置列、对角线上的互斥标志 colstc = 1; mdstr - stc + MAXSIZE - 1 = 1; sdstr + stc = 1; /标记栈顶元素的isMarked 值 topNode.isMarked = true; stack.pop(); stack.push(topNode); chessstrstc = 1;/标记棋盘对应位置 if(str = MAXSIZE - 1) / 如果此时已经到达最后一行,则表示此种布局方法是成功的,输出相关信息 coutA solution is:endl; for(i=0;iMAXSIZE;+i) for(j=0;jMAXSIZE;+j) if(chessij=1) cout(i+1,j+1); coutendl; scount+; else / 如果此时没有到达最后一行,则继续进栈并初始化 for(i = 0; i MAXSIZE; i+) topNode.row = str + 1; topNode.col = MAXSIZE - 1 - i; topNode.isMarked = false; stack.push(topNode); else /如果栈顶元素位置已确立,则栈顶元素出栈，初始化互斥标志,准备继续寻找其它的方法 colstc = 0; mdstr - stc +MAXSIZE - 1 = 0; sdstr + stc = 0; chessstrstc = 0; stack.pop(); return scount;三、运行结果测试结果为92种，把行列以坐标的形式列出来了，结果正确。四、总结这次编写主要是考察用栈解决实际问题的能力。以及递归的运用。实验中要运用到回溯。整体上讲对许多方面都起到了锻炼