数据结构课程设计马的遍历(共29页)

1、课 程 设 计 说 明 书课程名称： 数据结构 设计题目： 马的遍历 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 指导教师： 2015 年 6 月 7 日课 程 设 计 任 务 书设计题目马的遍历学生姓名所在院系计算机科学与信息工程学院专业、年级、班设计要求：任意行列数的棋盘中，马只能走“日”字。马从任意位置处出发，把棋盘的每一格都走一次，且只走一次。要求在屏幕上画出棋盘和马所有经过的路径。学生应完成的工作：1.分析题目要求2.利用数据结构和c语言知识找出实现方法3.编程完成实现4.按要求撰写课程设计报告和设计总结。参考文献阅读：1.c程序设计（第四版），谭浩强 清华

2、大学出版社2.数据结构（c语言版），严蔚敏 吴伟民 清华大学出版社工作计划：1. 接到题目后用课余时间设计程序，2. 第14周上机调试通过后，答辩，交报告（具体时间由各任课教师决定）。任务下达日期： 2015年 4 月 28 日 任务完成日期： 2015年 6 月 6 日指导教师（签名）： 学生（签名）： 马的遍历摘 要：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点 可以用一个二维数组chess来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。对于动态演示

3、问题，只要在“马”的位置显示“马”，已经走过的位置显示“”，未走过的位置显示“”“ ”“ ”“”等制表符，然后清屏，显示下一步，再清屏，依次类推。关键词：深度优先遍历；回溯法；数组存储棋盘；动态演示；目 录1. 设计背景11.1问题描述11.2基本要求12. 设计方案12.1问题分析和任务定义12.2概要设计和数据结构的选择23. 方案实施33.1数据结构设计33.2功能函数设计43.3编码实现54. 结果与结论144.1输入初始数据144.2判断能否遍历144.3动态演示145. 收获与致谢156参考文献151. 设计背景1.1 问题描述：中国象棋是10*9的棋盘，马的走法是“马走日”，这里

4、忽略了“蹩脚马”的情况，使马的遍历问题简单化。马在棋盘上遍历采用算法当中的优先算法和回溯法；从入口出发，按某一方向向前探索，若能走通并且从未走过，即某处可到达，则到达新店，否则探索下一个方向；如果发生“阻塞”的情况，就是后面走不通的情况，则沿原路返回到前一点，换一个方向再继续试探，知道找到一条通路，或无路可走又返回到入口点。期盼中马的遍历采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。1.2 基本要求：棋盘有10行9列，利用chess来表示一个棋盘，chessij=0或1；

5、其中0表示通路，1表示不通，当从某点向下试探时，中间点的8个方向可以试探；棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了保证边缘点也有八个方向可以走，使问题能够简单化，不用再判断当前点的试探方向有几个。2.设计方案2.1问题分析和任务定义：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最 多有八个，即假设马所在点的坐标为（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、图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点 可以用一个二维数组chess来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。 对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“”，未走过的位置显示“”“ ”“ ”“”等制表符，然后清屏，显示下一步，再清屏，依次类推。 棋盘的规格限制在20*20以内，起始点当然不能超出棋盘的范围，每输入一组数据，首先判断是否可以全部走完，如果可以，则动态演示，否则重新输入数据。 2.2概要设计和数据结构的选择：该算法需要定义一个二维数组chess用来表示棋盘，整形变量step存放步骤 号，count存

7、放运算次数。 定义8个函数(f1,f2,f3,f4,f5,f6,f7,f8)用来表示按8种规则走，定义一个h函数用来统计8种规则中有几种是可走的，再定义一个test函数用来测试是否可以走完，如果可以走完则返回值为1，否则返回0。 test函数和f1,f2,f3,f4,f5,f6,f7,f8八个函数是一个递归调用关系。然后通过主函数调用test函数，实现动态演示功能。具体过程见下图：3. 方案实施3.1数据结构设计：同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围个加了两层“墙”。具体数据结构定义如下：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); /*申明函数，这些函数就是用来表示八种走的规则*/int h(int x,int y) /*h函数用来测试（x，y）位置处，下一步可以跳的位置数，返回值为sum */ int sum; /*用来记录下一步可以跳的位置数*/ 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)处可走的位置数*/ 3.2功能函数设计：（1）测试函数模块int test(int x,int y)/*test函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1,否则返回0

10、*/ （2）主函数：void main()进入主函数后提示用户输入棋盘大小，只能输入小于23的数，其他的数字则提示输入错误，重新输入。然后提示输入起点位置，这里的起点位置就是日常生活观念中的顺序，开始点是(1,1),而不是数组中的初始位置(0,0),输入错误则提示重新输入。3.3编码实现：#include <stdio.h> #include <iostream> int chess2323,step=0,m=0,n=0,count=0; /* chess2323用来表示棋盘； step是步骤数； m和n是棋盘的规格行和列； count是运算次数；*/ 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); /*申明函数，这些函数就是用来表示八种走的规则*/ int h(int x,int y) /*h函数用来测试（x，y）位置处，下一步可以跳的位置数，返回值为sum */ int sum; /*用来记录下一步可以跳的位置数*/ 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)处可走的位置数*/ int test(int x,int y) /*test函数测试第step步为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1,否则返回0*/ int s9,a9; int min,i,j,k; count+;

13、step+; chessxy=step; if(step=m*n) return(1); /*如果已经走到了m×n的话，表示满足结束条件，返回1 */ s1=h(x-2,y+1);/*统计(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+) /*使用冒泡排序，对下一步的八个规则的sum从小到大排序*/ min=9; aj=1; for(i=1;i

14、<=8;i+) if(si<min) min=si; aj=i; /*排序结果存放在a数组中*/ k=i; sk=9; for(i=1;i<=8;i+) /*这个循环按sum从小到大的顺序依次调用相应的规则 */ 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-; /* 如果按任意八个规则都无法走满棋盘则回退，*/ chessxy=0; /* 把棋盘恢复状态，并返回0*/ return(0); /*按规则1走步 */ int f1(int x,int y) if(chessx-2y+1=0) if(test(x-2,y+1)=1) return(1); return(0); /*按规则2走步 */ int f2(int x,int y) if(chessx-1y+2=

16、0) if(test(x-1,y+2)=1) return(1); return(0); /*按规则3走步 */ int f3(int x,int y) if(chessx+1y+2=0) if(test(x+1,y+2)=1) return(1); return(0); /*按规则4走步 */ int f4(int x,int y) if(chessx+2y+1=0) if(test(x+2,y+1)=1) return(1); return(0); /*按规则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); /*按规则6走步 */ int f6(int x,int y) if(chessx+1y-2=0) if(test(x+1,y-2)=1) return(1); return(0); /*按规则7走步 */ int f7(int x,int y) if(chessx-1y-2=0) if(test(x-1,y-2)=1) return(1); return(0); /*按规则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-欢 迎 使 用 马 踏 棋 盘 演 示 系 统-n"); printf("nn 按 回 车 键 进 入 演 示 系 统 nnnn"); getchar(); system("cls"); printf("n-欢 迎 使 用 马 踏 棋 盘 演 示 系 统-n"); for(i=0;i<23;i+) /* 初始化棋盘大小 */ for(j=0;j<23

19、;j+) chessij=-1; printf("n输入棋盘行数:"); scanf("%d",&m); printf("n输入棋盘列数:"); 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("n起始点列坐标:"); s

20、canf("%d",&y0); /* 取得初始位置 */ if(x0>=1&&x0<=m)&&(y0>=1&&y0<=n) /* 判断输入是否有效*/ if(test(x0+1,y0+1)=1)/*测试是否可以走完，如果可以则回车，动态演示；否则退出，重新输入*/ printf("n可以全部走完，过程按回车键演示过程=>"); getchar(); for(cou=1;cou<=count;cou+)/*动态显示行走过程，每回车一次，显示下一步马的位置*/ get

21、char(); system("cls"); printf("n-欢 迎 使 用 马 踏 棋 盘 演 示 系 统-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("");/*如果该点已经走过，就在这点打印""*/ 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. 结果与结论4.1输入初始数据4.2 判断能否遍历4.3 动态

25、演示5. 收获与致谢这次课程设计，让我更加深刻了解数据结构里的优先深度遍历和回溯法，对数据结构的应用有了一定的提高，在设计过程中遇到一些思路上的困扰，但是通过老师同学的帮助，都成功一一克服。这次的课程设计给我相当的基础知识，为我以后工作打下了严实的基础。再次感谢小组同学的辛勤付出，以及老师的无私帮助6. 参考文献1.c程序设计（第四版），谭浩强 清华大学出版社2.数据结构（c语言版），严蔚敏 吴伟民 清华大学出版社指导教师评语：1、课程设计报告：a、内容： 不完整 完整 详细 b、方案设计： 较差 合理 非常合理c、实现： 未实现 部分实现 全部实现 d、文档格式： 不规范 基本规范 规范 2

26、、出勤： 全勤 缺勤 次3、答辩： a、未能完全理解题目，答辩情况较差 b、部分理解题目，部分问题回答正确 c、理解题目较清楚，问题回答基本正确 d、理解题目透彻，问题回答流利 课程设计报告成绩： ，占总成绩比例： 50% 课程设计其它环节成绩：环节名称： 出勤 ，成绩： ，占总成绩比例： 20% 环节名称： 答辩 ，成绩： ，占总成绩比例： 30% 总 成 绩： 指导教师签字：年 月 日7. 附件源程序：#include <stdio.h> #include <iostream> int chess2323,step=0,m=0,n=0,count=0; /* che

27、ss2323用来表示棋盘； step是步骤数； m和n是棋盘的规格行和列； count是运算次数；*/ 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); /*申明函数，这些函数就是用来表示八种走的规则*/ int h(int x,int y) /*h函数用来测试（x，y）位置处，下一步可以跳的位置数，返回值为sum */ int sum; /*用来记录下一步可以跳的位置数*/ 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)处可走的位置数*/ int test(int x,int y) /*test函数测试第step步为(x,y)位置的情况下

29、，是否可以走完棋盘，如果可以返回1,否则返回0*/ int s9,a9; int min,i,j,k; count+; step+; chessxy=step; if(step=m*n) return(1); /*如果已经走到了m×n的话，表示满足结束条件，返回1 */ s1=h(x-2,y+1);/*统计(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+) /*使用冒泡排序，对下一步的八个规则的sum从小到大排序*/ min=9; aj=1; for(i=1;i<=8;i+) if(si<min) min=si; aj=i; /*排序结果存放在a数组中*/ k=i; sk=9; for(i=1;i<=8;i+) /*这个循环按sum从小到大的顺序依次调用相应的规则 */ 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-; /* 如果按任意八个规则都无法走满棋盘则回退，*/ chessxy=0; /* 把棋盘恢复状态，并返回0*/ return(0); /*按规则1走步 */ int f1(int x,int y) if(chessx-2y+1=0) if(test(x-2,y+1)=1) return(1)

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

33、 int f5(int x,int y) if(chessx+2y-1=0) if(test(x+2,y-1)=1) return(1); return(0); /*按规则6走步 */ int f6(int x,int y) if(chessx+1y-2=0) if(test(x+1,y-2)=1) return(1); return(0); /*按规则7走步 */ int f7(int x,int y) if(chessx-1y-2=0) if(test(x-1,y-2)=1) return(1); return(0); /*按规则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-欢 迎 使 用 马 踏 棋 盘 演 示 系 统-n"); printf("nn 按 回 车 键 进 入 演 示 系 统 nnnn"); getchar(); system("cls"); printf("n-欢 迎 使 用 马 踏 棋 盘 演 示 系 统

35、-n"); for(i=0;i<23;i+) /* 初始化棋盘大小 */ for(j=0;j<23;j+) chessij=-1; printf("n输入棋盘行数:"); scanf("%d",&m); printf("n输入棋盘列数:"); scanf("%d",&n); /* 输入目标棋盘的大小 */ for(i=2;i<=m+1;i+) for(j=2;j<=n+1;j+) chessij=0; printf("n起始点行坐标:"); sc

36、anf("%d",&x0); printf("n起始点列坐标:"); scanf("%d",&y0); /* 取得初始位置 */ if(x0>=1&&x0<=m)&&(y0>=1&&y0<=n) /* 判断输入是否有效*/ if(test(x0+1,y0+1)=1)/*测试是否可以走完，如果可以则回车，动态演示；否则退出，重新输入*/ printf("n可以全部走完，过程按回车键演示过程=>"); getchar(); for(cou=1;cou<=count;cou+