北邮数据结构实验二-栈和队列

1、数据结构实验报告实验名称： 实验二栈和队列学生姓名：班 级：班内序号：学 号：日 期：1实验要求实验内容：1、 进一步掌握指针、模板类、异常处理的使用2、 掌握栈的操作的实现方法3、 掌握队列的操作的实现方法4、 学习使用栈解决实际问题的能力5、 学习使用队列解决实际问题的能力实验内容：利用栈结构实现八皇后问题。问题介绍：八皇后问题19世纪著名的数学家高斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。请设计算法打印所有可能的摆放方法。提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个

2、皇后是否在同一行、同一列和同一斜线上。2程序分析：程序源代码为：#include "stdafx.h"#include<iostream>#include<cmath>using namespace std;int p=0;class Queenpublic:数int Check(int i,int k);/判断位置是否符合要求 void putQueens(int k,int n);/递归调用函数，排列皇后 Queen()int s=0; void Print(int n);/输出皇后的排列，n为行数，输出数字为第n行中皇后位置的列private:

3、int a8; int s; ;void main() Queen Q;int n=8; cout<<"从左到右，从上到下依次为第一行到第八行排列"<<endl; cout<<"Queen的排列位置是:"<<endl; Q.putQueens(1,n); cout<<"共有 "<<p<<" 种排列方法"<<endl;void Queen:putQueens(int k,int n)/计算出皇后的排列，k是当前皇后数量，n

4、是数量上限 int i;置void Queen:Print(int n)cout<<"第"<<p+1<<"种排列方式是："<<endl;int i; putQueens(k+1,n); /调用递归函数，放置下一行皇后 if(k>n)/如果达到要求的皇后数量，则输出皇后排列顺序 Print(n); else /否则在该行中某位置添加一个皇后 for(i=1;i<=n;i+) if(Check(i,k) /判断该行中该位置放置能否放置皇后 ak=i; /若可以添加，则记录该行中该点的位置，作为排列皇

5、后的位示for(i=1;i<=n;i+) for(int p=1;p<=8;p+) if(p=ai) cout<<"Q "/在有“皇后”的位置，用大写字母“Q”标记表示 else cout<<"0 "cout<<" "/在没有“皇后”的位置，用数字“0”标记表 if(i%4=0)/经过调试能看到当每行只有棋盘上一行排列时，屏幕大小不够输出所有排列，故而棋盘上的每四行输出在屏幕上一行，棋盘上各行用空格隔开int Queen:Check(int i,int k)int j; j=1; whi

6、le(j<k) if(aj=i) | abs(aj-i)=abs(j-k) /判断列上是否有重复皇后|利用绝 cout<<endl; p+; 对值判断对角线上是否有皇后return 0; /不符合上述条件则返回0 j+; return 1; /符合条件，保证在同列、同对角线上没有重复皇后则返回12.1存储结构：栈（利用递归函数）2.2 关键算法分析基本思路：利用递归函数，实现不同行之间的递归调用，实现八皇后问题。【伪代码】1、 令k=1，皇后数目n=8；2、 判断k是否大于n3.1 是：打印出可以实现的排列方案3.2 否：循环行位置1判断该位置是否符合要求，若符合记录ak的纵

7、坐标值k+1 重复上述步骤。【关键算法】1.递归函数putQueensvoid Queen:putQueens(int k,int n)/计算出皇后的排列，k是当前皇后数量，n是数量上限 int i;置解析过程：先要判断k是否已经达到8，判断方法是看整数k+1是否超过n=8，若没有超过，则每次对于函数中的第k行，都从第k行第i=1个位置开始判断能否添加皇后。若不符合放置条件，则令位置i自增1，并且继续循环；若第i个位置符合放置皇后的条件，即为（Check（i，k）=1），那么则让数组a中的ak元素等于i，相当于在二维棋盘上的第k行中第i个元素标记为Q，则第k行的皇后位置已经确定，令k自增1，重

8、新调用putQueens函数，层层递归调用，直至能使得k=n=8，则停止调用putQueens函数，输出排列结果。 其时间复杂度为O(n*n).2.判断位置能否放置皇后int Queen:Check(int i,int k) putQueens(k+1,n); /调用递归函数，放置下一行皇后 if(k>n)/如果达到要求的皇后数量，则输出皇后排列顺序 Print(n); else /否则在该行中某位置添加一个皇后 for(i=1;i<=n;i+) if(Check(i,k) /判断该行中该位置放置能否放置皇后 ak=i; /若可以添加，则记录该行中该点的位置，作为排列皇后的位 in

9、t j;j=1; while(j<k) if(aj=i) | abs(aj-i)=abs(j-k) /判断列上是否有重复皇后|利用绝对值判断对角线上是否有皇后return 0; /不符合上述条件则返回0j+;解析过程：利用while对数字j循环，判断能否放入皇后。若aj也等于I,即为棋盘上第j行第i个元素被标记为Q，那么则不能在这个位置放入皇后，return 值为0；如果循环中aj-i等于j-k的绝对值，即对应棋盘上某一行放置Q元素的纵坐标数减去该位置的纵坐标数，绝对值和行数j与行数k的差的绝对值相等，那么显然不能符合对角线不多于一个皇后的条件，也会return 0。只有在上面两个条件都

10、符合的情况下，才会return 1，保证任意一个纵列，任意一个任意对角线不出现两个皇后。3.输出棋盘：void Queen:Print(int n)cout<<"第"<<p+1<<"种排列方式是："<<endl;示if(i%4=0)/经过调试能看到当每行只有棋盘上一行排列时，屏幕大小不够输int i; for(i=1;i<=n;i+) for(int p=1;p<=8;p+) if(p=ai) cout<<"Q "/在有“皇后”的位置，用大写字母“Q”标记表示 r

11、eturn 1; /符合条件，保证在同列、同对角线上没有重复皇后则返回1 else cout<<"0 "cout<<" "/在没有“皇后”的位置，用数字“0”标记表出所有排列，故而棋盘上的每四行输出在屏幕上一行，棋盘上各行用空格隔开解析过程：通过循环实现输出棋盘。通过递归调用，已经确定了某一个可行棋盘对应的数组a8.其中的每一个元素ak,代表对应棋盘上第k行的皇后的纵坐标为ak。那么我们可以这 cout<<endl; p+;样写出一个函数：令整型变量p=0。在每一个k下，p每次循环自增，当p=ak时，输出字母Q，代表皇

12、后的位置。而p不等于ak时，表明棋盘上该位置没有皇后，则输出空格。再通过k的自增从而实现该可行排列下所有行的输出。3. 程序运行结果(1) 测试主函数流程(2) 测试条件n取值大于0小于10本题中由于已经确定是八皇后问题，故而在main函数里面直接将n定义为8.(3)测试结果4. 总结（1）调试时出现的问题及解决的方法很明显使用VS2010，不能在一行输出棋盘上一行的条件下把92种情形全部打印出来，否则前面的几十种情况将无法显示出，。为了弥补这个问题，我将棋盘横向打印，使得屏幕上一行打印出棋盘上四行，这个需要一些语句的控制才能实现。但是即使这样，最后效果不如按照8*8打印出来的直观漂亮。（2）需要总结：通过本