桂林电子科技大学
数学与计算科学学院综合性、设计性实验报告
实验室：06406实验日期：2015年05月29日
院（系）
信息与计算科学系
年级、专业、班
1300710226
姓名
庞文正
成绩
课程
名称
数据结构实验
实验项目
名 称
马踏棋盘问题
指导
教师
教师
评语
教师签名：
年 月 日
一 ，实验目的
加深对图的理解，培养解决实际问题的编程能力。根据数据对象的特性，学会数据组织的方
start.y--;
curstep=1; //第一步
Move(start); //求解
}
五，实验结果分析或总结
运行半天不出来，比如输入 2 2还以为算法有误，后来想通了，真开心！
{n");
scanf("%d%d",&start.x,&start.y);
}
else
{
break;
}
}
for(i=0;i<8;i++) //初始化棋盘个单元位置
{
for(j=0;j<8;j++)
{
chessboard[i][j]=0;
}
}
start.x--;
格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域指向该顶点所能到达的第一个结点。
表头结点：
Vex
x
y
link
Vex:头结点所在的序号
x:头结点所在的横坐标；
y:头结点所在的纵坐标；
link:指向Vex下一个能够到达的邻接结点
for(i=0;i<8;i++) //输出走法
{
for(j=0;j<8;j++)
{
printf("%5d",chessboard[i][j]);
}
printf("\n");
}
exit(0);
}
else //棋盘位置没走完
{
for(i=0;i<8;i++)
{
next.x=curpos.x+fangxiang[i].x;
{
{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}
};
void Move(Coordinate curpos) //马踏棋盘算法
{
Coordinate next;
int i,j;
if(curpos.x<0||curpos.x>7||curpos.y<0||curpos.y>7) //判断越界
curstep--; //减少步数
}
void main()
{
int i,j;
Coordinate start;
printf("马踏棋盘求解！\n");
printf("请输入马的一个起始位置（x,y）：");
scanf("%d%d",&start.x,&start.y);
for(;;)
{
if(start.x<1||start.x>8||start.y<1||start.y>8) //判断输入值是否越界
链表中结点的结构同表头结点的结构同。在此不一一赘述了；
假定我们按照以下方式对棋盘上的格子进行编号（如红色标注），那么编号与格子所在的坐标（如蓝色标注）位置必然存在一定关系。（留给大家思考）
21（1，5）
22（2，5）
23（3，5）
24（4，5）
25（5，5）
16（1，4）
17（2，4）
18（3，4）
19（4，4）
20（5，4）
11（1，3）
12（2，3）
13（3，3）
14（4，3）
15（5，3）
6（1，2）
7（2，2）
8（3，2）
9（4，2）
10（5，2）
1（1，1）
2（2，1）
3（3，1）
4（4，1）
5（5，1）
综合起来，马踏棋盘问题就可以转化为图的遍历问题。
三，使用仪器，材料
XP系统电脑一台，vc++软件！
四，实验内容与步骤
#include<stdio.h>
#include<stdlib.h>
typedef struct
{
int x;
int y; //棋盘上的坐标
}Coordinate;
int chessboard[8][8];; //棋盘
int curstep; //马跳的步骤序号
Coordinate fangxiang[8]= //马可走的方向
法，把现实世界中的实际问题在计算机内部表示出来，培养基本的、良好的程序设计技能。
二，实验原理
整个棋盘可表示为一个M×N的二维数组。假若马目前在位置（i,j）则马下一步可移动的位置0、1、……、7可分别表示为(i-2,j+1),(i-1,j+2),(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，j）,有0<i<M+1,0<j<N+1）。
next.y=curpos.y+fangxiang[i].y;
if(curpos.x<0||curpos.x>7||curpos.y<0||curpos.y>7) //如果越界，不做任何处理
{
}
else //否则进行移动
{
Move(next);
}
}
}
chessboard[curpos.x][curpos.y]=0; //清除步数序号
{
return ;
}
if(chessboard[curpos.x][curpos.y]) //如果已走过，直接返回
{
return ;
}
chessboard[curpos.x][curpos.y]=curstep; //保存步骤数
curstep++;
if(curstep>64) //棋盘位置都走完了
{