数据结构实验2——栈和队列实验报告

《数据结构实验2——栈和队列实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、行、同一列和同一斜线上2.程序分析主程序：#includeusingnamespacestd;constintStackSize=8;//皇后的个数intnum=0;templateclassSeqStack//定义顺序栈模板类{public:SeqStack(){top=-1;}//构造函数，初始化空栈voidPush(Tx);//入栈操作voidPop();//出栈操作voidPlaceQueen(introw);//放置皇后boolJudgement();//判断是否符合条件voidPrint();//输出符合条件的皇后排列bool

3、Empty(){if(top==-1)returntrue;elsereturnfalse;};//判断栈是否为空private:Tdata[StackSize];//定义数组inttop;//栈顶指针};templatevoidSeqStack::Push(Tx)//入栈操作{if(top>=StackSize-1)throw"上溢";top++;//栈顶指针上移data[top]=x;}templatevoidSeqStack::Pop()//出栈操作{if(Empty())throw"下溢";top--;//栈顶指针下移}t

4、emplateboolSeqStack::Judgement()//判断该位置是否合适{for(inti=0;i

5、

6、(abs(data[top]-data[i]))==(top-i))//判断是否满足任意两个皇后不在同列同一斜线returnfalse;returntrue;}templatevoidSeqStack::PlaceQueen(introw)//放置皇后{for(inti=0;i

7、))//判断位置是否合适{if(rowvoidSeqStack::Print()//输出皇后函数{cout<<"NO."<

8、tackSize-1;j>data[i];j--){cout<<"□";}cout<Queen;Queen.PlaceQueen(0);cout<<"总共有"<::PlaceQueen(introw)//放置皇后{for(inti=0;i

9、kSize;i++){Push(i);//入栈if(Judgement())//判断位置是否合适{if(row