實驗二利用棧結構實現(xiàn)八皇后問題

《實驗二利用棧結構實現(xiàn)八皇后問題》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、數(shù)據(jù)結構實驗報告實驗名稱：實驗二一一利用棧結構實現(xiàn)八皇后問題學生姓名：班級：班內(nèi)序號：學號：曰期：實驗要求實驗目的：通過選擇下面五個題目之一進行實現(xiàn)，掌握如下內(nèi)容:＞進一步掌握指針、模板類、異常處理的使用＞掌握棧的操作的實現(xiàn)方法＞掌握隊列的操作的實現(xiàn)方法＞學習使用棧解決實際問題的能力＞學習使用隊列解決實際問題的能力實驗內(nèi)容：1、利用棧結構實現(xiàn)八皇后問題。2、八皇后問題19世紀著名的數(shù)學家高斯于1850年提出的。他的問題是：在8*8的棋盤上放置8個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列、同一斜線上。請設計算

2、法打印所有可能的擺放方法。3、提不：1.可以使用遞歸或非遞歸兩種方法實現(xiàn)2.實現(xiàn)一個關鍵算法：判斷任意兩個皇后是否在同一行、同一列和同一斜線上2.程序分析2.1存儲結構存儲結構：棧Queenm<^4OD=7aueen(61Qutenl61aueenl61aueenfSIaueenfSIaueen(51aueenf41aueen(41Queen

3、41aueen(31aueenf31aueenr31aueen(21aueen(21aueen

4、21QueenfllQueen⑴aueenfllqueen[0]queen[0]queen[

5、0]緬入S后，Push元索入Mbtop++若MlttS后位■不合授，PopWt,top-2.2關鍵算法分析2.2.1皇后擺放位置可行性的判斷判斷任意兩個皇后是否在同一行、同一列和同一斜線上for(inti=0;i

6、

7、(abs(queen[top]-queen[i]))==(top-i))returnfalse;returntrue;1.對于一個坐標，將前而每一行的皇后列標與本行的皇后列標比較，若列標相冋或列標想減的絕對值與行標相減的值相同，返回false2.否則i自

8、增13.列標i=8，即未發(fā)現(xiàn)沖突，循環(huán)結束，返回true2.2.2插入皇后算法//設置皇后voidSeqStack::SetQueen(intr)for(inti=l;i<=StackSize;i++){Push(i);if(Feasible()){if(r〈StackSize-l)SetQueen(r+1);else{Count+十；Print0;}}Pop();}}算法步驟：(1)判斷列標在(0,8)范圍內(nèi)(2)將列標入棧(3)判斷在該行列坐標下，皇后位置是否可行(4)若可行，判斷插入列表所在行是否為最后一行，若是，打

9、印列標；否則，開始下一行的皇后位置的選擇。時間復雜度0(n2)2.3其他程序代碼：//沒置皇后數(shù)組#includeusingnamespacestd;constintStackSize=8;template〈classT>classSeqStackSeqStack(){top=-l:}//構造函數(shù)voidPush(Tx);//入棧操作voidPop();//出棧操作voidSetQueen(introw);//設置皇后位置boolFeasible0;//判斷皇后可行性voidPrint();"打印boolEm

10、pty(){if(top==-l)returntrue;elsereturnfaprivate:public://判斷棧是否為空Tqueen[StackSize];inttop;）；templatevoidScqStack::Push(Tx)//入棧操作{if(top>=StackSize-l)throw"棧滿〃；top++;queen[top]=x:)template〈classT>voidSeqStack::Pop(){if(Empty())throw〃棧下溢"；top一一；)intCount=0

11、;templatevoidScqStack::SetQueen(intr)//設置呈后{for(inti=l;i<=StackSize;i++){Push⑴；if(Feasible0)//判斷是否可以擺放皇后{if(rboolSeqStack::Feasible()//可行性判斷{for(inti=0;i〈top;i++)//判斷皇后不在if(queen[top]=

12、=queen[i]

13、(abs(queen[top]-queen[i]))==(top-i))同一列或?qū)蔷€上returnfalse;returntrue;template〈classT>voidSeqStack::Print(){cout〈〈C()unt<