马的遍历课程设计报告.doc

攀枝花学院本科课程设计报告（论文）

马的遍历问题求解

学生姓名：
学生学号：
院 (系) ：
年级专业：

2023年 1 月

攀枝花学院本科学生课程设计任务书
题　目
马的遍历问题求解
1、课程设计的目的
1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。
2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。
3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。
2、课程设计的内容和规定（涉及原始数据、技术规定、工作规定等）
在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不反复地走过棋盘上的每一位置。
规定：
（1）依次输出所走过的各位置的坐标。
（2）最佳能画出棋盘的图形形式，并在其上动态地标注行走过程。
（3）程序能方便地地移植到其它规格的棋盘上。

3、重要参考文献
［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2023．
［2］《数据结构题集》，严蔚敏，清华大学出版社，2023．
［3］《数据结构》（C语言版），刘大有，高等教育出版社，2023．
［4］《Data Structure with C++》，William Ford．William Topp，清华大学出版社，2023．
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'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课程设计的目的……………………………………………………………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） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。

开始
输入入口点横坐标
横坐标在1—10之间
输入入口点纵坐标
纵坐标在1—9之间
显示马遍历途径
结束
2 流程图

假

真

假

3 设计思绪
一方面，中国象棋是10*9的棋盘，马的走法是“马走日”，忽略“蹩脚马”的情况。
另一方面，这个题目采用的是算法当中的深度优先算法和回溯法：在“走到”一个位置后要寻找下一个位置，假如发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。在寻找下一步的时候，对周边的这几个点进行比较，从而分出优劣限度，即看它们周边可以走的点谁最少，然后就走那条可走路线最少的那条。通过这样的筛选后，就会为后面的途径寻找提供方便，从而减少回溯次数。
最后，本程序的棋盘和数组类似，因而采用数组进行存储，同时由于有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。同时尚有八个方向的数组，和为栈设计的每个点周边的八个方向那些可以走的数组。

4 数据结构设计
同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，由于为了判断的方便，这里在棋盘周边各加了两层“墙”。具体数据结构定义如下：
int chessboard[14][13]; //采用最大的中国象棋10*9制的
int CanPass[14][13][8]; //每个棋子的八个方向哪些可以走
typedef struct
{ //棋盘的八个方向
int x,y;
}direction;
direction dir[8]={{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 struct{
pathnode pa[90]; //栈的容量最大为90
int 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(chess[x+1+dir[i].x][y+1+dir[i].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(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)
return d;
else
return -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;
else
{
p->top++;
p->pa[p->top].x=t.x;
p->pa[p->top].y=t.y;
p->pa[p->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;
else
{
t->x=p->pa[p->top].x;
t->y=p->pa[p->top].y;
t->di=p->pa[p->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)
{ //正常找到下一个方向的情况下
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;
}
else if(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主函数：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");
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棋盘初始化函数void Mark_Che(int v)
此函数作为棋盘初始化函数，由于每次执行程序时，棋盘上必须是所有都没有走过的。它会自动进行初始化棋盘，在14*13的棋盘上初始化。初始化后，棋盘大小的区域所有是0，而周边的两堵墙标志为1，时间复杂度为。

void Mark_Che()
{ //标志棋盘函数
int i,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标记初始化函数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++)
CanPass[i][j][k]=0;
}

结论

从这周的上机实践中，我体会到上机的重要性。编写程序，离不开上机，一段不懂的代码只有通过反复的研读，调试与修改，最终变成自己的代码。一周的学习，让我学会一些知识，不在于学到了那么点技术，而在于心理得到了洗礼！在此，我不说老师的功劳，也不提以前怎么怎么没好好听讲，没好好复习，没好好爱惜上机的机会。但这次，最终我的确得到了锻炼，这就足够了！对于接下来的路程，脚踏实地，勤奋努力比什么都重要；代码是枯燥的，但不枯燥的是学习的过程，难得的是学习过程中体会的快乐，有目的的学习与坚持，生活才会更加美好！

参 考 文 献

［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2023．
［2］《数据结构题集》，严蔚敏，清华大学出版社，2023．
［3］《数据结构》（C语言版），刘大有，高等教育出版社，2023．
［4］《Data Structure with C++》，William Ford．William Topp，清华大学出版社，2023．

附录A：程序代码

#include<stdio.h>

#include<stdlib.h>

int chess[14][13];
//定义棋盘
int CanPath[14][13][8];
//每个棋子的八个方向哪些可以走
typedef struct{ //棋盘的八个方向
int x,y;
}direction;
direction dir[8]={{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 struct{
pathnode pa[90];
int top;
}path; //顺序栈

void Init_Path(path *p)
{ //初始化栈
p->top=-1;
}
int Push_Path(path *p,pathnode t)
{ //进栈点及其向下一位移动的方向入栈
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;
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;
else
{
t->x=p->pa[p->top].x;
t->y=p->pa[p->top].y;
t->di=p->pa[p->top--].di;
return 1;
}
}

int Count(int x,int y)
{ //计算每个节点周边有几个方向可以走
int count=0,i=0;
for(i=0;i<8;i++)
if(chess[x+1+dir[i].x][y+1+dir[i].y]==0)
count++;
return count;
}
int Find_Direction(int x,int y)
{ //寻找下一个方向，假如找到返回值，否则为0
int dire,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)
return d;
else
return -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++)
CanPath[i][j][k]=0; //马的遍历成功，即通路为0
}
void Mark_Che()
{ //标志棋盘函数，棋盘上区域内都为0，区域边沿设为1

int i,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;

}
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)
{ //正常找到下一个方向的情况下
chess[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;
}
else if(num==90 && chess[x+1][y+1]==0)
{ //遍历到最后，t为-1
chess[x+1][y+1]=num;
f.x=x;
f.y=y;
f.di=t;
Push_Path(&p,f);
}

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->");
}
}
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");
else
break;
}
wh