北郵數(shù)據(jù)結(jié)構(gòu)實驗二實驗報告皇后問題

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

2、后是否在同一行、同一列和同一斜線上2. 程序分析2.1 存儲結(jié)構(gòu)利用棧的存儲結(jié)構(gòu)2.2 關(guān)鍵算法分析2.2.1 判斷算法分析：判斷第i行的皇后與前i-1行的皇后是否在同一列或者同一對角線上。判斷是否在同一列上只需比較棧內(nèi)存的數(shù)是否相等；判斷是否在同一對角線上只需比較行差和列差是否相等。代碼實現(xiàn)：bool stack:check() /bool型for(int i=0;i<top;i+)if(datatop=datai|abs(datatop-datai)=top-i) /符合列和對角線的點return false;return true;2.2.2 放置皇后代碼分析：放置皇后用遞歸函數(shù)實

3、現(xiàn)。從第0行開始放置皇后，窮盡該列。列值入棧，判斷皇后位置是否符合放置要求，若不能，則出棧；若能，則判斷是否為第8個皇后，若是，則打印棋盤，并且計數(shù)器+1；若不是，則進(jìn)行row+1行遞歸函數(shù)繼續(xù)。遞歸終止條件：row=stacksize-1。代碼實現(xiàn)：void stack:Queen(int row) /輸入的參數(shù)為皇后所在行數(shù)for(int col=0;col<stacksize;col+)push(col);if(check() /判斷不同行之間的皇后是否符合要求if(row=stacksize-1) /遞歸停止條件num+; /計數(shù)print(); /打印else Queen(ro

4、w+1); /遞歸（將皇后放置到下一行），直到把皇后放完8行為止pop(); /不符合，出棧2.3 其他當(dāng)棋盤大小為8x8時，共有92種方案，若要研究其他size的棋盤，更改stacksize值即可。3. 程序運行結(jié)果3.1 主函數(shù)流程圖開始row=0入棧出棧合適？ 否row+1 是row=8? 否 是計數(shù)器+1棋盤打印結(jié)束3.2 程序運行結(jié)果4. 總結(jié)1.遇到的問題剛開始接觸這個題目時，不太懂對判斷的皇后是否在同一對角線上的條件，只考慮到了一邊對角線，而沒有考慮到另外一種情況。正確的條件是：(abs(datatop-datai)=top-i)，而我卻把絕對值漏掉了，導(dǎo)致最后出現(xiàn)了2113種放

5、置方法；看到棋盤后我才知道我漏掉了另一種情況。我還遇到的另外一個問題是結(jié)果顯示不完全，只能看到第64到第92種方案，經(jīng)過查資料后才知道是屏幕緩沖區(qū)的高度設(shè)置不夠。適當(dāng)增加高度后即可顯示全部的方案。2.心得體會通過本次實驗，我對棧結(jié)構(gòu)有了進(jìn)一步的理解。解決這類擺放問題，充分運用了棧“后入先出”的特點，用棧來保存放置的位置；以及使用了遞歸函數(shù)對問題進(jìn)行了簡化。下附本程序所有源代碼：#include<iostream>#include<windows.h>using namespace std;const int stacksize=8;int num=0; /靜態(tài)變量num

6、用于計數(shù)class stack /建立一個棧類解決問題private:int datastacksize; /定義數(shù)組，datai保存皇后在第i行的第幾個位置int top; /棧頂指針public:stack()top=-1; /默認(rèn)構(gòu)造函數(shù)void push(int x); /入棧void pop(); /出棧bool Empty(); /判斷棧是否為空bool check(); /檢查列和斜線是否符合要求void print(); /打印解決方案void Queen(int row); /解決措施;bool stack:Empty()if(top=-1) return true;else

7、 return false;void stack:push(int x) if(top>=stacksize) /異常處理throw"上溢"elsetop+;datatop=x;void stack:pop() if(Empty() /異常處理throw"下溢"elsetop-;bool stack:check() /bool型for(int i=0;i<top;i+)if(datatop=datai|abs(datatop-datai)=top-i) /符合列和對角線的點return false;return true;void stack

8、:print()cout<<"第"<<num<<"種方案："<<endl;for(int i=0;i<stacksize;i+) /按行輸出，i表示第i行for(int j=0;j<datai;j+) /皇后前j個空位用表示cout<<"" cout<<"" /表示皇后for(int j=stacksize-1;j>datai;j-)/皇后后7-j個空位用表示 cout<<""cout<<endl;cout<<endl;void stack:Queen(int row) /輸入的參數(shù)為皇后所在行數(shù)for(int col=0;col<stacksize;col+)push(col);if(check() /判斷不同行之間的皇后是否符合要求if(row=stac