數(shù)據(jù)結(jié)構(gòu)與算法課程設計--騎士游歷

1、<p><b>　　計算機科學與技術系</b></p><p><b>　　課程設計報告</b></p><p>　　2011 ～2012 學年第 二 學期</p><p>　　2012 年6 月10 日</p><p><b>　　題目：</b></p>

2、;<p><b>　　名稱：騎士游歷</b></p><p>　　內(nèi)容：給你一個8*8的棋盤,騎士的開始位置,結(jié)束位置,讓你求得騎士從開始位置開始走到結(jié)束位置需要最小的步數(shù)是多少？（注意,騎士走日字）</p><p><b>　　要求：</b></p><p>　?。?）輸入：輸入包含多組數(shù)據(jù)，每一行都是一組

3、開始位置和結(jié)束位置,位置由兩個字符組成,一個是小寫字母(a-h),一個是數(shù)字(1-8),起始位置結(jié)束位置由一個空格隔開.</p><p>　　（2）輸出：輸出從起始位置到結(jié)束位置,騎士所要走過的最小的步數(shù).</p><p>　?。?）所設計的數(shù)據(jù)結(jié)構(gòu)應盡可能節(jié)省存儲空間。</p><p>　?。?）程序的運行時間應盡可能少。</p><p>

4、<b>　　問題分析和任務定義</b></p><p>　　此程序需要完成如下要求：給你一個8*8的棋盤,騎士的開始位置,結(jié)束位置,讓你求得騎士從開始位置開始走到結(jié)束位置需要最小的步數(shù)是多少？（注意,騎士走日字）</p><p>　　實現(xiàn)本程序需要解決以下幾個問題：</p><p>　　如何表示8*8的棋盤，確定棋盤上各點的位置。</p&

5、gt;<p>　　馬在棋盤上的各種行走方法怎樣來表示，行走過程如何實現(xiàn)。</p><p>　　如何表示位置由兩個字符組成,一個是小寫字母(a-h),一個是數(shù)字(1-8)。</p><p>　　如何找到一條滿足條件的路徑。</p><p>　　如何確定這條路徑是最短的。</p><p>　　本問題的關鍵和難點是如何根據(jù)騎士的走法規(guī)

6、則，找出一條最短路徑。</p><p><b>　　圖1:8*8的棋盤</b></p><p>　　如圖，建立如上的坐標系，于是每個點的位置就可以用一個有序數(shù)對來表示。如：（a,3）,（b,6）,（h,2）。</p><p>　　對于任意一點的馬最多有8中走法可以選擇。根據(jù)馬行走后行列坐標數(shù)值大小的增加和減少情況的變化，用有序數(shù)組對來表示其走法

7、。</p><p>　　static int bx[8] = {2,1,-1,-2,-2,-1,1,2};</p><p>　　static int by[8] = {1,2,2,1,-1,-2,-2,-1};</p><p>　　其中，bx數(shù)組與by數(shù)組下標相同的變量表示一種走法。</p><p>　　騎士在棋盤中的位置可由結(jié)構(gòu)體類型<

8、;/p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　int n,m; //n 記錄行數(shù)，m 記錄列數(shù)</p><p><b>　　int ch;</b></p><p><b>　　}node; <

9、/b></p><p><b>　　來表示。</b></p><p>　　對于騎士的起始與終點位置可由有序?qū)?x0,y0),(x1,y1)來表示。</p><p><b>　　另外建立一個隊列，</b></p><p>　　typedef struct //定義順序隊

10、列類型</p><p><b>　　{</b></p><p>　　node data[maxlen];</p><p>　　int front;</p><p><b>　　int rear;</b></p><p>　　}Sequeue; </p>&l

11、t;p>　　把騎士從起點到終點的每一步入隊，前一步出對。</p><p>　　概要設計與數(shù)據(jù)結(jié)構(gòu)選擇</p><p>　　對于所提出的關鍵問題，即找出從起點到終點的最短步數(shù)，這里所用到的方法是遍歷起點與終點的所有路徑，記錄下其步數(shù)，然后比較其中最小的步數(shù)，即為最短步數(shù)。</p><p>　　輸入起點和終點的坐標，起點先入對；</p><p&

12、gt;　　按照上述的8走法分別走一步，如果到達終點，計步器加一，如果未到終點，計步器加一并入對；（所有走法均入隊）</p><p>　　出對，以步驟2中的如對順序分別把其作為新起點，重復步驟2；</p><p>　　判斷是否對空，對空則以走過全部路徑，對未空，重復步驟3；對空，轉(zhuǎn)到步驟5；</p><p>　　比較每種路徑的步數(shù)，選出最小的數(shù)值，即為最小步數(shù)。<

13、;/p><p>　　以上操作相當于對于一棵8個結(jié)點的完全樹進行遍歷，查找滿足條件的結(jié)點，并找出這些結(jié)點中結(jié)點高度最低的結(jié)點。 </p><p>　　以上過程可由樹來表示。樹如圖2：</p><p><b>　　…… ……</b></p><p>　　…… …… …… ……

14、 ……</p><p>　　…… …… …… …… …… ……</p><p>　　圖2：騎士游歷的樹結(jié)構(gòu)</p><p>　　如圖3，先找到起點，即根節(jié)點，并進行入隊操作。由起點逐次訪問起點的各個子樹的根節(jié)點，比較是否等于終點的坐標，若相等，則保存路徑長度；若不相等，則把不相等

15、的子樹的根節(jié)點進行入隊操作。訪問完所有子樹的根節(jié)點后，進行一次出隊操作；即把根節(jié)點出隊。此后順次訪問隊頭節(jié)點的子樹的根節(jié)點，即順次訪問根節(jié)點的子樹的根節(jié)點的各個子樹的根節(jié)點，比較是否等于終點的坐標，若相等，則保存路徑長度；若不相等，則把不相等的子樹的根節(jié)點進行入隊操作。直到隊為空為止。</p><p><b>　　訪問順序如下：</b></p><p>　　…

16、 …… …</p><p><b>　　…</b></p><p>　　圖3：游歷的訪問順序</p><p><b>　　數(shù)據(jù)結(jié)構(gòu)如下：</b></p><p>　　typedef struct //騎士位置結(jié)構(gòu)體</p><p>&

17、lt;b>　　{</b></p><p>　　int n,m; //n 記錄行數(shù)，m 記錄列數(shù)</p><p><b>　　int ch;</b></p><p><b>　　}node;</b></p><p>　　typedef struct //

18、順序隊列類型結(jié)構(gòu)體</p><p><b>　　{</b></p><p>　　node data[maxlen];</p><p>　　int front;</p><p><b>　　int rear;</b></p><p><b>　　}Sequeue;&l

19、t;/b></p><p>　　圖4：詳細設計流程圖</p><p><b>　　詳細設計和編碼</b></p><p>　　首先，對于在問題分析和任務定義中所提出的問題逐個進行解決。</p><p>　　定義棋盤和走法，并對其進行初始化。</p><p>　　int way[8][8] 表

20、示棋盤每一點的位置，例如，way[2][2]表示第三行，第三列的坐標，way[3][6]表示第四行，第七列的坐標。因為在本實驗中并沒有要求騎士行走的路徑，所以棋盤可不顯示的定義。</p><p>　　對于走法，我們前面已經(jīng)提到了，對于馬在棋盤中的任意位置，最多有8種走法，用有序數(shù)對表示即：(2,1),(2,-1)(1,2),(1.-2)(-2,1),(-2,-1),(-1,2),(-1,-2)。故，我們可以做如下

21、定義：</p><p>　　根據(jù)馬行走后行列坐標數(shù)值大小的增加和減少情況的變化，用有序數(shù)組對來表示其走法。</p><p>　　static int bx[8] = {2,1,-1,-2,-2,-1,1,2};</p><p>　　static int by[8] = {1,2,2,1,-1,-2,-2,-1};</p><p>　　其中，b

22、x數(shù)組與by數(shù)組下標相同的變量表示一種走法。所以在騎士的行走過程中，只要讓騎士的位置即坐標加上或減去上述8中走法的數(shù)組表示。</p><p>　　對于騎士的起點和終點的位置表示，根據(jù)要求位置由兩個字符組成,一個是小寫字母(a-h),一個是數(shù)字(1-8)。所以有如下的表示方法：</p><p>　　int x0,y0,x1,y1; char xa，xb；x0=xa-‘a(chǎn)’; x1=xb-

23、‘a(chǎn)’;</p><p>　　其中，x0、y0表示起點坐標，x1、y1表示終點坐標，輸入的xa，xb為字符，減去‘a(chǎn)’，便可轉(zhuǎn)換成數(shù)字。這樣便可以把輸入的字符坐標轉(zhuǎn)換成用數(shù)字表示的坐標。</p><p>　　在得到騎士的起點終點坐標之后，便可以把起點入隊，入隊函數(shù)如下所示：</p><p>　　void add(Sequeue *S,int x,int y,int

24、z) //入隊函數(shù)</p><p><b>　　{</b></p><p>　　if(S->rear<maxlen-1 && S->rear>=0)</p><p><b>　　{</b></p><p>　　S->rear++;</p&g

25、t;<p>　　S->data[S->rear].n=x;</p><p>　　S->data[S->rear].m=y;</p><p>　　S->data[S->rear].ch=z;</p><p><b>　　}</b></p><p>　　else pri

26、ntf("error\n");</p><p><b>　　}</b></p><p>　　這里的參數(shù)x，y，z分別表示行坐標，列坐標，和到達該坐標從起點所走的步數(shù)。它們的值分別保存在隊列的n，m，ch中。</p><p>　　在對起點進行入隊之后，便可進行運動了，即騎士可以按規(guī)則(8種走法)走向下一位置。</p>

27、;<p>　　此后，在一個while循環(huán)中進行如下的操作，while循環(huán)的條件為：S->front<S->rear，保證在隊列不為空的情況下進行循環(huán)。</p><p>　　對于騎士的8種走法，可以通過for(i=0;i<8;i++)循環(huán)進行逐個試探。這里可以定義兩個證型變量x3、y3；用以存放騎士走一步后的位置，即坐標。則有如下定義：</p><p>

28、　　x3=bx[i]+x0; y3=by[i]+y0;</p><p>　　又由實際情況可知，x3、y3應該滿足x3、y3同時大于等于0且小于8；在此時設置標記數(shù)組step[maxlen][maxlen]=0;標記數(shù)組用以標記該位置是否已經(jīng)走過，走過則置1；所以x3、y3還應滿足step[x3][y3]==0;即(x3,y3)這個位置還未走過。若滿足以上條件，則可以定義node *p；并為其申請內(nèi)存空間。有如下一

29、段程序：</p><p>　　p=(node *)malloc(sizeof(node));</p><p>　　p->ch=S->data[S->front+1].ch+1;</p><p><b>　　p->n=x3;</b></p><p><b>　　p->m=y3;<

30、;/b></p><p>　　step[x3][y3]=1;</p><p>　　把(x3,y3)的值放入指針p指向的空間的（n，m）中，用以保存此位置；因為ch存放的是從起點到該位置所走的步數(shù)，故p->ch=S->data[S->front+1].ch+1;即它表示的意思是從起點x3、y3所走的步數(shù)。此時并把x3y3的標記置為1，說明此位置已經(jīng)被訪問過了。這時便可

31、以對x3、y3進行判斷了。</p><p>　　若p->n==x1 && p->m==y1，即比較x3、y3與終點的坐標是否相同。若相同則找到一種走法。此時定義 int a=0；int count[maxlen]; count[a]數(shù)組的作用就是記錄下每一種走法的步數(shù)；令count[a]=p->ch即可。若不滿足條件的話則把x3、y3入隊；</p><p&

32、gt;　　然后i++；重復上述操作，直到i不滿足條件為止，即已經(jīng)走完了8種走法；</p><p>　　此后，進行出棧操作；判斷S->front與S->rear的大小關系，若S->front>S->rear,則進行while循環(huán)，若不滿足，則跳出while循環(huán)。</p><p>　　最后，對計數(shù)數(shù)組count[a]中的值進行比較，找出最小值，即為，從終點到起點的

33、最小步數(shù)。程序如下：</p><p><b>　　int min;</b></p><p>　　min=count[0];</p><p>　　for(i=1;i<a;i++)</p><p><b>　　{</b></p><p>　　if(min>count[

34、i])</p><p>　　min=count[i];</p><p><b>　　}</b></p><p>　　printf("最短步數(shù)為: %d\n",min);</p><p><b>　　上機調(diào)試</b></p><p>　　1、語法錯誤及修正

35、：</p><p>　　本程序使用了循環(huán)思想和隊列的數(shù)據(jù)結(jié)構(gòu)，所以程序出現(xiàn)的語法錯誤主要在于隊列函數(shù)的調(diào)用及變量的定義，關鍵字和函數(shù)名稱的書寫，以及一些庫函數(shù)的規(guī)范使用。這些問題均可以根據(jù)編譯器的警告提示，對應的將其解決。</p><p>　　邏輯問題的修改和調(diào)整：</p><p>　　循環(huán)思想的使用雖然簡化了程序，但是增加了對函數(shù)循環(huán)控制的難度。在while循環(huán)中

36、，要實現(xiàn)對所有路徑的查找，而不能丟掉一條，也許丟掉的便是我們所需要的，這樣便造成了錯誤。又因為我們對路徑的查找使用了隊列的數(shù)據(jù)結(jié)構(gòu)，即對坐標進行了入隊和出對的操作。所以我們可以用對空的條件作為while循環(huán)的終止條件。這樣便可以無遺漏的查找起點到終點的所有路徑。</p><p>　　還有一點容易出現(xiàn)邏輯錯誤的是在何時進行入隊和出對的操作。對入隊的操作而言，在每一次行走后對于不滿足條件的坐標均要進行入隊操作。而對于

37、出對而言，每次出隊操作均在對每一步的八種走法走完之后才進行，這樣便可以保證路徑查找沒有遺漏。</p><p>　　時間，空間性能分析: </p><p>　　因為本算法需要用一個二維數(shù)組保存每一個位置的訪問狀態(tài)，也需要一個一維數(shù)組保存訪問到的滿足條件的步數(shù)，故其空間復雜度較高，會占據(jù)較大的內(nèi)存空間，其空間復雜度為O(maxlen*maxlen)。但是對于本算法而言，空間復雜度不但很高，時間

38、復雜度也很大。由于本算法將對路徑的遍歷轉(zhuǎn)變成了對樹的遍歷，需要遍歷所有的路徑并保存，從中找出滿足條件的路徑。所以無論起點和終點的位置如何，都需要進行所有的查找過程，所以對于本算法而言，時間復雜度很大，為O(8^n*n)。由此可得，本算法的時間空間性能較差，由于知識的局限性，故本人無法對此算法進行優(yōu)化。</p><p><b>　　4、經(jīng)驗和體會：</b></p><p&g

39、t;　　在剛拿到此問題時，感覺無從下手，但是經(jīng)過仔細的分析，了解到，對騎士路徑的查找，對八子樹的樹的遍歷算法很相像，不過要對每次遍歷的結(jié)果進行判斷，從而找出滿足條件的結(jié)果。因此在具體解決問題時采用了樹的數(shù)據(jù)結(jié)構(gòu)思想，再經(jīng)過完善和修改得出算法，并用程序語言實現(xiàn)。從這個過程中我了解到對問題從認識到建立模型，之后提出方法，修改方法，最終解決問題的過程。也使我體會到對于具體問題的解決，只要按照解決問題的過程，就不會出現(xiàn)盲目的情況。</p&

40、gt;<p><b>　　用戶使用說明</b></p><p>　　本程序運行時帶有提示性語句。開始時，程序會提示你輸入騎士游歷的起終點，輸入格式為每一行都是一組開始位置和結(jié)束位置,位置由兩個字符組成,一個是小寫字母(a-h),一個是數(shù)字(0-7),起始位置結(jié)束位置由一個空格隔開。故輸入的坐標橫坐標的取值范圍在（a-h）之間，縱坐標的取值范圍在（0-7）之間，輸入起終點位置后，

41、按回車，程序會給出從起點到終點的最短步數(shù)的值。之后，程序會提示你是否繼續(xù)輸入，輸入’y’表示繼續(xù)輸入，輸入‘n’表示不再進行輸入，即退出程序。這樣便可以手動的控制輸入的次數(shù)。方便查詢。</p><p><b>　　測試結(jié)果</b></p><p><b>　　圖五：運行結(jié)果</b></p><p><b>　　附

42、錄</b></p><p>　　#include"stdio.h"</p><p>　　#include "stdlib.h"</p><p>　　#define maxlen 100</p><p>　　int length=0; //記錄所走的步數(shù)</p><p

43、>　　static int bx[8] = {2,1,-1,-2,-2,-1,1,2};</p><p>　　static int by[8] = {1,2,2,1,-1,-2,-2,-1};</p><p>　　typedef struct </p><p><b>　　{</b></p><p>　　int n

44、,m; //n 記錄行數(shù)，m 記錄列數(shù)</p><p><b>　　int ch;</b></p><p><b>　　}node;</b></p><p>　　typedef struct //定義順序隊列類型</p><p><b>　　{</b&g

45、t;</p><p>　　node data[maxlen];</p><p>　　int front;</p><p><b>　　int rear;</b></p><p><b>　　}Sequeue;</b></p><p>　　Sequeue *setqueue()

46、</p><p><b>　　{</b></p><p>　　Sequeue *S;</p><p>　　S=(Sequeue *)malloc(sizeof(Sequeue));</p><p>　　S->front=0;</p><p>　　S->rear=0;</p>

47、<p><b>　　return S;</b></p><p><b>　　}</b></p><p>　　void add(Sequeue *S,int x,int y,int z) //入隊函數(shù)</p><p><b>　　{</b></p><p>

48、　　if(S->rear<maxlen-1 && S->rear>=0)</p><p><b>　　{</b></p><p>　　S->rear++;</p><p>　　S->data[S->rear].n=x;</p><p>　　S->data[S

49、->rear].m=y;</p><p>　　S->data[S->rear].ch=z;</p><p><b>　　}</b></p><p>　　else printf("error\n");</p><p><b>　　}</b></p>

50、;<p>　　void dele(Sequeue *s) //出隊函數(shù)</p><p><b>　　{</b></p><p>　　if(s->front<s->rear)</p><p>　　s->front++;</p><p><b>　　else</b

51、></p><p>　　printf("error\n");</p><p><b>　　}</b></p><p>　　void judge() //判斷步數(shù) </p><p><b>　　{</b></p><p>　　Seque

52、ue *S;</p><p>　　S=setqueue();</p><p>　　int x0,y0,x1,y1,x3,y3,i,j; int count[maxlen+100];int a=0; int step[maxlen][maxlen];</p><p>　　char xa,xb;</p><p>　　for( i=0;i<

53、maxlen;i++)</p><p><b>　　{</b></p><p>　　S->data[i].ch=0;</p><p><b>　　}</b></p><p>　　printf("請輸入騎士游歷的起終點：\n");</p><p>　　

54、scanf(" %c,%d %c,%d",&xa,&y0,&xb,&y1);</p><p>　　x0=xa-'a';</p><p>　　x1=xb-'a';</p><p>　　for( i=0;i<maxlen;i++)</p><p>　　for

55、( j=0;j<maxlen;j++)</p><p><b>　　{</b></p><p>　　step[i][j]=0;</p><p><b>　　}</b></p><p>　　step[x0][y0]=1;</p><p>　　add(S,x0,y0,0);

56、</p><p>　　while(S->front<S->rear)</p><p><b>　　{</b></p><p><b>　　node *p;</b></p><p>　　x0=S->data[S->front+1].n;</p><p&

57、gt;　　y0=S->data[S->front+1].m;</p><p>　　for(int i=0;i<8;i++)</p><p><b>　　{</b></p><p>　　x3=bx[i]+x0;</p><p>　　y3=by[i]+y0;</p><p>　　if

58、(x3>=0 && x3<8 && y3>=0 && y3<8 && step[x3][y3]==0)</p><p><b>　　{</b></p><p>　　p=(node *)malloc(sizeof(node));</p><p>　　p->

59、;ch=S->data[S->front+1].ch+1;</p><p><b>　　p->n=x3;</b></p><p><b>　　p->m=y3;</b></p><p>　　step[x3][y3]=1;</p><p>　　if(p->n==x1 &am

60、p;& p->m==y1)</p><p><b>　　{</b></p><p>　　step[x1][y1]=0;</p><p>　　count[a]=p->ch;</p><p><b>　　a++;</b></p><p><b>　　

61、}</b></p><p><b>　　else</b></p><p>　　add(S,p->n,p->m,p->ch);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>&

62、lt;b>　　dele(S);</b></p><p><b>　　}</b></p><p><b>　　int min;</b></p><p>　　min=count[0];</p><p>　　for(i=1;i<a;i++)</p><p>

63、　　if(min>count[i])</p><p>　　min=count[i];</p><p>　　printf("最短步數(shù)為: %d\n",min);</p><p><b>　　}</b></p><p>　　void main()</p><p><b

64、>　　{</b></p><p><b>　　char nn;</b></p><p><b>　　nn='y';</b></p><p>　　while(nn=='y')</p><p><b>　　{</b></p&g

65、t;<p><b>　　judge();</b></p><p>　　printf("是否繼續(xù)輸入？('y'是,'n'否)\n");</p><p>　　scanf(" %c",&nn);</p><p><b>　　}</b>&