數據結構課程設計八皇后的問題求解

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

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

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

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

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

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

7、，否則為0；數組b代表主對角線沖突，為bi-j+7，即從b0b14，如果某條主對角線上已經有皇后，則為1，否則為0；數組c代表從對角線沖突，為ci+j，即從c0c14，如果某條從對角線上已經有皇后，則為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-icolumn+7=1; /標記，下一次該主對角線上不能放

8、皇后 ci+icolumn=1; /標記，下一次該從對角線上不能放皇后 if(i7) qu(i+1); /如果行還沒有遍歷完，進入下一行 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); /如果前次的皇后放置導致后面的放置無論如何都不能滿足

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)數void qu(int i); /參數i代表行int main() int iline,icolumn; /棋盤初始化，空格為*，放置皇后的地方為 for(ilin

10、e=0;iline8;iline+) ailine=0; /列標記初始化，表示無列沖突 for(icolumn=0;icolumn8;icolumn+) queenilineicolumn=*; /主、從對角線標記初始化，表示沒有沖突 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-icolumn+7=1; /標記，下一次該主對角線上不能放皇后 ci+icolumn=1; /標記，下一次該從對角線上不能放皇后 if(i7) qu(i+1); /如果行還沒有遍歷完，進入下一行 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); /如果前次的皇后放置導致后面的放置無論如何都不能滿足要求，則回溯，重置 queeniicolumn=*; aicolumn=0; bi-icolumn+7=0; ci+icolumn=0; 第六章 運行結果分析由于在一些沖突問題上不太熟練，而且沒有玩過八皇后，所以對于一些規(guī)則不是很了解，所以在程序的編寫上出現(xiàn)一些錯誤，例如for語句的循環(huán)的次數沒有控制得當。八皇后問題的遞歸算法的運行結果：第七章 結束語轉眼，為期兩周的數據結構課程設計實習即將結束了。在這次實習中，自己的c語言知識和數據結構知識得到了鞏固，編程能力也有了一定的提高。同時也學會了解決問題的方法?？偨Y起來，自己主要有以下幾點體會：1. 必須牢固掌握基礎知識。2.必須培養(yǎng)嚴謹的科學態(tài)度。3.這次課程設計也讓我充分認識到數據結構這門課的重要性。它給我們一個思想和大綱，讓我們在編程時容易找到思路，不至于無章可循。同時它也有廣泛的實際應用。總之，在這次實習中，自己的c語言以及數據結構知識得到提高，編程能力也得到了提高。第八章 參考文獻1 于永彥，于長輝，劉作軍.c+程序設計實踐教學指