马的遍历课程设计报告(共26页).doc

精选优质文档-倾情为你奉上 攀枝花学院本科课程设计报告（论文） 马的遍历问题求解 学生姓名： 学生学号： 院 (系) ： 年级专业： 2014年 1 月 专心-专注-专业攀枝花学院本科学生课程设计任务书题目马的遍历问题求解1、课程设计的目的1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。 要求： （1）依次输出所走过的各位置的坐标。 （2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。 （3）程序能方便地地移植到其它规格的棋盘上。3、主要参考文献1数据结构（C语言版），严蔚敏，清华大学出版社，20032数据结构题集，严蔚敏，清华大学出版社，20053数据结构（C语言版），刘大有，高等教育出版社，20044Data Structure with C+，William FordWilliam Topp，清华大学出版社，20034、课程设计工作进度计划第1天 完成方案设计与程序框图 第2、3天 编写程序代码第4天 程序调试分析和结果第5天 课程设计报告和总结指导教师（签字）日期年 月 日教研室意见：年 月 日学生（签字）： 接受任务时间： 年 月 日注：任务书由指导教师填写。课程设计（论文）指导教师成绩评定表题目名称马的遍历问题求解评分项目分值得分评价内涵工作表现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对前人工作有改进或突破，或有独特见解。成绩指导教师评语指导教师签名： 年月日摘要马步遍历问题与骑士巡游(knight's tour)问题是指在有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）把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。然后按遍历的顺序输出结点。 关键词：象棋，遍历，数组 目 录摘 要1 概述1 1.1 前言1 1.1.1问题描述1 1.1.2课程设计的目的12 流程图23 设计思路34 数据结构设计45 功能函数算法分析5 5.1 计算一个点周围有几个点5 5.2 寻找下一个方向函数5 5.3 栈的相关函数6 5.4 马的遍历函数7 5.5 主函数9 5.6棋盘初始化函数10 5.7 标记初始化函数10结论11参考文献12附录A：程序代码13 1 概述1.1前言1.1.1问题描述根据中国象棋棋盘，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。 要求： （1）依次输出所走过的各位置的坐标。 （2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。 （3）程序能方便地地移植到其它规格的棋盘上。1.1.2课程设计的目的 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。1） 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2） 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。开始输入入口点横坐标横坐标在110之间输入入口点纵坐标纵坐标在19之间显示马遍历路径结束 2 流程图 假 真 假 3 设计思路首先，中国象棋是10*9的棋盘，马的走法是“马走日”，忽略“蹩脚马”的情况。其次，这个题目采用的是算法当中的深度优先算法和回溯法：在“走到”一个位置后要寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。在寻找下一步的时候，对周围的这几个点进行比较，从而分出优劣程度，即看它们周围可以走的点谁最少，然后就走那条可走路线最少的那条。经过这样的筛选后，就会为后面的路径寻找提供方便，从而减少回溯次数。最后，本程序的棋盘和数组类似，因而采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。 4 数据结构设计同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围各加了两层“墙”。具体数据结构定义如下：int chessboard1413; /采用最大的中国象棋10*9制的int CanPass14138; /每个棋子的八个方向哪些可以走typedef struct /棋盘的八个方向 int x,y;direction;direction dir8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1; /八个方向typedef struct /栈的节点结构 int x,y; /走过位置 int di; /走向下一个方向pathnode;typedef structpathnode pa90; /栈的容量最大为90int top; /栈顶path; /顺序栈 5 功能函数算法分析5.1 计算一个点周围有几个点函数int Count(int x,int y) 该函数实现的功能是在遍历的过程当中计算一个点周围有几个方向可以走，从而为后面的筛选提供依据。int Count(int x,int y) /计算每个节点周围有几个方向可以走int count=0,i=0;for(i=0;i<8;i+)if(chessx+1+diri.xy+1+diri.y=0)count+;return count;5.2寻找下一个方向函数int Find_Direction(int x,int y)该函数的功能是在走过一个点之后，寻找下一个适合的点，如果找到返回正常的方向值，否则返回-1。int Find_Direction(int x,int y) /寻找下一个方向int dire,min=9,count,d=9;for(dire=0;dire<8;dire+)if(chessx+1+dirdire.xy+1+dirdire.y=0&&CanPassx+1y+1dire=0) count=Count(x+dirdire.x,y+dirdire.y); if(min>count) min=count; d=dire; if(d<9)return d;elsereturn -1;5.3栈的相关函数初始化栈：void Init_Path(path *p)；p是用到得栈；判断栈是否是空：int Empty(path p)；p是栈，是空的话返回1，否则返回0，时间复杂度为；压栈函数：int Push_Path(path *p,pathnode t,int v)p是栈，t是压进去的节点，v是棋盘，时间复杂度为；出栈函数：int Pop_Path(path *p,pathnode *t)p是栈，t是拿出来的节点，时间复杂度为。void Init_Path(path *p)/初始化栈p->top=-1;int Push_Path(path *p,pathnode t) /压节点及其向下一位移动的方向入栈if(p->top>=89)return -1;elsep->top+;p->pap->top.x=t.x;p->pap->top.y=t.y;p->pap->top.di=t.di;return 1;int Empty(path p) /判断栈是否为空if(p.top<0) return 1;else return 0;int Pop_Path(path *p,pathnode *t) /出栈if(Empty_Path(*p)return -1;elset->x=p->pap->top.x;t->y=p->pap->top.y;t->di=p->pap->top-.di;return 1;5.4马的遍历函数：void Horse(int x,int y)这是该算法的精华部分，x,y表示入口地点，v表示棋盘类型即中国象棋，这个函数主体是一个循环，循环里面始终是在找下一个点，如果找到就将该点进栈，找不到则退栈。直到发生栈为空时退栈或循环结束，前一种情况时会提示找不到路径(虽然不会发生，但是为逻辑严密性依然要如此)，后一种情况则打印出走过的正确路径和走过之后的数组。void Horse(int x,int y) /x,y表示出发位置 /马遍历函数int num=1,t,i;path p;pathnode f;Init_Path(&p);for(num=1;num<=90;num+)t=Find_Direction(x,y);if(t!=-1) /正常找到下一个方向的情况下chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f);x=x+dirt.x;y=y+dirt.y;else if(num=64+26*v&&chessboardx+1y+1=0) /最后一次时t肯定是-1chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);elseif(Pop_Path(&p,&f)=-1) /出栈且栈为空的情况printf("无法为您找到一条适合的路径!n");exit(0);num-=2; /返回前一个点x=f.x;y=f.y;CanPathx+1y+1f.di=1; /遍历不成功，即这个方向不通 /根据栈中信息打印马的行走路径printf("马的遍历路径如下:n ");for(i=0;i<90;i+)printf("(%2d,%2d)->",p.pai.x,p.pai.y);if(i+1)%(8)=0)printf("bb n->");5.5主函数：int main()提示输入起点位置，这里的起点位置就是日常生活观念中的顺序，开始点是(1,1),而不是数组中的初始位置(0,0),输入错误则提示重新输入，时间复杂度为。int main() /主函数int x,y; char ch='y; while(ch='y')printf(" 中国象棋马的遍历 n:");Mark_Che();Mark_Dir();while(1)printf("请输入入口点横坐标（在案1-10之间）：");scanf("%d",&x);if(y<1|y>9)printf("输入错误，请重新输入!(横坐标在1-10之间)n");elsebreak;while(1)printf("请输入入口点纵坐标(在1-9之间)：");scanf("%d",&y);if(y<1|y>9)printf("输入错误，请重新输入!(纵坐标在1-9之间)n");elsebreak;Knight(x,y);Getchar();Printf("n");printf("是否继续马的遍历（是：y；否：其他）："); fflush(stdin);scanf("%c",&ch);5.6棋盘初始化函数void Mark_Che(int v)此函数作为棋盘初始化函数，因为每次执行程序时，棋盘上必须是全部都没有走过的。它会自动进行初始化棋盘，在14*13的棋盘上初始化。初始化后，棋盘大小的区域全部是0，而周围的两堵墙标志为1，时间复杂度为。void Mark_Che() /标志棋盘函数int i,j;for(i=0;i<14;i+) /首先全部标记为0for(j=0;j<13;j+)chessij=0;for(i=0;i<2;i+) /前面两行标记为1for(j=0;j<13;j+)chessij=1;for(j=0;j<2;j+) /前面两列标记为1for(i=0;i<14;i+)chessij=1;for(j=11;j<13;j+) /后面两列标记为1for(i=0;i<14;i+)chessij=1;for(i=12;i<14;i+)for(j=0;j<13;j+) /后面两行标记为1chessij=1;5.7标记初始化函数void Mark_Dir() 此函数和上面的函数功能类似，也是初始化才用，它是为栈的实现提供帮助的。开始时全部标记为0，表示周围的八个方向都可以走，时间复杂度为。void Mark_Dir() /初始化，为栈的实现做准备，全部标记为0，表示八个方向都是通路 /由于三维数组赋初值比较困难，因而采用单独的函数实现int i,j,k;for(i=0;i<14;i+)for(j=0;j<13;j+)for(k=0;k<8;k+)CanPassijk=0; 结论从这周的上机实践中，我体会到上机的重要性。编写程序，离不开上机，一段不懂的代码只有经过反复的研读，调试与修改，最终变成自己的代码。一周的学习，让我学会一些知识，不在于学到了那么点技术，而在于心理得到了洗礼！在此，我不说老师的功劳，也不提以前怎么怎么没好好听讲，没好好复习，没好好珍惜上机的机会。但这次，最终我确实得到了锻炼，这就足够了！对于接下来的路程，脚踏实地，勤奋努力比什么都重要；代码是枯燥的，但不枯燥的是学习的过程，难得的是学习过程中体会的快乐，有目标的学习与坚持，生活才会更加美好！参 考 文 献1数据结构（C语言版），严蔚敏，清华大学出版社，20032数据结构题集，严蔚敏，清华大学出版社，20053数据结构（C语言版），刘大有，高等教育出版社，2004 4Data Structure with C+，William FordWilliam Topp，清华大学出版社，2003附录A：程序代码#include<stdio.h>#include<stdlib.h>int chess1413; /定义棋盘int CanPath14138; /每个棋子的八个方向哪些可以走typedef struct /棋盘的八个方向int x,y; direction;direction dir8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1; /马遍历的八个方向/栈的设计（顺序到达的各点坐标，还要有从前一点到达本点的方向）typedef structint x,y; /马的走过位置int di; /马走的方向pathnode;typedef structpathnode pa90;int top;path; /顺序栈void Init_Path(path *p) /初始化栈p->top=-1;int Push_Path(path *p,pathnode t) /进栈点及其向下一位移动的方向入栈if(p->top>=89)return -1;elsep->top+;p->pap->top.x=t.x;p->pap->top.y=t.y;p->pap->top.di=t.di;return 1;int Empty_path(path p) /判断栈是否为空if(p.top<0) return 1;else return 0; int Pop_Path(path *p,pathnode *t) /出栈if(Empty_path(*p)return -1;elset->x=p->pap->top.x;t->y=p->pap->top.y;t->di=p->pap->top-.di;return 1;int Count(int x,int y) /计算每个节点周围有几个方向可以走int count=0,i=0;for(i=0;i<8;i+)if(chessx+1+diri.xy+1+diri.y=0) count+;return count;int Find_Direction(int x,int y) /寻找下一个方向，如果找到返回值，否则为0int dire,min=9,count,d=9;for(dire=0;dire<8;dire+)if(chessx+1+dirdire.xy+1+dirdire.y=0 &&CanPathx+1y+1dire=0)count=Count(x+dirdire.x,y+dirdire.y);if(min>count)min=count;d=dire;if(d<9)return d;elsereturn -1;void Mark_Dir() /初始化，为栈的实现做准备，全部标记为0，表示八个方向都是通路int i,j,k;for(i=0;i<14;i+)for(j=0;j<13;j+)for(k=0;k<8;k+)CanPathijk=0; /马的遍历成功，即通路为0void Mark_Che() /标志棋盘函数，棋盘上区域内都为0，区域边缘设为1int i,j;for(i=0;i<14;i+) /首先全部标记为0for(j=0;j<13;j+)chessij=0;for(i=0;i<2;i+) /前面两行标记为1 for(j=0;j<13;j+)chessij=1;for(j=0;j<2;j+) /前面两列标记为1 for(i=0;i<14;i+)chessij=1;for(j=11;j<13;j+) /后面两列标记为1for(i=0;i<14;i+)chessij=1;for(i=12;i<14;i+)for(j=0;j<13;j+) /后面两行标记为1chessij=1;void Horse(int x,int y) /x,y表示出发位置 /马的遍历函数int num=1,t,i;path p;pathnode f;Init_Path(&p);for(num=1;num<=90;num+)t=Find_Direction(x,y);if(t!=-1) /正常找到下一个方向的情况下chessx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f);x=x+dirt.x;y=y+dirt.y;else if(num=90 && chessx+1y+1=0) /遍历到最后，t为-1chessx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f);elseif(Pop_Path(&p,&f)=-1) /出栈且栈为空的情况printf("无法为您找到一条适合的路径!n");exit(0);num-=2; /返回前一个点x=f.x;y=f.y;CanPathx+1y+1f.di=1; /遍历不成功，即这个方向不通 /根据栈中信息打印出马的遍历路径printf("骑士巡游路径如下:n ");for(i=0;i<90;i+)printf("(%2d,%2d)->",p.pai.x,p.pai.y);if(i+1)%(8)=0) printf("bb n->"); void main() /主函数int x,y;char ch='y'printf(" 中国象棋马的遍历 n");printf("n"); while(ch='y') Mark_Che();Mark_Dir();while(1)printf("请输入入口点横坐标(在1-10之间)：");scanf("%d",&x);if(x<1|x>10)printf("输入错误，请重新输入!(横坐标在1-10之间)n");