资源描述：
《数据结构课程设计马的遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、课程设计说明书课程名称：数据结构设计题目：马的遍历院系：计算机科学与信息工程学院学生姓名：学号：专业班级：指导教师：2015年6月7日课程设计任务书设计题目马的遍历学生姓名册心B歹计算机科学与住如術所在阮系信息工程学院专业、年玻、龙设计要求：任意行列数的棋盘中，马只能走“日”字。马从任意位置处出发，把棋盘的每一格都走一次，且只走一次。要求在屏幕上画出棋盘和马所有经过的路径。学生应完成的工作：1.分析题目要求2.利用数据结构和c语言知识找出实现方法3.编程完成实现4.按要求撰写课程设汁报告和设计总结。参考文献阅读：1.《C程序设计（第四版）》，谭浩强清华大学出版社2.《数据结构（c语言版）》，
2、严蔚敏吴伟民清华大学出版社工作计划：1.接到题目后用课余时间设计程序，2.第14周上机调试通过后，答辩，交报告（具体时间由各任课教师决定）。任务下达日期：2015年4月28日任务完成日期：2015年6月6日指导教师（签名）：学生（签名）：马的遍历摘要：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点可以用一个二维数组chess[l[]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“•”，未
3、走过的位置显示“厂”“丁”“n卜”等制表符，然后清屏，显示下一步，再清屏，依次类推。关键词：深度优先遍历；回溯法；数组存储棋盘；动态演示;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來表示一个棋盘，chess[i][j]=o或1；其中0表示通路,1表示不通，当从某点向下试探吋，中间点的8个方向可以
5、试探；棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了保证边缘点也有八个方向可以走，使问题能够简单化，不用再判断当前点的试探方向有儿个。2.设计方案2.1问题分析和任务定义：中国彖棋屮马采用“口”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，即假设马所在点的坐标为(i,j),那么其它八个结点的坐标为(i+l,j+2),(i+2,j+l),(i+2,j・l),(i+l,j・2),(i-l,j-2),(i・2,j・l),(i・2,j+l),(i-l,j+2)把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的
6、顺序输岀结点可以用一个二维数组chess[][]来表示棋盘，一开始用來存放步骤号，若走过了则把它赋值为0。对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“•”，未走过的位置显示“厂”“丁”“-I”“卜”等制表符，然后清屏，显示下一步，再清屏，依次类推。棋盘的规格限制在20*20以内，起始点当然不能超出棋盘的范围，每输入一组数据，首先判断是否可以全部走完,如果可以，则动态演示，否则重新输入数据。1.2概要设计和数据结构的选择：该算法需要定义一个二维数组chess[][]用來表示棋盘，整形变量step存放步骤号,count存放运算次数。定义8个函数（fl,f2,f3,f4,f
7、5,f6,f7,⑻用来表示按8种规则走，定义一个h函数用来统计8种规则中有几种是可走的，再定义一个test函数用来测试是否可以走完，如果可以走完则返回值为1,否则返回0otest函数和fl,f2,f3,f4,f5,f6,f7,f8八个函数是一个递归调用关系。然后通过主函数调用test函数，实现动态演示功能。具体过程见下图：1.方案实施3.1数据结构设计：同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规
