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

..課程設(shè)計(jì)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課題名稱八皇后問(wèn)題演示專業(yè)通信工程班級(jí)通信工程1081學(xué)號(hào)201013120103姓名劉獻(xiàn)文指導(dǎo)教師田娟秀郭芳20XX7月6日XX工程學(xué)院課程設(shè)計(jì)任務(wù)書課程名稱數(shù)據(jù)結(jié)構(gòu)課題八皇后問(wèn)題演示專業(yè)班級(jí)通信工程1081 學(xué)生姓名劉獻(xiàn)文學(xué)號(hào)201013120103指導(dǎo)老師田娟秀郭芳審批任務(wù)書下達(dá)日期2012年7月1日任務(wù)完成日期2012年7月6日1設(shè)計(jì)內(nèi)容與設(shè)計(jì)要求1.1設(shè)計(jì)內(nèi)容〔4課題四：八皇后問(wèn)題演示八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題,是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后,使其不能互相攻擊,即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上,問(wèn)有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解,后來(lái)有人用圖論的方法解出92種結(jié)果。設(shè)計(jì)思路：

解決8皇后時(shí),在安放第i行皇后時(shí),需要在列的方向從1到n試探<j=1,…,n>：首先在第j列安放一個(gè)皇后,如果在列、主對(duì)角線、次對(duì)角線方向有其它皇后,則出現(xiàn)攻擊,撤消在第j列安放的皇后。如果沒(méi)有出現(xiàn)攻擊,在第j列安放的皇后不動(dòng),遞歸安放第i+1行皇后。對(duì)于八皇后問(wèn)題的實(shí)現(xiàn),如果結(jié)合動(dòng)態(tài)的圖形演示,則可以使算法的描述更形象、更生動(dòng)。要求用TurboC或VC6.0MFC實(shí)現(xiàn)的八皇后問(wèn)題的圖形程序,能夠演示全部的92組解。1.2選題方案：所選題目根據(jù)學(xué)號(hào)確定,學(xué)號(hào)模6加1,即〔學(xué)號(hào)%6+1。如你的學(xué)號(hào)為9,則所選題目號(hào)為：9%6+1＝〔題目4。注意,所有的課題都要求用圖形方式演示步驟和結(jié)果。同學(xué)們可以自己針對(duì)數(shù)據(jù)結(jié)構(gòu)課程中所講算法來(lái)設(shè)計(jì)一個(gè)演示過(guò)程的算法。1.3設(shè)計(jì)要求：1.3.1課程設(shè)計(jì)報(bào)告規(guī)范〔1需求分析a.程序的功能。b.輸入輸出的要求?！?概要設(shè)計(jì)a.程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個(gè)模塊的功能。b.課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)結(jié)構(gòu)；即要存儲(chǔ)什么數(shù)據(jù),這些數(shù)據(jù)是什么樣的結(jié)構(gòu),它們之間有什么關(guān)系等?！?詳細(xì)設(shè)計(jì)a.采用C語(yǔ)言定義相關(guān)的數(shù)據(jù)類型。寫出各模塊的類C碼算法。c.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。〔4調(diào)試分析以及設(shè)計(jì)體會(huì)a.測(cè)試數(shù)據(jù)：準(zhǔn)備典型的測(cè)試數(shù)據(jù)和測(cè)試方案,包括正確的輸入及輸出結(jié)果和含有錯(cuò)誤的輸入及輸出結(jié)果。b.程序調(diào)試中遇到的問(wèn)題以及解決問(wèn)題的方法。c.課程設(shè)計(jì)過(guò)程經(jīng)驗(yàn)教訓(xùn)、心得體會(huì)?！?使用說(shuō)明用戶使用手冊(cè)：說(shuō)明如何使用你編寫的程序,詳細(xì)列出每一步的操作步驟?！?書寫格式a.設(shè)計(jì)報(bào)告要求用A4紙打印成冊(cè)：b.一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為22?！?附錄源程序清單〔帶注釋1.3.2考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果,并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動(dòng)手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評(píng),并按優(yōu)秀、良好、中等、及格和不及格五個(gè)等級(jí)給出每位同學(xué)的課程設(shè)計(jì)成績(jī)。具體考核標(biāo)準(zhǔn)包含以下幾個(gè)部分：〔1平時(shí)出勤〔占10%〔2系統(tǒng)需求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及程序總體結(jié)構(gòu)合理與否〔占10%〔3程序能否完整、準(zhǔn)確地運(yùn)行,個(gè)人能否獨(dú)立、熟練地調(diào)試程序〔占40%〔4設(shè)計(jì)報(bào)告〔占30%注意：不得抄襲他人的報(bào)告〔或給他人抄襲,一旦發(fā)現(xiàn),成績(jī)?yōu)榱惴?。?獨(dú)立完成情況〔占10%。1.3.3課程驗(yàn)收要求〔1運(yùn)行所設(shè)計(jì)的系統(tǒng)?！?回答有關(guān)問(wèn)題?！?提交課程設(shè)計(jì)報(bào)告?！?提交軟盤〔源程序、設(shè)計(jì)報(bào)告文檔?！?依內(nèi)容的創(chuàng)新程度,完善程序情況及對(duì)程序講解情況打分。2進(jìn)度安排第20周：星期一8：00——12：00上課星期二8：00——12：00上機(jī)星期三14：30——18：30上機(jī)星期四8：00——12：00上機(jī)附：課程設(shè)計(jì)報(bào)告裝訂順序：封面、任務(wù)書、目錄、正文、評(píng)分表、附件〔A4大小的圖紙及程序清單。正文的格式:一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為22。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分〔要求畫出模塊圖；三、主要功能的實(shí)現(xiàn)〔至少要有一個(gè)主要模塊的流程圖；四、程序調(diào)試；五、總結(jié)；六、附件〔所有程序的原代碼,要求對(duì)程序?qū)懗霰匾淖⑨?。正文總字?jǐn)?shù)要求在5000字以上〔不含程序原代碼。目錄TOC\o"1-3"\h\u8843一、需求分析...7204901.1功能要求7128561.2涉及到的知識(shí)點(diǎn)719613二、概要設(shè)計(jì) 7306762.1數(shù)據(jù)結(jié)構(gòu)739442.2抽象數(shù)據(jù)類型的定義891352.3算法流程 88645三、詳細(xì)設(shè)計(jì) 921237四、調(diào)試分析及測(cè)試 13267454.1遇到的問(wèn)題及解決方法13272354.2程序使用說(shuō)明1392714.3測(cè)試結(jié)果1325400五、總結(jié)與體會(huì)161296六、評(píng)分表1714350七、附錄〔源程序18需求分析八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題,該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的,并作了部分解答。高斯在棋盤上放下了八個(gè)互不攻擊的皇后,他還認(rèn)為可能有76種不同的放法,這就是有名的"八皇后"問(wèn)題。在國(guó)際象棋中,皇后是最有權(quán)利的一個(gè)棋子；只要?jiǎng)e的棋子在它的同一行或同一列或同一斜線〔正斜線或反斜線上時(shí),它就能把對(duì)方棋子吃掉。所以高斯提出了一個(gè)問(wèn)題：在8*8的格的國(guó)際象棋上擺放八個(gè)皇后,使其不能相互攻擊,即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面,問(wèn)共有多少種解法?，F(xiàn)在我們已經(jīng)知道八皇后問(wèn)題有92個(gè)解答。1.1功能要求當(dāng)運(yùn)行程序時(shí),在屏幕上顯示一個(gè)比較直觀選擇界面。進(jìn)入界面后,就會(huì)提示輸入字符的輸入形式,在八皇后求解程序中,只要你選擇輸出解的格式,選擇1則顯示為每一列皇后的放置的行數(shù),選擇2則顯示的是以矩陣形式形象的顯示皇后的放置位置,選擇0則退出程序的調(diào)試。在調(diào)試結(jié)果中,■的位置也就表示了該皇后應(yīng)該所在的位置,□代表了空位置。1.2涉及到的知識(shí)點(diǎn)本次課程設(shè)計(jì)中,用到的主要知識(shí)有：遞歸法的應(yīng)用,for語(yǔ)句的靈活運(yùn)用,數(shù)據(jù)結(jié)構(gòu)中樹知識(shí)的靈活運(yùn)用、棧及數(shù)組的掌握.概要設(shè)計(jì)2.1數(shù)據(jù)結(jié)構(gòu).1.數(shù)組gEightQueen[],存放第i行皇后所在的列；2.cont為存放皇后問(wèn)題解的個(gè)數(shù),ment為皇后問(wèn)題解矩形形式顯示的解的個(gè)數(shù)；3.對(duì)角線標(biāo)記為q[j]-i與<j-k>,i為列,j為行,當(dāng)<q[j]==i>或者<abs<q[j]-i>==abs<j-k>>,則表示第i列皇后是否已在第j行存在或q[j]-i與<j-k>為對(duì)角線沖突；2.2抽象數(shù)據(jù)類型的定義print1<>//打印每一行皇后放置的列數(shù)的情況print2<>//打印以矩陣形式形象的顯示皇后的放置位置find<>//尋找可以放置皇后的位置place1<>、place2<>//遞歸調(diào)用,存入所有每一行皇后所在的列Sleep<i>//緩沖i/1000s顯示下一個(gè)矩陣形式皇后位置voidmain<>//主函數(shù)調(diào)用2.3算法流程1.當(dāng)n<=8時(shí),從n行開始擺放第n個(gè)皇后〔因?yàn)檫@樣便可以符合每一行一個(gè)皇后的要求把第n個(gè)皇后所在的列存入q[k]中,遞歸調(diào)用,存入第n行皇后所在的列,直到8個(gè)皇后都已放置,2.當(dāng)n>8時(shí),便打印出結(jié)果。開始算法流程圖如下:開始從n行開始擺放第n個(gè)皇后從n行開始擺放第n個(gè)皇后n++把第n個(gè)皇后所在的n++把第n個(gè)皇后所在的列存入q[k]中YNNn<=8n<=8打印結(jié)果打印結(jié)果詳細(xì)設(shè)計(jì)//位置標(biāo)明法打印voidprint1<intn>{ inti; cont++; printf<"第%d個(gè)解:",cont>; for<i=1;i<=n;i++> printf<"%d",q[i]>; printf<"\n">;}//矩陣表示法打印voidprint2<>//輸出一個(gè)解{ ment++;//輸出的解的個(gè)數(shù) inti=0; printf<"第%d個(gè)解:\n",ment>;Sleep<300>; for<i=1;i<9;i++>//i為行 {for<intd=1;d<9;d++>//d為列{if<d==q[i]>//如果此行中d為存入皇后的列 printf<"■">;//標(biāo)記輸出 elseprintf<"□">;//此行中其他列輸出 }printf<"\n">;//一行輸出完成,換行 }}//遞歸調(diào)用法擺放所有皇后情況voidplace1<intk>{ if<k>8> print1<8>; else for<inti=1;i<=8;i++> if<find<i,k>> { q[k]=i;//把第K個(gè)皇后所在的列存入q[k]中 place1<k+1>;//遞歸調(diào)用,存入第k+1個(gè)皇后所在的列,直到8個(gè)皇后都已放置 } }voidplace2<intk>{ if<k>8> print2<>; else for<inti=1;i<=8;i++> if<find<i,k>> { q[k]=i; place2<k+1>; }}//主函數(shù)調(diào)用voidmain<>{ intchoice; charch; printf<"\n\n\t**歡迎進(jìn)入八皇后問(wèn)題**\n\n">; ch='y'; while<ch=='y'||ch=='Y'> {printf<"\n\t查詢菜單\n">;printf<"\n\t******************************************************">;printf<"\n\t*No.1--------每一行皇后放置的列數(shù)的情況*">;printf<"\n\t*No.2--------視圖矩陣形式顯示皇后的位置*">;printf<"\n\t*No.0--------退出*">;printf<"\n\t******************************************************">;printf<"\n\t請(qǐng)選擇菜單號(hào)<No.0--No.2>：">;scanf<"%d",&choice>;switch<choice>{case1: printf<"\n\t每一行皇后放置的列數(shù)的情況\n\n">; place1<1>; //從第1個(gè)皇后開始放置 break;case2: place2<1>; //從第1個(gè)皇后開始放置 break;case0: ch='n'; break;default: printf<"\n\t\t菜單選擇錯(cuò)誤,請(qǐng)重新輸入!\n">;} }}各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖開始開始判斷輸入判斷輸入調(diào)用place1函數(shù)120調(diào)用place1函數(shù)2調(diào)用place2函數(shù)調(diào)用place2函數(shù)顯示每一行皇后放置的列數(shù)的情況顯示每一行皇后放置的列數(shù)的情況顯示視圖矩陣形式顯示皇后的位置顯示視圖矩陣形式顯示皇后的位置退出退出調(diào)試分析及測(cè)試4.1遇到的問(wèn)題及解決方法<1>．由于對(duì)八個(gè)皇后放置的位置不能一次確定,而且前一個(gè)皇后的放置位置直接影響著后面的放置位置,使程序調(diào)試時(shí)要花費(fèi)不少時(shí)間?！?由于開始編程時(shí)沒(méi)有設(shè)置時(shí)間緩沖,所以輸出92種矩陣形式顯示皇后的位置時(shí)dos窗口只能顯示出第64個(gè)以后的解,求教老師后,在顯示前插入一個(gè)Sleep〔,使每一個(gè)矩形形式解都能在dos窗口中很明顯的看到。4.2程序使用說(shuō)明〔1本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)〔2進(jìn)入演示程序后即顯示文本方式的用戶界面〔3進(jìn)入界面后,就會(huì)提示輸入字符的輸入形式,在八皇后求解程序中,只要你選擇輸出解的格式,選擇1則顯示為每一列皇后的放置的行數(shù),選擇2則顯示的是以矩陣形式形象的顯示皇后的放置位置,選擇0則退出程序的調(diào)試。在調(diào)試結(jié)果中,■的位置也就表示了該皇后應(yīng)該所在的位置,□代表了空位置。4.3測(cè)試結(jié)果初步運(yùn)行界面選擇輸入為"1"時(shí)的顯示,位置標(biāo)明每一行皇后放置的列數(shù)選擇輸入為"2"時(shí)的顯示,視圖矩陣形式顯示皇后位置選擇輸入為"0"時(shí)的顯示,即將退出dos窗口總結(jié)與體會(huì)通過(guò)這次的課程設(shè)計(jì),我從中得到了許多經(jīng)驗(yàn)和軟件設(shè)計(jì)的一些新思路；從這個(gè)八皇后問(wèn)題設(shè)計(jì)以及分析中,本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對(duì)于軟件設(shè)計(jì)的重要性,它的使用,可以改變軟件的運(yùn)行周期,思路從繁化簡(jiǎn),并且都能夠通過(guò)其相關(guān)引導(dǎo),將本身以前編程思想進(jìn)行擴(kuò)充,發(fā)展.這也是在這次課程設(shè)計(jì)中我所掌握得到的。但在這次的課設(shè)中也遇了一些問(wèn)題,如,八皇后在變成初期由于沒(méi)真正體會(huì)到"樹"在里面的運(yùn)用,不自覺(jué)的采用了非遞歸的算法,結(jié)果大大增加了程序的復(fù)雜程度。并且也讓整個(gè)程序的時(shí)間復(fù)雜度變得更大；在重溫了樹的回溯,以及二叉樹的遍歷后,最終將程序進(jìn)行了一次較大的改造。并且通過(guò)思考,再將以前的知識(shí)加以運(yùn)用才最終解決了這個(gè)問(wèn)題,整個(gè)程序的算法的可看性也有了較大的改進(jìn)?？偨Y(jié)一下自己,發(fā)現(xiàn)自己雖然在不僅在理論上沒(méi)有掌握牢固,并且在實(shí)踐的時(shí)候也遇到了問(wèn)題,所以自己還是遠(yuǎn)遠(yuǎn)的不足,不管是在數(shù)據(jù)結(jié)構(gòu)課程的設(shè)計(jì)上,還是其他專業(yè)課上,在以后的一段學(xué)習(xí)時(shí)間里必須堅(jiān)持自己思考,自己多動(dòng)腦,多動(dòng)手,這樣才能脫離理論,讓自己的學(xué)習(xí)更上一層樓。參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)教程/李春葆等編著.—3版—北京：清華大學(xué)出版社,2009.3數(shù)據(jù)結(jié)構(gòu)教程〔第三版上機(jī)實(shí)驗(yàn)教程/李春葆等編著.—北京：清華大學(xué)出版社,2009.3評(píng)分表應(yīng)用技術(shù)學(xué)院課程設(shè)計(jì)評(píng)分表課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)項(xiàng)目評(píng)價(jià)設(shè)計(jì)方案的合理性與創(chuàng)造性設(shè)計(jì)與調(diào)試結(jié)果設(shè)計(jì)說(shuō)明書的質(zhì)量答辯陳述與回答問(wèn)題情況課程設(shè)計(jì)周表現(xiàn)情況綜合成績(jī)教師簽名：日期：〔注：1．此頁(yè)附在課程設(shè)計(jì)報(bào)告之后；2．綜合成績(jī)按優(yōu)、良、中、及格和不及格五級(jí)評(píng)定。附錄〔源程序#include<stdio.h>#include<dos.h>#include<windows.h>constintN=20;intq[N];intcont=0,ment=0;voidprint1<intn>{ inti; cont++; printf<"第%d個(gè)解:",cont>; for<i=1;i<=n;i++> printf<"%d",q[i]>; printf<"\n">;}voidprint2<>//輸出一個(gè)解{ ment++;//輸出的解的個(gè)數(shù) inti=0; printf<"第%d個(gè)解:\n",ment>;Sleep<300>; for<i=1;i<9;i++>//i為行 {for<intd=1;d<9;d++>//d為列{if<d==q[i]>//如果此行中d為存入皇后的列 printf<"■">;//標(biāo)記輸出 elseprintf<"□">;//此行中其他列輸出 }printf<"\n">;//一行輸出完成,換行 }}intfind<inti,intk>{ intj;//定義j為行 j=1; while<j<k> { if<<q[j]==i>||<abs<q[j]-i>==abs<j-k>>>//判斷第i列皇后是否已在第j行存在或q[j]-i與<j-k>為對(duì)角線沖突 return0;//說(shuō)明第i列第j行不能放皇后 j++; } return1;}voidplace1<intk>{ if<k>8> print1<8>; else for<inti=1;i<=8;i++> if<find<i,k>> { q[k]=i;//把第K個(gè)皇后所在的列存入q[k]中 place1<k+1>;//遞歸調(diào)用,存入第k+1個(gè)皇后所在的列,直到8個(gè)皇后都已放置 } }voidplace2<intk>{ if<k>8> print2<>; else for<inti=1;i<=8;i++>