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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目八皇后的問題求解學(xué)生姓名指導(dǎo)教師學(xué) 院 信息學(xué)院 專業(yè)班級(jí)信科一班 完成時(shí)間2014年1月2日 第一章 課程設(shè)計(jì)目的本學(xué)期我們對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程進(jìn)行了學(xué)習(xí)。這門課程是一門實(shí)踐性非常強(qiáng)的課程，為了讓大家更好地理解與運(yùn)用所學(xué)知識(shí)，提高動(dòng)手能力，我們進(jìn)行了此次課程設(shè)計(jì)實(shí)習(xí)。這次課程設(shè)計(jì)不但要求實(shí)習(xí)者掌握數(shù)據(jù)結(jié)構(gòu)中的各方面知識(shí)，還要求實(shí)習(xí)者具備一定的語言基礎(chǔ)和編程能力。具體說來，這次課程設(shè)計(jì)主要有兩大方面目的。一是讓實(shí)習(xí)著通過學(xué)習(xí)掌握數(shù)據(jù)結(jié)構(gòu)中的知識(shí)。對(duì)于遞歸算法這一課題來說，所要求掌握的數(shù)據(jù)結(jié)構(gòu)知識(shí)主要有：if語句的選擇結(jié)構(gòu)，for語句的循環(huán)結(jié)構(gòu)，函數(shù)的調(diào)用來實(shí)現(xiàn)。二是二是通過

2、實(shí)習(xí)鞏固并提高實(shí)習(xí)者的c語言知識(shí)，并初步了解visual c+的知識(shí)，提高其編程能力與專業(yè)水平。第二章 課程設(shè)計(jì)內(nèi)容和要求2.1課程設(shè)計(jì)內(nèi)容組成員名稱和分工在一個(gè)的棋盤里放置個(gè)皇后，要求每個(gè)皇后兩兩之間不相沖（在每一橫列豎列斜列只有一個(gè)皇后）并要求用遞歸算法實(shí)現(xiàn)，輸出所有棋盤狀態(tài)，其中空的地方為“*”，放置皇后的地方為“”2.1.1八皇后的建立與輸出對(duì)給定的的棋盤里的八個(gè)皇后進(jìn)行討論，根據(jù)遞歸法，循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu)進(jìn)行建立并輸出之。2.2 運(yùn)行環(huán)境該程序的運(yùn)行環(huán)境為windows7系統(tǒng)，microsoft visual c+6.0版本。第三章 課程設(shè)計(jì)分析3.1數(shù)據(jù)類型規(guī)定了函數(shù)返回值類型。黨

3、執(zhí)行函數(shù)體中的語句后，通常會(huì)產(chǎn)生一個(gè)結(jié)果，這就是函數(shù)的返回值，它可以是任何有效的類型。若函數(shù)執(zhí)行后不返回值，數(shù)據(jù)類型習(xí)慣用void來表示。如果在函數(shù)定義時(shí)沒有數(shù)據(jù)類型出現(xiàn)，則默認(rèn)為函數(shù)返回值為整型值(int)。3.2 函數(shù)調(diào)用調(diào)用一個(gè)函數(shù)之前必須對(duì)該函數(shù)進(jìn)行說明。函數(shù)調(diào)用由函數(shù)名和函數(shù)調(diào)用運(yùn)算符( )組成，( )內(nèi)有0個(gè)或多個(gè)逗號(hào)分隔的參數(shù)(稱為實(shí)參)。每一個(gè)參數(shù)是一個(gè)表達(dá)式，且參數(shù)的個(gè)數(shù)與參數(shù)的類型要與被調(diào)函數(shù)定義的參數(shù)(稱為形參)個(gè)數(shù)和類型匹配。當(dāng)被調(diào)函數(shù)執(zhí)行時(shí)，首先計(jì)算實(shí)參表達(dá)式，并將結(jié)果值傳送給行參，然后執(zhí)行函數(shù)體，返回的返回值被傳送到調(diào)用函數(shù)。如果函數(shù)調(diào)用后有返回值，調(diào)用表達(dá)是可以用

4、在表達(dá)式中，而無參函數(shù)的調(diào)用是一個(gè)單獨(dú)的語句。3.3 選擇結(jié)構(gòu)if語句的基本形式可分為兩種：（1） if (表達(dá)式) 語句其執(zhí)行過程是，首先計(jì)算表達(dá)式的值，若不為0，條件判斷為真，則執(zhí)行( )后面的語句，否則，if語句中止執(zhí)行，即不執(zhí)行( )后面的語句。（2） if(表達(dá)式) 語句1 else 語句2其執(zhí)行過程是，首先計(jì)算表達(dá)式的值，若不為0，條件判斷為真，則執(zhí)行( )后面的語句，否則執(zhí)行語句2。3.4 循環(huán)結(jié)構(gòu)for 語句的一般形式：for (表達(dá)式1；表達(dá)式2；表達(dá)式3)語句；/循環(huán)體其執(zhí)行的過程有以下幾個(gè)步驟：求解表達(dá)式1；求解表達(dá)式2，若其值為真，則執(zhí)行for語句中指定的循環(huán)體語句，然

5、后執(zhí)行下面的第3)步。若為假，則結(jié)束循環(huán)；求解表達(dá)式3；轉(zhuǎn)回上面第2）步繼續(xù)執(zhí)行；循環(huán)結(jié)束，執(zhí)行for語句后面的其他語句。第四章 算法（數(shù)據(jù)結(jié)構(gòu)）描述4.1.1 八皇后的存儲(chǔ)結(jié)構(gòu)定義其列數(shù)，行數(shù)，主對(duì)角線，從對(duì)角線，算法的種類數(shù)，static char queen88;static int a8;/列數(shù)static int b15;/代表主對(duì)角線static int c15;代表從對(duì)角線static int iqueennum=0; /記錄總的棋盤狀態(tài)數(shù)void qu(int i); /參數(shù)i代表行4.1.2 初始化棋盤在確定其中八皇后棋盤中的位置時(shí)，應(yīng)該初始化一個(gè)棋盤，然后再輸入數(shù)據(jù)int

6、main() int iline,icolumn; /棋盤初始化，空格為*，放置皇后的地方為 for(iline=0;iline8;iline+) ailine=0; /列標(biāo)記初始化，表示無列沖突 for(icolumn=0;icolumn8;icolumn+) queenilineicolumn=*; /主、從對(duì)角線標(biāo)記初始化，表示沒有沖突 for(iline=0;iline15;iline+) biline=ciline=0; qu(0); return 0;4.1.3建立并輸出棋盤數(shù)組a、b、c分別用來標(biāo)記沖突，a數(shù)組代表列沖突，從a0a7代表第0列到第7列，如果某列上已經(jīng)有皇后，則為1

7、，否則為0；數(shù)組b代表主對(duì)角線沖突，為bi-j+7，即從b0b14，如果某條主對(duì)角線上已經(jīng)有皇后，則為1，否則為0；數(shù)組c代表從對(duì)角線沖突，為ci+j，即從c0c14，如果某條從對(duì)角線上已經(jīng)有皇后，則為1，否則為0；void qu(int i) int icolumn; for(icolumn=0;icolumn8;icolumn+) if(aicolumn=0&bi-icolumn+7=0&ci+icolumn=0) /如果無沖突 queeniicolumn=; /放皇后 aicolumn=1; /標(biāo)記，下一次該列上不能放皇后 bi-icolumn+7=1; /標(biāo)記，下一次該主對(duì)角線上不能放

8、皇后 ci+icolumn=1; /標(biāo)記，下一次該從對(duì)角線上不能放皇后 if(i7) qu(i+1); /如果行還沒有遍歷完，進(jìn)入下一行 else /否則輸出 /輸出棋盤狀態(tài) int iline,icolumn;for(int i=0;i1;i+)iqueennum+;cout第iqueennum種算法為：endl; for(iline=0;iline8;iline+) for(icolumn=0;icolumn8;icolumn+) printf(%c ,queenilineicolumn); printf(n); printf(nn); /如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足

9、要求，則回溯，重置 queeniicolumn=*; aicolumn=0; bi-icolumn+7=0; ci+icolumn=0; 第五章 源代碼程序八皇后問題#include #includeusing namespace std;static char queen88;static int a8;static int b15;static int c15;static int iqueennum=0; /記錄總的棋盤狀態(tài)數(shù)void qu(int i); /參數(shù)i代表行int main() int iline,icolumn; /棋盤初始化，空格為*，放置皇后的地方為 for(ilin

10、e=0;iline8;iline+) ailine=0; /列標(biāo)記初始化，表示無列沖突 for(icolumn=0;icolumn8;icolumn+) queenilineicolumn=*; /主、從對(duì)角線標(biāo)記初始化，表示沒有沖突 for(iline=0;iline15;iline+) biline=ciline=0; qu(0); return 0;void qu(int i) int icolumn; for(icolumn=0;icolumn8;icolumn+) if(aicolumn=0&bi-icolumn+7=0&ci+icolumn=0) /如果無沖突 queeniicol

11、umn=; /放皇后 aicolumn=1; /標(biāo)記，下一次該列上不能放皇后 bi-icolumn+7=1; /標(biāo)記，下一次該主對(duì)角線上不能放皇后 ci+icolumn=1; /標(biāo)記，下一次該從對(duì)角線上不能放皇后 if(i7) qu(i+1); /如果行還沒有遍歷完，進(jìn)入下一行 else /否則輸出 /輸出棋盤狀態(tài) int iline,icolumn;for(int i=0;i1;i+)iqueennum+;cout第iqueennum種算法為：endl; for(iline=0;iline8;iline+) for(icolumn=0;icolumn8;icolumn+) printf(%c

12、 ,queenilineicolumn); printf(n); printf(nn); /如果前次的皇后放置導(dǎo)致后面的放置無論如何都不能滿足要求，則回溯，重置 queeniicolumn=*; aicolumn=0; bi-icolumn+7=0; ci+icolumn=0; 第六章 運(yùn)行結(jié)果分析由于在一些沖突問題上不太熟練，而且沒有玩過八皇后，所以對(duì)于一些規(guī)則不是很了解，所以在程序的編寫上出現(xiàn)一些錯(cuò)誤，例如for語句的循環(huán)的次數(shù)沒有控制得當(dāng)。八皇后問題的遞歸算法的運(yùn)行結(jié)果：第七章 結(jié)束語轉(zhuǎn)眼，為期兩周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)實(shí)習(xí)即將結(jié)束了。在這次實(shí)習(xí)中，自己的c語言知識(shí)和數(shù)據(jù)結(jié)構(gòu)知識(shí)得到了鞏固，編程能力也有了一定的提高。同時(shí)也學(xué)會(huì)了解決問題的方法?？偨Y(jié)起來，自己主要有以下幾點(diǎn)體會(huì)：1. 必須牢固掌握基礎(chǔ)知識(shí)。2.必須培養(yǎng)嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度。3.這次課程設(shè)計(jì)也讓我充分認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)這門課的重要性。它給我們一個(gè)思想和大綱，讓我們?cè)诰幊虝r(shí)容易找到思路，不至于無章可循。同時(shí)它也有廣泛的實(shí)際應(yīng)用?？傊?，在這次實(shí)習(xí)中，自己的c語言以及數(shù)據(jù)結(jié)構(gòu)知識(shí)得到提高，編程能力也得到了提高。第八章 參考文獻(xiàn)1 于永彥，于長輝，劉作軍.c+程序設(shè)計(jì)實(shí)踐教學(xué)指