马踏棋盘数据结构实践报告.docx
《马踏棋盘数据结构实践报告.docx》由会员分享，可在线阅读，更多相关《马踏棋盘数据结构实践报告.docx（8页珍藏版）》请在冰点文库上搜索。
马踏棋盘数据结构实践报告
马踏棋盘问题
摘要：
马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。
理解栈的“后进先出”的特性以及学会使用回溯。
关键字：
马踏棋盘、递归、栈、回溯
1．引言
马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。
编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2….64依次填入一个8X8的方阵，并输出它的行走路线。
输入：
任意一个起始位置；输出：
无重复踏遍棋盘的结果，以数字1-64表示行走路线。
2．需求分析
（1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。
（2）输入马的起始位置，必须保证输入的数字在规定范围内，即0<=X<=7,0<=Y<=7。
（3）保证马能走遍整个棋盘，并且不重复。
（4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。
3．数据结构设计
采用栈数组为存储结构。
#definemaxsize100
struct
{
inti;
intj;
intdirector;
}stack[maxsize];
4．算法设计
4.1马的起始坐标
voidlocation（intx,inty）//马的位置坐标的初始化
{
top++;
stack[top].i=x;//起始位置的横坐标进栈
stack[top].j=y;//起始位置的竖坐标进栈
stack[top].director=-1;
a[x][y]=top+1;//标记棋盘
Try（x,y）;//探寻的马的行走路线
}
4.2路径探寻函数
voidTry（inti,intj）
{intcount,find,min,director;
inti1,j1,h,k,s;
intb[8]={-2,-2,-1,1,2,2,1,-1},c[8]={1,-1,-2,-2,-1,1,2,2};
//存储马各个出口相对当前位置行、列坐标的增量数组
intb2[8],b1[8];
for（h=0;h<=7;h++）//用数组b1[8]记录当前位置的下一个位置的可行路径的条数
{count=0;
i=stack[top].i+c[h];
j=stack[top].j+b[h];
if（i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0）//如果找到下一个位置
{
for（k=0;k<=7;k++）
{
i1=i+c[k];
j1=j+b[k];
if（i1>=0&&i1<=7&&j1>=0&&j1<=7&&a[i1][j1]==0）//如果找到下一个位置
count++;//记录条数
}
b1[h]=count;//将条数存入b1[8]中
}
}
for（h=0;h<=7;h++）//根据可行路径条数的大小，从小到大排序，并放入数组b2[8]中
{min=9;
for（k=0;k<=7;k++）
if（min>b1[k]）
{
min=b1[k];
b2[h]=k;
s=k;
}
b1[s]=9;
}
find=0;
director=stack[top].director;
for（h=director+1;h<=7;h++）//向8个方向进行寻找
{
i=stack[top].i+c[b2[h]];
j=stack[top].j+b[b2[h]];
if（i>=0&&i<=7&&j>=0&&j<=7&&a[i][j]==0）
{stack[top].director=h;//存储栈的寻找方向
top++;//进栈
stack[top].i=i;
stack[top].j=j;
stack[top].director=-1;//重新初始化下一栈的方向
a[i][j]=top+1;
find=1;//找到下一位置
break;
}
}
if（find!
=1）
{a[stack[top].i][stack[top].j]=0;//清除棋盘的标记
top--;//退栈
}
if（top<63）
Try（i,j）;//递归
}
4.3输出函数
voiddisplay（）
{
inti,j;
for（i=0;i<=7;i++）
{for（j=0;j<=7;j++）
printf（"\t%d",a[i][j]）;//输出马的行走路线
printf（"\n\n"）;
}
printf（"\n"）;
}
5.程序实现
5.1主函数
voidmain（）
{
inti,j,x,y;
for（i=0;i<=7;i++）//棋盘的初始化
for（j=0;j<=7;j++）
a[i][j]=0;
printf（"输入XY（0=scanf（"%d%d",&x,&y）;
if（x>=0&&x<=7&&y>=0&&y<=7）
//判断输入的起始位子是否正确
{
location（x,y）;
display（）;
}
elseprintf（"错误\n"）;
}
5.2运行结果
（1）当输入不符合要求时
（2）正确输入时
5.3算法分析
（1）马的起始坐标
一开始先建立一个栈数组，里面包括横坐标和竖坐标还有方向。
输入马的起始位置，进入坐标起始化函数，让输入的横坐标和竖坐标进栈，并初始化方向，并且标记棋盘，指示此位置已走过，此时的位置是栈的第一个元素，进入路径探寻函数。
（2）路径探寻函数
路径探寻函数中有两个分别存储马各个出口相对当前位置行、列坐标的增量数组。
要使马走遍所有的棋盘，必须要有一定的行走规律。
我使用的是记录当前位置的下一个位置的可行路径的条数，并对它们进行排序，按从小到大的顺序存储在一个一维数组中。
开始进行探寻，分别向8个方向探寻，如果找到一个方向可行，则存储栈的寻找方向，再进栈，重新初始化栈的寻找方向，并用二维数组标记此位置，再使用递归进入下一次新的探寻。
如果在某一次探寻中，没能找到方向，则清除该位置的标记，并退栈，再次递归，回到上次的寻找方向（之前已经存储过栈的寻找方向），跳过已经寻找过的方向，再进行探寻，直到全部棋盘都被走遍。
（3）输出函数
当马走遍所有的棋盘时，输出马的行走路线，因为之前已经把马的行走路线记录在二维数组中了，所以此时只需把二维数组中的标记输出即可。
6.设计体会
本次课程设计让我学会了很多东西，使得我对于栈的理解更深入了，使用更加熟练。
是此之前，我对于回溯并不是特别了解，但是这次设计让我学会了回溯的基本概念以及基础的用法。
当一件事情有很多种方法进行时，我们要将所有的方法集合起来形成一个集合，再用一定的规律去调用这个集合内的方法。
刚开始的时候，我并不能让马走遍所有的棋盘，但当我知道了回溯的思想之后，我修正了我的算法，最终使马走遍所有的棋盘。
我还考虑了递归与非递归的问题，在试验了两种方法之后，发现两种都可以，在时间的复杂度上也没有太大的差别（显示棋盘的时间上），但我还是使用的是递归的方法来完成本次设计。
参考文献：
[1]严蔚敏、吴伟民编著．数据结构（C语言版）．北京：
清华大学出版社，２００７
[2]谭浩强主编．C程序设计（第三版）．北京：
清华大学出版，2005
[3]张蕊、吕涛主编．C程序设计教程.华中科技大学出版，2012
升级会员 