課程設(shè)計(jì)——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(八皇后問題)

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

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

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

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

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

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

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

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

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

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

11、p>　?、?行沖突標(biāo)記數(shù)組B，B[j]=0 表示第j行空閑，B[j]=1 表示第j行被占領(lǐng)，范圍為1~8。</p><p>　?、?對角線沖突標(biāo)記數(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.算法描述與實(shí)現(xiàn)</b></p><p>　　利用JudgeQueen（）函數(shù)來實(shí)現(xiàn)對皇后擺放位置的確定，并用回溯法來完成對所有皇后的擺放。</p><p>　　void JudgeQueen1(int i)</p><p>　　void JudgeQueen2(int i)</p><p>

13、　　a[i]表示第i個(gè)皇后放置的列，范圍為1~8。</p><p>　　行沖突標(biāo)記數(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)用來實(shí)現(xiàn)當(dāng)8個(gè)皇后沒有擺完，遞歸擺放下一皇后的操作。</p><p>　　b[j]=0；c[i+j]=0；d[i-

15、j]=0；這三個(gè)語句來進(jìn)行回溯。</p><p>　　編寫程序主函數(shù)，在main( )中調(diào)用各個(gè)功能函數(shù)實(shí)現(xiàn)八皇后問題的要求，其中運(yùn)用switch( )函數(shù)實(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個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測試當(dāng)前位置（n，m）是否等于0（未被占領(lǐng)）。如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)（記得要橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測試下一個(gè)位置（n，m+1），但是如果當(dāng)n<=8，m=8時(shí)，發(fā)現(xiàn)此時(shí)已無法擺放時(shí)，便要進(jìn)行回溯。從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解

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

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

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

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

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

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

23、<b>　　參考文獻(xiàn)</b></p><p>　　[1]《數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典》李春葆等編 清華大學(xué)出版社</p><p>　　[2]《數(shù)據(jù)結(jié)構(gòu)(C語言版)》 黃國瑜 葉乃菁編 清華大學(xué)出版社</p><p>　　[3]《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》蘇仕華 等編 機(jī)械工業(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++)//每個(gè)皇后都有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)兩個(gè)對角線</p><p><b>　　d[i-j]=1;</b></p><p><b>　　if (i<8) </b></p><p>　　JudgeQueen1(i+1);//8個(gè)皇后沒有擺完，遞歸擺放下一皇后</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++)//每個(gè)皇后都有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)兩個(gè)對角線</p><p><b>　　d[i-j]=1;</b></p><p><b>　　

38、if (i<8) </b></p><p>　　JudgeQueen2(i+1);//8個(gè)皇后沒有擺完，遞歸擺放下一皇后</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--------位置標(biāo)明法 *";</p><p>　　cout<<"\n\t* 2

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

46、*********************";</p><p>　　cout<<"\n\n請選擇菜單號(hào)(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個(gè)皇后開始放置</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個(gè)皇后開始放置</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>