西安郵電學院
数据结构
课内实验报告书
院系名称：计算机学院
实验题目：马踏棋盘
学生姓名：
专业名称：计算机科学与技术班级：
学号：
时间： 2011年10月10日指导教师：曾艳
一、实验题目：马踏棋盘
二、实验目的：
通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。

三、实验要求：
设计一个国际象棋的马踏遍棋盘的演示程序。

要求：将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。

要求每个方格只进入一次，走遍棋盘上全部64个方格。

编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之
四、设计与实现过程
（1）栈或队列的定义及其主要操作的实现
struct Chess
{
int x;
int y;
int h;/*h记录下一次需要试探的马字格式的下标值*/
}Chess1[65];
（2）主要算法的描述
void Handlechess(int m,int n)
{
int flag=1,i;
double j=0.0;/*增加了j用于统计while循环的执行次数，很好奇循环到底执行了多少次*/
int chessx[8]={-2,-2,-1,-1,1,1,2,2};/*马字的格式的8个位置，按下标序依次试探*/
int chessy[8]={-1,1,-2,2,-2,2,-1,1};
for(i=1;i<=64;i++)
Chess1[i].h=0;/*赋初值*/
chess[m][n]=flag;
Chess1[flag].x=m;
Chess1[flag].y=n;
while(flag<64)
{ j+=1.0;
for(i=Chess1[flag].h;i<8;i++)/*i的初值由Chess1[flag].h确定*/
{
m=Chess1[flag].x+chessx[i];
n=Chess1[flag].y+chessy[i];
if((m>=0&&m<=7&&n>=0&&n<=7)&&(chess[m][n]==0))/*去掉了函数，改为直接用关系表达式判断，提高运行速度*/
{
Chess1[flag].h=i+1;/*h记录下一次需试探马字格式位置的下标*/
flag++;
chess[m][n]=flag;
Chess1[flag].x=m;
Chess1[flag].y=n;
break;
}
}
if(i==8)/*回退操作*/
{
m=Chess1[flag].x;
n=Chess1[flag].y;
Chess1[flag].h=0;
chess[m][n]=0;
flag--;
}
if(flag==0)
{
printf("the horse cannot reach!!!\n"); return;/*增加了return*/ }
}
printf("\n---%lf\n",j);/*显示while循环的执行次数，果然是个很大的值*/ }
五、运行结果
六、技巧与体会
当然还有的地方有待完善，另外贪心做法比此算法能更好的提高的效率，要去更好的学习。