.z.工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目： 八皇后 2008 年 6 月25 日設(shè)計任務(wù)書課題名稱八皇后設(shè)計目的用c++語言平臺將一個８＊８的棋盤上放上８個皇后，使得每一個皇后既攻擊不到另外七個皇后，也不被另外七個皇后所攻擊的92種結(jié)構(gòu)予以實現(xiàn)．通過這次課程設(shè)計,提高自己的編程能力,熟悉c++的編程壞境,為以后的程序開發(fā)打下基礎(chǔ).實驗環(huán)境1）

系統(tǒng)要求：win98以上操作系統(tǒng)；2）

語言平臺：tc++或vc++6.0；3）

執(zhí)行文件：八皇后.e*e任務(wù)要求試編寫程序?qū)崿F(xiàn)將八個皇后放置在國際象棋棋盤的無沖突的位置上的算法，并給出所有的解。工作進(jìn)度計劃序號起止日期工作容1查閱相關(guān)容2編寫代碼及實習(xí)報告3完善課程設(shè)計報告4答辯指導(dǎo)教師（簽章）：2008年6月30日-.z.摘要：八皇后問題要求在一個８＊８的棋盤上放上８個皇后，使得每一個皇后既攻擊不到另外七個皇后，也不被另外七個皇后所攻擊．按照國際象棋的規(guī)則，一個皇后可以攻擊與之處在同一行或同一列或同一斜線上的其他任何棋子．因此，八皇后問題等于要求八個皇后中的任意兩個不能被放在同一行或同一列或同一斜線上。而本課程設(shè)計本人的目的也是通過用c++語言平臺將一個８＊８的棋盤上放上８個皇后，使得每一個皇后既攻擊不到另外七個皇后，也不被另外七個皇后所攻擊的92種結(jié)構(gòu)予以實現(xiàn)．使用遞歸方法最終將其問題變得一目了然，更加易懂。關(guān)鍵詞：八皇后;c++;遞歸法目錄1.課題綜述11.1課題的來源及意義11.2面對的問題12.需求分析12.1涉及到的知識12.2軟硬件的需求12.3功能需求23.概要設(shè)計24.詳細(xì)設(shè)計和實現(xiàn)24.1算法描述及詳細(xì)流程圖24.1.1算法描述34.1.2算法流程圖35.代碼編寫及詳細(xì)注釋46.程序調(diào)試76.1調(diào)試過程、步驟及遇到的問題77.運行與測試77.1運行演示7總結(jié)9致10參考文獻(xiàn)11.-.z.1.課題綜述1.1課題的來源及意義八皇后問題是一個古老而著名的問題，該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的。在國際象棋中，皇后是最有權(quán)利的一個棋子；只要別的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時，它就能把對方棋子吃掉。所以高斯提出了一個問題：在8*8的格的國際象棋上擺放八個皇后，使其不能相互攻擊，即任意兩個皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法。到了現(xiàn)代，隨著計算機技術(shù)的飛速發(fā)展，這一古老而有趣的數(shù)學(xué)游戲問題也自然而然的被搬到了計算機上。運用所學(xué)計算機知識來試著解決這個問題是個鍛煉和提高我自己編程能力和獨立解決問題能力的好機會，可以使我增強信心，為我以后的編程開個好頭，故我選擇了這個有趣的課題。1.2面對的問題1）

解決沖突問題：這個問題包括了行，列，兩條對角線；列：規(guī)定每一列放一個皇后，不會造成列上的沖突；行：當(dāng)?shù)贗行被*個皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以I為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)；2）使用數(shù)據(jù)結(jié)構(gòu)的知識，用遞歸法解決問題。2.需求分析2.1涉及到的知識本次課程設(shè)計中，用到的主要知識有：遞歸法的運用，for語句的靈活運用，數(shù)據(jù)結(jié)構(gòu)中樹知識的靈活運用、棧及數(shù)組的掌握。2.2軟硬件的需求1）系統(tǒng)要求：win98以上操作系統(tǒng)；2)語言平臺：tc++或vc++6.0；2.3功能需求當(dāng)運行程序時，在屏幕上顯示每一種方法八個皇后的相對位置，要用比較直觀的界面顯示。3.概要設(shè)計本課件學(xué)生是用循環(huán)遞歸循環(huán)來實現(xiàn)的，分別一一測試了每一種擺法，并把它擁有的92種變化表現(xiàn)出來。在這個程序中，我的主要思路以及思想是這樣的：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)的實現(xiàn)而對于數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，學(xué)生則是著重于:數(shù)組a[I]：a[I]表示第I個皇后放置的列；I的圍：1..8;對角線數(shù)組：b[j](主對角線),c[j]（從對角線），根據(jù)程序的運行，去決定主從對角線是否放入皇后；4.詳細(xì)設(shè)計和實現(xiàn)4.1算法描述及詳細(xì)流程圖4.1.1算法描述A、數(shù)據(jù)初始化。B、從n列開始擺放第n個皇后（因為這樣便可以符合每一豎列一個皇后的要求），先測試當(dāng)前位置（n，m）是否等于0（未被占領(lǐng)）。如果是，擺放第n個皇后，并宣布占領(lǐng)（記得橫列豎列斜列一起設(shè)置），接著進(jìn)行遞歸；如果不是，測試下一個位置（n，m+1），但是如果當(dāng)n<=8，m=8時，發(fā)現(xiàn)此時已無法擺放時，便要進(jìn)行回溯。從問題的*一種可能出發(fā)，搜索從這種情況能出發(fā)，繼續(xù)搜索，這種不斷“回溯”的尋找解的方法，稱為“回溯法”。C、使用數(shù)組實現(xiàn)回溯法的思想。D、當(dāng)n>8時，便打印出結(jié)果。E、輸出函數(shù)我使用printf輸出，運行形式為：第m種方法為：********4.1.2算法流程圖5.代碼編寫及詳細(xì)注釋*include<conio.h>*include<math.h>*include<stdlib.h>*include<stdio.h>*include<iostream.h>*defineQUEENS8intiCount=0;//!記錄解的序號的全局變量。intSite[QUEENS];//!記錄皇后在各行上的放置位置的全局?jǐn)?shù)組。voidQueen(intn);//!遞歸求解的函數(shù)。voidOutput();//!輸出一個解。intIsValid(intn);//!判斷第n個皇后放上去之后，是否有〉沖突。voidmain()/*Main：主函數(shù)。*/{system("title葉青--遞歸算法八皇后問題");cout<<""<<"八皇后的解法："<<endl;cout<<""<<""<<endl;Queen(0);//!從第0行開始遞歸試探。getch();//!按任意鍵返回。}voidQueen(intn)/*Queen：遞歸放置第n個皇后，程序的核心!*/{inti;if(n==QUEENS)//!參數(shù)n從0開始，等于8時便試出了一個解，將它輸出并回溯。{Output();return;}for(i=1;i<=QUEENS;i++)//!n還沒到8，在第n行的各個行上依次試探。{Site[n]=i;//!在該行的第i行上放置皇后。if(IsValid(n))//!如果放置沒有沖突，就開始下一行的試探。 Queen(n+1);}}intIsValid(intn)/*IsValid：判斷第n個皇后放上去之后，是否合法，即是否無沖突。*/{inti;for(i=0;i<n;i++)//!將第n個皇后的位置依次于前面n－1個皇后的位置比較。{if(Site[i]==Site[n])//!兩個皇后在同一列上，返回0。return0;if(abs(Site[i]-Site[n])==(n-i))//!兩個皇后在同一對角線上，返回0。return0;}return1;//!沒有沖突，返回1。}voidOutput()/*Output：輸出一個解，即一種沒有沖突的放置方案。*/{ inti;printf("No.%-5d",++iCount);//!輸出序號。for(i=0;i<QUEENS;i++)//!依次輸出各個行上的皇后的位置，即所在的列數(shù)。 printf("%d",Site[i]);printf("\n");}6.程序調(diào)試6.1調(diào)試過程、步驟及遇到的問題在完整程序調(diào)試時遇到幾個小問題，后經(jīng)細(xì)心改正后才把調(diào)試工作做完。例如:當(dāng)用printf輸出時,出現(xiàn)了一些錯誤,幾經(jīng)調(diào)試后,發(fā)現(xiàn)原來是缺少了stdio.h這樣一個頭文件,添加了頭文件后,還出現(xiàn)了一些問題,邏輯錯誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時卻沒有錯誤,就是沒有正確的輸出答案,一開始我也不知道是怎么回事,通過和同學(xué)的交流,發(fā)現(xiàn)是邏輯錯誤,經(jīng)過改正后,程序終于可以運行了.7.運行與測試7.1運行演示總結(jié)通過了19周這個星期的程序設(shè)計，我從中得到了許多的經(jīng)驗以及軟件設(shè)計的一些新的思路；從這個八皇后問題設(shè)計以及分析中，本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對于計算機軟件設(shè)計的重要性，它的使用，可以改變一個軟件的運行周期，也可以將軟件的思路從繁化簡，并且都能夠通過數(shù)據(jù)結(jié)構(gòu)的相關(guān)引導(dǎo)，將本身以前編程思想進(jìn)行擴充，發(fā)展；這也是在這次課程設(shè)計中我所掌握得到的。但由于我的基本知識還不是則扎實，也缺乏對軟件設(shè)計的經(jīng)驗，在這過程中也出現(xiàn)了一些問題，如，八皇后在變成初期由于沒真正體會到數(shù)據(jù)結(jié)構(gòu)中“樹”在里面的運用，將程序往大一時c語言的方向發(fā)展，不自覺的采用了非遞歸的算法，結(jié)果大大增加了程序的復(fù)雜程度。并且也讓整個程序的時間復(fù)雜度變得更大；在后來學(xué)生對數(shù)據(jù)結(jié)構(gòu)的第六章進(jìn)行了比較深入的研讀，才發(fā)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)樹的實際運用的空間是相當(dāng)?shù)拇?，并且，通過了重溫樹的回溯，以及二叉樹的遍歷，最終將程序進(jìn)行了一次較大的改造。并且通過思考，再將以前的數(shù)組知識加以運用才最終解決了這個問題，整個程序的算法的可看性也有了相當(dāng)?shù)母倪M(jìn)。課程設(shè)計隨著時間的推移，也即將結(jié)束了，但這個學(xué)期數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義，它從一個程度上改變了我們的編程思想，如何將一個程序快速而又準(zhǔn)備的進(jìn)行編寫，進(jìn)行編譯，都成為了我們思考的重點，也通過這一個學(xué)期的學(xué)習(xí)，我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個階段，我也明白了，好的思想，不能提留于字面上的認(rèn)知，還需要的是平時多練多寫一些相關(guān)的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關(guān)鍵。課程設(shè)計已經(jīng)接近尾聲了，但它給我的不只是程序設(shè)計上的滿足，更重要的是對自己編程思想的一次更新，以及對算法的一個全新的認(rèn)識！我覺得還可以考慮開發(fā)N皇后問題,在主界面中添加一個int型的變量,程序一開始要求輸入一個數(shù)(確定是幾皇后問題),輸入后按下enter后,輸出各種解.主程序與八皇后的求解大體相同.致在這次課程設(shè)計中,我遇到了不少問題,包括程序上的和課程設(shè)計的撰寫上的,同學(xué)曾給過我許多幫助,在此我表示對他們的忠心感。同時，指導(dǎo)老師和實驗人員給了我很多上機的機會，給了我一個做課程設(shè)計的很好的條件，我才能夠順利的完成，在此，我僅以文字的形式表示忠心感，感他們這么多天對我的幫助。參考文獻(xiàn)[1]仕華,數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.-:機械工業(yè),2005.5[2]于永彥,建洋.課程設(shè)計指導(dǎo)書.：工學(xué)院計算機工程系,2006[3]振安,燕君，忱.C++語言課程設(shè)計.：高等教育,2003[4]志泊,海燕,王春玲.VisualC++程序設(shè)計.中國鐵道,2005[5]呂鳳哲,C++語言程序設(shè)計（第二版）.：電子工業(yè),2005[6]殷人昆，永雷等.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++）.:清華大學(xué)，1999[7]嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)．：清華大學(xué)，1997[8]春葆.數(shù)據(jù)結(jié)構(gòu)—考研指導(dǎo).:清華大學(xué),2002[9]慧南．?dāng)?shù)據(jù)結(jié)構(gòu)—C++語言描述．：人民郵電，2005．03指導(dǎo)教師評語**1061303127葉青班級信息106選題名