數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)報(bào)告

數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)報(bào)目錄一、

問題描述及程序功能2

總體設(shè)計(jì)

2算法詳細(xì)設(shè)計(jì)3四、程序測(cè)試及結(jié)果分析

6復(fù)雜度分析7

不足

7小結(jié)7

附錄8

一.問題描述及程序功能八皇后問題是一個(gè)古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出的，并做了部分解答，高斯在棋盤上放下了八個(gè)互不攻擊的皇后，他還認(rèn)為可能有76種不同的放法，這就是有名的“八皇后”問題。

在國際象棋中，皇后是最有權(quán)利的一個(gè)棋子；只要?jiǎng)e的棋子在它的同一行或同一列或同一斜線（正斜線或反斜線）上時(shí)，它就能把對(duì)方棋子吃掉。所以高斯提出了一個(gè)問題：在8*8的格的國際象棋上擺放八個(gè)皇后，使其不能相互攻擊，即任意兩個(gè)皇后都不能處于同一列、同一行、或同一條斜線上面，問共有多少種解法?，F(xiàn)在我們已經(jīng)知道八皇后問題有92個(gè)解答。

二、總體設(shè)計(jì)先對(duì)八皇后問題進(jìn)行研究，探尋它們之間的位置關(guān)系，得知共有92組正解，然后根據(jù)這些解的個(gè)數(shù)及關(guān)系并且運(yùn)用數(shù)據(jù)結(jié)構(gòu)的知識(shí)內(nèi)容進(jìn)行代碼的編寫、調(diào)試、運(yùn)行，最后得出滿意的代碼程序。如果在設(shè)計(jì)遞歸程序的話，回溯法是很重要的一種方法，回溯法的應(yīng)用：

回溯法也是設(shè)計(jì)遞歸過程的一種重要方法，原理或步驟為：試著先把第一個(gè)皇后放在棋盤上，然后再放第二個(gè)，使兩個(gè)皇后不會(huì)互相攻擊，再放第三個(gè)皇后，使得她與前面兩個(gè)皇后都不會(huì)互相攻擊，依此類推，直至所有的皇后都放上去。如果第七個(gè)皇后放上后，第八個(gè)皇后已經(jīng)沒有安全的位置可以放置，則試著調(diào)試第七個(gè)皇后的位置，再嘗試第八個(gè)皇后有沒有安全的位置；如果第七個(gè)皇后的所有安全位置都已嘗試過了，第八個(gè)皇后還是沒有安全的位置，則試著調(diào)試第六個(gè)皇后的位置，重新放置第七、八個(gè)皇后的嘗試。如此類推，最糟糕的事情就是一直到將第一個(gè)皇后的位置進(jìn)行調(diào)整。本次的數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)主要運(yùn)用非遞歸算法，進(jìn)行一次挑戰(zhàn)。設(shè)計(jì)要求界面友好，函數(shù)功能要?jiǎng)澐趾?總體設(shè)計(jì)應(yīng)畫一流程圖,程序要加必要的注釋要提供程序測(cè)試方案,程序一定要經(jīng)得起測(cè)試，寧可功能少一些，也要能運(yùn)行起來，不能運(yùn)行的程序是沒有價(jià)值的。算法詳細(xì)設(shè)計(jì)在本次編碼的最初，本來應(yīng)用的回溯遞歸的算法，那種方法相對(duì)于非遞歸算法要簡(jiǎn)單方便許多，程序也會(huì)更易理解。比如在一些函數(shù)及接結(jié)構(gòu)體的定義中會(huì)更直接鮮明，也更有利于我們學(xué)習(xí)運(yùn)用數(shù)據(jù)結(jié)構(gòu)這門課程，如在編的一回溯遞歸發(fā)的代碼中，有一開頭：intCount=0;//計(jì)算總共解的數(shù)量intcolumn[N+1];//column[m]=n表示第m行，第n行放置了皇后，這里下標(biāo)并從0開始introw[N+1];//row[m]=1表示第m行沒有皇后，=0表示有皇后intb[2*N+1];//b[m]=1表示第m條主對(duì)角線沒有皇后intc[2*N+1];//c[m]=1表示第m條次對(duì)角線沒有皇后，=0表示有皇后intnumQueen=1;//計(jì)數(shù)已經(jīng)放置的皇后數(shù)目，當(dāng)numQueen=N時(shí)候則表示已經(jīng)完成探測(cè)intgood=1;//good表示沒有發(fā)生沖突，good=0表示發(fā)生沖突這段代碼雖然定義了許多個(gè)數(shù)組及函數(shù)，但對(duì)于我們的理解運(yùn)用是很有幫助的，不過，由于自己選的課程設(shè)計(jì)是非遞歸的。所以我也進(jìn)自己最大的努力去編了一個(gè)程序，雖然有些復(fù)雜，但終究還是可以實(shí)現(xiàn)了。本次課程設(shè)計(jì)中，用到的主要知識(shí)有：多層循環(huán)方法、回溯法的應(yīng)用,for語句的靈活運(yùn)用，數(shù)據(jù)結(jié)構(gòu)中樹知識(shí)的靈活運(yùn)用、棧及數(shù)組的掌握.

a.采用C語言定義相關(guān)的數(shù)據(jù)類型s[t]八皇后的擺放位置；num解的個(gè)數(shù)；p()主函數(shù)；b.各模塊的C代碼算法主函數(shù)的代碼：voidp()//定義主函數(shù){intf=0;//輸入皇后所在的行num++;//解的個(gè)數(shù)累加printf("第%d種",num);//輸出第num種解for(f=0;f<N;f++){printf("%d",s[f]);//輸出正解的情況，s[f]}printf("\n");//空行}intcheck(intt,inti)//判斷皇后位置是否合理//{inta=0;for(a=0;a<t;a++){if(s[t-1-a]==i-1-a)//判斷是否有皇后在同一行{return0;}}for(a=0;a<t;a++){if(s[t-a-1]==i)//判斷皇后是否有在同一列{return0;}}for(a=0;a<N-i-1;a++){if(s[t-1-a]==i+1+a)//判斷皇后是否在同一斜線上{return0;}}return1;}檢驗(yàn)是否符合的解的代碼：check(intt,inti)intcheck(intt,inti)//判斷是否合理//{inta=0;for(a=0;a<t;a++){if(s[t-1-a]==i-1-a)//判斷皇后是否在同一行{return0;}}for(a=0;a<t;a++){if(s[t-a-1]==i)//判斷皇后是否在同一列{return0;}}for(a=0;a<N-i-1;a++){if(s[t-1-a]==i+1+a)//判斷皇后是否在同一斜線上{return0;}}return1;}c主要函數(shù)的流程圖主要函數(shù)流程圖(見附錄)四、程序測(cè)試及結(jié)果分析程序測(cè)試結(jié)果在程序測(cè)試過程中，調(diào)試的時(shí)候沒有錯(cuò)誤，但在運(yùn)行測(cè)試時(shí)的結(jié)果卻與實(shí)際答案不符，在經(jīng)過程序檢查調(diào)試之后，才發(fā)現(xiàn)代碼有個(gè)地方不對(duì)，經(jīng)過修改，才得到了正確的代碼。測(cè)試結(jié)果如下：2、結(jié)果分析雖然在這之前我們已經(jīng)學(xué)了C語言，也做過課程設(shè)計(jì)，但在編寫程序的時(shí)候，還是出現(xiàn)了許多問題，比如在編寫程序的時(shí)候，由于沒有太注意語言的切換就使用了符號(hào)，使程序在調(diào)試的時(shí)候出現(xiàn)了許多問題，經(jīng)過多次的調(diào)試，才完成了這個(gè)沒有錯(cuò)誤的程序代碼；還有在程序沒有錯(cuò)誤后，運(yùn)行結(jié)果卻又出現(xiàn)了問題，使結(jié)果運(yùn)行出來與已知答案不符，很是糾結(jié)，在算法的再三核對(duì)下，終于找到了問題，只因?yàn)橐粋€(gè)“-”的原因，也讓我知道了C語言算法的嚴(yán)密。。五、復(fù)雜度分析該算法的運(yùn)行時(shí)間和和皇后的放置方法成正比，在最好情況下的時(shí)間和空間復(fù)雜度均為O（1），在最差情況下均為O（n*n），平均情況在它們之間。

不足

遇到的問題及解決方法

(1)．由于對(duì)八個(gè)皇后放置的位置不能一次確定，而且前一個(gè)皇后的放置位置直接影響著后面的放置位置，使程序調(diào)試時(shí)要花費(fèi)不少時(shí)間。

(2)．本程序有些代碼重復(fù)出現(xiàn)，顯得程序的有些代碼看起來很雜亂。但其中最主要的問題是邏輯錯(cuò)誤導(dǎo)致程序死循環(huán)或不循環(huán)或循環(huán)一小部分,但是編譯時(shí)卻沒有錯(cuò)誤,就是沒有正確的輸出答案。(3).由于運(yùn)用的是非遞歸方式，代碼復(fù)雜凌亂，相對(duì)于遞歸回溯的方法來講無論時(shí)間還是空間復(fù)雜度都要差。(4).

這里在編寫回溯算法時(shí)候需要特別注意以下幾點(diǎn)：?

回溯循環(huán)的結(jié)束在于第一個(gè)皇后被回溯。

?

當(dāng)找到一個(gè)解時(shí)，需要復(fù)制整個(gè)棋盤，不然接下來的回溯將破壞已經(jīng)找到的解。

?

找到一個(gè)解后，需要在當(dāng)前皇后的基礎(chǔ)上回溯。?

回溯一個(gè)皇后時(shí)，要對(duì)當(dāng)前的列數(shù)進(jìn)行重置。小結(jié)從這個(gè)八皇后問題設(shè)計(jì)以及分析中，本人從中理解到了數(shù)據(jù)結(jié)構(gòu)對(duì)于軟件設(shè)計(jì)的重要性，它的使用，可以改變軟件的運(yùn)行周期，思路從繁化簡(jiǎn)，并且都

能夠通過其相關(guān)引導(dǎo)，將本身以前編程思想進(jìn)行擴(kuò)充，發(fā)展.這也是在這次課程設(shè)計(jì)中我所掌握得到的。

但在這次的課設(shè)中也遇了一些問題，如，八皇后在變成初期由于沒真正體會(huì)到“樹”在里面的運(yùn)用,不自覺的采用了非遞歸的算法，結(jié)果大大增加了程序的復(fù)雜程度。并且也讓整個(gè)程序的時(shí)間復(fù)雜度變得更大；在重溫了樹的回溯，以及二叉樹的遍歷后，最終將程序進(jìn)行了一次較大的改造。并且通過思考，再將以前的數(shù)組知識(shí)加以運(yùn)用才最終解決了這個(gè)問題，整個(gè)程序的算法的可看性也有了較大的改進(jìn)。

在本次課程設(shè)計(jì)的學(xué)習(xí)過程中,我在其中的最大的收獲,就是得到了許多的經(jīng)驗(yàn)以及軟件設(shè)計(jì)的一些新的思路.

邁著時(shí)間的步伐，這次的課程設(shè)計(jì)也即將結(jié)束，但這個(gè)學(xué)期數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)還是具有相當(dāng)大的意義，特別是這次的課程設(shè)計(jì),它從一個(gè)程度上改變了我們的編程思想，如何將一個(gè)程序快速而又準(zhǔn)備的進(jìn)行編寫，進(jìn)行編譯，都成為了我思考的重點(diǎn)，也通過上一個(gè)學(xué)期的學(xué)習(xí)，我們將數(shù)據(jù)結(jié)構(gòu)的思想帶入到了我們以后的編程學(xué)習(xí)中去。在這個(gè)階段，我也明白了，好的思想，不能提留于字面上的認(rèn)知，還需要的是平時(shí)多練多寫一些相關(guān)的程序，并且通過修改，加入新的算法去嘗試改變自己的一些編程思想。保持更新算法的速度，這才是關(guān)鍵。

八、附錄程序源代碼：#include<windows.h>#include<stdio.h>#include<stdlib.h>#defineN8/*定義主函數(shù)*/ints[8];//輸入皇后數(shù)intnum=0;//初始化解的個(gè)數(shù)num=0voidp()//定義主函數(shù){intf=0;//輸入皇后所在的行num++;//解的個(gè)數(shù)累加printf("第%d種",num);//輸出第num種解for(f=0;f<N;f++){printf("%d",s[f]);//輸出正解的情況，s[f]}printf("\n");//空行}intcheck(intt,inti)//判斷皇后位置是否合理//{inta=0;for(a=0;a<t;a++){if(s[t-1-a]==i-1-a)//判斷是否有皇后在同一行{return0;}}for(a=0;a<t;a++){if(s[t-a-1]==i)//判斷皇后是否有在同一列{return0;}}for(a=0;a<N-i-1;a++){if(s[t-1-a]==i+1+a)//判斷皇后是否在同一斜線上{return0;}}return1;}intmain(intargc,char*argv[]){intt=0;inti=0;while(t!=-1){if(check(t,s[t])==1){t++;if(t==N){p();//調(diào)用主函數(shù)//t--;while(s[t]>=N-1)//當(dāng)皇后數(shù)小于8時(shí)，繼續(xù)向下