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

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

2、布局。這是來源于國際象棋的一個(gè)問題。皇后可以沿著縱橫和兩條斜線 8 個(gè)方向相互捕捉。如圖所示，一個(gè)皇后放在棋盤的第 4 行第 3 列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個(gè)皇后相互捕捉，也就是下一個(gè)皇后不能放的位置。 1 2 3 4 5 6 7 8× ×× × ×× × ×× × Q × ×

3、× × ×× × ×× × ×× ×× ×圖 2-1：擺放示意圖根據(jù)這個(gè)規(guī)則，我們可以利用一個(gè)函數(shù)來判斷某個(gè)位置是否安全，安全的位置說明它所在的同一行、同一列或兩條線上都沒有放置過皇后，因此不會出現(xiàn)皇后互相攻擊的情況；否則該位置不安全。其具體實(shí)現(xiàn)過程是找出所有放置的皇后，將他們的位置與該位置進(jìn)行比較判斷。又注

4、意到同一行只能放一個(gè)皇后，因此，只需要對前面的各行逐行掃描皇后，就可以找出所有皇后的位置。下圖是其中一種擺放皇后的方法：四 設(shè)計(jì)過程 設(shè)計(jì)過程1. 1.算法思想分析 算法思想分析這道題可以用遞歸循環(huán)的方法來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個(gè)問題。（1）沖突（包括行、列、兩條對角線）① 列：規(guī)定每一列放一個(gè)皇后，不會造成列上的沖突。② 行：當(dāng)?shù)?i 行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把

5、以 i 為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。③ 對角線：對角線有兩個(gè)方向。在同一對角線上的所有點(diǎn)（設(shè)下標(biāo)為（i,j） ） ，要么（i+j）是常數(shù)，要么（i-j）是常數(shù)。因此，當(dāng)?shù)?i 個(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 行被占

6、領(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. 2.算法描述與實(shí)現(xiàn) 算法描述與實(shí)現(xiàn)利用 JudgeQueen（）函數(shù)來實(shí)現(xiàn)對皇后擺放位置的確定，并用回溯法來完成對所有皇后的擺放。void JudgeQ

7、ueen1(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）條對角線空閑，c[i-j]=1 表示第（i-j）條對角線被占領(lǐng)，范圍-7~7。D[i+j]=0 表示第（i+j）條對角線空閑，d[i+j]=1 表示第（i+j）條對角線被占領(lǐng)，范圍