西安郵電學院

数据结构

课内实验报告书

一、实验题目：马踏棋盘

二、实验目的：

通过本次实验，熟练掌握抽象数据类型栈和队列的实现，学会使用栈和队列解决具体应用问题，从而体会栈和队列的特点。

三、实验要求：

设计一个国际象棋的马踏遍棋盘的演示程序。

要求：将马随机放在国际象棋的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循环的执行次数，果然是个很大的值*/

}

五、运行结果

六、技巧与体会

当然还有的地方有待完善，另外贪心做法比此算法能更好的提高的效率，要去更好的学习。

 

第二篇：马踏棋盘

马踏棋盘

学 院 专 业 学 号 学生姓名 指导教师

年 月 日

摘要：

国际象棋想必大家都玩过，但你有没有想过，让一个“马”遍历国际象棋8*8的棋盘，有没有可能？如果有可能，在给定起点的情况下，有多少种可能？下面，我们将用计算机来模拟“马”对棋盘的遍历.

关键字：

回溯算法 贪心算法 遍历

正文：

已知国际象棋为8×8棋盘，共64个格，规则中，马按

照如图所示规则移动。将马放在任意方格中，令马遍历每个方

格一次且仅一次，编制非递归程序，将数字1，2，?，64按

照马的行走路线依次填入一个8×8的方阵，并输出结果。

通过结合图示，我们不难发现，当马的起始位置（i,j）

确定的时候，可以走到下列8个位置之一：

(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）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不可达的位置。8个可能位置可以用一维数组Htry1[0?7]和HTry2[0..7]来表示：

Htry1：

Htry2：

0 1 2 3 4 5 6 7

所以位于（i,j）的马可以走到新位置是在棋盘范围内的（i+ Htry1[h],j+Htry2[h]）,其中h的取值是0~7.

整个问题，我们可以用两种算法来解决，既“回溯算法”与“贪心算法” 我们先来看回溯算法：

搜索空间是整个棋盘上的8*8个点.约束条件是不出边界且每个点只能经过

一次.搜索过程是从一点(i，j)出发，按深度有限的原则，从8个方向中尝试一个可以走的点，直到走过棋盘上所有的点.当没有点可达且没有遍历完棋盘时，就要撤销该点，从该点上一点开始找出另外的一个可达点，直到遍历完整个棋盘 我们接着看程序的需求分析：

1．输入的形式和输入值的范围；

分开输入马的初始行坐标X和列坐标Y，X和Y的范围都是［0,7］。

2．输出的形式；

一共提供了2种输出方式：

（1）以数组下标形式输入，代表起始位置，i表示行标，j表示列标。

（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。

接下来就是整个程序的设计了：

1．本程序包含2个模块

(1).主程序模块:

Void main()

{

初始化棋盘；

while(1) {

接受命令；

处理命令；

}

执行Path(x,y);

}

(2).栈模块－实现栈抽象数据类型

2.探讨每次选择位置的“最佳策略”思路

这里涉及到了贪心算法的思想.所谓贪心算法，就是确定马的起始节点后，在对其子结点进行选取时，优先选择出度最小的子节点进行搜索，这是一种局部调整最优的做法，如果优先选择出度多的子结点，那出度少的子结点就会越来越多，很可能出现‘死’结点（即没有出度又不能跳过的节点），反过来如果每次都优先选择出度少的结点跳，那出度少的结点就会越来越少，这样跳成功的机会就更大一些。

1）先求出每个坐标点的出度值，即是该坐标下一步有几个方向可以走

2）出度值越小,则被上一点选中的可能性就越大，下一个方向八个值的选择顺序保存MAP[X][Y][K]数组中，0<=K<=7，例如MAP[X][Y][0]保存的是下一步优先选择走的方向，MAP[X][Y][7]就是最后才走的。边界的点最先走，然后再走中间.

3．踏遍棋盘伪码算法：

While（）

{

若已经走了64步,则{

打印输出结果；若要寻找多条路径，出栈，回溯到上一步，下一步方向加1*}

否则{

若该点所有方向已走完{

出栈，回溯到上一个点，上一个点要走的方向加1}

若该点所有方向未走完{

若该点未走过且在棋盘内{

入栈，已走步数加1}

否则{*下一步方向加1}

}

}

}

程序源码（含注释）：

#include<malloc.h>

#include<limits.h>

#include<stdio.h>

#include<math.h>

#include<process.h>

#include<conio.h>

#include<dos.h>

#define CLS system("cls")

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 1

#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */

#define N 8 /*定义棋盘大小*/

typedef int Status;

typedef struct chess

{

int x;

int y;

int z;

}chess;

typedef chess SElemType;

int map[N][N][8]; /*按各点权值递升存放待走方向,每点8个*/ int weight[N][N]; /*各点的权值*/

int board[N][N]; /*棋盘,未走过时值为0,走过后值为1*/ static SElemType HTry[8] = /* 8个候选方向的偏移值*/

{

{-2, 1, 0},{ -1, 2, 0},{ 1, 2, 0},{ 2, 1, 0},{ 2, -1, 0}, {1, -2, 0}, {-1, -2, 0}, {-2, -1, 0}

};

void setweight();/*求各点权值*/

void setmap(); /*各点的8个方向按权值递增排列*/

void Path(int x, int y); /*主算法函数,踏遍棋盘*/

/*栈的顺序存储表示 */

typedef struct SqStack

{

SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */

int stacksize; /* 当前已分配的存储空间，以元素为单位 */

}SqStack; /* 顺序栈 */

Status InitStack(SqStack *S) /* 构造一个空栈S */

{

(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!(*S).base)

exit(OVERFLOW); /* 存储分配失败 */

(*S).top=(*S).base;

(*S).stacksize=STACK_INIT_SIZE;

return OK;

}

Status StackEmpty(SqStack S)

{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */

if(S.top==S.base)

return TRUE;

else

return FALSE;

}

Status GetTop(SqStack S,SElemType *e)

{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */ if(S.top>S.base)

{

*e=*(S.top-1);

return OK;

}

else

return ERROR;

}

Status SetTop(SqStack S,SElemType *e)

{

if(S.top>S.base)

{

*(S.top-1)=*e;

return OK;

}

else

return ERROR;

}

Status Push(SqStack *S,SElemType e)

{ /* 插入元素e为新的栈顶元素 */

if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */

{

(*S).base=(SElemType

*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base)

exit(OVERFLOW); /* 存储分配失败 */

(*S).top=(*S).base+(*S).stacksize;

(*S).stacksize+=STACKINCREMENT;

}

*((*S).top)++=e;

return OK;

}

Status Pop(SqStack *S,SElemType *e)

{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */

if((*S).top==(*S).base)

return ERROR;

*e=*--(*S).top;

return OK;

}

void main()/*主函数*/

{

int x,y;

int i,j,k=0;

for(i=0;i<N;i++)

for(j=0;j<N;j++)

board[i][j]=0;

setweight();

setmap();

while(1)

{

printf("输入马的行坐标 X (from 0 to 7):");

scanf("%d",&x);

printf("输入马的列坐标 Y (from 0 to 7):");

scanf("\n%d",&y);

if(x<0||x>7||y<0||y>7)

{printf("输入错误!\n\n");

flushall();}

else

break;

}

Path(x,y);

}/*end main()*/

/*求各点权值:可走的方向数.该值越小,则被上一点选中的可能性越大*/ void setweight()

{

int i,j,k,x1,y1;

for(i=0;i<N;i++)/*for 1*/

{

for(j=0;j<N;j++)/*for 2*/

{

weight[i][j]=0;

for(k=0;k<N;k++)/*for 2*/

{

x1=i+HTry[k].x;

y1=j+HTry[k].y;

if(x1>=0&&x1<N&&y1>=0&&y1<N)

{

weight[i][j]++;/*即在8个方向中，（i，j）点有几个方向可以移动*/

}

}

}

} /*end of for 1 */

}/*end setweight()*/

/*检查(i,j)是否在棋盘内*/

int check(int i,int j)

{

if(i<0||i>=8||j<0||j>=8)

return 0;

return 1;

}

/*将各点的8个方向按该方向下的目标点的权值递增排列*/

void setmap()

{

int i,j,k,m,d1,d2,x1,x2,y1,y2,l1,l2;

for(i=0;i<N;i++)/*for 1*/

{

for(j=0;j<N;j++)/*for 2*/

{

for(k=0;k<8;k++)

map[i][j][k]=k;/*默认8个方向顺时针赋值*/

for(k=0;k<8;k++)

/*for 3 与 for 4 两个循环 对方向索引按 点的权值升序排列，不能到达的方向排在最后*/

{

for(m=k+1;m<8;m++) /*for 4*/

{

d1=map[i][j][k];

x1=i+HTry[d1].x;

y1=j+HTry[d1].y;

d2=map[i][j][m];

x2=i+HTry[d2].x;

y2=j+HTry[d2].y;

l1=check(x1,y1);

l2=check(x2,y2);

if((l1==0&&l2)||(l1&&l2&&(weight[x1][y1]>weight[x2][y2]))) {

map[i][j][k]=d2;

map[i][j][m]=d1; /*交换两个方向值,按权值递增排列,不可到达的目标点(超出棋盘)的方向放在最后面*/

}

/*end if*/

}

/*end for 4*/

}

/*end for 3*/

}

/*end for 2*/

}

/*end for 1*/

}/*end setmap()*/

/*输出函数*/

void output(SqStack &a)

{ SqStack b;

int c[8][8]={0},j,k=N*N,l=1,x,y;

InitStack (&b);

SElemType e;

while(!StackEmpty(a))

{

Pop(&a,&e);

c[e.x][e.y]=k;

k--;

Push(&b,e);

}

GetTop(b,&e);

x=e.x;y=e.y;

printf("起始坐标:(%d,%d)\n",x,y);

while(!StackEmpty(b))

{ Pop(&b,&e);

printf("(%d,%d)",e.x,e.y);

Push(&a,e);

}

printf("棋盘表示: 0 1 2 3 4 5 6 7\n"); printf(" ┌─┬─┬─┬─┬─┬─┬─┬─┐\n"); printf(" 0");

for(j=0;j<=7;j++)

{if(c[0][j]<10) printf("│ %d",c[0][j]);else

printf("│%d",c[0][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n");

printf(" 1");

for(j=0;j<=7;j++)

{ if(c[1][j]<10) printf("│ %d",c[1][j]);else

printf("│%d",c[1][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n");

printf(" 2");

for(j=0;j<=7;j++)

{ if(c[2][j]<10) printf("│ %d",c[2][j]);else

printf("│%d",c[2][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n");

printf(" 3");

for(j=0;j<=7;j++)

{ if(c[3][j]<10) printf("│ %d",c[3][j]);else

printf("│%d",c[3][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n"); printf(" 4");

for(j=0;j<=7;j++)

{ if(c[4][j]<10) printf("│ %d",c[4][j]);else

printf("│%d",c[4][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n"); printf(" 5");

for(j=0;j<=7;j++)

{ if(c[5][j]<10) printf("│ %d",c[5][j]);else

printf("│%d",c[5][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n"); printf(" 6");

for(j=0;j<=7;j++)

{if(c[6][j]<10) printf("│ %d",c[6][j]);else

printf("│%d",c[6][j]);}printf("│\n");

printf(" ");

printf("├─┼─┼─┼─┼─┼─┼─┼─┤\n"); printf(" 7");

for(j=0;j<=7;j++)

{if(c[7][j]<10) printf("│ %d",c[7][j]);else

printf("│%d",c[7][j]);}printf("│\n");

printf(" ");

printf("└─┴─┴─┴─┴─┴─┴─┴─┘\n");

}

/*踏遍棋盘算法*/

void Path(int xx, int yy)

{ int c[N*N]={0},h[N*N]={0};

SqStack a;

SElemType ptemp;

SElemType pop_temp,get_temp;

SElemType p,dest_p; /*当前点和目标点*/ int step=0,x,y,s,k=1,l=1,d =0;

char ch;

p.x = xx; p.y = yy;p.z = 0;/*初始化出发点*/

board[xx][yy]=1;

InitStack(&a);

Push(&a,p); /*起始点的坐标和首选方向入栈*/ while(1)

{

if (step==(N*N-1)) { output(a); printf("退出/返回/下一条路径?q/b/n\n"); printf("第%d条路径",k); ch=getch(); if(ch=='b') {CLS;main();} else if(ch=='q') exit(1); else /*寻找下一条路径*/ { k++;/*路径数加1*/ Pop(&a,&pop_temp); /*退栈*/ GetTop(a,&get_temp); /*取当前栈顶元素*/ ptemp.x=get_temp.x; ptemp.y=get_temp.y; ptemp.z=get_temp.z+1; SetTop(a,&ptemp); /*更改方向*/ step--; continue; } } if(StackEmpty(a)) break; GetTop(a,&p); x=p.x; y=p.y; d=p.z; if(d>=8)/*该点所有方向已走完，退栈*/ { board[x][y]=0; /*抹去痕迹*/ step--; /*步数减一*/ Pop(&a,&pop_temp); /*退栈*/ GetTop(a,&get_temp); /*取当前栈顶元素*/ ptemp.x=get_temp.x; ptemp.y=get_temp.y; ptemp.z=get_temp.z+1; SetTop(a,&ptemp); /*更改方向*/ } /*end if (d>=8)*/ if(d<8)/*方向未走完*/ { s=map[x][y][d];/*map[x][y][0]未必是(x,y)点的HTry[0]方向, 而是到该点可到的权值最小的点的方向即HTry[map[x][y][0]*/ dest_p.x=x+HTry[s].x;dest_p.y=y+HTry[s].y;

if(check(dest_p.x,dest_p.y)&&board[dest_p.x][dest_p.y]==0)

/*目标点在棋盘内且未被走过,则将目标点入栈同时标记当前点为已走过*/

{

h[step]=step;

board[x][y]=1;step++;/*步数加一*/

dest_p.z=0;

Push(&a,dest_p);/*存入目标点,方向栈初始*/

}

else/*目标点已被走过或目标点不在棋盘内,换方向*/

{

ptemp.x=p.x;

ptemp.y=p.y;

ptemp.z=d+1;/*取下一个方向*/

SetTop(a,&ptemp);/*切换方向*/ }

} /*enf if(d<8)*/

} /*end while(1)*/

}

至此，源程序完

结果截图：

参考文献：

1：谭浩强，C语言程序设计（第二版），清华大学出版社

2：（美）Anany Levtin（著），潘彦译，算法设计与分析基础，清华大学出版社 3：吕国英，算法设计与分析，清华大学出版社