马的遍历课程设计报告讲解.docx
《马的遍历课程设计报告讲解.docx》由会员分享，可在线阅读，更多相关《马的遍历课程设计报告讲解.docx（28页珍藏版）》请在冰点文库上搜索。
马的遍历课程设计报告讲解
攀枝花学院本科课程设计报告（论文）
马的遍历问题求解
学生姓名：
学生学号：
院（系）：
年级专业：
2014年1月
攀枝花学院本科学生课程设计任务书
题 目
马的遍历问题求解
1、课程设计的目的
1）使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。
2）使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。
3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。
2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等）
在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。
要求：
（1）依次输出所走过的各位置的坐标。
（2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。
（3）程序能方便地地移植到其它规格的棋盘上。
3、主要参考文献
［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003．
［2］《数据结构题集》，严蔚敏，清华大学出版社，2005．
［3］《数据结构》（C语言版），刘大有，高等教育出版社，2004．
［4］《DataStructurewithC++》，WilliamFord．WilliamTopp，清华大学出版社，2003．
4、课程设计工作进度计划
第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'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）把这些点看作马所在点的邻接点，所以可以采用类似图的深度优先遍历，以马所在点为初始点对整个棋盘进行遍历。
然后按遍历的顺序输出结点。
关键词：
象棋，遍历，数组
摘要………………………………………………………………………………………Ⅰ
1概述…………………………………………………………………………………………1
1.1前言……………………………………………………………………………………1
1.1.1问题描述……………………………………………………………………………1
1.1.2课程设计的目的……………………………………………………………1
2流程图…………………………………………………………………………………………2
3设计思路……………………………………………………………………………………3
4数据结构设计………………………………………………………………………4
5功能函数算法分析………………………………………………………………………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）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。
2流程图
假
真
假
3设计思路
首先，中国象棋是10*9的棋盘，马的走法是“马走日”，忽略“蹩脚马”的情况。
其次，这个题目采用的是算法当中的深度优先算法和回溯法：
在“走到”一个位置后要寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。
在寻找下一步的时候，对周围的这几个点进行比较，从而分出优劣程度，即看它们周围可以走的点谁最少，然后就走那条可走路线最少的那条。
经过这样的筛选后，就会为后面的路径寻找提供方便，从而减少回溯次数。
最后，本程序的棋盘和数组类似，因而采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。
同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。
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];//栈的容量最大为90
inttop;//栈顶
}path;//顺序栈
5功能函数算法分析
5.1计算一个点周围有几个点函数intCount（intx,inty）
该函数实现的功能是在遍历的过程当中计算一个点周围有几个方向可以走，从而为后面的筛选提供依据。
intCount（intx,inty）
{//计算每个节点周围有几个方向可以走
intcount=0,i=0;
for（i=0;i<8;i++）
if（chess[x+1+dir[i].x][y+1+dir[i].y]==0）
count++;
returncount;
}
5.2寻找下一个方向函数intFind_Direction（intx,inty）
该函数的功能是在走过一个点之后，寻找下一个适合的点，如果找到返回正常的方向值，否则返回-1。
intFind_Direction（intx,inty）
{//寻找下一个方向
intdire,min=9,count,d=9;
for（dire=0;dire<8;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（min>count）{
min=count;
d=dire;
}
}
}
if（d<9）
returnd;
else
return-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）
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.top<0）return1;
elsereturn0;
}
intPop_Path（path*p,pathnode*t）
{//出栈
if（Empty_Path（*p））
return-1;
else
{
t->x=p->pa[p->top].x;
t->y=p->pa[p->top].y;
t->di=p->pa[p->top--].di;
return1;
}
}
5.4马的遍历函数：
voidHorse（intx,inty）
这是该算法的精华部分，x,y表示入口地点，v表示棋盘类型即中国象棋，这个函数主体是一个循环，循环里面始终是在找下一个点，如果找到就将该点进栈，找不到则退栈。
直到发生栈为空时退栈或循环结束，前一种情况时会提示找不到路径（虽然不会发生，但是为逻辑严密性依然要如此），后一种情况则打印出走过的正确路径和走过之后的数组。
voidHorse（intx,inty）//x,y表示出发位置
{//马遍历函数
intnum=1,t,i;
pathp;
pathnodef;
Init_Path（&p）;
for（num=1;num<=90;num++）
{
t=Find_Direction（x,y）;
if（t!
=-1）
{//正常找到下一个方向的情况下
chessboard[x+1][y+1]=num;
f.x=x;f.y=y;f.di=t;
Push_Path（&p,f）;
x=x+dir[t].x;y=y+dir[t].y;
}
elseif（num==64+26*v&&chessboard[x+1][y+1]==0）
{//最后一次时t肯定是-1
chessboard[x+1][y+1]=num;
f.x=x;f.y=y;f.di=t;
Push_Path（&p,f,v）;
}
else
{
if（Pop_Path（&p,&f）==-1）
{//出栈且栈为空的情况
printf（"无法为您找到一条适合的路径!
\n"）;
exit（0）;
}
num-=2;//返回前一个点
x=f.x;
y=f.y;
CanPath[x+1][y+1][f.di]=1;//遍历不成功，即这个方向不通
}
}//根据栈中信息打印马的行走路径
printf（"马的遍历路径如下:
\n"）;
for（i=0;i<90;i++）
{
printf（"（%2d,%2d）->",p.pa[i].x,p.pa[i].y）;
if（（i+1）%（8）==0）
printf（"\b\b\n->"）;
}
}
5.5主函数：
intmain（）
提示输入起点位置，这里的起点位置就是日常生活观念中的顺序，开始点是（1,1）,而不是数组中的初始位置（0,0）,输入错误则提示重新输入，时间复杂度为。
intmain（）
{//主函数
intx,y;
charch='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"）;
else
break;
}
while
（1）
{
printf（"请输入入口点纵坐标（在1-9之间）：
"）;
scanf（"%d",&y）;
if（y<1||y>9）
printf（"输入错误，请重新输入!
（纵坐标在1-9之间）\n"）;
else
break;
}
Knight（x,y）;
Getchar（）;
Printf（"\n"）;
printf（"是否继续马的遍历（是：
y；否：
其他）：
"）;
fflush（stdin）;
scanf（"%c",&ch）;
}
}
5.6棋盘初始化函数voidMark_Che（intv）
此函数作为棋盘初始化函数，因为每次执行程序时，棋盘上必须是全部都没有走过的。
它会自动进行初始化棋盘，在14*13的棋盘上初始化。
初始化后，棋盘大小的区域全部是0，而周围的两堵墙标志为1，时间复杂度为。
voidMark_Che（）
{//标志棋盘函数
inti,j;
for（i=0;i<14;i++）//首先全部标记为0
for（j=0;j<13;j++）
chess[i][j]=0;
for（i=0;i<2;i++）//前面两行标记为1
for（j=0;j<13;j++）
chess[i][j]=1;
for（j=0;j<2;j++）//前面两列标记为1
for（i=0;i<14;i++）
chess[i][j]=1;
for（j=11;j<13;j++）//后面两列标记为1
for（i=0;i<14;i++）
chess[i][j]=1;
for（i=12;i<14;i++）
for（j=0;j<13;j++）//后面两行标记为1
chess[i][j]=1;
}
5.7标记初始化函数voidMark_Dir（）
此函数和上面的函数功能类似，也是初始化才用，它是为栈的实现提供帮助的。
开始时全部标记为0，表示周围的八个方向都可以走，时间复杂度为。
voidMark_Dir（）
{//初始化，为栈的实现做准备，全部标记为0，表示八个方向都是通路
//由于三维数组赋初值比较困难，因而采用单独的函数实现
inti,j,k;
for（i=0;i<14;i++）
for（j=0;j<13;j++）
for（k=0;k<8;k++）
CanPass[i][j][k]=0;
}
结论
从这周的上机实践中，我体会到上机的重要性。
编写程序，离不开上机，一段不懂的代码只有经过反复的研读，调试与修改，最终变成自己的代码。
一周的学习，让我学会一些知识，不在于学到了那么点技术，而在于心理得到了洗礼！
在此，我不说老师的功劳，也不提以前怎么怎么没好好听讲，没好好复习，没好好珍惜上机的机会。
但这次，最终我确实得到了锻炼，这就足够了！
对于接下来的路程，脚踏实地，勤奋努力比什么都重要；代码是枯燥的，但不枯燥的是学习的过程，难得的是学习过程中体会的快乐，有目标的学习与坚持，生活才会更加美好！
参考文献
［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2003．
［2］《数据结构题集》，严蔚敏，清华大学出版社，2005．
［3］《数据结构》（C语言版），刘大有，高等教育出版社，2004．
［4］《DataStructurewithC++》，WilliamFord．WilliamTopp，清华大学出版社，2003．
附录A：
程序代码
#include
#include
intchess[14][13];
//定义棋盘
intCanPath[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];
inttop;
}path;//顺序栈
voidInit_Path（path*p）
{//初始化栈
p->top=-1;
}
intPush_Path（path*p,pathnodet）
{//进栈点及其向下一位移动的方向入栈
if（p->top>=89）
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_path（pathp）
{//判断栈是否为空
if（p.top<0）return1;
elsereturn0;
}
intPop_Path（path*p,pathnode*t）
{//出栈
if（Empty_path（*p））
return-1;
else
{
t->x=p->pa[p->top].x;
t->y=p->pa[p->top].y;
t->di=p->pa[p->top--].di;
return1;
}
}
intCount（intx,inty）
{//计算每个节点周围有几个方向可以走
intcount=0,i=0;
for（i=0;i<8;i++）
if（chess[x+1+dir[i].x][y+1+dir[i].y]==0）
count++;
returncount;
}
intFind_Direction（intx,inty）
{//寻找下一个方向，如果找到返回值，否则为0
intdire,min=9,count,d=9;
for（dire=0;dire<8;dire++）
{
if（chess[x+1+dir[dire].x][y+1+dir[dire].y]==0&&
CanPath[x+1][y+1][dire]==0）
{
count=Count（x+dir[dire].x,y+dir[dire].y）;
if（min>count）
{
min=count;
d=dire;
}
}
}
if（d<9）
returnd;
else
return-1;
}
voidMark_Dir（）
{//初始化，为栈的实现做准备，全部标记为0，表示八个方向都是通路
inti,j,k;
for（i=0;i<14;i++）
for（j=0;j<13;j++）
for（k=0;k<8;k++）
CanPa
升级会员 