北郵信通院數(shù)據(jù)結(jié)構(gòu)實驗二__八皇后問題實驗報告(內(nèi)附源代碼完整版)

1、.數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱 ： 實驗二 八皇后問題學(xué)生姓名 ：班級：班內(nèi)序號 ：學(xué)號：日期： 2014年11月27日1實驗要求【實驗?zāi)康?】進(jìn)一步掌握指針、模板類 、異常處理的使用掌握棧的操作的實現(xiàn)方法掌握隊列的操作的實現(xiàn)方法學(xué)習(xí)使用棧解決實際問題的能力學(xué)習(xí)使用隊列解決實際問題的能力【實驗內(nèi)容 】利用棧結(jié)構(gòu)實現(xiàn)八皇后問題。八皇后問題19 世紀(jì)著名的數(shù)學(xué)家高斯于1850 年提出的 。 他的問題是 ：在 8*8 的棋盤上放置8 個皇后 ，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列 、同一斜線上 。 請設(shè)計算法打印所有可能的擺放方法。提示 ：1、可以使用遞歸或非遞歸兩種方法實現(xiàn)2、實現(xiàn)

2、一個關(guān)鍵算法：判斷任意兩個皇后是否在同一行、同一列和同一斜線上2. 程序分析.專業(yè) .專注.2.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu) ：棧（遞歸）2.2 關(guān)鍵算法分析遞歸調(diào)用擺放皇后1、關(guān)鍵算法偽代碼：（ 1 ） .如果輸入的 row 大于皇后的數(shù)量 ，則輸出皇后的位置（ 2 ） 否則 col 從 0 開始遞增(3)檢測 （ row ， col ）上的點是否符合條件，不符合則col 自增 ，符合則轉(zhuǎn)到下一個皇后的排列2、代碼詳細(xì)分析：void SeqStack:PlaceQueen(int row)/ 擺放皇后.專業(yè) .專注.for (int col=0;col n;col+)/ 遍歷 07 ，Push(co

3、l);if (Check()/ 判斷擺放皇后的位置是否合適if (row n-1)/ 若還沒有放到最后一個，則進(jìn)行下一個皇后的放置PlaceQueen(row+1);elsenum+;/ 計數(shù)器加1Print(n);/ 打印成功的坐標(biāo)點Pop();/ 若不符合條件則出棧3、計算時間復(fù)雜度： O(n2) 判斷皇后位置是否合適：1、 關(guān)鍵算法偽代碼：.專業(yè) .專注.對于一個坐標(biāo) ，將前面每一個坐標(biāo)均與這個坐標(biāo)比較若在同一列或在同一斜線上，則返回 0，否則 j 自增 1 ，面每一個坐標(biāo)與前面做比較若與前面坐標(biāo)在同一列最后返回2、 代碼分析 ：bool SeqStack:Check()for(inti

4、=0;itop;i+)/ 依次檢查前面已擺放的皇后位置if(datatop=datai|(abs(datatop-datai)=(top-i)/ 判斷是否在同一列同一斜線return false;return true;3、 時間復(fù)雜度 ： O(n)2.3 其他說明 ：由于輸出顯示時對話框有限，而程序結(jié)果比較多，占用空間大,運(yùn)用輸出坐標(biāo)位置來表示 ，則可以輸出全部解。3. 程序運(yùn)行結(jié)果（ 1）程序框圖 ：.專業(yè) .專注.開始輸入 nY判斷是否滿行輸出結(jié)果N判斷位置 qrowNcol+是否符合要求Yqrow=colrow+(2)程序代碼 ：#include using namespace std

5、;const int m=1024;/ 定義棧的最大高度int num=0;/ 初始化方案種類計數(shù)器int n;/ 擺放的皇后個數(shù)class SeqStack/ 定義.專業(yè) .專注.順序棧public:SeqStack()top=-1;/ 構(gòu)造函數(shù)，初始化空棧void Push(int x);/ 入棧void Pop();/ 出棧void PlaceQueen(int row);/ 擺放皇后的遞歸函數(shù)boolCheck();/ 判斷是否在同一行同一列同一斜線void Print(int n);/ 打印以坐標(biāo)的形式bool Empty();/ 判別棧是否為空private:int datam;/

6、 定義數(shù)組int top;/ 棧頂指針;void SeqStack:Push(int x)/ 入棧操作.專業(yè) .專注.if(top= m-1) throw 上溢 ;top+;/ 棧頂指針上移datatop=x;void SeqStack:Pop()/ 出棧操作if(Empty() throw 下溢 ;top-;/ 棧頂指針下移void SeqStack:PlaceQueen(int row)/ 擺放皇后for (int col=0;col n;col+)/ 遍歷 07 ，Push(col);if (Check()/ 判斷擺放皇.專業(yè) .專注.后的位置是否合適if(rown-1)/ 若還沒有放到

7、最后一個 ，則進(jìn)行下一個皇后的放置PlaceQueen(row+1);elsenum+;/ 計數(shù)器加 1Print(n);/ 打印成功的坐標(biāo)點Pop();/ 若不符合條件則出棧bool SeqStack:Empty()if(top=-1)return true;.專業(yè) .專注.elsereturn false;bool SeqStack:Check()for(inti=0;itop;i+)/ 依次檢查前面已擺放的皇后位置if(datatop=datai|(abs(datatop-datai)=(top-i)/ 判斷是否在同一列同一斜線return false;return true;void

8、SeqStack:Print(int n)/ 將棧的數(shù)組形式打印成坐標(biāo)int i;for(i=1;i=n;i+)cout(i,datai-1+1);coutendl;.專業(yè) .專注.void main() cout0 ）n;if(n1024)cout 輸入錯誤 endl;SeqStack Queen;/ 定義類的對象Queen.PlaceQueen(0);/ 從棧底開始賦值coutQueen可能的擺放位置種類:numendl;/ 輸出擺放方法的總數(shù)（ 3）運(yùn)行結(jié)果 ：.專業(yè) .專注.專業(yè) .專注.專業(yè) .專注.4. 總結(jié)調(diào)試時出現(xiàn)的問題： 最初由于遞歸的思想未能很好掌握，導(dǎo)致幾次調(diào)試都出現(xiàn)比較嚴(yán)重的錯誤 ；且在運(yùn)用該方法時，未能將八皇后問題的具體思路搞清，沒有考慮 “如果前次的皇后放置錯誤導(dǎo)致后面的放置無論如何都不能滿足要求，在設(shè)計遞歸算法總是只顯示幾種，為了將 92 種情形全部打印，采用坐標(biāo)的形式。使用了棧的存儲結(jié)構(gòu)來存儲位置的縱坐標(biāo)，不符合時將其出棧，要注意棧是否為空?？偨Y(jié) ：這次實驗讓我更好地掌