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

《課程設(shè)計——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(八皇后問題)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊長春大學(xué)課程設(shè)計紙一設(shè)計目的1．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；3.提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；4.訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。二設(shè)計內(nèi)容求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。這是來源于國際象棋的一個問題?；屎罂梢匝刂?/p>

2、縱橫和兩條斜線8個方向相互捕捉。如圖所示，一個皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個皇后相互捕捉，也就是下一個皇后不能放的位置。12345678××××××××××Q×××××××××××××××圖2-1：擺放示意圖根據(jù)這個規(guī)則，我們可以利用一個函數(shù)來判斷某個位置是否安全，安全的位置說明它所在的同一行、同一列或兩條線上都沒有放置過皇后，因此不會出現(xiàn)皇后互相攻擊的情況；否則該位置不安全。其具體實現(xiàn)過程是找出所有放置的皇后，將他們的位置與該位置進(jìn)行比較判斷。又注意到同一行只能放一個皇后，因此，只需要對前

3、面的各行逐行掃描皇后，就可以找出所有皇后的位置。共11頁第11頁┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊長春大學(xué)課程設(shè)計紙下圖是其中一種擺放皇后的方法：QQQQQQQQ圖2-2：一種擺放皇后的方法三設(shè)計要求1.問題分析和任務(wù)定義：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？2.邏輯設(shè)計：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義(包括

4、數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖。3.詳細(xì)設(shè)計：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。4.程序編碼：把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。5.程序調(diào)試：采用自底向上，分模塊進(jìn)行

5、，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。6.結(jié)果分析：程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析。共11頁第11頁┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊長春大學(xué)課程設(shè)計紙7.編寫課程設(shè)計說明書。四設(shè)計過程1.算法思想分析這道題可以用遞歸循環(huán)的方法來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個

6、問題。（1）沖突（包括行、列、兩條對角線）①列：規(guī)定每一列放一個皇后，不會造成列上的沖突。②行：當(dāng)?shù)趇行被某個皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。③對角線：對角線有兩個方向。在同一對角線上的所有點（設(shè)下標(biāo)為（i,j）），要么（i+j）是常數(shù)，要么（i-j）是常數(shù)。因此，當(dāng)?shù)趇個皇后占領(lǐng)了第j列后，要同時把以（i+j）、（i-j）為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。（2）數(shù)據(jù)結(jié)構(gòu)①解數(shù)組A，A[i]表示第i個皇后放置的列，范圍為1~8。②行沖突標(biāo)記數(shù)組B，B[j]=0表示第j行空閑，B[j]=1表示

7、第j行被占領(lǐng)，范圍為1~8。③對角線沖突標(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。2.算法描述與實現(xiàn)利用JudgeQueen（）函數(shù)來實現(xiàn)對皇后擺放位置的確定，并用回溯法來完成對所有皇后的擺放。voidJudgeQueen1(inti)voidJudgeQueen2(inti)a[i]表示第i個皇后放置的列，范圍為1~8。行沖突標(biāo)記數(shù)組b，b[j]=

8、0表示第j行空閑，b[j]=1表示第j行被占領(lǐng)，范圍為1~8c[i-j]=0表示第（i-j）條對角線空閑，c[i-j]=1表示第（i-j）條對角線被占領(lǐng)，范圍-7~7。D[i+j]=0表示第（i+j）條對角