1、<p><b>　　一 設(shè)計目的</b></p><p>　　1．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；</p><p>　　2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；</p><p>　　3.提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；</p>

2、<p>　　4.訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學的工作方法和作風。</p><p><b>　　二 設(shè)計內(nèi)容</b></p><p>　　求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。</p><p>　　這是來源于國際象棋的一個問題?；屎罂梢匝刂?/p>

3、縱橫和兩條斜線8個方向相互捕捉。如圖所示，一個皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個皇后相互捕捉，也就是下一個皇后不能放的位置。 </p><p>　　圖2-1：擺放示意圖</p><p>　　根據(jù)這個規(guī)則，我們可以利用一個函數(shù)來判斷某個位置是否安全，安全的位置說明它所在的同一行、同一列或兩條線上都沒有放置過皇后，因此不會出現(xiàn)皇后互相攻

4、擊的情況；否則該位置不安全。其具體實現(xiàn)過程是找出所有放置的皇后，將他們的位置與該位置進行比較判斷。又注意到同一行只能放一個皇后，因此，只需要對前面的各行逐行掃描皇后，就可以找出所有皇后的位置。</p><p>　　下圖是其中一種擺放皇后的方法：</p><p>　　圖2-2：一種擺放皇后的方法</p><p><b>　　三 設(shè)計要求</b>&

5、lt;/p><p>　　1.問題分析和任務(wù)定義：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ </p><p>　　2.邏輯設(shè)計：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要

6、模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。</p><p>　　3.詳細設(shè)計：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。</p><p>　　

7、4.程序編碼：把詳細設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。</p><p>　　5.程序調(diào)試：采用自底向上，分模塊進行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結(jié)果。</p><p>　　6.結(jié)果分析：程序運行結(jié)果

8、包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析。</p><p>　　7.編寫課程設(shè)計說明書。</p><p><b>　　四 設(shè)計過程</b></p><p><b>　　1.算法思想分析</b></p><p>　　這道題可以用遞歸循環(huán)的方法來做，分別一一測試

9、每一種擺法，直到得出正確的答案。主要解決以下幾個問題。</p><p>　?。?）沖突（包括行、列、兩條對角線）</p><p>　?、?列：規(guī)定每一列放一個皇后，不會造成列上的沖突。</p><p>　?、?行：當?shù)趇行被某個皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以i為下標的標記置為被占領(lǐng)狀態(tài)。</p><p>　?、?對角線

10、：對角線有兩個方向。在同一對角線上的所有點（設(shè)下標為（i,j）），要么（i+j）是常數(shù)，要么（i-j）是常數(shù)。因此，當?shù)趇個皇后占領(lǐng)了第j列后，要同時把以（i+j）、（i-j）為下標的標記置為被占領(lǐng)狀態(tài)。</p><p><b>　?。?）數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　① 解數(shù)組A，A[i]表示第i個皇后放置的列，范圍為1~8。</p><

11、p>　　② 行沖突標記數(shù)組B，B[j]=0 表示第j行空閑，B[j]=1 表示第j行被占領(lǐng)，范圍為1~8。</p><p>　　③ 對角線沖突標記數(shù)組C、D。C[i-j]=0 表示第（i-j）條對角線空閑，C[i-j]=1 表示第（i-j）條對角線被占領(lǐng)，范圍-7~7。D[i+j]=0 表示第（i+j）條對角線空閑，D[i+j]=1 表示第（i+j）條對角線被占領(lǐng)，范圍2~16。</p>&l

12、t;p><b>　　2.算法描述與實現(xiàn)</b></p><p>　　利用JudgeQueen（）函數(shù)來實現(xiàn)對皇后擺放位置的確定，并用回溯法來完成對所有皇后的擺放。</p><p>　　void JudgeQueen1(int i)</p><p>　　void JudgeQueen2(int i)</p><p>

13、　　a[i]表示第i個皇后放置的列，范圍為1~8。</p><p>　　行沖突標記數(shù)組b，b[j]=0 表示第j行空閑，b[j]=1 表示第j行被占領(lǐng)，范圍為1~8</p><p>　　c[i-j]=0 表示第（i-j）條對角線空閑，c[i-j]=1 表示第（i-j）條對角線被占領(lǐng)，范圍-7~7。D[i+j]=0 表示第（i+j）條對角線空閑，d[i+j]=1 表示第（i+j）條對角線被占

14、領(lǐng)，范圍2~16。</p><p>　　利用if ((b[j]==0) &&(c[i+j]==0)&& (d[i-j]==0))語句來判斷擺放位置是否沖突。</p><p>　　利用JudgeQueen1(i+1)的函數(shù)調(diào)用來實現(xiàn)當8個皇后沒有擺完，遞歸擺放下一皇后的操作。</p><p>　　b[j]=0；c[i+j]=0；d[i-

15、j]=0；這三個語句來進行回溯。</p><p>　　編寫程序主函數(shù)，在main( )中調(diào)用各個功能函數(shù)實現(xiàn)八皇后問題的要求，其中運用switch( )函數(shù)實現(xiàn)八皇后問題的操作，并調(diào)用上述的JudgeQueen（）函數(shù)。</p><p><b>　　算法流程</b></p><p><b>　　A、 數(shù)據(jù)初始化。</b>&

16、lt;/p><p>　　B、 從n列開始擺放第n個皇后（因為這樣便可以符合每一豎列一個皇后的要求），先測試當前位置（n，m）是否等于0（未被占領(lǐng)）。如果是，擺放第n個皇后，并宣布占領(lǐng)（記得要橫列豎列斜列一起設(shè)置），接著進行遞歸；如果不是，測試下一個位置（n，m+1），但是如果當n<=8，m=8時，發(fā)現(xiàn)此時已無法擺放時，便要進行回溯。從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解

17、的方法，稱為“回溯法”。</p><p>　　C、 當n>8時，便打印出結(jié)果。</p><p>　　流程圖如4-1所示：</p><p>　　圖4-1：程序流程圖</p><p><b>　　3.系統(tǒng)測試</b></p><p>　　（1）由于對八個皇后放置的位置不能一次確定，而且前一個皇后

18、的放置位置直接影響著后面的放置位置，使程序調(diào)試時要花費不少時間。</p><p>　?。?）本程序有些代碼重復(fù)出現(xiàn)，顯得程序的有些代碼看起來很雜亂。</p><p>　?。?）本程序模塊劃分比較合理，且利用指數(shù)組存儲棋盤，操作方便。</p><p>　?。?）算法的時空分析。</p><p>　　該算法的運行時間和和皇后的放置方法成正比，在最

19、好情況下的時間和空間復(fù)雜度均為O（1），在最差情況下均為O（n2）），平均情況在它們之間，即（1+ n2）/2。</p><p><b>　?、僦鹘缑?lt;/b></p><p>　　在Dos下運行程序，出現(xiàn)如下主界面?？梢酝ㄟ^輸入數(shù)字0、1、2加回車實現(xiàn)不同的目的，在此界面中可以得到位置標明法和視圖顯示法兩種表示出所計算出的八皇后的擺放分布。圖如4-2所示：</p

20、><p>　　圖4-2：運行時主界面</p><p><b>　?、谧咏缑?</b></p><p>　　在主界面下輸入數(shù)字1可以進入如下的子界面。下圖為按每一行皇后所擺放的列的位置輸出的結(jié)果的部分截圖，如4-3所示：</p><p><b>　　圖4-3：子界面</b></p><

21、p><b>　?、圩咏缑?</b></p><p>　　在主界面輸入2時所進入的子界面。以視圖的方式按矩陣方式輸出八皇后擺放所得的結(jié)果。如圖4-4所示：</p><p>　　圖4-4：按矩陣方式打印</p><p><b>　　五．設(shè)計總結(jié)</b></p><p>　　通過該題的練習，使我們學

22、會了由遞歸到非遞歸的轉(zhuǎn)換以及回溯法的思想，而且可以分析它們的效率高低，什么時候用遞歸合理，什么時候不能用，這都是通過這次課程設(shè)計學到的。八皇后的問題經(jīng)過小組討論分析之后，我們便有了設(shè)計的思路，最終成功的設(shè)計出來。這次課設(shè)也讓我懂得了編程時候一定要思維嚴謹。但這次的設(shè)計同時也有一些不足之處，如算法不算太簡潔，還有一些基本的知識沒有完全掌握等等，這些為我以后的學習提供了教訓，相信以后我能夠做得更好。</p><p>

23、<b>　　參考文獻</b></p><p>　　[1]《數(shù)據(jù)結(jié)構(gòu)程序設(shè)計題典》李春葆等編 清華大學出版社</p><p>　　[2]《數(shù)據(jù)結(jié)構(gòu)(C語言版)》 黃國瑜 葉乃菁編 清華大學出版社</p><p>　　[3]《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》蘇仕華 等編 機械工業(yè)出版社</p><p><b>

24、;　　附錄</b></p><p>　　#include<iostream></p><p>　　using namespace std;</p><p>　　int a[8],b[24],c[24],d[24];</p><p>　　int i, k,g1=0,g2=0;</p><p>　　

25、void print1()</p><p><b>　　{ </b></p><p><b>　　g1++;</b></p><p>　　cout<<"\t第"<<g1<<"種情況: ";</p><p>　　for (

26、k=1;k<9;k++)</p><p>　　cout<<" "<<" "<<a[k];</p><p>　　cout<<"\n";</p><p><b>　　}</b></p><p>　　void pr

27、int2()</p><p><b>　　{ </b></p><p><b>　　int t,n;</b></p><p><b>　　g2++;</b></p><p>　　cout<<"\t第"<<g2<<&qu

28、ot;種情況: \n\t";</p><p>　　for (k=1;k<9;k++)</p><p><b>　　{</b></p><p><b>　　n=a[k];</b></p><p>　　for(t=1;t<n;t++)</p><p>　　c

29、out<<"0 ";</p><p>　　cout<<"1 ";</p><p><b>　　t++;</b></p><p>　　for(t;t<9;t++)</p><p>　　cout<<"0 ";</p&g

30、t;<p>　　cout<<"\n\t";</p><p><b>　　}</b></p><p>　　cout<<"\n";</p><p><b>　　}</b></p><p>　　void JudgeQueen1(

31、int i)</p><p><b>　　{</b></p><p><b>　　int j;</b></p><p>　　for (j=1;j<9;j++)//每個皇后都有8種可能位置</p><p><b>　　{</b></p><p>　

32、　if ((b[j]==0) &&(c[i+j]==0)&& (d[i-j]==0))//判斷位置是否沖突</p><p><b>　　{</b></p><p>　　a[i]=j;//擺放皇后</p><p>　　b[j]=1;//宣布占領(lǐng)第J行</p><p>　　c[i+j

33、]=1;//占領(lǐng)兩個對角線</p><p><b>　　d[i-j]=1;</b></p><p><b>　　if (i<8) </b></p><p>　　JudgeQueen1(i+1);//8個皇后沒有擺完，遞歸擺放下一皇后</p><p><b>　　else <

34、/b></p><p>　　print1();//完成任務(wù)，打印結(jié)果</p><p>　　b[j]=0;//回溯</p><p><b>　　c[i+j]=0;</b></p><p><b>　　d[i-j]=0;</b></p><p><b>　　

35、}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void JudgeQueen2(int i)</p><p><b>　　{</b></p><p>　　int j ,e=1;

36、</p><p>　　for (j=1;j<9;j++)//每個皇后都有8種可能位置</p><p><b>　　{</b></p><p>　　if ((b[j]==0) &&(c[i+j]==0)&& (d[i-j]==0))//判斷位置是否沖突</p><p><b&

37、gt;　　{</b></p><p>　　a[i]=j;//擺放皇后</p><p>　　b[j]=1;//宣布占領(lǐng)第J行</p><p>　　c[i+j]=1;//占領(lǐng)兩個對角線</p><p><b>　　d[i-j]=1;</b></p><p><b>　　

38、if (i<8) </b></p><p>　　JudgeQueen2(i+1);//8個皇后沒有擺完，遞歸擺放下一皇后</p><p><b>　　else</b></p><p>　　print2();//完成任務(wù)，打印結(jié)果</p><p>　　b[j]=0;//回溯</p>

39、<p><b>　　c[i+j]=0;</b></p><p><b>　　d[i-j]=0;</b></p><p><b>　　e++;</b></p><p><b>　　}</b></p><p><b>　　}</b&g

40、t;</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　int choice,e=1;</p><p><b>　　char ch;</b></p>

41、<p>　　cout<<"\n\n\t ** 歡迎使用八皇后問題查詢軟件 **\n\n";</p><p>　　for( k=0;k<24;k++)//數(shù)據(jù)初始化 </p><p><b>　　{</b></p><p><b>　　b[k]=0;</b&g

42、t;</p><p><b>　　c[k]=0;</b></p><p><b>　　d[k]=0;</b></p><p><b>　　}</b></p><p><b>　　ch='y';</b></p><p>

43、;　　while(ch=='y'||ch=='Y')</p><p><b>　　{</b></p><p>　　cout<<"\n\t 查 詢 菜 單\n";</p><p>　　cout<<"\n\t*****

44、*************************************************";</p><p>　　cout<<"\n\t* 1--------位置標明法 *";</p><p>　　cout<<"\n\t* 2

45、--------視圖顯示法 *";</p><p>　　cout<<"\n\t* 0--------退 出 *";</p><p>　　cout<<"\n\t*********************************

46、*********************";</p><p>　　cout<<"\n\n請選擇菜單號(0--2)：";</p><p>　　cin>>choice;</p><p>　　switch(choice)</p><p><b>　　{</b></p

47、><p><b>　　case 1:</b></p><p>　　cout<<"\n\t每一行皇后放置的列數(shù)的情況\n\n";</p><p>　　JudgeQueen1(1);//從第1個皇后開始放置</p><p><b>　　break;</b></p>

48、;<p><b>　　case 2:</b></p><p>　　cout<<"\n\t使用回車查看下一種情況（共92種）\n\n";;</p><p>　　JudgeQueen2(1);//從第1個皇后開始放置</p><p><b>　　break;</b></p&

49、gt;<p><b>　　case 0:</b></p><p><b>　　ch='n';</b></p><p><b>　　break;</b></p><p><b>　　default:</b></p><p>