数据结构课程设计马遍历.doc

课 程 设 计 说 明 书 课程名称： 数据结构 设计题目： 马的遍历 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 指导教师： 2015 年 6 月 7 日 课 程 设 计 任 务 书 设计题目 马的遍历 学生姓名 所在院系 计算机科学与信息工程学院 专业、年级、班 设计要求： 任意行列数的棋盘中，马只能走“日”字。马从任意位置处出发，把棋盘的每一格都走一次，且只走一次。要求在屏幕上画出棋盘和马所有经过的路径。 学生应完成的工作： 1.分析题目要求 2.利用数据结构和c语言知识找出实现方法 3.编程完成实现 4.按要求撰写课程设计报告和设计总结。 参考文献阅读： 1.《c程序设计（第四版）》，谭浩强 清华大学出版社 2.《数据结构（c语言版）》，严蔚敏 吴伟民 清华大学出版社 工作计划： 1. 接到题目后用课余时间设计程序， 2. 第14周上机调试通过后，答辩，交报告（具体时间由各任课教师决定）。 任务下达日期： 2015年 4 月 28 日 任务完成日期： 2015年 6 月 6 日 指导教师（签名）： 学生（签名）： 马的遍历 摘 要：中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点 可以用一个二维数组chess[][]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“●”，未走过的位置显示“┌”“ ┬”“ ┐”“├”等制表符，然后清屏，显示下一步，再清屏，依次类推。 关键词：深度优先遍历；回溯法；数组存储棋盘；动态演示； 目 录 1. 设计背景 1 1.1问题描述 1 1.2基本要求 1 2. 设计方案 1 2.1问题分析和任务定义 1 2.2概要设计和数据结构的选择 2 3. 方案实施 3 3.1数据结构设计 3 3.2功能函数设计 4 3.3编码实现 5 4. 结果与结论 14 4.1输入初始数据 14 4.2判断能否遍历 14 4.3动态演示 14 5. 收获与致谢 15 6．参考文献 15 PAGE \* MERGEFORMAT1 1. 设计背景 1.1 问题描述： 中国象棋是10*9的棋盘，马的走法是“马走日”，这里忽略了“蹩脚马”的情况，使马的遍历问题简单化。 马在棋盘上遍历采用算法当中的优先算法和回溯法；从入口出发，按某一方向向前探索，若能走通并且从未走过，即某处可到达，则到达新店，否则探索下一个方向；如果发生“阻塞”的情况，就是后面走不通的情况，则沿原路返回到前一点，换一个方向再继续试探，知道找到一条通路，或无路可走又返回到入口点。期盼中马的遍历采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。 基本要求： 棋盘有10行9列，利用chess来表示一个棋盘，chess[i][j]=0或1；其中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）把这些点看作马所在 点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点 可以用一个二维数组chess[][]来表示棋盘，一开始用来存放步骤号，若走过了则把它赋值为0。 对于动态演示问题，只要在“马”的位置显示“马”，已经走过的位置显示“●”，未走过的位置显示“┌”“ ┬”“ ┐”“├”等制表符，然后清屏，显示下一步，再清屏，依次类推。 棋盘的规格限制在20*20以内，起始点当然