马的遍历课程设计报告

12020年4月19日马的遍历课程设计报告攀枝花学院本科课程设计报告（论文）马的遍历问题求解学生姓名：学生学号：院(系)：年级专业：1月攀枝花学院本科学生课程设计任务书题目马的遍历问题求解1、课程设计的目的1)使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。要求：（1）依次输出所走过的各位置的坐标。（2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。（3）程序能方便地地移植到其它规格的棋盘上。3、主要参考文献［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，．［2］《数据结构题集》，严蔚敏，清华大学出版社，．［3］《数据结构》（C语言版），刘大有，高等教育出版社，．［4］《DataStructurewithC++》，WilliamFord．WilliamTopp，清华大学出版社，．4、课程设计工作进度计划第1天完成方案设计与程序框图第2、3天编写程序代码第4天程序调试分析和结果第5天课程设计报告和总结指导教师（签字）日期年月日教研室意见：年月日学生（签字）：接受任务时间：年月日注：任务书由指导教师填写。文档仅供参考，不当之处，请联系改正。12020年4月19日文档仅供参考，不当之处，请联系改正。02020年4月19日课程设计（论文）指导教师成绩评定表题目名称马的遍历问题求解评分项目分值得分评价内涵工作表现20%01学习态度6遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。02科学实践、调研7经过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。03课题工作量7按期圆满完成规定的任务，工作量饱满。能力水平35%04综合运用知识的能力10能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。05应用文献的能力5能独立查阅相关文献和从事其它调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。06设计（实验）能力，方案的设计能力5能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。07计算及计算机应用能力5具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。08对计算或实验结果的分析能力（综合分析能力、技术经济分析能力）10具有较强的数据收集、分析、处理、综合的能力。成果质量45%09插图（或图纸）质量、篇幅、设计（论文）规范化程度5符合本专业相关规范或规定要求；规范化符合本文件第五条要求。10设计说明书（论文）质量30综述简练完整，有看法；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。11创新10对前人工作有改进或突破，或有独特看法。成绩指导教师评语指导教师签名：年月日文档仅供参考，不当之处，请联系改正。I2020年4月19日摘要马步遍历问题与骑士巡游(knight'stour)问题是指在有8×8方格的国际象棋棋盘上进行奇异的骑士L型(L-shaped)移动的问题。而骑士巡游问题实际是带有约束条件的马步遍历问题,因此在用程序求解的时候能够一并求解。中国象棋中马采用“日”字走法，对棋盘上马所在的结点，一步内到达的结点最多有八个，即假设马所在点的坐标为（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）把这些点看作马所在点的邻接点，因此能够采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点。关键词：象棋，遍历，数组文档仅供参考，不当之处，请联系改正。02020年4月19日目录摘要………………………………………………………………………………………Ⅰ1概述…………………………………………………………………………………………11.1前言……………………………………………………………………………………11.1.1问题描述……………………………………………………………………………11.1.2课程设计的目的……………………………………………………………12流程图…………………………………………………………………………………………23设计思路……………………………………………………………………………………3文档仅供参考，不当之处，请联系改正。12020年4月19日4数据结构设计………………………………………………………………………45功能函数算法分析………………………………………………………………………55.1计算一个点周围有几个点………………………………………………………………55.2寻找下一个方向函数………………………………………………………………55.3栈的相关函数………………………………………………………………………65.4马的遍历函数………………………………………………………………………75.5主函数……………………………………………………………………………………95.6棋盘初始化函数…………………………………………………………………105.7标记初始化函数…………………………………………………………………10结文档仅供参考，不当之处，请联系改正。22020年4月19日论…………………………………………………………………………………………11参考文献………………………………………………………………………………12附录A：程序代码…………………………………………………………………………13文档仅供参考，不当之处，请联系改正。-0-2020年4月19日1概述1.1前言1.1.1问题描述根据中国象棋棋盘，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。要求：（1）依次输出所走过的各位置的坐标。（2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。（3）程序能方便地地移植到其它规格的棋盘上。1.1.2课程设计的目的使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。文档仅供参考，不当之处，请联系改正。-1-2020年4月19日3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。文档仅供参考，不当之处，请联系改正。-2-2020年4月19日2流程图假真假开始输入入口点横坐标横坐标在1—10之间输入入口点纵坐标纵坐标在1—9之间显示马遍历路径结束文档仅供参考，不当之处，请联系改正。-4-2020年4月19日3设计思路首先，中国象棋是10*9的棋盘，马的走法是“马走日”，忽略“蹩脚马”的情况。其次，这个题目采用的是算法当中的深度优先算法和回溯法：在“走到”一个位置后要寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。在寻找下一步的时候，对周围的这几个点进行比较，从而分出优劣程度，即看它们周围能够走的点谁最少，然后就走那条可走路线最少的那条。经过这样的筛选后，就会为后面的路径寻找提供方便，从而减少回溯次数。最后，本程序的棋盘和数组类似，因而采用数组进行存储，同时因为有回溯，因此采用栈的方法，而且为了最后打印方便，采用的是顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些能够走的数组。文档仅供参考，不当之处，请联系改正。-5-2020年4月19日文档仅供参考，不当之处，请联系改正。-0-2020年4月19日4数据结构设计同上面述，棋盘采用数组形式，而且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围各加了两层“墙”。具体数据结构定义如下：intchessboard[14][13];//采用最大的中国象棋10*9制的intCanPass[14][13][8];//每个棋子的八个方向哪些能够走typedefstruct{//棋盘的八个方向intx,y;}direction;directiondir[8]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};//八个方向typedefstruct{//栈的节点结构intx,y;//走过位置intdi;//走向下一个方向}pathnode;typedefstruct{pathnodepa[90];//栈的容量最大为90inttop;//栈顶}path;//顺序栈文档仅供参考，不当之处，请联系改正。-1-2020年4月19日5功能函数算法分析5.1计算一个点周围有几个点函数intCount(intx,inty)该函数实现的功能是在遍历的过程当中计算一个点周围有几个方向能够走，从而为后面的筛选提供依据。intCount(intx,inty){//计算每个节点周围有几个方向能够走intcount=0,i=0;for(i=0;i8;i++)if(chess[x+1+dir[i].x][y+1+dir[i].y]==0)count++;文档仅供参考，不当之处，请联系改正。-2-2020年4月19日returncount;}5.2寻找下一个方向函数intFind_Direction(intx,inty)该函数的功能是在走过一个点之后，寻找下一个适合的点，如果找到返回正常的方向值，否则返回-1。intFind_Direction(intx,inty){//寻找下一个方向intdire,min=9,count,d=9;for(dire=0;dire8;dire++){if(chess[x+1+dir[dire].x][y+1+dir[dire].y]==0&&CanPass[x+1][y+1][dire]==0){count=Count(x+dir[dire].x,y+dir[dire].y);if(mincount){min=count;d=dire;}}}if(d9)文档仅供参考，不当之处，请联系改正。-3-2020年4月19日returnd;elsereturn-1;}5.3栈的相关函数初始化栈：voidInit_Path(path*p)；p是用到得栈；判断栈是否是空：intEmpty(pathp)；p是栈，是空的话返回1，否则返回0，时间复杂度为；压栈函数：intPush_Path(path*p,pathnodet,intv)p是栈，t是压进去的节点，v是棋盘，时间复杂度为；出栈函数：intPop_Path(path*p,pathnode*t)p是栈，t是拿出来的节点，时间复杂度为。voidInit_Path(path*p){//初始化栈p-top=-1;}intPush_Path(path*p,pathnodet){//压节点及其向下一位移动的方向入栈if(p-top=89)文档仅供参考，不当之处，请联系改正。-4-2020年4月19日return-1;else{p-top++;p-pa[p-top].x=t.x;p-pa[p-top].y=t.y;p-pa[p-top].di=t.di;return1;}}intEmpty(pathp){//判断栈是否为空if(p.top0)return1;elsereturn0;}i