數(shù)據(jù)結構課程設計馬的遍歷

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課 程 設 計 說 明 書課程名稱： 數(shù)據(jù)結構 設計題目： 馬的遍歷 院 系： 計算機科學與信息工程學院 學生姓名： 學 號： 專業(yè)班級： 指導教師： 2015 年 6 月 7 日專心-專注-專業(yè)課 程 設 計 任 務 書設計題目馬的遍歷學生姓名所在院系計算機科學與信息工程學院專業(yè)、年級、班設計要求：任意行列數(shù)的棋盤中，馬只能走“日”字。馬從任意位置處出發(fā)，把棋盤的每一格都走一次，且只走一次。要求在屏幕上畫出棋盤和馬所有經(jīng)過的路徑。學生應完成的工作：1.分析題目要求2.利用數(shù)據(jù)結構和c語言知識找出實現(xiàn)方法3.編程完成實現(xiàn)4.按要求撰寫課程設計報告和設計總結。參考文獻閱

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

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

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

5、s來表示一個棋盤，chessij=0或1；其中0表示通路，1表示不通，當從某點向下試探時，中間點的8個方向可以試探；棋盤采用數(shù)組形式，并且這里的數(shù)組比棋盤的數(shù)組規(guī)模稍大，因為為了保證邊緣點也有八個方向可以走，使問題能夠簡單化，不用再判斷當前點的試探方向有幾個。2.設計方案2.1問題分析和任務定義：中國象棋中馬采用“日”字走法，對棋盤上馬所在的結點，一步內(nèi)到達的結點最 多有八個，即假設馬所在點的坐標為（i，j），那么其它八個結點的坐標為（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)先遍歷，以馬所在點為初始點對整個棋盤進行遍歷。然后按遍歷的順序輸出結點 可以用一個二維數(shù)組chess來表示棋盤，一開始用來存放步驟號，若走過了則把它賦值為0。 對于動態(tài)演示問題，只要在“馬”的位置顯示“馬”，已經(jīng)走過的位置顯示“”，未走過的位置顯示“”“ ”“ ”“”等制表符，然后清屏，顯示下一步，再清屏，依次類推。 棋盤的規(guī)格限制在20*20以內(nèi)，起始點當然不能超出棋盤的范圍，每輸入一組數(shù)據(jù)，首先判斷是否可以全部走完，如果可以，則動態(tài)演示，否則重新輸入數(shù)據(jù)。 2.2概要設計和數(shù)據(jù)結構的選擇：該算法需要定義一個二維數(shù)組chess用來表示棋盤，

7、整形變量step存放步驟 號，count存放運算次數(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)用關系。然后通過主函數(shù)調(diào)用test函數(shù)，實現(xiàn)動態(tài)演示功能。具體過程見下圖：3. 方案實施3.1數(shù)據(jù)結構設計：同上面述，棋盤采用數(shù)組形式，并且這里的數(shù)組比棋盤的數(shù)組規(guī)模稍大，因為為了判斷的方便，這里在棋盤周圍個加了兩層“墻”。具體數(shù)據(jù)結構定義如下：i

8、nt chess2323 /* chess2323用來表示棋盤； 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=

9、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ù)*/ 3.2功能函數(shù)設計：（1）測試函數(shù)模塊int test(int x,int y)/*test函數(shù)測試第step步為(x,y)位置的情況下，是

10、否可以走完棋盤，如果可以返回1,否則返回0*/ （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ī)格行和列； c

11、ount是運算次數(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ù)*/ sum=0; if(chessx-1y-2=0) sum+; if(chessx-

12、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)位置的情況下，是否可以走完棋盤，如果可以返回1,否則返回0*/ int s9,a9; in

13、t min,i,j,k; count+; step+; chessxy=step; if(step=m*n) return(1); /*如果已經(jīng)走到了m×n的話，表示滿足結束條件，返回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從小到大排序*/ m

14、in=9; aj=1; for(i=1;i<=8;i+) if(si<min) min=si; aj=i; /*排序結果存放在a數(shù)組中*/ k=i; sk=9; for(i=1;i<=8;i+) /*這個循環(huán)按sum從小到大的順序依次調(diào)用相應的規(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) retu

15、rn(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; /* 把棋盤恢復狀態(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,i

16、nt 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走步 */ int f5(int x,int y) if(chessx+2y-1=0)

17、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(chessx-2y-1=0) if(test(x-2,y-1)=1) retu

18、rn(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)-n"); for(i=0;i<23;i+) /* 初始化棋盤

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

20、ot;n起始點列坐標:"); 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+)/*動態(tài)顯示行走過程，

21、每回車一次，顯示下一步馬的位置*/ getchar(); 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)走過，就在這點打印""*/ el

22、se if(cou=chessij) printf("馬");/*如果在這一步馬在該點，則在這點打印"馬"*/ 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("&

23、quot;); if(i=m+1&&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) print

24、f("");/*打印棋盤*/ 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. 結果與結論4.1輸

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

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

27、0,n=0,count=0; /* chess2323用來表示棋盤； 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;

28、/*用來記錄下一步可以跳的位置數(shù)*/ sum=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函

29、數(shù)測試第step步為(x,y)位置的情況下，是否可以走完棋盤，如果可以返回1,否則返回0*/ int s9,a9; int min,i,j,k; count+; step+; chessxy=step; if(step=m*n) return(1); /*如果已經(jīng)走到了m×n的話，表示滿足結束條件，返回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-

30、2,y-1); for(j=1;j<=8;j+) /*使用冒泡排序，對下一步的八個規(guī)則的sum從小到大排序*/ min=9; aj=1; for(i=1;i<=8;i+) if(si<min) min=si; aj=i; /*排序結果存放在a數(shù)組中*/ k=i; sk=9; for(i=1;i<=8;i+) /*這個循環(huán)按sum從小到大的順序依次調(diào)用相應的規(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); i

31、f(ai=4) if(f4(x,y)=1) 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; /* 把棋盤恢復狀態(tài)，并返回0*/ return(0); /*按規(guī)則1走步 */ int f1(int x,int y) if(chessx-2y+1=0) if(test(

32、x-2,y+1)=1) return(1); 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); r

33、eturn(0); /*按規(guī)則5走步 */ 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走步 */ in

34、t f8(int x,int y) if(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-歡

35、迎 使 用 馬 踏 棋 盤 演 示 系 統(tǒng)-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); /* 輸入目標棋盤的大小 */ for(i=2;i<=m+1;i+) for(j=2;j<=n+1;j+) chessij=0; printf(&quo

36、t;n起始點行坐標:"); scanf("%d",&x0); printf("n起始點列坐標:"); 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;