数据结构课程设计马的遍历

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

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

3、经走过的位置显示“”，未走过的位置显示“厂”“ 丁”“ n 卜” 等制表符，然后清屏，显示下一步，再清屏，依次类推。关键词：深度优先遍历；回溯法；数组存储棋盘；动态演示;1. 设计背景11.1问题描述11. 2基本要求12. 设计方案12.1问题分析和任务定义12. 2概要设计和数据结构的选择23. 方案实施331数据结构设计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=o或1；其中0

5、表示通路, 1表示不通，当从某点向下试探吋，中间点的8个方向可以试探；棋盘采用数组形式， 并且这里的数组比棋盘的数组规模稍大，因为为了保证边缘点也有八个方向可以走，使 问题能够简单化，不用再判断当前点的试探方向有儿个。2. 设计方案2.1问题分析和任务定义：中国彖棋屮马采用“口”字走法，对棋盘上马所在的结点，一步内到达的结点最多有 八个，即假设马所在点的坐标为(i, j),那么其它八个结点的坐标为(i+l,j+2),(i+2,j+l), (i+2,jl) , (i+l,j2), (i-l,j-2) , (i2,jl) , (i2,j+l) , (i-l,j+2)把这些点看作马所在点的邻接点，所

6、以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋 盘进行遍历。然后按遍历的顺序输岀结点 可以用一个二维数组chess来表示棋盘， 一开始用來存放步骤号，若走过了则把它赋值为0。 对于动态演示问题，只要在“马” 的位置显示“马”，已经走过的位置显示“ ”，未走过的位置显示“厂” “ 丁” “ -i ” “卜”等制表符，然后清屏，显示下一步，再清屏，依次类推。棋盘的规格限制在20*20 以内，起始点当然不能超出棋盘的范围，每输入一组数据，首先判断是否可以全部走完, 如果可以，则动态演示，否则重新输入数据。2. 2概要设计和数据结构的选择：该算法需要定义一个二维数组chess用來表示棋盘，

7、整形变量step存放步骤号, count存放运算次数。 定义8个函数（fl,f2,f3,f4,f5,f6,f7,用来表示按8种规则走，定 义一个h函数用来统计8种规则中有几种是可走的，再定义一个test函数用来测试是否 可以走完，如果可以走完则返回值为1,否则返回0o test函数和fl,f2,f3,f4,f5,f6,f7,f8 八个函数是一个递归调用关系。然后通过主函数调用test函数，实现动态演示功能。具 体过程见下图：3. 方案实施3.1数据结构设计：同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍人，因为 为了判断的方便，这里在棋盘周围个加了两层“墙”。具体数据结构定义如下

8、：int chess2323/* chess 23 23用来表示棋盘；int fl (int x, int y), f2(int x, int y)，f3(int x, int y), f4(int x, inty), 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二

9、0;if (chessxly-2=0)sum+;if (chessx-2y+l=o)sum+;if (chess x+2 y+l=o)sum+;if(chessx+2y-1二二0)sum+;if (chessx-2 yt二二0)sum+;if (chessxly+2=0)sum+;if (chessx+ly-2=0)sum+;if (chess x+l y+2=0)sum+;return (sum);/*每找到一个位置sum+,最后返回sum值就是在(x, y)处可走的位置数*/3. 2功能函数设计：(1)测试函数模块 int test(int x,int y)/*test函数测试第step步

10、为(x,y)位置的情况下，是否可以走完棋盘，如果可以返回1,否则返 回0*/(2)主函数：void main()进入主函数后提示用户输入棋盘大小，只能输入小于23的数，其他的数字则提示输入错误，重 新输入。然后提示输入起点位置，这里的起点位置就是日常生活观念屮的顺序，开始点是(1,1),而不 是数组中的初始位置(0,0),输入错误则提示重新输入。3. 3编码实现:jtincludc <stdio. h>itinclude <iostream>int chess2323,step=0, m=0, n=0, count二0;/* chess23 23用来表示棋盘；step是

11、步骤数；m和n是棋盘的规格行和列；count是运算次数；*/int fl(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;i

12、f(chessx-1y-2=0)sum+;if (chessx-2y+1二二0)sum+;if (chessx+2y+l=0)sum+;if (chessx+2y-l=0)sum+;if (chess x-2 yt=0)suin+;if (chess xt y+2二二0)sum+;if (chess x+1 y-2=0)sum+;if (chessx+1y+2=0)suin+;return(sum);/*每找到一个位置sum+,最后返回sum值就是在(x, y)处可走的位置数*/int test (int x, int y) atest函数测试第step步为(x, y)位置的情况下，是 否可以

13、走完棋盘，如果可以返回1,否则返回0*/int s9, a9;int min, i, j, k;count+;step+;chessxy二step;if (stcp=m*n)return(1) ; /*如果已经走到了 mxn的话，表示满足结束条件，返冋1 */sl二h(x-2, y+1) ;/*统计(x, y)处的下一步的八个位置的sum值*/ s2=h(x-l,y+2);s3二 h(x+l,y+2);s4二 h(x+2, y+1);s5二h(x+2, y-1);s =h (x+1, y-2);s7=h(x-1, y-2);s =h (x-2, y-1);for(j=l; j<=8; j

14、+)/*使用冒泡排序，对下一步的八个规则的sum从小到大排序*/min=9;aj=l;for(i=l;i<=8;i+)if (sim in)min=si;aj=i; /*排序结果存放在er数组中*/k二 i;sk=9; for (i=l; i<=8; i+)/*这个循环按sum从小到大的顺序依次调用相应的规则*/if (ai二二 1)if (fl (x, y)=l)return(l);if (ai=2)if(f2(x, y)二二 1)return (1);if (ai=3)if (f3(x, y)=l)rcturn(l);if (ai=4)if (f4(x, y)二二 1)retu

15、rn (1);辻(ai=5)if(f5 (x, y)=l)return (1);if (ai=6)if (f6 (x, y) =1)return (1);if(ai=7)if(f7(x, y)=l) return (1);if (ai=8)if(f8 (x, y)=l) return (1);)step一一;/*如果按任意八个规则都无法走满棋盘则回退，*/ chessxy二0;/*把棋盘恢复状态，并返回0*/return (0);/*按规则1走步*/int fl (int x, int y)if (chessx2y+l=0)if(test(x2, y+1)二二1)return (1);retu

16、rn (0);/*按规则2走步*/int f2(int x, int y)if (chess xt y+2=0)if(test(xl, 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)=l) return(l);return (0);/*按规则4走步*/int f4(int x, int y)if (chessx+2y+l=0)if (test(x+2, y+1)二二1) return(1);return (0);/*按规则5走步*/int f5

17、(int x, int y)if (chess x+2 yt=0)if (test (x+2, yt) = l) return (1);return (0);/*按规则6走步*/int f6(int x, int y)if (chessx+1y2=0)if (test (x+1, y-2)=l)return(l);return (0);/*按规则7走步*/int f7(int x, int y)if (chessxt y-2二二0)if (test (x-1, y-2) = 1) return仃);return(0);/*按规则8走步*/int f8 (int x, int y)if(ches

18、sx-2y-1二二0)if (test (x-2, y-l)=l) return (1);return (0);void main()int i, j, xo, yo, q=0, cou;while (q=0)system(cls);printf（，zn欢迎使用马踏棋盘演示系统）；printf （，znn按回车键进入演示系统nnnn");gctchar ();欢迎使用马踏棋盘演system（cls）； printf （n示系统n)；for(i=0;i<23;i+)/*初始化棋盘大小*/for(j=0;j<23;j+)chessij=-l;printfcn输入棋盘行数：)；

19、seanf&m);printf (，zn输入棋盘列数:)； scanf (，z%d，z, &n) ;/*输入目标棋盘的大小*/for(i=2;i<=m+l;i+)for(j=2;j<=n+l;j+)chessij二0;printf ("n起始点行坐标:")；scanf ("%ct, &x0);printf (，zn起始点列坐标：)；scanf(%d,&y0) ;/* 取得初始位置 */if (x0>二 1&&x0二m)&&(y0>二l&&y0二n) /* 判断输

20、入是否有效*/iif (test (xo+1, y0+l)=l)/*测试是否可以走完，如果可以则回车，动态演示; 否则退出，重新输入*/printf(z，n可以全部走完，过程按回车键演示过程=>)；getchar ();for (cou=l; cou<=count; cou+) /*动态显示行走过程，每回车一次，显示下一 步马的位置*/getchar ();system(cls);printf (，zn欢迎使用马踏棋盘演示系统);printf （z，正在为您演示?rt）;printf （第d 步：，cou）;for （i=2;i<=m+l;i+）printf （rt）;for

21、（j=2;j<=n+l;j+）if （chessij二二0）printf ;/*如果该点已经走过,就在这点打印*/ else if （cou=chessi j）printf （马）；/*如果在这一步马在该点，则在这点打印马chessij=0;elseif （i 二二 2&&j=2） printf （，z 厂"）；if（i=2&&j>2&&j<n+l）printf ct"）;if （i二二2&&j二二n+1）printf（-1 ）；if（i>2&&im+l&&

22、;j=2）printf （ 卜）；if （i=m+l&&j=2）printf （“ l，/）;if（i=m+l&&j>2&&j<n+l）printf （"丄“）;if（i=m+l&&j二二n+1）printf（"“）；if（i>2&&im+l&&j二二n+1）printf ch “）;if（i2&&im+l&&j>2&&jn+l）printf （，+，/） ;/*打印棋盘*/if （cou<m*n）pr

23、intf （，zn按回车键演示下一步）；elseprintf （，zn演示完毕!按任意键退出.n）;q二 1;elseprintf （，zn无法全部走完!按回车键重新输入! n）;get char （）;getchar （）;count二0;el seprintf （，zn输入错误!超过范围！ n）；printf （，zn按回车键重新输入! n）;get char （）;get char （）;4.1输入初始数据4.结果与结论4. 2判断能否遍历wc:usersadministratordesktopdebugcppl.exefamb不系统-ia欢迎使用马踏棋盘演输入棋盘行数:10打入棋盘列数

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

25、理口c、实现：未实现口部分实现口全部实现口d、文档格式：不规范口基木规范口规范口2、出勤：全勤口缺勤次3、答辩：a、未能完全理解题目，答辩情况较差 口b、部分理解题目，部分问题回答正确口c、理解题目较清楚，问题回答基本正确口d、理解题目透彻，问题回答流利口课程设计报告成绩：,占总成绩比例：50%课程设计其它环节成绩：环节名称：出勤,成绩： ,占总成绩比例：20%环节名称：答辩，成绩： ,占总成绩比例：30%总成绩：指导教师签字：年 月 日7 附件源程序：ttinclude <stdio.h>tiincludc <iostrceiniint chess2323,step=o,m

26、=0,n=0,count=0;/* chess2323用来表示棋盘；step是步骤数；m和n是棋盘的规格行和列；count是运算次数；*/x, int y), f5 (int返回值为sum */int fl (int x, int y), f2(int x, int y), f3(int x, int y), f4(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)位置处，下一步可以跳的位

27、置数, int sum; /*用来记录下一步可以跳的位置数*/sum二0;if (chessx-1y-2=0)sum+;if (chessx-2y+l=0)sum+;if (chessx+2 y+l=0)suin+;if(chessx+2y-1二二0)sum+;if (chessx-2 yt二二0)sum+;if (chessx-1y+2=0)sum+;if (chessx+1y-2=0)sum+;if (chess x+1 y+2=0)sum+;return (sum);/*每找到一个位置sum+,最后返回sum值就是在(x, y)处可走的位置数*/int test (int x, int

28、y) /*test函数测试第step步为(x, y)位置的情况下,是 否可以走完棋盘，如果可以返回1,否则返回0*/int s9, a9;int min, i, j, k;count+;step+;chessxy=step;if (step二二m*n)return(1) ; /*如果已经走到了 mxn的话，表示满足结束条件，返回1 */s=h (x-2, y+1) ;/*统计(x, y)处的下一步的八个位置的sum值*/ s2=h (x-1, y+2);s3=h(x+l,y+2);s4二h(x+2, y+1);s5二h(x+2, y-1);s6二h(x+l, y-2);s7=h (x-1, y

29、-2);s8=h(x-2, y-1);for(j=l; j二8; j+)/*使用冒泡排序，对下一步的八个规则的sum从小到大排序*/min=9;aj=l;for(i=l;i<=8;i+)if (simin)min=si;aj=i ; /*排序结果存放在a数组中*/k=i;sk二9; for (i=l; i<=8; i+)/*这个循环按sum从小到大的顺序依次调用相应的规则*/if (ai二二 1)if(fl(x, y)=l)return(l);辻(ai=2)if(f2(x, y)=l)return (1);if (ai=3)if (f3 (x, y)=l)return(l);if

30、(ai=4)if (f4(x, y)二二 1)return ；if (ai=5)if(f5 (x, y)=l)return (1);if (ai=6) if(f6(x, y)二二 1)return (1);辻(ai=7)if(f7 (x, y)=l) return (1);if (ai二二 8)if (f8 (x, y)=l) return (1);step-一；/*如果按任意八个规则都无法走满棋盘则回退，*/ chesstx y=0;/*把棋盘恢复状态，并返回0*/return(0);/*按规则1走步*/int fl(int x, int y)if(chessx-2y+1二二0)if (te

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

32、return (1);return (0);/*按规则5走步*/int f5(int x, int y)if(chessx+2y-l=0) if (test (x+2, y-l)=l) return (1);return (0);/*按规则6走步*/int f6(int x, int y)if (chessx+l y-2=0) if (test (x+1, y-2)=l)return (1);return(o);/*按规则7走步*/int f7 (int x, int y)if (chessx-1y-2=o)if (test (x-1, y-2)=1) return (1);return (0

33、);/*按规则8走步*/int f8(int x, int y)if (chessx2y-l=o) 辻(test (x-2, y-l)=l) rcturn(l);return (0);void main()int i, j, xo, yo, q二0, cou;while(q二二0)system(，zcls，z);printf（，zn欢迎使用马踏棋盘演示系统n）；printf （，znn按冋车键进入演示系统nnnrt);get char (); systcm(cls)；printf（z，n欢迎使用马踏棋盘演示系统n）；for （i二0; i23; i+）/*初始化棋盘大小*/for（j=0;j<23;j+）chessij=-l;printfcan输入棋盘行数:）；scanf（d，&m）;printf cn输入棋盘列数:）； scanf （ct, &n） ;/*输入目标棋盘的大小*/for（i=2;i<=m+l;i+）for（j=2;j<=n+l;j+）chessij二0;printf cn起始点行坐标:）;scanf （ct, &x0）;printf cn起始点列坐标:）；scanf （d, &y0） ;/* 取得初始位置 */if （x0>=l&&x0<=m）&am