一 設(shè)計(jì)目的1．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力；2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能；3.提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問題的能力；4.訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)二 設(shè)計(jì)內(nèi)容求出在一個(gè)n×n的棋盤上，放置n個(gè)不能互相捕捉的國(guó)際象棋“皇后”的所有布局這是來源于國(guó)際象棋的一個(gè)問題皇后可以沿著縱橫和兩條斜線8個(gè)方向相互捕捉如圖所示，一個(gè)皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個(gè)皇后相互捕捉，也就是下一個(gè)皇后不能放的位置 12345678××××××××××Q×××××××××××××××圖2-1：擺放示意圖根據(jù)這個(gè)規(guī)則，我們可以利用一個(gè)函數(shù)來判斷某個(gè)位置是否安全，安全的位置說明它所在的同一行、同一列或兩條線上都沒有放置過皇后，因此不會(huì)出現(xiàn)皇后互相攻擊的情況；否則該位置不安全其具體實(shí)現(xiàn)過程是找出所有放置的皇后，將他們的位置與該位置進(jìn)行比較判斷又注意到同一行只能放一個(gè)皇后，因此，只需要對(duì)前面的各行逐行掃描皇后，就可以找出所有皇后的位置。

下圖是其中一種擺放皇后的方法：QQQQQQQQ圖2-2：一種擺放皇后的方法三 設(shè)計(jì)要求1.問題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？ 2.邏輯設(shè)計(jì)：對(duì)問題描述中涉及的操作對(duì)象定義相應(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è)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖3.詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法在這個(gè)過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架4.程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序同時(shí)加入一些注解和斷言，使程序中邏輯概念清楚5.程序調(diào)試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測(cè)試數(shù)據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。

調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果6.結(jié)果分析：程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果算法的時(shí)間、空間復(fù)雜性分析7.編寫課程設(shè)計(jì)說明書四 設(shè)計(jì)過程1.算法思想分析這道題可以用遞歸循環(huán)的方法來做，分別一一測(cè)試每一種擺法，直到得出正確的答案主要解決以下幾個(gè)問題1）沖突（包括行、列、兩條對(duì)角線）① 列：規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突② 行：當(dāng)?shù)趇行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)③ 對(duì)角線：對(duì)角線有兩個(gè)方向在同一對(duì)角線上的所有點(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)2）數(shù)據(jù)結(jié)構(gòu)① 解數(shù)組A，A[i]表示第i個(gè)皇后放置的列，范圍為1~8② 行沖突標(biāo)記數(shù)組B，B[j]=0 表示第j行空閑，B[j]=1 表示第j行被占領(lǐng)，范圍為1~8③ 對(duì)角線沖突標(biāo)記數(shù)組C、DC[i-j]=0 表示第（i-j）條對(duì)角線空閑，C[i-j]=1 表示第（i-j）條對(duì)角線被占領(lǐng)，范圍-7~7。

D[i+j]=0 表示第（i+j）條對(duì)角線空閑，D[i+j]=1 表示第（i+j）條對(duì)角線被占領(lǐng)，范圍2~162.算法描述與實(shí)現(xiàn)利用JudgeQueen（）函數(shù)來實(shí)現(xiàn)對(duì)皇后擺放位置的確定，并用回溯法來完成對(duì)所有皇后的擺放void JudgeQueen1(int i)void JudgeQueen2(int i)a[i]表示第i個(gè)皇后放置的列，范圍為1~8行沖突標(biāo)記數(shù)組b，b[j]=0 表示第j行空閑，b[j]=1 表示第j行被占領(lǐng)，范圍為1~8c[i-j]=0 表示第（i-j）條對(duì)角線空閑，c[i-j]=1 表示第（i-j）條對(duì)角線被占領(lǐng)，范圍-7~7D[i+j]=0 表示第（i+j）條對(duì)角線空閑，d[i+j]=1 表示第（i+j）條對(duì)角線被占領(lǐng)，范圍2~16利用if ((b[j]==0) &&(c[i+j]==0)&& (d[i-j]==0))語句來判斷擺放位置是否沖突利用JudgeQueen1(i+1)的函數(shù)調(diào)用來實(shí)現(xiàn)當(dāng)8個(gè)皇后沒有擺完，遞歸擺放下一皇后的操作b[j]=0；c[i+j]=0；d[i-j]=0；這三個(gè)語句來進(jìn)行回溯編寫程序主函數(shù)，在main( )中調(diào)用各個(gè)功能函數(shù)實(shí)現(xiàn)八皇后問題的要求，其中運(yùn)用switch( )函數(shù)實(shí)現(xiàn)八皇后問題的操作，并調(diào)用上述的JudgeQueen（）函數(shù)。

算法流程A、 數(shù)據(jù)初始化B、 從n列開始擺放第n個(gè)皇后（因?yàn)檫@樣便可以符合每一豎列一個(gè)皇后的要求），先測(cè)試當(dāng)前位置（n，m）是否等于0（未被占領(lǐng)）如果是，擺放第n個(gè)皇后，并宣布占領(lǐng)（記得要橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測(cè)試下一個(gè)位置（n，m+1），但是如果當(dāng)n<=8，m=8時(shí)，發(fā)現(xiàn)此時(shí)已無法擺放時(shí)，便要進(jìn)行回溯從問題的某一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解的方法，稱為“回溯法”C、 當(dāng)n>8時(shí)，便打印出結(jié)果流程圖如4-1所示：圖4-1：程序流程圖數(shù)據(jù)初始化測(cè)試下個(gè)位置m=m+1開始從n列開始擺放第n個(gè)皇后當(dāng)前位置（n，m）是否被占領(lǐng)擺放皇后，并宣布占領(lǐng)n=n+1是否n<=8&m=8進(jìn)行回溯打印結(jié)果3.系統(tǒng)測(cè)試（1）由于對(duì)八個(gè)皇后放置的位置不能一次確定，而且前一個(gè)皇后的放置位置直接影響著后面的放置位置，使程序調(diào)試時(shí)要花費(fèi)不少時(shí)間2）本程序有些代碼重復(fù)出現(xiàn)，顯得程序的有些代碼看起來很雜亂2）本程序模塊劃分比較合理，且利用指數(shù)組存儲(chǔ)棋盤，操作方便4）算法的時(shí)空分析該算法的運(yùn)行時(shí)間和和皇后的放置方法成正比，在最好情況下的時(shí)間和空間復(fù)雜度均為O（1），在最差情況下均為O（n2）），平均情況在它們之間，即（1+ n2）/2。

①主界面在Dos下運(yùn)行程序，出現(xiàn)如下主界面可以通過輸入數(shù)字0、1、2加回車實(shí)現(xiàn)不同的目的，在此界面中可以得到位置標(biāo)明法和視圖顯示法兩種表示出所計(jì)算出的八皇后的擺放分布圖如4-2所示：圖4-2：運(yùn)行時(shí)主界面②子界面1在主界面下輸入數(shù)字1可以進(jìn)入如下的子界面下圖為按每一行皇后所擺放的列的位置輸出的結(jié)果的部分截圖，如4-3所示：圖4-3：子界面③子界面2在主界面輸入2時(shí)所進(jìn)入的子界面以視圖的方式按矩陣方式輸出八皇后擺放所得的結(jié)果如圖4-4所示：圖4-4：按矩陣方式打印五．設(shè)計(jì)總結(jié)通過該題的練習(xí)，使我們學(xué)會(huì)了由遞歸到非遞歸的轉(zhuǎn)換以及回溯法的思想，而且可以分析它們的效率高低，什么時(shí)候用遞歸合理，什么時(shí)候不能用，這都是通過這次課程設(shè)計(jì)學(xué)到的八皇后的問題經(jīng)過小組討論分析之后，我們便有了設(shè)計(jì)的思路，最終成功的設(shè)計(jì)出來這次課設(shè)也讓我懂得了編程時(shí)候一定要思維嚴(yán)謹(jǐn)?shù)@次的設(shè)計(jì)同時(shí)也有一些不足之處，如算法不算太簡(jiǎn)潔，還有一些基本的知識(shí)沒有完全掌握等等，這些為我以后的學(xué)習(xí)提供了教訓(xùn)，相信以后我能夠做得更好參考文獻(xiàn)[1]《數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)題典》李春葆等編 清華大學(xué)出版社[2]《數(shù)據(jù)結(jié)構(gòu)(C語言版)》 黃國(guó)瑜 葉乃菁編 清華大學(xué)出版社[3]《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》蘇仕華 等編 機(jī)械工業(yè)出版社附錄#includeusing namespace std;int a[8],b[24],c[24],d[24];int i, k,g1=0,g2=0;void print1(){ g1++; cout<<"\t第"<