數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-8皇后問(wèn)題

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　選題： 八皇后問(wèn)題</b></p><p><b>　　姓 名：</b></p><p><b>　　學(xué) 號(hào)：</b></p><p><b>　　指

2、導(dǎo)老師： </b></p><p>　　目   錄一.選題概述---------------------------------------3</p><p>　　設(shè)計(jì)要求與分析--------------------------------3</p><p>　　數(shù)據(jù)結(jié)構(gòu)與定義--------------------------

3、------4</p><p><b>　　1.結(jié)構(gòu)體定義</b></p><p><b>　　2.函數(shù)定義</b></p><p><b>　　3.函數(shù)之間的定義</b></p><p>　　程序段與分析----------------------------------5&

4、lt;/p><p>　　完整程序代碼及運(yùn)行結(jié)果截圖------------------7</p><p>　　心得體會(huì)--------------------------------------10</p><p>　　參考文獻(xiàn)--------------------------------------10</p><p><b>　　

5、一．選題概述：</b></p><p>　　在實(shí)際應(yīng)用中，有相當(dāng)一類問(wèn)題需要找出它的解集合，或者要求找出某些約束條件下的最優(yōu)解。求解時(shí)經(jīng)常使用一種稱為回溯的方法來(lái)解決。所謂回溯就是走回頭路，該方法是在一定的約束條件下試探地搜索前進(jìn)，若前進(jìn)中受阻，則回頭另?yè)裢防^續(xù)搜索。為了能夠沿著原路逆序回退，需用棧來(lái)保存曾經(jīng)到達(dá)的每一個(gè)狀態(tài)，棧頂?shù)臓顟B(tài)即為回退的第一站，因此回溯法均可利用棧來(lái)實(shí)現(xiàn)。而解決八皇后問(wèn)題就

6、是利用回溯法和棧來(lái)實(shí)現(xiàn)的。</p><p><b>　　二．設(shè)計(jì)要求與分析</b></p><p>　　八皇后問(wèn)題是在8x8的國(guó)際象棋棋盤上，安放8個(gè)皇后，要求沒(méi)有一個(gè)皇后能夠“吃掉”任何其他一個(gè)皇后，即沒(méi)有兩個(gè)或兩個(gè)以上的皇后占據(jù)棋盤上的同一行、同一列或同一條對(duì)角線。</p><p>　　八皇后在棋盤上分布的各種可能的格局，其數(shù)目非常大，約等

7、于232種，但是，可以將一些明顯不滿足問(wèn)題要求的格局排除掉。由于任意兩個(gè)皇后不能同行，即每一行只能放置一個(gè)皇后，因此將第i個(gè)皇后放置在第i行上。這樣在放置第i個(gè)皇后時(shí)，只要考慮它與前i一1個(gè)皇后處于不同列和不同對(duì)角線位置上即可。因此，其算法基本思想如下：</p><p>　　從第1行起逐行放置皇后，每放置一個(gè)皇后均需要依次對(duì)第1，2，…，8列進(jìn)行試探，并盡可能取小的列數(shù)。若當(dāng)前試探的列位置是安全的，即不與已放置的

8、其他皇后沖突，則將該行的列位置保存在棧中，然后繼續(xù)在下一行上尋找安全位置；若當(dāng)前試探的列位置不安全，則用下一列進(jìn)行試探，當(dāng)8列位置試探完畢都未找到安全位置時(shí)，就退?；厮莸缴弦恍校薷臈ｍ敱４娴幕屎笪恢?，然后繼續(xù)試探。</p><p>　　該算法抽象描述如下：</p><p>　?。?)置當(dāng)前行當(dāng)前列均為1;</p><p>　?。?）while(當(dāng)前行號(hào)《8)<

9、;/p><p>　?。?）｛檢查當(dāng)前行，從當(dāng)前列起逐列試探，尋找安全列號(hào)；</p><p>　?。?）if（找到安全列號(hào)）</p><p>　　（5）放置皇后，將列號(hào)記入棧中，并將下一行置成當(dāng)前行，第1列置為當(dāng)前列；</p><p><b>　?。?）else</b></p><p>　?。?）退?；?/p>

10、溯到上一行，移去該行已放置的皇后，以該皇后所在列的下一列作為</p><p><b>　　當(dāng)前列；</b></p><p><b>　?。?）｝結(jié)束程序。</b></p><p><b>　　數(shù)據(jù)結(jié)構(gòu)與定義</b></p><p><b>　　結(jié)構(gòu)體定義</b&

11、gt;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　int col[MaxSize]; //col[i]存放第i個(gè)皇后的列號(hào)</p><p>　　int top; //棧頂指針</p><p><b>　　}Typ

12、e;</b></p><p><b>　　2.函數(shù)定義</b></p><p>　　bool place(Type st,int i,int j) //測(cè)試(i,j)是否與1~i-1皇后有沖突 </p><p>　　void queen(int n) //求解皇后問(wèn)題</p><p>　　void ma

13、in() //主函數(shù)</p><p><b>　　函數(shù)之間的調(diào)用關(guān)系</b></p><p>　　main queen place</p><p><b>　　程序塊與分析</b></p><p>　　bool place(Type st,int i,int j)//測(cè)試

14、(i,j)是否與1~i-1皇后有沖突</p><p><b>　　{</b></p><p><b>　　int k=1;</b></p><p>　　if(i==1) return true;//存放第一個(gè)皇后時(shí)沒(méi)有沖突</p><p>　　while(k<=i-1)//j=1到k-1是已經(jīng)

15、放置了皇后的列</p><p><b>　　{</b></p><p>　　if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i)))</p><p>　　return false;</p><p><b>　　k++;</b></p><p

16、><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　?。╧，st.col[k]） （k，st.col[k]）</p><p>　　j-st.col[k]

17、 j-st.col[k] </p><p>　　(i,j) i-k i-k (i,j)</p><p>　　//測(cè)試(i,j)位置是否與已經(jīng)放好的第1個(gè)到第i~1皇后有沖突。已經(jīng)放置好的第1個(gè)到第1~i-1個(gè)皇后已放置在st棧中。St棧用

18、的是順序棧，棧頂指針從1開(kāi)始，st.col[k]用于存放第k（1<=i<=k-1）個(gè)皇后的列號(hào)，即皇后的位置是（k,st.col[k]）。對(duì)于（i，j）位置上的皇后與已經(jīng)放置的皇后（k，st.col[k]）發(fā)生沖突的情況時(shí)，則有：st.col[k]==j;對(duì)角線的沖突情況是：|j-st.col[k]|==|k-i|。</p><p>　　void queen(int n)//求解n皇后問(wèn)題</p

19、><p><b>　　{</b></p><p>　　int i,j,k;</p><p>　　bool find;</p><p>　　Type st;//定義棧st</p><p>　　st.top=0;//初始化棧頂指針</p><p>　　st.top++;//將(1,

20、1)放進(jìn)棧</p><p>　　st.col[st.top]=1;</p><p>　　while(st.top>0)//棧不空時(shí)循環(huán)</p><p><b>　　{</b></p><p>　　i=st.top;//當(dāng)前皇后為第i個(gè)皇后</p><p>　　if(st.top==n)//所

21、有皇后都放置好了，輸出一個(gè)解</p><p><b>　　{</b></p><p>　　printf("第%d個(gè)解：",++count);</p><p>　　for(k=1;k<=st.top;k++)</p><p>　　printf("(%d,%d)",k,st.co

22、l[k]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　find=false;</p><p>　　for(j=1;j<=n;j++)</p><p><b>　　{</b></

23、p><p>　　if(place(st,i+1,j))//在i+1行找到一個(gè)放置皇后的位置(i+1,j)</p><p><b>　　{</b></p><p><b>　　st.top++;</b></p><p>　　st.col[st.top]=j;</p><p>　　f

24、ind=true;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(find==false)//在i+1行找不到放皇后的位置，回溯</p><p>

25、;<b>　　{</b></p><p>　　while(st.top>0)</p><p><b>　　{</b></p><p>　　if(st.col[st.top]==n)//本行也沒(méi)有可放的位置，則退棧</p><p><b>　　st.top--;</b>&l

26、t;/p><p>　　for(j=st.col[st.top]+1;j<=n;j++)//在本行的下一個(gè)位置找</p><p>　　if(place(st,st.top,j))</p><p><b>　　{</b></p><p>　　st.col[st.top]=j;</p><p><

27、;b>　　break;</b></p><p><b>　　}</b></p><p>　　if(j>n)//當(dāng)前皇后在本行沒(méi)有可放的位置</p><p>　　st.top--;//退棧</p><p>　　else//本行找到一個(gè)位置后，推出回溯</p><p><

28、b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　vo

29、id main() //主函數(shù)</p><p><b>　　{</b></p><p><b>　　int n;</b></p><p>　　printf("請(qǐng)輸入皇后個(gè)數(shù)n=");</p><p>　　scanf("%d",&n);</p>

30、;<p>　　printf("%d皇后問(wèn)題求解如下:\n",n);</p><p><b>　　queen(n);</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　完整程序代碼及

31、運(yùn)行結(jié)果截圖</p><p>　　#include <stdio.h></p><p>　　#include <stdlib.h></p><p>　　#define MaxSize 100</p><p>　　typedef struct</p><p><b>　　{</b&

32、gt;</p><p>　　int col[MaxSize];//col[i]存放第i個(gè)皇后的列號(hào)</p><p>　　int top;//棧頂指針</p><p>　　}StType;//定義順序棧類型</p><p>　　int count=0;</p><p>　　bool place(StType st,int

33、 i,int j)//測(cè)試(i,j)是否與1~i-1皇后有沖突</p><p><b>　　{</b></p><p><b>　　int k=1;</b></p><p>　　if(i==1) return true;//存放第一個(gè)皇后時(shí)沒(méi)有沖突</p><p>　　while(k<=i-1

34、)//j=1到k-1是已經(jīng)放置了皇后的列</p><p><b>　　{</b></p><p>　　if((st.col[k]==j)||(abs(j-st.col[k])==abs(k-i)))</p><p>　　return false;</p><p><b>　　k++;</b><

35、/p><p><b>　　}</b></p><p>　　return true;</p><p><b>　　}</b></p><p>　　void queen(int n)//求解n皇后問(wèn)題</p><p><b>　　{</b></p>

36、<p>　　int i,j,k;</p><p>　　bool find;</p><p>　　StType st;//定義棧st</p><p>　　st.top=0;//初始化棧頂指針</p><p>　　st.top++;//將(1,1)放進(jìn)棧</p><p>　　st.col[st.top]=1;&

37、lt;/p><p>　　while(st.top>0)//棧不空時(shí)循環(huán)</p><p><b>　　{</b></p><p>　　i=st.top;//當(dāng)前皇后為第i個(gè)皇后</p><p>　　if(st.top==n)//所有皇后都放置好了，輸出一個(gè)解</p><p><b>　　

38、{</b></p><p>　　printf("第%d個(gè)解：",++count);</p><p>　　for(k=1;k<=st.top;k++)</p><p>　　printf("(%d,%d)",k,st.col[k]);</p><p>　　printf("\n&q

39、uot;);</p><p><b>　　}</b></p><p>　　find=false;</p><p>　　for(j=1;j<=n;j++)</p><p>　　if(place(st,i+1,j))//在i+1行找到一個(gè)放置皇后的位置(i+1,j)</p><p><b&

40、gt;　　{</b></p><p><b>　　st.top++;</b></p><p>　　st.col[st.top]=j;</p><p>　　find=true;</p><p><b>　　break;</b></p><p><b>　　

41、}</b></p><p>　　if(find==false)//在i+1行找不到放皇后的位置，回溯</p><p><b>　　{</b></p><p>　　while(st.top>0)</p><p><b>　　{</b></p><p>　　if

42、(st.col[st.top]==n)//本行也沒(méi)有可放的位置，則退棧</p><p><b>　　st.top--;</b></p><p>　　for(j=st.col[st.top]+1;j<=n;j++)//在本行的下一個(gè)位置找</p><p>　　if(place(st,st.top,j))</p><p&g

43、t;<b>　　{</b></p><p>　　st.col[st.top]=j;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if(j>n)//當(dāng)前皇后在本行沒(méi)有可放的位置</p><

44、p>　　st.top--;//退棧</p><p>　　else//本行找到一個(gè)位置后，推出回溯</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>&l

45、t;b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p><b>　　int n;</b></p><p>　　printf(&q

46、uot;請(qǐng)輸入皇后個(gè)數(shù)n=");</p><p>　　scanf("%d",&n);</p><p>　　printf("%d皇后問(wèn)題求解如下:\n",n);</p><p><b>　　queen(n);</b></p><p>　　printf("\

47、n");</p><p><b>　　}</b></p><p><b>　　心得體會(huì)</b></p><p>　　善于學(xué)習(xí)別人,多請(qǐng)教牛人,才會(huì)更快提高自己。有些問(wèn)題也許就是自己在某一點(diǎn)想不通，想法轉(zhuǎn)不過(guò)來(lái)，這就消耗了很多時(shí)間。而經(jīng)過(guò)牛人的點(diǎn)撥問(wèn)題就解決了，牛人們也會(huì)更直接，更清晰的教導(dǎo)一些技術(shù)，通過(guò)向他們學(xué)習(xí)

48、，才會(huì)更快的提高自己的技能。</p><p>　　多找一些題目來(lái)練習(xí)，多敲代碼，才會(huì)更有感覺(jué)。在練習(xí)的過(guò)程中找出規(guī)則，形成編程思想。</p><p>　　小組合作形成共同進(jìn)步。小組成員的討論過(guò)程中，將各自的想法提出來(lái)，分析優(yōu)缺點(diǎn)，這過(guò)程中每個(gè)成員也可以學(xué)習(xí)到其他成員的解題思想，也可以審視自己的解題思想，獲得提升。</p><p><b>　　參考文獻(xiàn)<