數(shù)據(jù)結(jié)構(gòu)課程設(shè)計馬的遍歷(共29頁)

1、課 程 設(shè) 計 說 明 書課程名稱： 數(shù)據(jù)結(jié)構(gòu) 設(shè)計題目： 馬的遍歷 院 系： 計算機科學(xué)與信息工程學(xué)院 學(xué)生姓名： 學(xué) 號： 專業(yè)班級： 指導(dǎo)教師： 2015 年 6 月 7 日課 程 設(shè) 計 任 務(wù) 書設(shè)計題目馬的遍歷學(xué)生姓名所在院系計算機科學(xué)與信息工程學(xué)院專業(yè)、年級、班設(shè)計要求：任意行列數(shù)的棋盤中，馬只能走“日”字。馬從任意位置處出發(fā)，把棋盤的每一格都走一次，且只走一次。要求在屏幕上畫出棋盤和馬所有經(jīng)過的路徑。學(xué)生應(yīng)完成的工作：1.分析題目要求2.利用數(shù)據(jù)結(jié)構(gòu)和c語言知識找出實現(xiàn)方法3.編程完成實現(xiàn)4.按要求撰寫課程設(shè)計報告和設(shè)計總結(jié)。參考文獻(xiàn)閱讀：1.c程序設(shè)計（第四版），譚浩強 清華

2、大學(xué)出版社2.數(shù)據(jù)結(jié)構(gòu)（c語言版），嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社工作計劃：1. 接到題目后用課余時間設(shè)計程序，2. 第14周上機調(diào)試通過后，答辯，交報告（具體時間由各任課教師決定）。任務(wù)下達(dá)日期： 2015年 4 月 28 日 任務(wù)完成日期： 2015年 6 月 6 日指導(dǎo)教師（簽名）： 學(xué)生（簽名）： 馬的遍歷摘 要：中國象棋中馬采用“日”字走法，對棋盤上馬所在的結(jié)點，一步內(nèi)到達(dá)的結(jié)點最多有八個，所以可以采用類似圖的深度優(yōu)先遍歷，以馬所在點為初始點對整個棋盤進行遍歷。然后按遍歷的順序輸出結(jié)點 可以用一個二維數(shù)組chess來表示棋盤，一開始用來存放步驟號，若走過了則把它賦值為0。對于動態(tài)演示

3、問題，只要在“馬”的位置顯示“馬”，已經(jīng)走過的位置顯示“”，未走過的位置顯示“”“ ”“ ”“”等制表符，然后清屏，顯示下一步，再清屏，依次類推。關(guān)鍵詞：深度優(yōu)先遍歷；回溯法；數(shù)組存儲棋盤；動態(tài)演示；目 錄1. 設(shè)計背景11.1問題描述11.2基本要求12. 設(shè)計方案12.1問題分析和任務(wù)定義12.2概要設(shè)計和數(shù)據(jù)結(jié)構(gòu)的選擇23. 方案實施33.1數(shù)據(jù)結(jié)構(gòu)設(shè)計33.2功能函數(shù)設(shè)計43.3編碼實現(xiàn)54. 結(jié)果與結(jié)論144.1輸入初始數(shù)據(jù)144.2判斷能否遍歷144.3動態(tài)演示145. 收獲與致謝156參考文獻(xiàn)151. 設(shè)計背景1.1 問題描述：中國象棋是10*9的棋盤，馬的走法是“馬走日”，這里

4、忽略了“蹩腳馬”的情況，使馬的遍歷問題簡單化。馬在棋盤上遍歷采用算法當(dāng)中的優(yōu)先算法和回溯法；從入口出發(fā)，按某一方向向前探索，若能走通并且從未走過，即某處可到達(dá)，則到達(dá)新店，否則探索下一個方向；如果發(fā)生“阻塞”的情況，就是后面走不通的情況，則沿原路返回到前一點，換一個方向再繼續(xù)試探，知道找到一條通路，或無路可走又返回到入口點。期盼中馬的遍歷采用數(shù)組進行存儲，同時因為有回溯，所以采用棧的方法，并且為了最后打印方便，采用的是順序棧的方法。同時還有八個方向的數(shù)組，和為棧設(shè)計的每個點周圍的八個方向那些可以走的數(shù)組。1.2 基本要求：棋盤有10行9列，利用chess來表示一個棋盤，chessij=0或1；

5、其中0表示通路，1表示不通，當(dāng)從某點向下試探時，中間點的8個方向可以試探；棋盤采用數(shù)組形式，并且這里的數(shù)組比棋盤的數(shù)組規(guī)模稍大，因為為了保證邊緣點也有八個方向可以走，使問題能夠簡單化，不用再判斷當(dāng)前點的試探方向有幾個。2.設(shè)計方案2.1問題分析和任務(wù)定義：中國象棋中馬采用“日”字走法，對棋盤上馬所在的結(jié)點，一步內(nèi)到達(dá)的結(jié)點最 多有八個，即假設(shè)馬所在點的坐標(biāo)為（i，j），那么其它八個結(jié)點的坐標(biāo)為（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-2,j+1）,（i-1,j+2）把這些點看作馬所在點的鄰接點，所以可以采用類似

6、圖的深度優(yōu)先遍歷，以馬所在點為初始點對整個棋盤進行遍歷。然后按遍歷的順序輸出結(jié)點 可以用一個二維數(shù)組chess來表示棋盤，一開始用來存放步驟號，若走過了則把它賦值為0。 對于動態(tài)演示問題，只要在“馬”的位置顯示“馬”，已經(jīng)走過的位置顯示“”，未走過的位置顯示“”“ ”“ ”“”等制表符，然后清屏，顯示下一步，再清屏，依次類推。 棋盤的規(guī)格限制在20*20以內(nèi)，起始點當(dāng)然不能超出棋盤的范圍，每輸入一組數(shù)據(jù)，首先判斷是否可以全部走完，如果可以，則動態(tài)演示，否則重新輸入數(shù)據(jù)。 2.2概要設(shè)計和數(shù)據(jù)結(jié)構(gòu)的選擇：該算法需要定義一個二維數(shù)組chess用來表示棋盤，整形變量step存放步驟 號，count存

7、放運算次數(shù)。 定義8個函數(shù)(f1,f2,f3,f4,f5,f6,f7,f8)用來表示按8種規(guī)則走，定義一個h函數(shù)用來統(tǒng)計8種規(guī)則中有幾種是可走的，再定義一個test函數(shù)用來測試是否可以走完，如果可以走完則返回值為1，否則返回0。 test函數(shù)和f1,f2,f3,f4,f5,f6,f7,f8八個函數(shù)是一個遞歸調(diào)用關(guān)系。然后通過主函數(shù)調(diào)用test函數(shù)，實現(xiàn)動態(tài)演示功能。具體過程見下圖：3. 方案實施3.1數(shù)據(jù)結(jié)構(gòu)設(shè)計：同上面述，棋盤采用數(shù)組形式，并且這里的數(shù)組比棋盤的數(shù)組規(guī)模稍大，因為為了判斷的方便，這里在棋盤周圍個加了兩層“墻”。具體數(shù)據(jù)結(jié)構(gòu)定義如下：int chess2323 /* chess

8、2323用來表示棋盤； int f1(int x,int y),f2(int x,int y),f3(int x,int y),f4(int x,int y),f5(int x,int y),f6(int x,int y),f7(int x,int y),f8(int x,int y); /*申明函數(shù)，這些函數(shù)就是用來表示八種走的規(guī)則*/int h(int x,int y) /*h函數(shù)用來測試（x，y）位置處，下一步可以跳的位置數(shù)，返回值為sum */ int sum; /*用來記錄下一步可以跳的位置數(shù)*/ sum=0; if(chessx-1y-2=0) sum+; if(chessx-2y

9、+1=0) sum+; if(chessx+2y+1=0) sum+; if(chessx+2y-1=0) sum+; if(chessx-2y-1=0) sum+; if(chessx-1y+2=0) sum+; if(chessx+1y-2=0) sum+; if(chessx+1y+2=0) sum+; return(sum); /*每找到一個位置sum+，最后返回sum值就是在(x,y)處可走的位置數(shù)*/ 3.2功能函數(shù)設(shè)計：（1）測試函數(shù)模塊int test(int x,int y)/*test函數(shù)測試第step步為(x,y)位置的情況下，是否可以走完棋盤，如果可以返回1,否則返回0

10、*/ （2）主函數(shù)：void main()進入主函數(shù)后提示用戶輸入棋盤大小，只能輸入小于23的數(shù)，其他的數(shù)字則提示輸入錯誤，重新輸入。然后提示輸入起點位置，這里的起點位置就是日常生活觀念中的順序，開始點是(1,1),而不是數(shù)組中的初始位置(0,0),輸入錯誤則提示重新輸入。3.3編碼實現(xiàn)：#include <stdio.h> #include <iostream> int chess2323,step=0,m=0,n=0,count=0; /* chess2323用來表示棋盤； step是步驟數(shù)； m和n是棋盤的規(guī)格行和列； count是運算次數(shù)；*/ int f1(i

11、nt x,int y),f2(int x,int y),f3(int x,int y),f4(int x,int y),f5(int x,int y),f6(int x,int y),f7(int x,int y),f8(int x,int y); /*申明函數(shù)，這些函數(shù)就是用來表示八種走的規(guī)則*/ int h(int x,int y) /*h函數(shù)用來測試（x，y）位置處，下一步可以跳的位置數(shù)，返回值為sum */ int sum; /*用來記錄下一步可以跳的位置數(shù)*/ sum=0; if(chessx-1y-2=0) sum+; if(chessx-2y+1=0) sum+; if(ches

12、sx+2y+1=0) sum+; if(chessx+2y-1=0) sum+; if(chessx-2y-1=0) sum+; if(chessx-1y+2=0) sum+; if(chessx+1y-2=0) sum+; if(chessx+1y+2=0) sum+; return(sum); /*每找到一個位置sum+，最后返回sum值就是在(x,y)處可走的位置數(shù)*/ int test(int x,int y) /*test函數(shù)測試第step步為(x,y)位置的情況下，是否可以走完棋盤，如果可以返回1,否則返回0*/ int s9,a9; int min,i,j,k; count+;

13、step+; chessxy=step; if(step=m*n) return(1); /*如果已經(jīng)走到了m×n的話，表示滿足結(jié)束條件，返回1 */ s1=h(x-2,y+1);/*統(tǒng)計(x，y)處的下一步的八個位置的sum值*/ s2=h(x-1,y+2); s3=h(x+1,y+2); s4=h(x+2,y+1); s5=h(x+2,y-1); s6=h(x+1,y-2); s7=h(x-1,y-2); s8=h(x-2,y-1); for(j=1;j<=8;j+) /*使用冒泡排序，對下一步的八個規(guī)則的sum從小到大排序*/ min=9; aj=1; for(i=1;i

14、<=8;i+) if(si<min) min=si; aj=i; /*排序結(jié)果存放在a數(shù)組中*/ k=i; sk=9; for(i=1;i<=8;i+) /*這個循環(huán)按sum從小到大的順序依次調(diào)用相應(yīng)的規(guī)則 */ if(ai=1) if(f1(x,y)=1) return(1); if(ai=2) if(f2(x,y)=1) return(1); if(ai=3) if(f3(x,y)=1) return(1); if(ai=4) if(f4(x,y)=1) return(1); if(ai=5) if(f5(x,y)=1) return(1); if(ai=6) if(f6

15、(x,y)=1) return(1); if(ai=7) if(f7(x,y)=1) return(1); if(ai=8) if(f8(x,y)=1) return(1); step-; /* 如果按任意八個規(guī)則都無法走滿棋盤則回退，*/ chessxy=0; /* 把棋盤恢復(fù)狀態(tài)，并返回0*/ return(0); /*按規(guī)則1走步 */ int f1(int x,int y) if(chessx-2y+1=0) if(test(x-2,y+1)=1) return(1); return(0); /*按規(guī)則2走步 */ int f2(int x,int y) if(chessx-1y+2=

16、0) if(test(x-1,y+2)=1) return(1); return(0); /*按規(guī)則3走步 */ int f3(int x,int y) if(chessx+1y+2=0) if(test(x+1,y+2)=1) return(1); return(0); /*按規(guī)則4走步 */ int f4(int x,int y) if(chessx+2y+1=0) if(test(x+2,y+1)=1) return(1); return(0); /*按規(guī)則5走步 */ int f5(int x,int y) if(chessx+2y-1=0) if(test(x+2,y-1)=1) r

17、eturn(1); return(0); /*按規(guī)則6走步 */ int f6(int x,int y) if(chessx+1y-2=0) if(test(x+1,y-2)=1) return(1); return(0); /*按規(guī)則7走步 */ int f7(int x,int y) if(chessx-1y-2=0) if(test(x-1,y-2)=1) return(1); return(0); /*按規(guī)則8走步 */ int f8(int x,int y) if(chessx-2y-1=0) if(test(x-2,y-1)=1) return(1); return(0); voi

18、d main() int i,j,x0,y0,q=0,cou; while(q=0) system("cls"); printf("n-歡 迎 使 用 馬 踏 棋 盤 演 示 系 統(tǒng)-n"); printf("nn 按 回 車 鍵 進 入 演 示 系 統(tǒng) nnnn"); getchar(); system("cls"); printf("n-歡 迎 使 用 馬 踏 棋 盤 演 示 系 統(tǒng)-n"); for(i=0;i<23;i+) /* 初始化棋盤大小 */ for(j=0;j<23

19、;j+) chessij=-1; printf("n輸入棋盤行數(shù):"); scanf("%d",&m); printf("n輸入棋盤列數(shù):"); scanf("%d",&n); /* 輸入目標(biāo)棋盤的大小 */ for(i=2;i<=m+1;i+) for(j=2;j<=n+1;j+) chessij=0; printf("n起始點行坐標(biāo):"); scanf("%d",&x0); printf("n起始點列坐標(biāo):"); s

20、canf("%d",&y0); /* 取得初始位置 */ if(x0>=1&&x0<=m)&&(y0>=1&&y0<=n) /* 判斷輸入是否有效*/ if(test(x0+1,y0+1)=1)/*測試是否可以走完，如果可以則回車，動態(tài)演示；否則退出，重新輸入*/ printf("n可以全部走完，過程按回車鍵演示過程=>"); getchar(); for(cou=1;cou<=count;cou+)/*動態(tài)顯示行走過程，每回車一次，顯示下一步馬的位置*/ get

21、char(); system("cls"); printf("n-歡 迎 使 用 馬 踏 棋 盤 演 示 系 統(tǒng)-n"); printf("正在為您演示?n"); printf("第%d步：",cou); for(i=2;i<=m+1;i+) printf("n"); for(j=2;j<=n+1;j+) if(chessij=0) printf("");/*如果該點已經(jīng)走過，就在這點打印""*/ else if(cou=chessij) pr

22、intf("馬");/*如果在這一步馬在該點，則在這點打印"馬"*/ chessij=0; else if(i=2&&j=2) printf(""); if(i=2&&j>2&&j<n+1) printf(""); if(i=2&&j=n+1) printf(""); if(i>2&&i<m+1&&j=2) printf(""); if(i=m+1&

23、&j=2) printf(""); if(i=m+1&&j>2&&j<n+1) printf(""); if(i=m+1&&j=n+1) printf(""); if(i>2&&i<m+1&&j=n+1) printf(""); if(i>2&&i<m+1&&j>2&&j<n+1) printf("");/*打印棋

24、盤*/ if(cou<m*n) printf("n按回車鍵演示下一步"); else printf("n演示完畢!按任意鍵退出.n"); q=1; else printf("n無法全部走完!按回車鍵重新輸入!n"); getchar(); getchar(); count=0; else printf("n輸入錯誤!超過范圍!n"); printf("n按回車鍵重新輸入!n"); getchar(); getchar(); 4. 結(jié)果與結(jié)論4.1輸入初始數(shù)據(jù)4.2 判斷能否遍歷4.3 動態(tài)

25、演示5. 收獲與致謝這次課程設(shè)計，讓我更加深刻了解數(shù)據(jù)結(jié)構(gòu)里的優(yōu)先深度遍歷和回溯法，對數(shù)據(jù)結(jié)構(gòu)的應(yīng)用有了一定的提高，在設(shè)計過程中遇到一些思路上的困擾，但是通過老師同學(xué)的幫助，都成功一一克服。這次的課程設(shè)計給我相當(dāng)?shù)幕A(chǔ)知識，為我以后工作打下了嚴(yán)實的基礎(chǔ)。再次感謝小組同學(xué)的辛勤付出，以及老師的無私幫助6. 參考文獻(xiàn)1.c程序設(shè)計（第四版），譚浩強 清華大學(xué)出版社2.數(shù)據(jù)結(jié)構(gòu)（c語言版），嚴(yán)蔚敏 吳偉民 清華大學(xué)出版社指導(dǎo)教師評語：1、課程設(shè)計報告：a、內(nèi)容： 不完整 完整 詳細(xì) b、方案設(shè)計： 較差 合理 非常合理c、實現(xiàn)： 未實現(xiàn) 部分實現(xiàn) 全部實現(xiàn) d、文檔格式： 不規(guī)范 基本規(guī)范 規(guī)范 2

26、、出勤： 全勤 缺勤 次3、答辯： a、未能完全理解題目，答辯情況較差 b、部分理解題目，部分問題回答正確 c、理解題目較清楚，問題回答基本正確 d、理解題目透徹，問題回答流利 課程設(shè)計報告成績： ，占總成績比例： 50% 課程設(shè)計其它環(huán)節(jié)成績：環(huán)節(jié)名稱： 出勤 ，成績： ，占總成績比例： 20% 環(huán)節(jié)名稱： 答辯 ，成績： ，占總成績比例： 30% 總 成 績： 指導(dǎo)教師簽字：年 月 日7. 附件源程序：#include <stdio.h> #include <iostream> int chess2323,step=0,m=0,n=0,count=0; /* che

27、ss2323用來表示棋盤； step是步驟數(shù)； m和n是棋盤的規(guī)格行和列； count是運算次數(shù)；*/ int f1(int x,int y),f2(int x,int y),f3(int x,int y),f4(int x,int y),f5(int x,int y),f6(int x,int y),f7(int x,int y),f8(int x,int y); /*申明函數(shù)，這些函數(shù)就是用來表示八種走的規(guī)則*/ int h(int x,int y) /*h函數(shù)用來測試（x，y）位置處，下一步可以跳的位置數(shù)，返回值為sum */ int sum; /*用來記錄下一步可以跳的位置數(shù)*/ su

28、m=0; if(chessx-1y-2=0) sum+; if(chessx-2y+1=0) sum+; if(chessx+2y+1=0) sum+; if(chessx+2y-1=0) sum+; if(chessx-2y-1=0) sum+; if(chessx-1y+2=0) sum+; if(chessx+1y-2=0) sum+; if(chessx+1y+2=0) sum+; return(sum); /*每找到一個位置sum+，最后返回sum值就是在(x,y)處可走的位置數(shù)*/ int test(int x,int y) /*test函數(shù)測試第step步為(x,y)位置的情況下

29、，是否可以走完棋盤，如果可以返回1,否則返回0*/ int s9,a9; int min,i,j,k; count+; step+; chessxy=step; if(step=m*n) return(1); /*如果已經(jīng)走到了m×n的話，表示滿足結(jié)束條件，返回1 */ s1=h(x-2,y+1);/*統(tǒng)計(x，y)處的下一步的八個位置的sum值*/ s2=h(x-1,y+2); s3=h(x+1,y+2); s4=h(x+2,y+1); s5=h(x+2,y-1); s6=h(x+1,y-2); s7=h(x-1,y-2); s8=h(x-2,y-1); for(j=1;j<

30、=8;j+) /*使用冒泡排序，對下一步的八個規(guī)則的sum從小到大排序*/ min=9; aj=1; for(i=1;i<=8;i+) if(si<min) min=si; aj=i; /*排序結(jié)果存放在a數(shù)組中*/ k=i; sk=9; for(i=1;i<=8;i+) /*這個循環(huán)按sum從小到大的順序依次調(diào)用相應(yīng)的規(guī)則 */ if(ai=1) if(f1(x,y)=1) return(1); if(ai=2) if(f2(x,y)=1) return(1); if(ai=3) if(f3(x,y)=1) return(1); if(ai=4) if(f4(x,y)=1)

31、 return(1); if(ai=5) if(f5(x,y)=1) return(1); if(ai=6) if(f6(x,y)=1) return(1); if(ai=7) if(f7(x,y)=1) return(1); if(ai=8) if(f8(x,y)=1) return(1); step-; /* 如果按任意八個規(guī)則都無法走滿棋盤則回退，*/ chessxy=0; /* 把棋盤恢復(fù)狀態(tài)，并返回0*/ return(0); /*按規(guī)則1走步 */ int f1(int x,int y) if(chessx-2y+1=0) if(test(x-2,y+1)=1) return(1)

32、; return(0); /*按規(guī)則2走步 */ int f2(int x,int y) if(chessx-1y+2=0) if(test(x-1,y+2)=1) return(1); return(0); /*按規(guī)則3走步 */ int f3(int x,int y) if(chessx+1y+2=0) if(test(x+1,y+2)=1) return(1); return(0); /*按規(guī)則4走步 */ int f4(int x,int y) if(chessx+2y+1=0) if(test(x+2,y+1)=1) return(1); return(0); /*按規(guī)則5走步 */

33、 int f5(int x,int y) if(chessx+2y-1=0) if(test(x+2,y-1)=1) return(1); return(0); /*按規(guī)則6走步 */ int f6(int x,int y) if(chessx+1y-2=0) if(test(x+1,y-2)=1) return(1); return(0); /*按規(guī)則7走步 */ int f7(int x,int y) if(chessx-1y-2=0) if(test(x-1,y-2)=1) return(1); return(0); /*按規(guī)則8走步 */ int f8(int x,int y) if(

34、chessx-2y-1=0) if(test(x-2,y-1)=1) return(1); return(0); void main() int i,j,x0,y0,q=0,cou; while(q=0) system("cls"); printf("n-歡 迎 使 用 馬 踏 棋 盤 演 示 系 統(tǒng)-n"); printf("nn 按 回 車 鍵 進 入 演 示 系 統(tǒng) nnnn"); getchar(); system("cls"); printf("n-歡 迎 使 用 馬 踏 棋 盤 演 示 系 統(tǒng)

35、-n"); for(i=0;i<23;i+) /* 初始化棋盤大小 */ for(j=0;j<23;j+) chessij=-1; printf("n輸入棋盤行數(shù):"); scanf("%d",&m); printf("n輸入棋盤列數(shù):"); scanf("%d",&n); /* 輸入目標(biāo)棋盤的大小 */ for(i=2;i<=m+1;i+) for(j=2;j<=n+1;j+) chessij=0; printf("n起始點行坐標(biāo):"); sc

36、anf("%d",&x0); printf("n起始點列坐標(biāo):"); scanf("%d",&y0); /* 取得初始位置 */ if(x0>=1&&x0<=m)&&(y0>=1&&y0<=n) /* 判斷輸入是否有效*/ if(test(x0+1,y0+1)=1)/*測試是否可以走完，如果可以則回車，動態(tài)演示；否則退出，重新輸入*/ printf("n可以全部走完，過程按回車鍵演示過程=>"); getchar(); for(cou=1;cou<=count;cou+