數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)用C++語(yǔ)言解決八皇后問(wèn)題

1、 1 引 言在程序設(shè)計(jì)中，可以用兩種方法解決問(wèn)題：一是傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)方法，二是更先進(jìn)的面向?qū)ο蟪绦蛟O(shè)計(jì)方法。在結(jié)構(gòu)化程序設(shè)計(jì)中關(guān)鍵是如何將問(wèn)題域中的行為（即操作）抽取出來(lái)，作為c+程序中的函數(shù)。由于多個(gè)函數(shù)均需要訪問(wèn)某些數(shù)據(jù)，這些數(shù)據(jù)常被設(shè)計(jì)為全局變量。而在面向?qū)ο蟪绦蛟O(shè)計(jì)中關(guān)鍵是如何將問(wèn)題域中的實(shí)體（即日常所見(jiàn)的概念）抽取出來(lái)，作為c+程序中的類，而屬性與行為作為類的兩類要素通常是必不可少的，甚至還應(yīng)考慮類必須滿足的約束1。1.1課程設(shè)計(jì)目的深入理解數(shù)據(jù)結(jié)構(gòu)的基本理論，掌握數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)方法，掌握基于數(shù)據(jù)結(jié)構(gòu)的各種操作的實(shí)現(xiàn)方法，訓(xùn)練對(duì)基礎(chǔ)知識(shí)和基本方法的綜合運(yùn)用能力，增強(qiáng)對(duì)算法的

2、理解能力，提高軟件設(shè)計(jì)能力。在實(shí)踐中培養(yǎng)獨(dú)立分析問(wèn)題和解決問(wèn)題的作風(fēng)和能力。熟練運(yùn)用c+語(yǔ)言、基本數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)知識(shí)，獨(dú)立編制一個(gè)具有中等難度的、解決實(shí)際應(yīng)用問(wèn)題的應(yīng)用程序2。1.2課程設(shè)計(jì)內(nèi)容國(guó)際象棋中皇后威力很大，它可以象“車”一樣沿直線上下或左右移動(dòng)；也可以如同“象”那樣沿著斜線移動(dòng)。雙方的皇后是不能在同一行或同一列或同一斜線上對(duì)持的。那么，在一張空白的國(guó)際象棋盤上最多可以放上幾個(gè)皇后并且不讓它們互相攻擊呢？這個(gè)問(wèn)題是偉大數(shù)學(xué)家高斯在十九世紀(jì)中期提出來(lái)的，并作了部分解答。高斯在棋盤上放下了八個(gè)互不攻擊的皇后，他還認(rèn)為可能有76種不同的放法，這就是有名的“八皇后”問(wèn)題?，F(xiàn)在我們已經(jīng)知

3、道八皇后問(wèn)題有92個(gè)解答。那么你能試著找出幾種方法嗎？如果你動(dòng)手試試，就一定會(huì)發(fā)現(xiàn)開(kāi)頭幾顆皇后很容易放置，越到后來(lái)就越困難。由于我們的記憶有限，很可能在某個(gè)位置放過(guò)子后來(lái)證明不行取消了，但是以后又重新放上子去試探，這樣就會(huì)不斷地走彎路，花費(fèi)大量的精力。因此，必須找到一個(gè)簡(jiǎn)易有效、有條不紊的法則才行3。 2問(wèn)題描述和分析2.1問(wèn)題描述在一個(gè)的棋盤里放置個(gè)皇后，要求每個(gè)皇后兩兩之間不相沖（在每一橫列豎列斜列只有一個(gè)皇后）。一個(gè)合適的解應(yīng)是在每列、每行確實(shí)有一個(gè)皇后，且在一條對(duì)角線上最多只有一個(gè)皇后2.2分析問(wèn)題分析：(1) 滿足上述條件的八個(gè)皇后，必然是每行一個(gè)，每列一個(gè)。(2)棋盤上任意一行、任

4、意一列、任意一條斜線上都不能有兩個(gè)皇后。如果我們把88的棋盤看成是一個(gè)平面直角坐標(biāo)系，則八皇后問(wèn)題就可以用數(shù)學(xué)語(yǔ)言來(lái)描述了，任意兩個(gè)皇后在平面上的坐標(biāo)應(yīng)該同時(shí)滿足以下三個(gè)條件：兩個(gè)皇后不在同一行：兩個(gè)皇后的橫坐標(biāo)不相等；兩個(gè)皇后不在同一列：兩個(gè)皇后的縱坐標(biāo)不相等；兩個(gè)皇后不在同一條斜線上：兩個(gè)皇后的橫坐標(biāo)之差的絕對(duì)值不等于兩個(gè)皇后的縱坐標(biāo)之差的絕對(duì)值。依據(jù)“分而治之”的思想，先討論4皇后的問(wèn)題。也就是說(shuō)在44的盤內(nèi)放4個(gè)后。8皇后的問(wèn)題實(shí)際上是4皇后問(wèn)題的衍生。如圖2.1所示。圖2.1 模擬棋盤圖首先清理棋盤，把所有的坐標(biāo)值都?xì)w零，如圖2.2所示。 圖 2.2 棋盤坐標(biāo)清零然后放第一個(gè)q1到（

5、1，1）的位置，。即q1.row=1，q1.col=1，如圖2.3所示。圖2.3 放入第一顆棋子q1會(huì)占據(jù)它所在的所有橫，豎，斜的位置。調(diào)用seize（1,1）函數(shù)來(lái)實(shí)現(xiàn)這個(gè)功能。讓q1所在的橫豎斜線上所在的坐標(biāo)都置1，如圖2.4所示。圖2.4 繼續(xù)探索接著放q2。放q2的過(guò)程可以看作是在43的棋格里放q2-q4的過(guò)程。其中33的棋格中間斜線被q1占據(jù)，因此q2放在（2，3）的位置。即q2.row=2，q2.col=3。放完q2后，調(diào)用seize（2，3）函數(shù)來(lái)實(shí)現(xiàn)q2的占據(jù)坐標(biāo)，如圖2.5所示。 圖2.5 劃出下一顆棋子可能的區(qū)間接下來(lái)要放q3，可以看作是一個(gè)在42的棋格里放q3、q4。但是

6、我們看到第3行已經(jīng)沒(méi)有空位放q3了。因此回退到q2的時(shí)刻，把q2往后放，尋找第2個(gè)適合q2的位置。若沒(méi)有位置可放，則退回到q1改變q1的位置，如圖2.6所示。圖2.6 放入第二顆棋子q2從（2，3）的位置出來(lái)后，可以放在（2，4）的位置。即q2.row=2，q2.col=4。如此q3便可放到（3，2）的位置，如圖2.7所示。圖2.7 繼續(xù)探索但是如此一來(lái)，q3放在（3，2）的位置會(huì)占據(jù)q4（4，3）的位置使q4無(wú)法安放。所以應(yīng)該回退到q1。使q1放在（1，2）的位置，如圖2.8所示。 圖2.8 無(wú)解 退回q1q2因?yàn)椋?，1）（2，2）（2，3）都被q1占據(jù)，因此只能放在（2，4）的位置，如圖

7、2.9所示。圖2.9 得出一個(gè)解至此，我們已經(jīng)得到4皇后的一個(gè)解，判斷是否已解出的條件是q4是否被安放成功。此時(shí)q4被安置，得出一個(gè)解，因此應(yīng)該輸出4個(gè)q的位置調(diào)用函數(shù)print（）輸出此時(shí)的4個(gè)q的位置。輸出以后程序還沒(méi)有完，因?yàn)槲覀冞€沒(méi)有把所有的棋盤都遍歷完畢。q1只是到了（1，2）。要到（1，4）以后程序才算結(jié)束。所以我們應(yīng)該把q1往后移動(dòng)一位到（1，3）繼續(xù)找解。q1在（1，3）的時(shí)候重復(fù)上邊的過(guò)程可以得到q4的另一組解。我們可以看到，四皇后的兩個(gè)解是相對(duì)的（對(duì)稱）。實(shí)際上皇后問(wèn)題的任何一個(gè)解都有另外一個(gè)解和它相對(duì)應(yīng)。因此皇后問(wèn)題的解一定是一個(gè)偶數(shù)。最后q4到了（1，4）以后全部棋盤遍

8、歷完畢。輸出所有的解。程序結(jié)束。我們可以設(shè)計(jì)一個(gè)函數(shù)queen（int i）來(lái)模擬4q的遞歸調(diào)用。另外需要一個(gè)seize(i,j)函數(shù)判斷坐標(biāo)（i,j）是否被占據(jù)。一個(gè)print（）函數(shù)來(lái)打印解。因?yàn)檎麄€(gè)函數(shù)調(diào)用是一個(gè)遞歸的過(guò)程，遞歸結(jié)束后一切解都被析構(gòu)了，所以print()函數(shù)必須被安置在queen(int k)函數(shù)里。seize（i,j）函數(shù)作用是判斷坐標(biāo)（i,j）是否被占據(jù)，如占據(jù)則返回1，如沒(méi)占據(jù)則返回0。我們往（3，2）中放q3。在判斷是否占據(jù)的時(shí)候，需要考慮3中情況：1.列上是否被占據(jù)了。即圖中的（2，2）（1，2）兩點(diǎn)，注意，在這里只需要判斷i（既3）以上的坐標(biāo)就行了，因?yàn)榈?行

9、以下不可能有q，我們還沒(méi)有放。因此不用判斷（4，2）這個(gè)點(diǎn)。（2，2）（1，2）兩點(diǎn)的坐標(biāo)用算法表示可以寫(xiě)成k=i-1 to 1;if(k,j)=q) retrun 1; return 02.左斜線上是否被占據(jù)了。即圖中的（2，1）。算法可以寫(xiě)成：k=i-1 to 1if(k,j-i+k)=q) return1;return 03.右斜線上是否被占據(jù)了。即圖中的（2，3）（1，4）。算法可以寫(xiě)成：k=i-1 to 1if(k,j+i-k)=q) return1;return 0后把三種情況進(jìn)行邏輯或運(yùn)算以后返回給主函數(shù)。換句話說(shuō)就是行，左斜，右斜只要有一個(gè)有q存在的話，就返回1給主函數(shù)，否則返

10、回0。 3數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)考慮我們用q1-q4四個(gè)整型數(shù)組來(lái)表示4個(gè)q。qi的數(shù)值表示q所在的位置。比如q1=3表示q1放在（1，3）的位置。44的棋盤我們用一個(gè)整型變量size來(lái)表示。要改變棋盤的大小只需要改變size的數(shù)值即可。最主要的是queen（int i）函數(shù)的設(shè)計(jì)。queen（int i）函數(shù)負(fù)責(zé)主要的棋盤遍歷，從第一個(gè)q放入到遍歷結(jié)束。另外queen（int i）函數(shù)也是一個(gè)遞歸函數(shù)，當(dāng)q8沒(méi)有被放置時(shí)，不斷的調(diào)用自己。直到q8成功放置，輸出解。3.2流程圖 圖3.1流程圖主程序比較簡(jiǎn)單，只需要調(diào)用一個(gè)queen(1)的函數(shù)把1傳給函數(shù)中的變量。queen函數(shù)負(fù)責(zé)解

11、決解法問(wèn)題。這是一個(gè)遞歸的過(guò)程，當(dāng)放下第1個(gè)q后，接著自己調(diào)用自己放第2個(gè)q。直到4和q放完。如果放完后則輸出組合。然后移動(dòng)第1個(gè)q的位置繼續(xù)進(jìn)行。直到所有的棋盤都被遍歷結(jié)束4。4算法設(shè)計(jì)4.1主要設(shè)計(jì)思想回溯的基本思想是：為了求得問(wèn)題的解，先選擇某一種可能情況向前探索，在探索過(guò)程中，一旦發(fā)現(xiàn)原來(lái)的選擇是錯(cuò)誤的，就退回一步重新選擇，繼續(xù)向前探索，如此反復(fù)進(jìn)行，直至得到解或證明無(wú)解。如迷宮問(wèn)題：進(jìn)入迷宮后，先隨意選擇一個(gè)前進(jìn)方向，一步步向前試探前進(jìn)，如果碰到死胡同，說(shuō)明前進(jìn)方向已無(wú)路可走，這時(shí)，首先看其它方向是否還有路可走，如果有路可走，則沿該方向再向前試探；如果已無(wú)路可走，則返回一步，再看其它

12、方向是否還有路可走；如果有路可走，則沿該方向再向前試探。按此原則不斷搜索回溯再搜索，直到找到新的出路或從原路返回入口處無(wú)解為止5。4.2算法的偽碼描述主程序較簡(jiǎn)單，只需要進(jìn)行一些參數(shù)賦值，并執(zhí)行queen函數(shù)即可。algorithm main ()1input size2queen(1)3returnend mainqueen函數(shù)：程序的核心部分，解皇后問(wèn)題的全部過(guò)程由該函數(shù)完成。依據(jù)流程圖寫(xiě)出算法。algorithm queen(val k)1 i=12 loop (isize)1break2else1q(k)=i2if(k=size)1print()3queen(k+1)3end loop

13、4returnend queenseize函數(shù)：函數(shù)作用是判斷坐標(biāo)（i,j）是否被占據(jù)，如占據(jù)則返回1，如沒(méi)占據(jù)則返回0。algorithm seize(val i ,val j )1k=i-1;2loop (k=0)1if (qk=j|qk=j+i-k|qk=j-i+k)1return 12k=k-13end loop4return 0end seizeprint函數(shù)：函數(shù)作用是打印已經(jīng)的出的一組解。在調(diào)用函數(shù)的時(shí)候，q1-q4里存的分別是四個(gè)q的縱坐標(biāo)。用兩個(gè)循環(huán)嵌套打印。algorithm printdigit()1i=02loop(isize)1print qi3printcount+

14、4i+5returnendprintdigit 以上是打印數(shù)據(jù)的一組解。每個(gè)數(shù)字分別代表相應(yīng)的q的縱坐標(biāo)。這樣打印的優(yōu)點(diǎn)是簡(jiǎn)單，快捷。但是沒(méi)有圖形輸出，不方便用戶查看。下邊我們定義一個(gè)圖形打印printgraphic函數(shù)algorithm printgraphic()1i=1;j=12loop(i=size)1printcount+“is:”2loop(j=size)1if(qi=j)1print“q”i2else print“”3end loop3end loop4returnend printgraphic這個(gè)函數(shù)會(huì)直接打印出一組解的圖形表達(dá)形式。如像圖的4q問(wèn)題解會(huì)如下打?。簈qqq在打

15、印時(shí)我們可以交替使用這兩個(gè)函數(shù)?？梢韵扔胮rintdigit把所有的解都打出來(lái)，然后用printgraphic打印特定的用戶選擇的解。4.3運(yùn)行環(huán)境本程序在windows xp系統(tǒng)vc+6.0環(huán)境下調(diào)試、運(yùn)行4.4運(yùn)行結(jié)果程序運(yùn)行開(kāi)始，進(jìn)入提示界面，按任意鍵進(jìn)入數(shù)據(jù)計(jì)算功能如圖411圖4.1按任意鍵進(jìn)行 操作輸出問(wèn)題的各種解，如圖4.2，圖4.2 輸出92種解5結(jié)束語(yǔ) 這次課程設(shè)計(jì)，主要是解決了八皇后問(wèn)題，得出該問(wèn)題的92種可能。該課題是一個(gè)十分有趣項(xiàng)目。通過(guò)這次設(shè)計(jì)我從中了解到無(wú)論是在上個(gè)世紀(jì)還是現(xiàn)在，軟件開(kāi)發(fā)所涉及的工作基本都沒(méi)有變化，它們都起始于一個(gè)實(shí)際需要或某個(gè)靈感，然后就是分析，設(shè)計(jì)

16、，編碼，調(diào)試，維護(hù)。這些任務(wù)以某種方式動(dòng)態(tài)地結(jié)合起來(lái)就構(gòu)成了軟件開(kāi)發(fā)的整個(gè)過(guò)程，這就是所謂的“軟件開(kāi)發(fā)周期”。但對(duì)于這些工作，具體怎樣做，什么時(shí)候做，每個(gè)人都有自己的一套方式，甚至有的人有幾套方式。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)很重要的一門課程，也是必須要熟練掌握的課程，這次的課程設(shè)計(jì)對(duì)我的數(shù)據(jù)結(jié)構(gòu)知識(shí)進(jìn)行了一次全面的綜合訓(xùn)練，加深了對(duì)數(shù)據(jù)結(jié)構(gòu)基本概念和基本知識(shí)的理解，鞏固了課堂上學(xué)的知識(shí)，掌握了數(shù)據(jù)結(jié)構(gòu)的一些基本方法，深刻理解了算法，鍛煉了自己分析問(wèn)題解決問(wèn)題的能力。在本課程設(shè)計(jì)完成之際，最先要感謝的就是我的導(dǎo)師曾愛(ài)群老師。曾老師有著豐富的經(jīng)驗(yàn)、對(duì)知識(shí)的追求孜孜不倦、精益求精的治學(xué)態(tài)度、給我留下了深刻

17、的印象。我很慶幸我在此次課程設(shè)計(jì)中選擇曾老師做我的導(dǎo)師，能與曾老師這樣的學(xué)識(shí)淵博，有實(shí)踐經(jīng)驗(yàn)的老師做課題，對(duì)我今后的學(xué)習(xí)工作將有很大益處。我深深的感受到自己在課程設(shè)計(jì)期間，在曾老師的指導(dǎo)下受益匪淺。 在本次課程設(shè)計(jì)過(guò)程中，曾老師為我提出了很多建議和意見(jiàn)，在這個(gè)學(xué)期中，我們隨時(shí)都能與他取得聯(lián)系詢問(wèn)相關(guān)問(wèn)題，我的這次設(shè)計(jì)順利完成離不開(kāi)曾老師的幫助，曾老師為我的論文的順利完成提供了極大的支持。在做課題的這段時(shí)間里，我不僅跟曾老師學(xué)會(huì)了怎樣做學(xué)問(wèn)，更從曾老師身上學(xué)到了許多做人的道理。曾老師嚴(yán)于律己、寬以待人的崇高品質(zhì)更將是我一生的榜樣。無(wú)論在學(xué)習(xí)上，還是在生活中，我從曾老師身上學(xué)到了很多東西，這些將成

18、為我一筆寶貴的財(cái)富。在此，我衷心的感謝曾老師為我所做的一切，感謝曾老師對(duì)我的關(guān)心、指導(dǎo)和教誨。參考文獻(xiàn)1 richard f. gilberg, behrouz a. forouzan. data structure. brooks/cole, thomson asia pte ltd, usa, 2000.2 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu)（第二版）. 北京：清華大學(xué)出版社, 1992.3 朱曉冬, 段延娥. 數(shù)據(jù)結(jié)構(gòu)web動(dòng)畫(huà)算法. 軟件評(píng)論, 2008，1：1-5498/computer_web/syllabus/data_structure/course%

19、20home,%20summer%202003.htm5王紅梅，胡明，王濤 數(shù)據(jù)結(jié)構(gòu)c+版 北京清華大學(xué)出版社，2005.7附錄1 源程序清單#include stdio.hint a8,b24,c24,d24;int i, k,g1=0,g2=0;void print1() g1+;printf(t第%2d種情況: ,g1); for (k=1;k9;k+) printf(%4d,ak);/ getch(); printf(n);void print2() int t,n;g2+; printf(t第%2d種情況: nt,g2); for (k=1;k9;k+) n=ak; for(t=1;

20、tn;t+) printf(0 ); printf(1 ); t+; for(t;t9;t+) printf(0 ); printf(nt);printf(n);getch();void try1(int i) int j; for (j=1;j9;j+) /*每個(gè)皇后都有8種可能位置*/ if (bj=0) &(ci+j=0)& (di-j=0)/*判斷位置是否沖突*/ ai=j; /*擺放皇后*/ bj=1; /*宣布占領(lǐng)第j行*/ ci+j=1; /*占領(lǐng)兩個(gè)對(duì)角線*/ di-j=1; if (i8) try1(i+1); /*8個(gè)皇后沒(méi)有擺完，遞歸擺放下一皇后*/ else print1(); /*完成任務(wù)，打印結(jié)果*/ bj=0; /*回溯*/ ci+j=0; di-j=0; void try2(int i) int j; for (j=1;j9;j+) /*每個(gè)皇后都有8種可能位置*/ if (bj=0) &(ci+j=0)& (di-