Removed-数据结构实验2——栈和队列实验报告37.pdf

《Removed-数据结构实验2——栈和队列实验报告37.pdf》由会员分享，可在线阅读，更多相关《Removed-数据结构实验2——栈和队列实验报告37.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、同一列和同一斜线上2.程序分析主程序：#include using namespace std;const int StackSize=8;/皇后的个数int num=0;template class SeqStack/定义顺序栈模板类 public:SeqStack()top=-1;/构造函数，初始化空栈14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412 void Push(T x);/入栈

3、操作 void Pop();/出栈操作 void PlaceQueen(int row);/放置皇后 bool Judgement();/判断是否符合条件 void Print();/输出符合条件的皇后排列 bool Empty()if(top=-1)return true;else return false;/判断栈是否为空 private:T dataStackSize;/定义数组 int top;/栈顶指针;template void SeqStack:Push(T x)/入栈操作 if(top=StackSize-1)throw 上溢;top+;/栈顶指针上移 datatop=x;te

4、mplate void SeqStack:Pop()/出栈操作 if(Empty()throw 下溢;top-;/栈顶指针下移template bool SeqStack:Judgement()/判断该位置是否合适 for(int i=0;itop;i+)14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412 if(datatop=datai|(abs(datatop-datai)=(top-i)

5、/判断是否满足任意两个皇后不在同列同一斜线 return false;return true;template void SeqStack:PlaceQueen(int row)/放置皇后 for(int i=0;iStackSize;i+)Push(i);/入栈if(Judgement()/判断位置是否合适if(rowStackSize-1)PlaceQueen(row+1);/如果合适满足条件则放置一个皇后,递归调用else num+;/不满足条件则到下一行 Print();/输出符合条件的皇后 Pop();/出栈template void SeqStack:Print()/输出皇后函数c

6、outNO.num:endl;for(int i=0;iStackSize;i+)for(int j=0;jdatai;j+)cout;14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412 coutdatai;j-)cout;coutendl;coutendl;void main()SeqStack Queen;Queen.PlaceQueen(0);cout总共有num种摆放方法。endl;2

7、.1 存储结构1、存储结构：栈（递归）2.2 关键算法分析1、递归void Queen:Queens(int k,int n)/计算出皇后的排列，k 是当前皇后数量，n是数量上限14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412void SeqStack:PlaceQueen(int row)/放置皇后 for(int i=0;iStackSize;i+)Push(i);/入栈if(Judge

8、ment()/判断位置是否合适if(rowStackSize-1)PlaceQueen(row+1);/如果合适满足条件则放置一个皇后else num+;/不满足条件则到下一行 Print();/输出符合条件的皇后 Pop();/出栈算法步骤：（1）.如果输入的 k 大于皇后的数量，则输出皇后的位置（2）。否则 i 从 1 开始递增(3),检测（k，i）上的点是否符合条件，不符合则 i 自增，符合则转到下一个皇后的排列时间复杂度：O(n)2、判断皇后放置位置是否符合要求template bool SeqStack:Judgement()/判断该位置是否合适 for(int i=0;itop;i

9、+)if(datatop=datai|(abs(datatop-datai)=(top-i)/判断是否满足任意两个皇后不在同列同一斜线 return false;14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412 return true;算法步骤：1.对于一个坐标，将前面每一个坐标均与这个坐标比较2.若在同一列或在同一斜线上，则返回 0，3.否则 j 自增 1，面每一个坐标与前面做比较4.若与

10、前面坐标在同一列5.最后返回 12.3 其他说明：由于输出显示时对话框有限，而程序结果比较多，占用空间大，最后只显示 60 种到 92 种，可以运用输出坐标位置来表示，则可以输出全部解如：void SeqStack:Print()/输出皇后函数coutNO.num:endl;for(int i=0;iStackSize;i+)for(int j=0;jdatai;j+)cout;coutdatai;j-)cout;coutendl;coutendl;14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”748

11、4845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”234123.程序运行结果1 实验流程图 开始输入 n 判断是否满行qk=ik+YN输出结果判断位置（i，k）是否符合要求NYi+2 测试条件：无特殊测试条件3.实验结果:14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412 14“”“”“”“”“”“”“”232403001201502426435

12、2009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”234124.总结1、调试时出现的问题及解决的方法在调试过程中出现运行结果最后一列打印格子，只出现皇后，并且打印出许多重复的皇后布局，导致程序不断运行。解决方法，经过查找发现是皇后位置的判断语句出错。2 心得体会较熟练的掌握了栈和队列的应用，以及函数递归调用的思想3 下一步的改进不仅可以设计放置八皇后，也可以是9皇后，10皇后，只要修改N，目前程序无法显示全部92种方法，可以加一些控制语句使它分页显示92种14“”“”“”“”“”“”“”2324030012015024264352009“”200932820302130“”“”“”2008“”7484845l00081700230012_3 _ _4202010“”“”41“”_2“”“”1“”23412