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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：41 大?。?94.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩40頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè) 計報告　　課設(shè)課題：數(shù) 據(jù) 結(jié) 構(gòu) ━━ N皇后（八皇后） 　　學(xué) 院：電子信息學(xué) 院 1　　專業(yè)：計算機科學(xué) 與技術(shù) 1</p&g

2、t;　　姓名： 1　　班級： 1　　指導(dǎo)老師： 1&

3、lt;p>　　報告日期： 　　年月制　　目錄　　一、設(shè)計目的………………………………………………………………………………………4&l

4、t;p>　　二、課程設(shè)計基本要求……………………………………………………………………………4　　三、課程設(shè)計內(nèi)容及安排…………………………………………………………………………4　　四、八皇后背景知識………………………………………………………………………………5　　五、八皇后問題的實現(xiàn)………………………………

5、……………………………………………6　　5.1、遞歸方法解八皇后問題…………………………………………………………………6　　5.1.1、遞歸介紹…………………………………………………………………………7　　5.1.2、使用到的函數(shù)和變量……………………………………………………………8<

6、;p>　　5.1.3、具體運行結(jié)果…………………………………………………………………10　　5.1.4、算法流程圖……………………………………………………………………11　　5.1.5、遞歸算法代碼…………………………………………………………………12　　5.1.6、算法分析…………………………………………

7、……………………………13　　5.2、回溯法解決八皇后問題…………………………………………………………………13　　5.2.1、回溯法介紹……………………………………………………………………13　　5.2.2、使用到的函數(shù)與變量…………………………………………………………14<p&g

8、t;　　5.2.3、具體運行結(jié)果…………………………………………………………………15　　5.2.4、算法流程圖……………………………………………………………………16　　5.2.5、回溯算法代碼…………………………………………………………………17　　5.2.6、算法分析……………………………………………………

9、…………………18　　5.3、堆棧法解八皇后問題……………………………………………………………………18　　5.3.1、堆棧法介紹……………………………………………………………………18　　5.3.2、使用到的函數(shù)與變量…………………………………………………………19

10、5.3.3、具體運行過程…………………………………………………………………20　　5.3.4、算法流程圖……………………………………………………………………21　　5.3.5、堆棧法實現(xiàn)的源代碼…………………………………………………………21　　5.3.6、算法分析………………………………………………………………

11、………25　　5.4、三種算法的比較…………………………………………………………………………25　　5.5、八皇后問題所有輸出結(jié)果………………………………………………………………26　　六、N皇后問題的實現(xiàn)……………………………………………………………………………30

12、6.1、N皇后問題介紹…………………………………………………………………………30　　6.2、使用到的函數(shù)與變量……………………………………………………………………30　　6.3、具體的執(zhí)行………………………………………………………………………………31　　6.4、算法流程圖…………………………………………………

13、……………………………31　　6.5、N皇后的源代碼…………………………………………………………………………32　　6.6、算法分析…………………………………………………………………………………32　　七、經(jīng)驗和體會……………………………………………………………………………………32<

14、;p>　　八、參考文獻………………………………………………………………………………………32　　九、附錄……………………………………………………………………………………………33　　附錄一：遞歸算法代碼………………………………………………………………………34　　附錄二：回溯算法代碼………………………………

15、………………………………………34　　附錄三：堆棧法的源代碼……………………………………………………………………36　　附錄四：N皇后的源代碼……………………………………………………………………39　　一、設(shè)計目的　　《數(shù)據(jù)結(jié)構(gòu)》是一

16、門實踐性較強的軟件基礎(chǔ)課程，為了學(xué)好這門課程，必須在掌握理論知識的同時，加強上機實踐。本課程設(shè)計的目的就是要達到理論與實際應(yīng)用相結(jié)合，使同學(xué)們能夠根據(jù)數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計技能。　　二、課程設(shè)計基本要求　　1、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)

17、計能力；　　2、初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；　　3、提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；　　4、訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。　　5、設(shè)計的

18、題目要求達到一定工作量（300行以上代碼），并具有一定的深度和難度。　　6、編寫出課程設(shè)計說明書，說明書不少于10頁（代碼不算）。　　三、課程設(shè)計內(nèi)容　　1、問題分析和任務(wù)定義：根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？

19、　　2、邏輯設(shè)計：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；　　3、詳細(xì)設(shè)計：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮

20、系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作作出進一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；　　4、程序編碼：把詳細(xì)設(shè)計的結(jié)果進一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；　　5、程序調(diào)試與

21、測試：采用自底向上，分模塊進行，即先調(diào)試低層函數(shù)。能夠熟練掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；　　6、結(jié)果分析：程序運行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析；　　7、編寫課程設(shè)計報告；<

22、/p>　　四、八皇后背景知識　　國際象棋中皇后威力很大，它可以象“車”一樣沿直線上下或左右移動；也可以如同“象”那樣沿著斜線移動。雙方的皇后是不能在同一行或同一列或同一斜線上對持的。那么，在一張空白的國際象棋盤上最多可以放上幾個皇后并且不讓它們互相攻擊呢？這個問題是偉大數(shù)學(xué)家高斯在十九世紀(jì)中期提出來的，并作了部分解答。高斯在棋盤上

23、放下了八個互不攻擊的皇后，他還認(rèn)為可能有76種不同的放法，這就是有名的“八皇后”問題?，F(xiàn)在我們已經(jīng)知道八皇后問題有92個解答。那么你能試著找出幾種方法嗎？如果你動手試試，就一定會發(fā)現(xiàn)開頭幾顆皇后很容易放置，越到后來就越困難。由于我們的記憶有限，很可能在某個位置放過子后來證明不行取消了，但是以后又重新放上子去試探，這樣就會不斷地走彎路，花費大量的精力。因此，必須找到一個簡易有效、有條不紊的法則才行。

24、;　　讓我們先從四皇后談起。若要在如圖1所示的4×4棋盤中，放置四個互不攻擊的皇后，可以如下從上到下逐行地考慮：當(dāng)然在每行中只能放置一個而且必須放置一個皇后，問題是每行中的皇后應(yīng)放在第幾列？　　圖1

25、; 圖2　　如果第一行的皇后放置在第一列，第二行的皇后就不能放置在第一、二列，只能放置在第三列或第四列。如果第二行的皇后放置在第三列，那第三行的皇后就沒有安身之處了。那么暫且把第二行的皇后放在第四列，看看情況如何。這時，第三行的皇后可以放在第二列（見圖2）。然而，第四行的皇后仍然無家可歸！要放置好第四個皇后，必須

26、對前幾個皇后的位置予以修正。　　前面已經(jīng)說過，第三行以至于第二行的所有位置均已考慮過了，只得考慮讓第一行的皇后挪一下。如果把第一行的皇后放在第二列，第二行的皇后放在第四列上，第三行的皇后放在第一列上，第四行的皇后放在第三列上，正好四個皇后互不攻擊（見圖3a）。如果繼續(xù)這樣逐行逐列地考慮下去，還可以找到四皇后問題地另一個解答（見圖3b）。

27、　　圖3　　對于八皇后問題，也可如此解決：從上到下每行放一個皇后；在每一行中均從左至右逐列試放。能放則放（繼續(xù)考慮下一行）不能放則換（列數(shù)加1）換不成則退（退回前一行，讓前一皇后所在列數(shù)加1后繼續(xù)考慮），這就是探索八皇后解答的途徑。　　為了記住在探索過程中每行皇后放置的位置就需要用棧。我們可用數(shù)組T來作棧；在T(P)中存放第P行皇后所

28、在的列數(shù)。例如在第1行的皇后放在第3列，則可置T(1)=3。對于八皇后問題，如此安排后，數(shù)組T只需有八個分量就夠了。　　由于我們在每行中只放一個皇后，故而皇后之間保證不會左右相互攻擊了；那么如何檢查它們是否在上下或斜線方向相互攻擊呢？　　我們用一個數(shù)組C來記錄每一列上是否放了皇后，不管在哪一行上的第1列上放了一個皇后，就令C(1)=1，...。若把放在第

29、1列上的皇后取走放到別的位置上去了，那么再令C(1)=0,...。這樣，只要查看C(I)是否為零，就可以知道第I列上是否可以放置皇后了！顯然，八皇后問題中的數(shù)組C也只需八個分量就可以了。　　在8×8的國際象棋棋盤上，有15條從左上走向右下的斜線，稱為主斜線（如圖4中左圖）；同樣有15條從右上走向左下的斜線，稱為副斜線。由于每放一個皇后，它所在的兩條斜線上就不能再放皇后了。我們可以如同前

30、面所述的那樣，再引進兩個數(shù)組S,M(每個數(shù)組有15個分量），分別記錄相應(yīng)的主斜線和副斜線上是否已經(jīng)放下了皇后。在圖4中右圖，若在第2行第3列放了一個皇后，則應(yīng)令S(7)=1,M(4)=1,表示第7條主斜線，第4條副斜線上已有皇后，以后不能再放置了。因為，主對角線數(shù)7可由8＋行數(shù)－列數(shù)＝8+2-3=7計算得到，副斜線數(shù)4可由行數(shù)＋列數(shù)－1＝2+3-1＝4計算得到。所以一般地說，在第P行，第T(P)列放置皇后以后，應(yīng)該令：C(T(P))=1

31、；S(8+P-T(P))=1；M(P+T(P)-1)=1。有了以上準(zhǔn)備知識，就能為八皇后問題寫算法了　　五、八皇后問題的實現(xiàn)　　5.1、遞歸方法解八皇后問題　　5.1.1、遞歸的介紹　　調(diào)用子程序的含義：<

32、;p>　　在過程和函數(shù)的學(xué)習(xí)中，我們知道調(diào)用子程序的一般形式是：主程序調(diào)用子程序A，子程序A調(diào)用子程序B，如圖如示，這個過程實際上是：　　當(dāng)主程序執(zhí)行到調(diào)用子程序A語句時，系統(tǒng)保存一些必要的現(xiàn)場數(shù)據(jù)，跳轉(zhuǎn)到子程序A（為了說得簡單些，我這里忽略了參數(shù)傳遞這個過程）。　　當(dāng)子程序A執(zhí)行到調(diào)用子程序B語句時，系統(tǒng)作法如上，跳轉(zhuǎn)到子程序B。</p&g

33、t;　　子程序B執(zhí)行完所有語句后，跳轉(zhuǎn)回子程序A調(diào)用子程序B語句的下一條語句（我這又忽略了返回值處理）　　子程序A執(zhí)行完后，跳轉(zhuǎn)回主程序調(diào)用子程序A語句的下一條語句　　主程序執(zhí)行到結(jié)束。　　做個比較：我在吃飯（執(zhí)行主程序）吃到一半時，某人叫我（執(zhí)行子程序

34、A），話正說到一半，電話又響了起來（執(zhí)行子程序B），我只要先接完電話，再和某人把話說完，最后把飯吃完　　認(rèn)識遞歸函數(shù)　　我們在高中時都學(xué)過數(shù)學(xué)歸納法，例：　　求 n！ 　　我們可以把n！這么定義

35、 　　也就是說要求3！，我們必須先求出2！，要求2！，必須先求1！，要求1！，就必須先求0！，而0!=1，所以1!=0!*1=1，再進而求2!，3!。分別用函數(shù)表示，則如圖： 　　我們可以觀察到，除計算0！子程序外，其他的子程序基本相似，我們可以設(shè)計這么一個子程序：　　int factorial(int i){

36、　　int res; 　　res=factorial(I-1)*i; 　　return res; 　　} 　　那么當(dāng)執(zhí)行主程序語句s=factorial(

37、3)時，就會執(zhí)行factorial(3),但在執(zhí)行factorial(3)，又會調(diào)用factorial(2)，這時大家要注意，factorial(3)和factorial(2)雖然是同一個代碼段，但在內(nèi)存中它的數(shù)據(jù)區(qū)是兩份！而執(zhí)行factorial(2)時又會調(diào)用factorial（1），執(zhí)行factorial（1）時又會調(diào)用factorial（0），每調(diào)用一次factorial函數(shù)，它就會在內(nèi)存中新增一個數(shù)據(jù)區(qū)，那么這些復(fù)制了多份的函

38、數(shù)大家可以把它看成是多個不同名的函數(shù)來理解；　　但我們這個函數(shù)有點問題，在執(zhí)行factorial（0）時，它又會調(diào)用factorial（－1）。。。造成死循環(huán)，也就是說，在factorial函數(shù)中，我們要在適當(dāng)?shù)臅r候保證不再調(diào)用該函數(shù)，也就是不執(zhí)行res=factorial(I-1)*i;這條調(diào)用語句。所以函數(shù)要改成： 　　int factorial(i

39、nt i){ 　　int res; 　　if (I>0) res=factorial(I-1)*i; else res=1;　　return res; 　　}<

40、p>　　那么求3!的實際執(zhí)行過程如圖所示： 　　5.1.2、使用到的函數(shù)和變量　　在這個算法中共有六個函數(shù)，除了Main()主函數(shù)，還有IsValid(int n)，Output()，Queen(int n)，變量icount，Site這些組成程序，　　紅框圈出的是遞歸函數(shù)的應(yīng)用，既自己調(diào)用自己在Queen

41、(int n)中調(diào)用queen是典型的遞歸調(diào)用。　　編譯沒有錯誤　　5.1.3、具體運行結(jié)果　　運行結(jié)果表示出有92種可能性　　5.1.4、算法流程圖　　遞歸的圖解演示<

42、;/b>　　5.1.5、程序代碼見附錄一　　5.1.6、算法分析　　遞歸是一種很古老的算法，其應(yīng)用的也十分的廣泛，在和多復(fù)雜的程序中也是經(jīng)常性的使用，雖然其的程序編寫相對的簡單，但其確消耗很多的資源，在沒有好的算法的前提下，這是相對能夠運行的算法，當(dāng)然這也是在編程著能夠擁有一定的編寫能力的基礎(chǔ)上的。<

43、/p>　　遞歸的優(yōu)點是：編寫簡單，缺點是：消耗資源大。　　八皇后問題是一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用遞歸是最為常見的方法，由于遞歸是自己套自己，把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個函數(shù)中。　　該算法中所有語句的頻度之和(即算法的時間耗費)為：　　T(n)=2n3+3n2+2n+1&

44、lt;/p>　　當(dāng)n趨向于無窮時，其時間復(fù)雜度為O(n3)。　　5.2、回溯法解決八皇后問題　　5.2.1、回溯法介紹　　在計算機奧賽中，有時會遇到這樣一類題目，它的問題可以分解，但是又不能得出明確的動態(tài)規(guī)劃或是遞歸解法，此時可以考慮用回溯法解決此類問題?；厮莘ǖ膬?yōu)點在于其程序結(jié)構(gòu)明確

45、，可讀性強，易于理解，而且通過對問題的分析可以大大提高運行效率。但是，對于可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花費的時間比較長。　　回溯法的基本思想　　對于用回溯法求解的問題，首先要將問題進行適當(dāng)?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每

46、種可能的解的情況；從而得出結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因為在深度優(yōu)先搜索的過程中，不斷的將每個解（并不一定是完整的，事實上這也就是構(gòu)造約束函數(shù)的意義所在）與約束函數(shù)進行對照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時間。　　回溯法中，首先需要明確下面三個概念：　?。ㄒ唬┘s束函數(shù)：約束函數(shù)是根據(jù)題意

47、定出的。通過描述合法解的一般特征用于去除不合法的解，從而避免繼續(xù)搜索出這個不合法解的剩余部分。因此，約束函數(shù)是對于任何狀態(tài)空間樹上的節(jié)點都有效、等價的。　?。ǘ顟B(tài)空間樹：剛剛已經(jīng)提到，狀態(tài)空間樹是一個對所有解的圖形描述。樹上的每個子節(jié)點的解都只有一個部分與父節(jié)點不同。　?。ㄈU展節(jié)點、活結(jié)點、死結(jié)點：所謂擴展節(jié)點，就是當(dāng)前正在求出它的子節(jié)點的節(jié)點，

48、在DFS中，只允許有一個擴展節(jié)點?；罱Y(jié)點就是通過與約束函數(shù)的對照，節(jié)點本身和其父節(jié)點均滿足約束函數(shù)要求的節(jié)點；死結(jié)點反之。由此很容易知道死結(jié)點是不必求出其子節(jié)點的（沒有意義）。　　深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（FIFO）　　在分支界限法中，一般用的是FIFO或最小耗費搜索；其思想是一次性將一個節(jié)點的所有子節(jié)點求出并將其放入一個待求子節(jié)點的隊列。通

49、過遍歷這個隊列（隊列在遍歷過程中不斷增長）完成搜索。而DFS的作法則是將每一條合法路徑求出后再轉(zhuǎn)而向上求第二條合法路徑。而在回溯法中，一般都用DFS。為什么呢？這是因為可以通過約束函數(shù)殺死一些節(jié)點從而節(jié)省時間，由于DFS是將路徑逐一求出的，通過在求路徑的過程中殺死節(jié)點即可省去求所有子節(jié)點所花費的時間。FIFO理論上也是可以做到這樣的，但是通過對比不難發(fā)現(xiàn)，DFS在以這種方法解決問題時思路要清晰非常多。<p&

50、gt;　　因此，回溯法可以被認(rèn)為是一個有過剪枝的DFS過程。　　利用回溯法解題的具體步驟　　首先，要通過讀題完成下面三個步驟：　　描述解的形式，定義一個解空間，它包含問題的所有解。　　構(gòu)造狀態(tài)空間樹。<p

51、>　　構(gòu)造約束函數(shù)（用于殺死節(jié)點）。　　然后就要通過DFS思想完成回溯，完整過程如下：　　設(shè)置初始化的方案（給變量賦初值，讀入已知數(shù)據(jù)等）。　　變換方式去試探，若全部試完則轉(zhuǎn)(7)。　　判斷此法是否成功（通過約束函數(shù)），不成功則轉(zhuǎn)(2)。&l

52、t;p>　　試探成功則前進一步再試探。　　正確方案還未找到則轉(zhuǎn)(2)。　　已找到一種方案則記錄并打印。　　退回一步（回溯），若未退到頭則轉(zhuǎn)(2)。　　已退到頭則結(jié)束或打印無解。　　回溯法的數(shù)據(jù)結(jié)構(gòu)</

53、b>　　回溯法的狀態(tài)空間樹，在計算機上的數(shù)據(jù)結(jié)構(gòu)有兩種表示方法。當(dāng)用k表示樹的節(jié)點層數(shù)，n表示節(jié)點總數(shù)，m表示解的總數(shù)時：　　用m個k元組表示m種不同的解。其中，每組中的元素是[1,n]中的一個元素。在Pascal中，可以這樣定義變量：　　var a:array[1..k,1..m]of integer;（

54、integer可以依n的范圍決定）　　m個n元組表示m種不同的解。因為所有的節(jié)點都包含在每個解的表示中，每組中的元素只有兩種情況，被選用和不被選用。在Pascal中，可以這樣定義變量：　　var a:array[1..n,1..m]of boolean;　　這兩種數(shù)據(jù)結(jié)構(gòu)的解空間最多都含有2n個不同的元組<

55、/p>　　5.2.2、使用到的函數(shù)與變量　　回溯發(fā)是很好的算法，在所有算發(fā)中空間復(fù)雜度是最小的，其只有一個主函數(shù)main()，和一個變量total，就可以成功的解決八皇后問題，我本人對于這種算法非常的推崇，也覺的是所有解決了八皇后問題中最好的。　　編譯沒有錯誤<

56、;p>　　5.2.3、具體運行結(jié)果　　運行結(jié)果如圖　　5.2.4、算法流程圖　　回溯算法的圖解　　5.2.5、程序代碼見附錄二　　5.2.6、算法分

57、析　　回溯是一個很好的算法，其應(yīng)用的也十分的廣泛，在和多復(fù)雜的程序中也是經(jīng)常性的使用，雖然其的程序編寫相對的簡單，但其確消耗很多的資源，在沒有好的算法的前提下，這是相對能夠運行的算法，當(dāng)然這也是在編程著能夠擁有一定的編寫能力的基礎(chǔ)上的。　　回溯的優(yōu)點是：編寫復(fù)雜，缺點是：消耗資源小。　　八皇后問題是一個經(jīng)典的數(shù)據(jù)

58、結(jié)構(gòu)問題用回溯是最為常見的方法，由于回溯是自己套自己，把八皇后問題的調(diào)用函數(shù)在代碼界面上融合到了一個函數(shù)中。　　該算法中所有語句的頻度之和(即算法的時間耗費)為：　　T(n)=2n2+1　　分析：當(dāng)n趨向于無窮時，其時間復(fù)雜度為O(n2+1 +2)。　　5.3、堆棧法解八

59、皇后問題　　5.3.1、堆棧法介紹　　堆棧的概念　　堆棧(Stack)是一種比較重要的線性數(shù)據(jù)結(jié)構(gòu)，如果對數(shù)據(jù)結(jié)構(gòu)知識不是很了解的話，我們可以把它簡單的看作一維數(shù)組。但是對一維數(shù)組進行元素的插入、刪除操作時，可以在任何位置進行，而對于棧來說，插入、刪除操作是固定在一端進行的，

60、這一端稱為棧頂(top)，另一端稱為棧底(bottom)，向棧中插入數(shù)據(jù)的操作稱為壓入(Push)，從棧中刪除數(shù)據(jù)稱為彈出(Pop)。　　二堆棧的存儲方式　　對棧中元素的操作是按后進先出(Last In First Out,簡稱LIFO)的原則進行的，即最后壓入的元素最先彈出。<p&g

61、t;　　在棧的操作過程中，有一個永遠指向棧頂?shù)臈ｍ斨羔?，在壓入和彈出?shù)據(jù)時，棧頂指針向上或向下移動。當(dāng)棧頂指針為零時(即指向棧底的后面)，棧為空棧。如果壓入的數(shù)據(jù)過多超出了棧的最大空間，則發(fā)生棧上溢。　　在程序設(shè)計中，我們可以使用一維數(shù)組實現(xiàn)對棧的操作。假設(shè)用一維數(shù)組s[1..arrmax]表示棧，則對于非空棧，s[1]為最早壓入棧的元素，同時設(shè)棧頂指針top，則s[top]為最后壓入棧的元素。

62、當(dāng)top=arrmax時棧滿，若此時有數(shù)據(jù)入棧將產(chǎn)生“數(shù)組越界”的錯誤，極為棧上溢，反之當(dāng)top=0,意為?？?。　　5.3.2、使用到的函數(shù)與變量　　組成的程序的函數(shù)有：DeSetQueen(int row，int col)，DisplayAndSet()，main()，NoConflict(int row,int col)，Pop()，Push(int

63、 row，int col)，Queen()，SetQueen(int row，int col)，變量有：ArrayQueen,OutQueen,Top 。　　沒有編譯錯誤　　5.3.3、具體運行過程　　運行結(jié)果放在queen.txt文件中<p&g

64、t;　　八皇后問題的源代碼　　運行在queen.txt文件中的92種結(jié)果　　5.3.4、算法流程圖　　5.3.5、程序代碼見附錄三　　5.3.6、算法分析　　堆棧是一個很好的算法，其應(yīng)用的也十

65、分的廣泛，在和多復(fù)雜的程序中也是經(jīng)常性的使用，雖然其的程序編寫相對的簡單，但其確消耗很多的資源，在沒有好的算法的前提下，這是相對能夠運行的算法，當(dāng)然這也是在編程著能夠擁有一定的編寫能力的基礎(chǔ)上的。　　堆棧的優(yōu)點是：算法比較的平均，運行十分的復(fù)雜。　　八皇后問題是一個經(jīng)典的數(shù)據(jù)結(jié)構(gòu)問題用遞歸是最為常見的方法，由于遞歸是自己套自己，把八皇后問題的調(diào)用函數(shù)在代

66、碼界面上融合到了一個函數(shù)中。　　該算法中所有語句的頻度之和(即算法的時間耗費)為：　　T(n)=2nn+1　　分析：當(dāng)n趨向于無窮時，其時間復(fù)雜度為O(n2 +1)。　　5.4、三種算法的比較　　遞歸簡單，但消耗資源。</p

67、>　　回溯比較的復(fù)雜，但消耗資源少。　　堆棧比較的平均　　5.5、八皇后問題所有輸出結(jié)果為（8×8棋盤）：　　第1種情況: 第2種情況: 第3種情況:

68、　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * * * * * Q * * * * * * * Q * * * * * * Q * *　　* * * * Q * * * * * * Q * * * * *

69、 * * * * * * Q　　* * * * * * * Q * * * * * Q * * * * Q * * * * *　　* Q * * * * * * * * * * * * * Q * * * * * * Q *　　* * * Q * * *

70、 * Q * * * * * * * * * * Q * * * *　　* * * * * Q * * * * * * Q * * * * Q * * * * * *　　* * Q * * * * * * * Q * * * * * * * * * Q * * *

71、　　第4種情況: 第5種情況: 第6種情況:　　Q * * * * * * * * * * * * Q * * * * * Q * * * *　　* * * * Q * * * Q * * * * * * *

72、 Q * * * * * * *　　* * * * * * * Q * * * * Q * * * * * * * Q * * *　　* * * * * Q * * * Q * * * * * * * * * * * * * Q　　*

73、 * Q * * * * * * * * * * * * Q * Q * * * * * *　　* * * * * * Q * * * Q * * * * * * * * * * * Q * 　　* Q * * * * * * * * * * * * Q *

74、 * * Q * * * * * 　　* * * Q * * * * * * * Q * * * * * * * * * Q * *　　第7種情況: 第8種情況: 第9種情況:　　* * * * Q * * *

75、 * * Q * * * * * * * * * Q * * *　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * * * * * * Q * * * * * * Q * * * * Q * * * *</

76、p>　　* * * Q * * * * * * * * Q * * * * * * * * Q * *　　* Q * * * * * * * * * * * * * Q * * * * * * * Q　　* * * * * * Q * *

77、Q * * * * * * * Q * * * * * *　　* * Q * * * * * * * * Q * * * * * * * * * * Q *　　* * * * * Q * * * * * * * Q * * * * Q * * * * *

78、;　　第10種情況: 第11種情況: 第12種情況:　　* * * * * * Q * * * * * Q * * * * * * Q * * * *　　Q * * * * * * * Q * * * * * * * Q

79、 * * * * * * *　　* * Q * * * * * * * * * * * * Q * * * * Q * * *　　* * * * * * * Q * * * * * Q * * * * * * * * * Q　　* * * * *

80、 Q * * * * Q * * * * * * * * * * Q * *　　* * * Q * * * * * * * * * * Q * * * Q * * * * *　　* Q * * * * * * * Q * * * * * * * * *

81、* * * Q *　　* * * * Q * * * * * * Q * * * * * Q * * * * * *　　第13種情況: 第14種情況: 第15種情況:　　* Q * * * * * * * * *

82、* Q * * * * * * * * * * Q　　* * * * * Q * * * * Q * * * * * * * Q * * * * *　　Q * * * * * * * Q * * * * * * * Q * * * * * * *&l

83、t;p>　　* * * * * * Q * * * * * * * Q * * * * * * Q * *　　* * * Q * * * * * Q * * * * * * * Q * * * * * *　　* * * * * * * Q * * * * * *

84、 * Q * * * * Q * * *　　* * Q * * * * * * * * * * Q * * * * * * * * Q *　　* * * * Q * * * * * * Q * * * * * * * Q * * * *<p&g

85、t;　　第16種情況: 第17種情況: 第18種情況:　　* * * Q * * * * * * * * Q * * * * * * * * Q * *　　* * * * * Q * * * * * * * * Q * * * Q * *

86、 * * *　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * * * Q * * * * * * Q * * * * * * * * * * * Q　　* Q * * * * * *

87、 * Q * * * * * * * * * Q * * * *　　* * * * * * * Q * * * * * * * Q * Q * * * * * *　　* * Q * * * * * * * * * * Q * * * * * * *

88、 * Q *　　* * * * * * Q * * * Q * * * * * * * * * Q * * *　　第19種情況: 第20種情況: 第21種情況:　　* * * * Q * * * * * * *

89、 * Q * * * * * Q * * * *　　* * Q * * * * * * * Q * * * * * * * * * * * * Q　　Q * * * * * * * Q * * * * * * * Q * * * * * * *

90、　　* * * * * Q * * * * * * * * * Q * * Q * * * * *　　* * * * * * * Q * * * * Q * * * * * * * * Q * *　　* Q * * * * * * * Q * *

91、 * * * * * Q * * * * * *　　* * * Q * * * * * * * Q * * * * * * * * * * Q *　　* * * * * * Q * * * * * * * Q * * * * * Q * * *

92、　　第22種情況: 第23種情況: 第24種情況:　　* * * * * * * Q * * * Q * * * * * * * Q * * * *　　* * * Q * * * * * * * * * * * Q *

93、* * * * * Q *　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * Q * * * * * * * * * Q * * * * * * * * * * Q　　* * * *

94、* Q * * * * * * * * Q * * * * * Q * * *　　* Q * * * * * * * Q * * * * * * * Q * * * * * *　　* * * * * * Q * * * * * * Q * * *

95、* * * * Q * *　　* * * * Q * * * * * Q * * * * * * * Q * * * * *　　第25種情況: 第26種情況: 第27種情況:　　* * * * * Q * * *

96、 * * * * Q * * * * * * * * Q *　　* * * Q * * * * * * Q * * * * * * * Q * * * * *　　Q * * * * * * * Q * * * * * * * Q * * * * * * *</p

97、>　　* * * * Q * * * * * * * * * Q * * * * * * Q * *　　* * * * * * * Q * * * * Q * * * * * * * * * * Q　　* Q * * * * * * *

98、 * * * * * * Q * * * * Q * * *　　* * * * * * Q * * Q * * * * * * * Q * * * * * *　　* * Q * * * * * * * * Q * * * * * * * Q * * * *</p

99、>　　第28種情況: 第29種情況: 第30種情況:　　* * * * Q * * * * Q * * * * * * * Q * * * * * * 　　* * * * * * Q * * * * * Q * * *

100、 * * * * * * * Q　　Q * * * * * * * * * * * * * Q * * * * * * Q * *　　* * Q * * * * * Q * * * * * * * Q * * * * * * *　　* * *

101、 * * * * Q * * Q * * * * * * * Q * * * * *　　* * * * * Q * * * * * * * * * Q * * * * Q * * *　　* * * Q * * * * * * * * * Q * * *

102、* * * * * Q *　　* Q * * * * * * * * * Q * * * * * * * Q * * * *　　第31種情況: 第32種情況: 第33種情況:　　* * * * * Q * *

103、* * * * * * Q * * * * * * * * Q　　* Q * * * * * * * Q * * * * * * * Q * * * * * *　　* * * * * * Q * * * * Q * * * * * * * Q * * * *</p&g

104、t;　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * Q * * * * * * * * * * * * Q * * * * * * Q *　　* * * * Q * * * * * *

105、 * Q * * * * * * * Q * * *　　* * * * * * * Q * * Q * * * * * * * Q * * * * *　　* * * Q * * * * * * * * * Q * * * * * * * Q * *&

106、lt;p>　　第34種情況: 第35種情況: 第36種情況:　　* * * * Q * * * * * * * * Q * * * * * * Q * * *　　* Q * * * * * * * Q * * * * * * * Q

107、 * * * * * *　　* * * * * * * Q * * * * * * Q * * * * * * Q * *　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * * Q * *

108、 * * * * * Q * * * * * * * * * * Q *　　* * * * * * Q * * * * * * * * Q * * * Q * * * *　　* * Q * * * * * * * * * Q * * * * * * *

109、* * * Q　　* * * * * Q * * * * Q * * * * * * * Q * * * * *　　第37種情況: 第38種情況: 第39種情況:　　* * Q * * * * * * * * * *

110、 Q * * * * * * Q * * *　　* * * * Q * * * * * * Q * * * * * * * * * * * Q　　* * * * * * Q * * * * * * * Q * * * * Q * * * *<p

111、>　　Q * * * * * * * Q * * * * * * * Q * * * * * * *　　* * * Q * * * * * * * * * * * Q * * * * * * Q *　　* Q * * * * * * * Q * * * * *

112、* * Q * * * * * *　　* * * * * * * Q * * * * Q * * * * * * * * Q * *　　* * * * * Q * * * * Q * * * * * * * Q * * * * *

113、　第40種情況: 第41種情況: 第42種情況:　　* * Q * * * * * * * * * * * Q * * * * * * Q * *　　* * * * * Q * * * * * * Q * * * * * * Q * * * *<

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載