實(shí)驗(yàn)二——利用棧結(jié)構(gòu)實(shí)現(xiàn)八皇后問題.doc

《實(shí)驗(yàn)二——利用棧結(jié)構(gòu)實(shí)現(xiàn)八皇后問題.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、北京郵電大學(xué)信息與通信工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)二——利用棧結(jié)構(gòu)實(shí)現(xiàn)八皇后問題學(xué)生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：實(shí)驗(yàn)要求實(shí)驗(yàn)?zāi)康模和ㄟ^選擇下面五個(gè)題目之一進(jìn)行實(shí)現(xiàn)，掌握如下內(nèi)容：?進(jìn)一步掌握指針、模板類、異常處理的使用?掌握棧的操作的實(shí)現(xiàn)方法?掌握隊(duì)列的操作的實(shí)現(xiàn)方法?學(xué)習(xí)使用棧解決實(shí)際問題的能力?學(xué)習(xí)使用隊(duì)列解決實(shí)際問題的能力實(shí)驗(yàn)內(nèi)容：1、利用棧結(jié)構(gòu)實(shí)現(xiàn)八皇后問題。2、八皇后問題19世紀(jì)著名的數(shù)學(xué)家高斯于1850年提出的。他的問題是：在8*8的棋盤上放置8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇

2、后都不能處于同一行、同一列、同一斜線上。請(qǐng)?jiān)O(shè)計(jì)算法打印所有可能的擺放方法。3、提示：1.可以使用遞歸或非遞歸兩種方法實(shí)現(xiàn)2.實(shí)現(xiàn)一個(gè)關(guān)鍵算法：判斷任意兩個(gè)皇后是否在同一行、同一列和同一斜線上第7頁北京郵電大學(xué)信息與通信工程學(xué)院2.程序分析2.1存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：棧2.2關(guān)鍵算法分析2.2.1皇后擺放位置可行性的判斷判斷任意兩個(gè)皇后是否在同一行、同一列和同一斜線上for(inti=0;i

3、

4、(abs(queen[top]-queen[i]))==(t

5、op-i))returnfalse;returntrue;1.對(duì)于一個(gè)坐標(biāo)，將前面每一行的皇后列標(biāo)與本行的皇后列標(biāo)比較，若列標(biāo)相同或列標(biāo)想減的絕對(duì)值與行標(biāo)相減的值相同，返回false2.否則i自增13.列標(biāo)i=8，即未發(fā)現(xiàn)沖突，循環(huán)結(jié)束，返回true第7頁北京郵電大學(xué)信息與通信工程學(xué)院2．2．2插入皇后算法voidSeqStack::SetQueen(intr)//設(shè)置皇后{for(inti=1;i<=StackSize;i++){Push(i);if(Feasible()){if(r

6、-1)SetQueen(r+1);else{Count++;Print();}}Pop();}}算法步驟：（1）判斷列標(biāo)在（0，8）范圍內(nèi)（2）將列標(biāo)入棧（3）判斷在該行列坐標(biāo)下，皇后位置是否可行（4）若可行，判斷插入列表所在行是否為最后一行，若是，打印列標(biāo)；否則，開始下一行的皇后位置的選擇。時(shí)間復(fù)雜度O（n2）2.3其他程序代碼：#includeusingnamespacestd;constintStackSize=8;//設(shè)置皇后數(shù)組template第7頁北京郵電大學(xué)信息

7、與通信工程學(xué)院classSeqStack{public:SeqStack(){top=-1;}//構(gòu)造函數(shù)voidPush(Tx);//入棧操作voidPop();//出棧操作voidSetQueen(introw);//設(shè)置皇后位置boolFeasible();//判斷皇后可行性voidPrint();//打印boolEmpty(){if(top==-1)returntrue;elsereturnfalse;};//判斷棧是否為空private:Tqueen[StackSize];inttop;};templ

8、atevoidSeqStack::Push(Tx)//入棧操作{if(top>=StackSize-1)throw"棧滿";top++;queen[top]=x;}templatevoidSeqStack::Pop(){if(Empty())throw"棧下溢";top--;}intCount=0;templatevoidSeqStack::SetQueen(intr)//設(shè)置皇后{for(inti=1;i<=StackSize;i++){Pus

9、h(i);if(Feasible())//判斷是否可以擺放皇后{if(rboolSeqStack::Feasible()//可行性判斷{for(inti=0;i

10、

11、(abs(queen[top]-queen[i]))==(top-i))//判斷皇后不在同一列或?qū)?/p>

12、角線上returnfalse;returntrue;}templatevoidSeqStack::Print(){cout<