數(shù)據(jù)結(jié)構(gòu)與算法_馬踏棋盤

1、合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告20122013 學(xué)年第 2 學(xué)期課程課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)名稱課程設(shè)計(jì)名稱馬踏棋盤學(xué)生姓名學(xué)生姓名學(xué)號(hào)學(xué)號(hào)專業(yè)班級(jí)專業(yè)班級(jí)指導(dǎo)教師指導(dǎo)教師2013 年 6 月計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 1 -目目 錄錄數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告馬踏棋盤.- 2 -問題描述.- 2 -1、問題分析與定義.- 2 -2、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì).- 3 -數(shù)據(jù)結(jié)構(gòu)的選擇 .- 3 -概要設(shè)計(jì) .- 3 -3、詳細(xì)設(shè)計(jì)和編碼.- 4 -4、上機(jī)調(diào)試過程.- 6 -5、測試結(jié)果及分析.- 7 -6、用戶使用說明.- 9 -7、參考文獻(xiàn).- 9 -附錄源程序.- 10 -計(jì)科系

2、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 2 -數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告馬踏棋盤馬踏棋盤題目：題目：【問題描述】設(shè)計(jì)一個(gè)國際象棋的馬踏遍棋盤的演示程序。要求：將馬隨機(jī)放在國際象棋的 88 棋盤 Board88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部 64 個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字 1，2，64 依次填入一個(gè) 88 的方陣，輸出之。1 1、問題分析與定義、問題分析與定義走棋規(guī)則：馬走 32 格對(duì)角線，簡單的說就是走 L 形棋盤如圖所示，將馬放在棋盤中的任意一個(gè)位置，按照馬的走棋規(guī)則，我們能夠發(fā)現(xiàn)，如果沒有其他棋子的影響，

3、它最多有 8 個(gè)出口，最少有 2 個(gè)出口。馬所在位置及其出口算法核心思想：本程序的核心算法是“貪心算法” 。在每個(gè)結(jié)點(diǎn)對(duì)其子結(jié)點(diǎn)進(jìn)行選取時(shí)，優(yōu)先選擇出口最小的進(jìn)行搜索， 出口的意思是在這些子結(jié)點(diǎn)中它們的可行子結(jié)點(diǎn)的個(gè)數(shù)，也就是孫子結(jié)點(diǎn)越少的越優(yōu)先跳，為什么要這樣選取，這是一種局部調(diào)整最優(yōu)的做法，如果優(yōu)先選擇出口多的子結(jié)點(diǎn)，那出口少的子結(jié)點(diǎn)就會(huì)越來越多，很可能出現(xiàn)死結(jié)點(diǎn)（顧名思義就是沒有出口又沒有跳過的結(jié)點(diǎn)） ，這樣對(duì)下面的搜索純粹是徒勞，這樣會(huì)浪費(fèi)很多無用的時(shí)間，反過來如果每次都優(yōu)先選擇出口少的結(jié)點(diǎn)跳，那出口少的結(jié)點(diǎn)就會(huì)越來越少，這樣跳成功的機(jī)會(huì)就更大一些。 012345670 8 1 1 7

4、 2 2 H 3 6 3 4 5 4 5 6 7 計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 3 -2 2、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的選擇棧：本程序可以利用棧的知識(shí)來解決，當(dāng)然，棧也包括鏈棧和順序棧，由于本程序數(shù)據(jù)有限，并且順序棧較鏈棧簡單，所以該程序最終選擇使用順序棧來解決。貪心算法：在算法中采用逐步構(gòu)造最優(yōu)解。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下） 。決策一旦作出就不可再更改。概要設(shè)計(jì)、主程序模塊：void main()定義變量；接受命令；處理命令；退出；、起始坐標(biāo)函數(shù)模塊馬兒在棋盤上的起始位置；、探尋路徑函數(shù)模塊馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤

5、；、輸出路徑函數(shù)模塊輸出馬兒行走的路徑； 流程圖如下： 輸入的初始位置是否正確 否 是 主程序模塊起始坐標(biāo)函數(shù)模塊探尋路徑函數(shù)模塊 輸出路徑函數(shù)模塊塊 結(jié)束計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 4 - 3 3、詳細(xì)設(shè)計(jì)和編碼、詳細(xì)設(shè)計(jì)和編碼下圖顯示了馬位于方格（2，3）時(shí)，8 個(gè)可能的移動(dòng)位置。一般來說，當(dāng)馬位于位置（i,j）時(shí)，可以走到下列 8 個(gè)位置之一012345670811722H373454567(i-2,j+1)、 （i-1,j+2） 、(i+1,j+2)、(i+2,j+1)(i+2,j-1)、(i+1,j-2)、(i-1,j-2)、(i-2,j-1) 但是，如果(i,j)靠近棋盤的邊緣，

6、上述有些位置可能超出棋盤范圍，成為不允許的位置。8 個(gè)可能位置可以用兩個(gè)一維數(shù)組 Htry10.7和 Htry20.7來表示： 0 1 2 3 4 5 6 7Htry1 -2 -1 1 2 2 1 -1 -2 0 1 2 3 4 5 6 7Htry2 1 2 2 1 -1 -2 -2 -1位于(i,j)的馬可以走到的新位置是在棋盤范圍內(nèi)的(i+Htryh,j+Htry2h),其中h=0,1,2,7。每次在多個(gè)可走位置中選擇其中一個(gè)進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 5 -流程圖如下：開始Int i、ji=

7、0iNBoardij=0i +輸入棋子起始位置判斷棋子是否出棋盤MultiplexFor 循環(huán)從這個(gè)位置開始結(jié)束計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 6 -4 4、上機(jī)調(diào)試過程、上機(jī)調(diào)試過程（1） 、本次實(shí)驗(yàn)的主要目的是在于掌握和理解棧的特性和它的應(yīng)用。在編制該程序中遇到了很多問題。首先，在開始剛編制程序的時(shí)候遇到的問題是，程序編譯都通不過，主要在一些細(xì)節(jié)的問題上，還有在程序的返回值在剛開始時(shí)也沒有正確返回。經(jīng)過編譯慢慢調(diào)試，編譯都能通過，沒有錯(cuò)誤和警告。（2） 、雖然編譯都能通過，但是運(yùn)行時(shí)卻出錯(cuò)，程序不能終止，只有通過人工方式結(jié)束程序，可能是在某些地方出現(xiàn)了無限死循環(huán)了，然后在仔細(xì)檢查代碼，發(fā)現(xiàn)沒

8、有標(biāo)記馬兒嘗試的方向 director，這樣的話，馬兒回溯的時(shí)候，下一次又有可能走那個(gè)方向，這樣就出現(xiàn)了死循環(huán)。（3） 、標(biāo)記好馬兒嘗試的方向后，編譯運(yùn)行，但是運(yùn)行結(jié)果卻不符合程序所要求的結(jié)果，說明在算法上肯定有錯(cuò)誤，檢查發(fā)現(xiàn)，馬兒走的坐標(biāo)沒有控制后，它的橫縱坐標(biāo)必須控制 0 到 7 之間，否則的話馬兒就會(huì)踏出棋盤以外，這樣輸出的結(jié)果就不對(duì)。還有就是棋盤走過的位置要標(biāo)記一下，以便下次走不重復(fù)走，當(dāng)回溯的時(shí)候的記得把標(biāo)記給清掉，這個(gè)地方有時(shí)候也很容易混淆。5 5、測試結(jié)果及分析、測試結(jié)果及分析輸入數(shù)據(jù) 1：根據(jù)要求重新輸入馬的初始位置（9,9） ，由于輸入數(shù)據(jù)不再要求范圍之內(nèi),程序要求用戶重新輸

9、入;圖（1）計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 7 -輸入數(shù)據(jù) 2：根據(jù)要求重新輸入馬的初始位置（1,1） ，結(jié)果如下圖（2）= =圖（3）計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 8 -測試結(jié)果如圖（1）所示、當(dāng)輸入馬的坐標(biāo)為（9,9）時(shí)，由于該坐標(biāo)不在 88 的棋盤內(nèi)，所以程序提示要求重新輸入；如圖（2）所示，重新輸入數(shù)據(jù)位（1,1）滿足棋盤要求，得到在該位置的馬踏棋盤的結(jié)果。如圖（3）所示，當(dāng)位置選定為（4,4）時(shí)的結(jié)果。結(jié)果分析：如圖（3）所示，以數(shù)字遞增順序表示馬的下一個(gè)出口位置。如圖中，1 表示初始位置，按照國際象棋中馬的走棋規(guī)則并選擇最優(yōu)位置，即為 2 位置；3 表示 2 位置的馬的下一個(gè)出口位置

10、。以此循環(huán)下去，直到數(shù)字遍及整個(gè)棋盤。注：馬 的走棋路線即為圖中白線標(biāo)記部分（僅標(biāo)記了前 4 個(gè)位置）測試數(shù)據(jù) 1:輸入馬的初始位置(9，9)，由于不符合要求，程序要求重新輸入6 6、用戶使用說明、用戶使用說明用戶需將源程序清單輸入可運(yùn)行 C+的編輯平臺(tái)，例如 vc+, c+ Builder 等等，然后進(jìn)行編譯，然后用戶根據(jù)提示輸入馬的初始位置，程序會(huì)提示所輸入馬的初始位置必須在 1-8 之間，否則需要重新輸入，直至輸入的位置符合要求為止；輸入正確之后，程序會(huì)輸入馬兒踏遍整個(gè)棋盤的具體執(zhí)行步驟。注：阿拉伯?dāng)?shù)字 1、2、3、462、63、64。下一個(gè)數(shù)字所在位置即為上一個(gè)位置馬兒的出口。7 7、

11、參考文獻(xiàn)、參考文獻(xiàn)1王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法.北京：鐵道工業(yè)出版社，2007 年 6 月第一版2.徐孝凱，魏榮數(shù)據(jù)結(jié)構(gòu),北京：機(jī)械工業(yè)出版社，1996 年3.徐孝凱數(shù)據(jù)結(jié)構(gòu)簡明教程 ，北京:清華大學(xué)出版社，1995 年4.陳文博，朱青數(shù)據(jù)結(jié)構(gòu)與算法 ，北京：機(jī)械工業(yè)出版社，1996 年5.許卓群，張乃孝，楊冬青，唐世渭數(shù)據(jù)結(jié)構(gòu) ，高等教育出版社，1988 年6.李廉治，姜文清，郭福順數(shù)據(jù)結(jié)構(gòu) ，大連理工大學(xué)出版社，1989 年計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 9 -附錄附錄源程序源程序/（1） 、定義頭文件和預(yù)定義#include#define MAXSIZE 100#define N 8/（

12、2） 、數(shù)據(jù)類型定義int board88; /定義棋盤int Htry18=1,-1,-2,2,2,1,-1,-2; /*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置行下標(biāo)的增量數(shù)組*/int Htry28=2,-2,1,1,-1,-2,2,-1; /*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置列下標(biāo)的增量數(shù)組*/struct Stack /定義棧類型 int i; /行坐標(biāo)int j; /列坐標(biāo) int director; /存儲(chǔ)方向stackMAXSIZE; /定義一個(gè)棧數(shù)組int top=-1; /棧指針/（3） 、函數(shù)聲明void InitLocation(int xi,int yi); /馬兒在棋盤上的起始

13、位置坐標(biāo)int TryPath(int i,int j); /馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤void Display(); /輸出馬兒行走的路徑/（4） 、起始坐標(biāo)函數(shù)模塊void InitLocation(int xi,int yi)int x,y; /定義棋盤的橫縱坐標(biāo)變量top+; /棧指針指向第一個(gè)棧首stacktop.i=xi; /將起始位置的橫坐標(biāo)進(jìn)棧stacktop.j=yi; /將起始位置的縱坐標(biāo)進(jìn)棧計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 10 -stacktop.director=-1; /將起始位置的嘗試方向賦初值boardxiyi=top+1; /標(biāo)記棋盤x=stackto

14、p.i; /將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)y=stacktop.j; /將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y) /調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個(gè)棋盤返回 1 否則返回 0Display(); /輸出馬兒的行走路徑else printf(無解); /（5） 、探尋路徑函數(shù)模塊int TryPath(int i,int j)int find,director,number,min; /定義幾個(gè)臨時(shí)變量int i1,j1,h,k,s; /定義幾個(gè)臨時(shí)變量int a8,b18,b28,d8; /定義幾個(gè)臨時(shí)數(shù)組while(top-1) /棧不空時(shí)循環(huán)for(h=0;h

15、=0&i=0&j8) /如果找到下一位置for(k=0;k=0&i1=0&j18) /如果找到下一位置 number+; /記錄條數(shù) ah=number; /將條數(shù)存入數(shù)組 a8中 for(h=0;h8;h+) /根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組 d8中min=9; for(k=0;kak) min=ak; dh=k; /將下表存入數(shù)組 d8中 s=k; as=9; director=stacktop.director; if(top=63) /如果走完整個(gè)棋盤返回 1return (1);find=0; /表示沒有找到下一個(gè)位置for(h=direct

16、or+1;h=0&i=0&j8) /如果找到下一位置計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告- 12 -find=1; /表示找到下一個(gè)位置break;if(find=1) /如果找到下一個(gè)位置進(jìn)棧stacktop.director=director; /存儲(chǔ)棧結(jié)點(diǎn)的方向 top+; /棧指針前移進(jìn)棧stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一棧結(jié)點(diǎn)的嘗試方向boardij=top+1; /標(biāo)記棋盤else /否則退棧boardstacktop.istacktop.j=0; /清除棋盤的標(biāo)記top-; /棧指針前移退棧return (0); /（6）輸出路徑函數(shù)模塊void Display() int i,j; for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d ,boardij); /輸出馬兒在棋盤上走過的路徑printf(nn);計(jì)科系數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)