數(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ì)名稱馬踏棋盤學(xué)生姓名學(xué)號(hào)專業(yè)班級(jí)指導(dǎo)教師2013 年6月目 錄數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告馬踏棋盤- 2 -問(wèn)題描述- 2 -1、問(wèn)題分析與定義- 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)試過(guò)程- 6 -5、測(cè)試結(jié)果及分析- 7 -6、用戶使用說(shuō)明- 9 -7、參考文獻(xiàn)- 9 -附錄源程序- 10 -數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告馬踏棋盤題目：【問(wèn)題描述】設(shè)計(jì)一個(gè)國(guó)際象棋的馬踏遍棋盤的演示程序。要求：將馬隨機(jī)放在國(guó)際象棋的8×

2、8棋盤Board88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，64依次填入一個(gè)8×8的方陣，輸出之。1、問(wèn)題分析與定義走棋規(guī)則：馬走3×2格對(duì)角線，簡(jiǎn)單的說(shuō)就是走L形棋盤如圖所示，將馬放在棋盤中的任意一個(gè)位置，按照馬的走棋規(guī)則，我們能夠發(fā)現(xiàn)，如果沒(méi)有其他棋子的影響，它最多有8個(gè)出口，最少有2個(gè)出口。 012345670  8 1   1 7   2

3、0; 2   H    3 6   3  4  5 4   5        6        7        馬所在位置及其出口算法核心思想：本程序的核心算

4、法是“貪心算法”。在每個(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ì)越來(lái)越多，很可能出現(xiàn)死結(jié)點(diǎn)（顧名思義就是沒(méi)有出口又沒(méi)有跳過(guò)的結(jié)點(diǎn)），這樣對(duì)下面的搜索純粹是徒勞，這樣會(huì)浪費(fèi)很多無(wú)用的時(shí)間，反過(guò)來(lái)如果每次都優(yōu)先選擇出口少的結(jié)點(diǎn)跳，那出口少的結(jié)點(diǎn)就會(huì)越來(lái)越少，這樣跳成功的機(jī)會(huì)就更大一些。2、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的選擇棧：本程序可以利用棧的知識(shí)來(lái)解決，當(dāng)然，棧也包括鏈棧和順序棧，由于本程序數(shù)據(jù)有限，并且順

5、序棧較鏈棧簡(jiǎn)單，所以該程序最終選擇使用順序棧來(lái)解決。貪心算法：在算法中采用逐步構(gòu)造最優(yōu)解。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出就不可再更改。概要設(shè)計(jì)、主程序模塊：void main()定義變量；接受命令；處理命令；退出；、起始坐標(biāo)函數(shù)模塊馬兒在棋盤上的起始位置；、探尋路徑函數(shù)模塊馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤；、輸出路徑函數(shù)模塊輸出馬兒行走的路徑； 流程圖如下：主程序模塊 輸入的初始位置是否正確 否 是 起始坐標(biāo)函數(shù)模塊 探尋路徑函數(shù)模塊 輸出路徑函數(shù)模塊塊 結(jié)束 3、詳細(xì)設(shè)計(jì)和編碼下圖顯示了馬位于方格（2，3）時(shí)，8個(gè)可能的移動(dòng)位置。一般來(lái)說(shuō)，當(dāng)馬位

6、于位置（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)靠近棋盤的邊緣，上述有些位置可能超出棋盤范圍，成為不允許的位置。8個(gè)可能位置可以用兩個(gè)一維數(shù)組Htry10.7和Htry20.7來(lái)表示： 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)的馬可以走到的

7、新位置是在棋盤范圍內(nèi)的(i+Htryh,j+Htry2h),其中h=0,1,2,7。每次在多個(gè)可走位置中選擇其中一個(gè)進(jìn)行試探，其余未曾試探過(guò)的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用。流程圖如下：開(kāi)始Int i、ji=0i<NBoardij=0i +輸入棋子起始位置判斷棋子是否出棋盤MultiplexFor循環(huán)從這個(gè)位置開(kāi)始結(jié)束4、上機(jī)調(diào)試過(guò)程（1）、本次實(shí)驗(yàn)的主要目的是在于掌握和理解棧的特性和它的應(yīng)用。在編制該程序中遇到了很多問(wèn)題。首先，在開(kāi)始剛編制程序的時(shí)候遇到的問(wèn)題是，程序編譯都通不過(guò)，主要在一些細(xì)節(jié)的問(wèn)題上，還有在程序的返回值在剛開(kāi)始時(shí)也沒(méi)有正確返回。

8、經(jīng)過(guò)編譯慢慢調(diào)試，編譯都能通過(guò)，沒(méi)有錯(cuò)誤和警告。（2）、雖然編譯都能通過(guò)，但是運(yùn)行時(shí)卻出錯(cuò)，程序不能終止，只有通過(guò)人工方式結(jié)束程序，可能是在某些地方出現(xiàn)了無(wú)限死循環(huán)了，然后在仔細(xì)檢查代碼，發(fā)現(xiàn)沒(méi)有標(biāo)記馬兒嘗試的方向director，這樣的話，馬兒回溯的時(shí)候，下一次又有可能走那個(gè)方向，這樣就出現(xiàn)了死循環(huán)。（3）、標(biāo)記好馬兒嘗試的方向后，編譯運(yùn)行，但是運(yùn)行結(jié)果卻不符合程序所要求的結(jié)果，說(shuō)明在算法上肯定有錯(cuò)誤，檢查發(fā)現(xiàn)，馬兒走的坐標(biāo)沒(méi)有控制后，它的橫縱坐標(biāo)必須控制0到7之間，否則的話?cǎi)R兒就會(huì)踏出棋盤以外，這樣輸出的結(jié)果就不對(duì)。還有就是棋盤走過(guò)的位置要標(biāo)記一下，以便下次走不重復(fù)走，當(dāng)回溯的時(shí)候的記得把

9、標(biāo)記給清掉，這個(gè)地方有時(shí)候也很容易混淆。5、測(cè)試結(jié)果及分析輸入數(shù)據(jù)1：根據(jù)要求重新輸入馬的初始位置（9,9），由于輸入數(shù)據(jù)不再要求范圍之內(nèi),程序要求用戶重新輸入;圖（1）輸入數(shù)據(jù)2：根據(jù)要求重新輸入馬的初始位置（1,1），結(jié)果如下圖（2）=圖（3）測(cè)試結(jié)果如圖（1）所示、當(dāng)輸入馬的坐標(biāo)為（9,9）時(shí)，由于該坐標(biāo)不在8×8的棋盤內(nèi)，所以程序提示要求重新輸入；如圖（2）所示，重新輸入數(shù)據(jù)位（1,1）滿足棋盤要求，得到在該位置的馬踏棋盤的結(jié)果。如圖（3）所示，當(dāng)位置選定為（4,4）時(shí)的結(jié)果。結(jié)果分析：如圖（3）所示，以數(shù)字遞增順序表示馬的下一個(gè)出口位置。如圖中，1表示初始位置，按照國(guó)際象棋

10、中馬的走棋規(guī)則并選擇最優(yōu)位置，即為2位置；3表示2位置的馬的下一個(gè)出口位置。以此循環(huán)下去，直到數(shù)字遍及整個(gè)棋盤。注：馬 的走棋路線即為圖中白線標(biāo)記部分（僅標(biāo)記了前4個(gè)位置）測(cè)試數(shù)據(jù)1:輸入馬的初始位置(9，9)，由于不符合要求，程序要求重新輸入6、用戶使用說(shuō)明用戶需將源程序清單輸入可運(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ù)字所在

11、位置即為上一個(gè)位置馬兒的出口。7、參考文獻(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)簡(jiǎn)明教程，北京:清華大學(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年附錄源程序/（1）、定義頭文件和預(yù)定義#include<stdio.h>#define MAXSIZE 100#define N 8/（2）、數(shù)據(jù)類型定義

12、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); /馬兒在棋盤上的起始位置坐標(biāo)int Try

13、Path(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)棧stacktop.director=-1; /將起始位置的嘗試方向賦初值boardxiyi=top+1; /標(biāo)記棋盤x=stacktop.i; /將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)y=stackt

14、op.j; /將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(TryPath(x,y) /調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個(gè)棋盤返回1否則返回0Display(); /輸出馬兒的行走路徑else printf("無(wú)解"); /（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<8;h+) /用數(shù)組a8記錄當(dāng)

15、前位置的下一個(gè)位置的可行路徑的條數(shù)number=0; i=stacktop.i+Htry1h; j=stacktop.j+Htry2h; b1h=i; b2h=j; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置for(k=0;k<8;k+)i1=b1h+Htry1k; j1=b2h+Htry2k; if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1&

16、lt;8) /如果找到下一位置 number+; /記錄條數(shù) ah=number; /將條數(shù)存入數(shù)組a8中 for(h=0;h<8;h+) /根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d8中min=9; for(k=0;k<8;k+)if(min>ak) min=ak; dh=k; /將下表存入數(shù)組d8中 s=k; as=9; director=stacktop.director; if(top>=63) /如果走完整個(gè)棋盤返回1return (1);find=0; /表示沒(méi)有找到下一個(gè)位置for(h=director+1;h<8;h+) /向八個(gè)方向進(jìn)行探尋i=s

17、tacktop.i+Htry1dh; j=stacktop.j+Htry2dh;if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置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=

18、top+1; /標(biāo)記棋盤else /否則退棧boardstacktop.istacktop.j=0; /清除棋盤的標(biāo)記top-; /棧指針前移退棧return (0); /（6）輸出路徑函數(shù)模塊void Display() int i,j; for(i=0;i<N;i+)for(j=0;j<N;j+)printf("t%d ",boardij); /輸出馬兒在棋盤上走過(guò)的路徑printf("nn");printf("n");/（5）主程序模塊void main()int i,j;int x,y;for(i=0;i<N;i+) /初始化棋盤 for(j=0;j<N;j+) boardij=0;for(;)printf("請(qǐng)輸入棋子起始坐標(biāo)(1<=x<=8 and 1<=y<=8)n");printf("請(qǐng)輸入行坐標(biāo) x = ");scanf("