數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)馬的遍歷問題

1、衡陽師范學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題 目： 馬的遍歷問題 系 別： 專 業(yè)： 班 級(jí)： 學(xué)生姓名： 學(xué) 號(hào)： 指導(dǎo)老師： 完成日期： 目錄一、問題描述3二、設(shè)計(jì)思路. . .3 三、算法分析31.計(jì)算一個(gè)點(diǎn)周圍有幾個(gè)點(diǎn)32.尋找下一個(gè)方向43.棧的相關(guān)函數(shù). 4 4.馬的遍歷函數(shù). 5 5.主函數(shù). 7 6.棋盤初始化. 8 7.標(biāo)記初始化. 8四、測(cè)試結(jié)果9五、源程序10六、課程設(shè)計(jì)心得151 問題描述根據(jù)中國象棋棋盤，對(duì)任一位置上放置的一個(gè)馬，均能選擇一個(gè)合適的路線，使得該棋子能按象棋的規(guī)則不重復(fù)地走過棋盤上的每一位置。 要求： （1）依次輸出所走過的各位置的坐標(biāo)。 （2）最好能畫出棋盤的圖形形

2、式，并在其上動(dòng)態(tài)地標(biāo)注行走過程。 （3）程序能方便地地移植到其它規(guī)格的棋盤上。2 設(shè)計(jì)思路首先，中國象棋是10*9的棋盤，馬的走法是“馬走日”，忽略“蹩腳馬”的情況。其次，這個(gè)題目采用的是算法當(dāng)中的深度優(yōu)先算法和回溯法：在“走到”一個(gè)位置后要尋找下一個(gè)位置，如果發(fā)生“阻塞”的情況，就是后面走不通的情況，則向后回溯，重新尋找。在尋找下一步的時(shí)候，對(duì)周圍的這幾個(gè)點(diǎn)進(jìn)行比較，從而分出優(yōu)劣程度，即看它們周圍可以走的點(diǎn)誰最少，然后就走那條可走路線最少的那條。經(jīng)過這樣的篩選后，就會(huì)為后面的路徑尋找提供方便，從而減少回溯次數(shù)。最后，本程序的棋盤和數(shù)組類似，因而采用數(shù)組進(jìn)行存儲(chǔ)，同時(shí)因?yàn)橛谢厮荩圆捎脳５姆?/p>

3、法，并且為了最后打印方便，采用的是順序棧的方法。同時(shí)還有八個(gè)方向的數(shù)組，和為棧設(shè)計(jì)的每個(gè)點(diǎn)周圍的八個(gè)方向那些可以走的數(shù)組。3 算法分析1、 計(jì)算一個(gè)點(diǎn)周圍有幾個(gè)點(diǎn)函數(shù)int Count(int x,int y) 該函數(shù)實(shí)現(xiàn)的功能是在遍歷的過程當(dāng)中計(jì)算一個(gè)點(diǎn)周圍有幾個(gè)方向可以走，從而為后面的篩選提供依據(jù)。int Count(int x,int y)/計(jì)算每個(gè)節(jié)點(diǎn)周圍有幾個(gè)方向可以走int count=0,i=0;for(i=0;i<8;i+)if(chessboardx+1+diri.xy+1+diri.y=0)count+;return count;2、尋找下一個(gè)方向函數(shù)int Find

4、_Direction(int x,int y)該函數(shù)的功能是在走過一個(gè)點(diǎn)之后，尋找下一個(gè)適合的點(diǎn)，如果找到返回正常的方向值，否則返回-1。int Find_Direction(int x,int y)/尋找下一個(gè)方向int dire,min=9,count,d=9;for(dire=0;dire<8;dire+)if(chessboardx+1+dirdire.xy+1+dirdire.y=0&&CanPassx+1y+1dire=0)count=Count(x+dirdire.x,y+dirdire.y);if(min>count)min=count;d=dire

5、;if(d<9)return d;elsereturn -1;3、棧的相關(guān)函數(shù)初始化棧：void Init_Path(path *p)；p是用到得棧；判斷棧是否是空：int Empty(path p)；p是棧，是空的話返回1，否則返回0，時(shí)間復(fù)雜度為；壓棧函數(shù)：int Push_Path(path *p,pathnode t,int v)p是棧，t是壓進(jìn)去的節(jié)點(diǎn)，v是棋盤，時(shí)間復(fù)雜度為；出棧函數(shù)：int Pop_Path(path *p,pathnode *t)p是棧，t是拿出來的節(jié)點(diǎn)，時(shí)間復(fù)雜度為。void Init_Path(path *p)/初始化棧p->top=-1;int

6、 Push_Path(path *p,pathnode t,int v)/壓節(jié)點(diǎn)及其向下一位移動(dòng)的方向入棧if(p->top>=63+26*v)return -1;elsep->top+;p->pap->top.x=t.x;p->pap->top.y=t.y;p->pap->top.di=t.di;return 1;int Empty(path p)/判斷棧是否為空if(p.top<0) return 1;return 0;4、馬的遍歷函數(shù)：void Horse(int x,int y)這是該算法的精華部分，x,y表示入口地點(diǎn)，v表示

7、棋盤類型即中國象棋，這個(gè)函數(shù)主體是一個(gè)循環(huán)，循環(huán)里面始終是在找下一個(gè)點(diǎn)，如果找到就將該點(diǎn)進(jìn)棧，找不到則退棧。直到發(fā)生棧為空時(shí)退?；蜓h(huán)結(jié)束，前一種情況時(shí)會(huì)提示找不到路徑(雖然不會(huì)發(fā)生，但是為邏輯嚴(yán)密性依然要如此)，后一種情況則打印出走過的正確路徑和走過之后的數(shù)組。void Horse(int x,int y,int v)/x,y表示出發(fā)位置/馬的遍歷函數(shù)int num=1,t,i;path p;pathnode f;Init_Path(&p);for(num=1;num<=64+26*v;num+)t=Find_Direction(x,y);if(t!=-1)/正常找到下一個(gè)方向

8、的情況下chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);x=x+dirt.x;y=y+dirt.y;else if(num=64+26*v&&chessboardx+1y+1=0)/最后一次時(shí)t肯定是-1chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);elseif(Pop_Path(&p,&f)=-1)/出棧且棧為空的情況printf("!無法為您找到一條適合的路徑!n");exit(0);n

9、um-=2;x=f.x;y=f.y;CanPassx+1y+1f.di=1;/end else/根據(jù)棧中信息打印出馬行走路徑printf("馬的遍歷路徑如下:n ");for(i=0;i<64+26*v;i+)printf("(%2d,%d)->",p.pai.x,p.pai.y);if(i+1)%(8+v)=0)printf("bb n->");printf("bb n");printf("根據(jù)數(shù)組打印結(jié)果是:n");for(i=0;i<8+2*v;i+)/根據(jù)棋盤數(shù)組

10、來打印for(t=0;t<8+v;t+)printf("%4d",chessboardi+2t+2);printf("n");5、主函數(shù)：int main()提示輸入起點(diǎn)位置，這里的起點(diǎn)位置就是日常生活觀念中的順序，開始點(diǎn)是(1,1),而不是數(shù)組中的初始位置(0,0),輸入錯(cuò)誤則提示重新輸入，時(shí)間復(fù)雜度為。int main() /主函數(shù)int x,y; char ch='y; while(ch='y')printf(" 中國象棋馬的遍歷 n:");Mark_Che();Mark_Dir();while(1

11、)printf("請(qǐng)輸入入口點(diǎn)橫坐標(biāo)（在案1-10之間）：");scanf("%d",&x);if(y<1|y>9)printf("輸入錯(cuò)誤，請(qǐng)重新輸入!(橫坐標(biāo)在1-10之間)n");elsebreak;while(1)printf("請(qǐng)輸入入口點(diǎn)縱坐標(biāo)(在1-9之間)：");scanf("%d",&y);if(y<1|y>9)printf("輸入錯(cuò)誤，請(qǐng)重新輸入!(縱坐標(biāo)在1-9之間)n");elsebreak;Knight(x,y

12、);Getchar();Printf("n");printf("是否繼續(xù)馬的遍歷（是：y；否：其他）："); fflush(stdin);scanf("%c",&ch);6、棋盤初始化函數(shù)void Mark_Che(int v)此函數(shù)作為棋盤初始化函數(shù)，因?yàn)槊看螆?zhí)行程序時(shí)，棋盤上必須是全部都沒有走過的。它會(huì)自動(dòng)進(jìn)行初始化棋盤，在14*13的棋盤上初始化。初始化后，棋盤大小的區(qū)域全部是0，而周圍的兩堵墻標(biāo)志為1，時(shí)間復(fù)雜度為。void Mark_Che(int v)int i,j;for(i=0;i<12+2*v;i+)/

13、首先全部標(biāo)記為0for(j=0;j<12+v;j+)chessboardij=0;for(i=0;i<2;i+)/前面兩行標(biāo)記為1for(j=0;j<12+v;j+)chessboardij=1;for(j=0;j<2;j+)/前面兩列for(i=0;i<12+2*v;i+)chessboardij=1;for(j=10+v;j<12+v;j+)/后面兩列for(i=0;i<12+2*v;i+)chessboardij=1;for(i=10+2*v;i<12+2*v;i+)for(j=0;j<12+v;j+)/后面兩行chessboardi

14、j=1;7、標(biāo)記初始化函數(shù)void Mark_Dir() 此函數(shù)和上面的函數(shù)功能類似，也是初始化才用，它是為棧的實(shí)現(xiàn)提供幫助的。開始時(shí)全部標(biāo)記為0，表示周圍的八個(gè)方向都可以走，時(shí)間復(fù)雜度為。void Mark_Dir(int v)/由于三維數(shù)組賦初值比較困難，因而采用單獨(dú)的函數(shù)實(shí)現(xiàn)int i,j,k;for(i=0;i<12+2*v;i+)for(j=0;j<12+v;j+)for(k=0;k<8;k+)CanPassijk=0;4 測(cè)試結(jié)果5 源程序#include<iostream>#include<cstdio>using namespace s

15、td;int chessboard1413;/棋盤int CanPass14138;/每個(gè)棋子的八個(gè)方向哪些可以走typedef struct/棋盤的八個(gè)方向int y,x;direction;direction dir8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1;/八個(gè)方向/棧的設(shè)計(jì)typedef structint x,y;/走過位置int di;/方向pathnode;typedef structpathnode pa90;int top;path;/順序棧void Init_Path(path *p)/初始化棧p->top=-1;int Pu

16、sh_Path(path *p,pathnode t,int v)/壓節(jié)點(diǎn)及其向下一位移動(dòng)的方向入棧if(p->top>=63+26*v)return -1;elsep->top+;p->pap->top.x=t.x;p->pap->top.y=t.y;p->pap->top.di=t.di;return 1;int Empty(path p)/判斷棧是否為空if(p.top<0) return 1;return 0;int Pop_Path(path *p,pathnode *t)/出棧if(Empty(*p)return -1;e

17、lset->x=p->pap->top.x;t->y=p->pap->top.y;t->di=p->pap->top-.di;return 1;int Count(int x,int y)/計(jì)算每個(gè)節(jié)點(diǎn)周圍有幾個(gè)方向可以走int count=0,i=0;for(i=0;i<8;i+)if(chessboardx+1+diri.xy+1+diri.y=0)count+;return count;int Find_Direction(int x,int y)/尋找下一個(gè)方向int dire,min=9,count,d=9;for(dire

18、=0;dire<8;dire+)if(chessboardx+1+dirdire.xy+1+dirdire.y=0&&CanPassx+1y+1dire=0)count=Count(x+dirdire.x,y+dirdire.y);if(min>count)min=count;d=dire;if(d<9)return d;elsereturn -1;void Horse(int x,int y,int v)/x,y表示出發(fā)位置/馬的遍歷函數(shù)int num=1,t,i;path p;pathnode f;Init_Path(&p);for(num=1;n

19、um<=64+26*v;num+)t=Find_Direction(x,y);if(t!=-1)/正常找到下一個(gè)方向的情況下chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);x=x+dirt.x;y=y+dirt.y;else if(num=64+26*v&&chessboardx+1y+1=0)/最后一次時(shí)t肯定是-1chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);elseif(Pop_Path(&p,&f

20、)=-1)/出棧且棧為空的情況printf("!無法為您找到一條適合的路徑!n");exit(0);num-=2;x=f.x;y=f.y;CanPassx+1y+1f.di=1;/end else/根據(jù)棧中信息打印出馬行走路徑printf("馬的遍歷路徑如下:n ");for(i=0;i<64+26*v;i+)printf("(%2d,%d)->",p.pai.x,p.pai.y);if(i+1)%(8+v)=0)printf("bb n->");printf("bb n");

21、printf("根據(jù)數(shù)組打印結(jié)果是:n");for(i=0;i<8+2*v;i+)/根據(jù)棋盤數(shù)組來打印for(t=0;t<8+v;t+)printf("%4d",chessboardi+2t+2);printf("n");void Mark_Dir(int v)/由于三維數(shù)組賦初值比較困難，因而采用單獨(dú)的函數(shù)實(shí)現(xiàn)int i,j,k;for(i=0;i<12+2*v;i+)for(j=0;j<12+v;j+)for(k=0;k<8;k+)CanPassijk=0;void Mark_Che(int v)/標(biāo)

22、志棋盤函數(shù)int i,j;for(i=0;i<12+2*v;i+)/首先全部標(biāo)記為0for(j=0;j<12+v;j+)chessboardij=0;for(i=0;i<2;i+)/前面兩行標(biāo)記為1for(j=0;j<12+v;j+)chessboardij=1;for(j=0;j<2;j+)/前面兩列for(i=0;i<12+2*v;i+)chessboardij=1;for(j=10+v;j<12+v;j+)/后面兩列for(i=0;i<12+2*v;i+)chessboardij=1;for(i=10+2*v;i<12+2*v;i+)for(j=0;j<12+v;j+)/后面兩行chessboardij=1;int main()/主函數(shù)int x,y,v;char ch='y' while(ch='y') while(1) printf(