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

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

2、一個(gè)關(guān)鍵算法：判斷任意兩個(gè)皇后是否在同一行、同一列和同一斜線上2. 程序分析.專業(yè) .專注.2.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) ：棧（遞歸）2.2 關(guān)鍵算法分析遞歸調(diào)用擺放皇后1、關(guān)鍵算法偽代碼：（ 1 ） .如果輸入的 row 大于皇后的數(shù)量 ，則輸出皇后的位置（ 2 ） 否則 col 從 0 開(kāi)始遞增(3)檢測(cè) （ row ， col ）上的點(diǎn)是否符合條件，不符合則col 自增 ，符合則轉(zhuǎn)到下一個(gè)皇后的排列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)/ 若還沒(méi)有放到最后一個(gè)，則進(jìn)行下一個(gè)皇后的放置PlaceQueen(row+1);elsenum+;/ 計(jì)數(shù)器加1Print(n);/ 打印成功的坐標(biāo)點(diǎn)Pop();/ 若不符合條件則出棧3、計(jì)算時(shí)間復(fù)雜度： O(n2) 判斷皇后位置是否合適：1、 關(guān)鍵算法偽代碼：.專業(yè) .專注.對(duì)于一個(gè)坐標(biāo) ，將前面每一個(gè)坐標(biāo)均與這個(gè)坐標(biāo)比較若在同一列或在同一斜線上，則返回 0，否則 j 自增 1 ，面每一個(gè)坐標(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、 時(shí)間復(fù)雜度 ： O(n)2.3 其他說(shuō)明 ：由于輸出顯示時(shí)對(duì)話框有限，而程序結(jié)果比較多，占用空間大,運(yùn)用輸出坐標(biāo)位置來(lái)表示 ，則可以輸出全部解。3. 程序運(yùn)行結(jié)果（ 1）程序框圖 ：.專業(yè) .專注.開(kāi)始輸入 nY判斷是否滿行輸出結(jié)果N判斷位置 qrowNcol+是否符合要求Yqrow=colrow+(2)程序代碼 ：#include using namespace std

5、;const int m=1024;/ 定義棧的最大高度int num=0;/ 初始化方案種類計(jì)數(shù)器int n;/ 擺放的皇后個(gè)數(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)/ 若還沒(méi)有放到

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