数据结构马的遍历实验

马的遍历问题

目录

1.问题描述： ............................................................................................. 1

2.设计思路： ............................................................................................. 1

3.数据结构设计： ..................................................................................... 1

4.功能函数设计： ..................................................................................... 2

5．编码实现： .......................................................................................... 3

6.运行和测试： ......................................................................................... 8

马的遍历问题

1.问题描述：

在中国象棋（10*9）和国际象棋（8*8）的棋盘的任意位置上放一个马，然后按照“马走日”的走法，在没有蹩马脚的下，选择一个合适的路线，使得棋子能够不重复的

走完棋盘上的每一步。试设计这样一个算法，能够实现这样的功能，并且能够打印出走过的正确路径。

2.设计思路：

这个题目采用的是算法当中的深度优先算法和回溯法：在“走到”一个位置后要寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。

但是如果只是单纯的这样简单寻找的话，造成的结果很可能是机器没有提示错误，但是CPU运行率高达50%，因为要尝试超过1万亿种路线,普通的计算机难以实现这样巨大的运算量。

所以这种方法有待改进。

改进后的方法思想基本类似，但是回溯量大大减少，有时甚至不用回溯都可以完成。它的精华在于寻找下一步的时候，不是单纯的在周围的八个方向中按照既定的顺序找到一个可以走的点就结束；而是对周围的这几个点进行比较，从而分出优劣程度，即看它们周围可以走的点谁最少，然后就走那条可走路线最少的那条。进过这样的筛选后，就会为后面的路径寻找提供方便，从而减少回溯次数。

本程序的棋盘和数组类似，因而采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。

3.数据结构设计：

同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围个加了两层“墙”。具体数据结构定义如下： int chessboard[14][13];//采用最大的中国象棋10*9制的 int CanPass[14][13][8];//每个棋子的八个方向哪些可以走 typedef struct

{//棋盘的八个方向 int y; int x; }direction;

direction dir[8]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};//八个方向 typedef struct

1

{栈的节点结构 int x,y;//走过位置

int di;//走向下一个方向 }pathnode; typedef struct{

pathnode pa[90];//栈的容量最大为90 int top;//栈顶 }path;//顺序栈

4.功能函数设计：

（1）棋盘初始化函数void Mark_Che(int v)

此函数作为棋盘初始化函数，因为每次执行程序时，棋盘上必须是全部都没有走过的。 它会自动按照用户输入的棋盘类型进行初始化棋盘，如果是国际象棋，就只在前面的12*12的棋盘上初始化；如果是中国象棋，则在14*13的棋盘上初始化。初始化后，棋盘大小的区域全部是0，而周围的两堵墙标志为1. （2）标记初始化函数void Mark_Dir(int v)

此函数和上面的函数功能类似，也是初始化只用，它是为栈的实现提供帮助的。开始时全部标记为0，表示周围的八个方向都可以走。

（3）计算一个点周围有几个点函数int Count(int x,int y)

该函数实现的功能是在遍历的过程当中计算一个点周围有几个方向可以走，从而为后面的筛选提供依据。

（4）寻找下一个方向函数int Find_Direction(int x,int y)

该函数的功能是在走过一个点之后，寻找下一个适合的点，如果找到返回正常的方向值，否则返回-1。 （5）栈的相关函数

初始化栈：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是拿出来的节点 （6）骑士遍历函数：void Knight(int x,int y,int v)

这是该算法的精华部分，x,y表示入口地点，v表示棋盘类型，这个函数主体是一个循环，循环里面始终是在找下一个点，如果找到就将该点进栈，找不到则退栈。直到发生栈为空时时还退栈或循环结束，前一种情况时会提示找不到路径(虽然不会发生，但是为逻辑严密性依然要如此)，后一种情况则打印出走过的正确路径和走过之后的数组。 （7）主函数：void main()

进入主函数后提示用户输入那种棋盘，只能输入0和1两个数字，其他的数字则提示输入错误，重新输入。然后提示输入起点位置，这里的起点位置就是日常生活观念中的顺序，开始点是(1,1),而不是数组中的初始位置(0,0),输入错误则提示重新输入。

2

5．编码实现：

#include #include

int chessboard[14][13];//棋盘

int CanPass[14][13][8];//每个棋子的八个方向哪些可以走

typedef struct{//棋盘的八个方向 int y,x; }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,int v) {//压节点及其向下一位移动的方向入栈 if(p->top>=63+26*v) 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)

3

{//判断栈是否为空 if(p.top<0) return 1; return 0; }

int Pop_Path(path *p,pathnode *t) {//出栈 if(Empty(*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(chessboard[x+1+dir[i].x][y+1+dir[i].y]==0) count++; return count; }

int Find_Direction(int x,int y) {//寻找下一个方向 int dire,min=9,count,d=9; for(dire=0;dire<8;dire++) { if(chessboard[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;

4

else return -1; }

void Knight(int x,int y,int v)//x,y表示出发位置 {//骑士遍历函数 int num=1,t,i; path p; pathnode f; Init_Path(&p); for(num=1;num<=+26*v;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,v); x=x+dir[t].x;y=y+dir[t].y; } else if(num==+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; CanPass[x+1][y+1][f.di]=1; }//end else } //根据栈中信息打印出骑士行走路径 printf(\"骑士巡游路径如下:\\n \"); for(i=0;i<+26*v;i++) {

5

printf(\"(%2d,%d)->\ if((i+1)%(8+v)==0) printf(\"\\b\\b \\n->\"); } printf(\"\\b\\b \\n\"); printf(\"根据数组打印结果是:\\n\"); for(i=0;i<8+2*v;i++) {//根据棋盘数组来打印 for(t=0;t<8+v;t++) printf(\"%4d\ printf(\"\\n\"); } }

void Mark_Dir(int v)

{//由于三维数组赋初值比较困难，因而采用单独的函数实现 int i,j,k; for(i=0;i<12+2*v;i++) for(j=0;j<12+v;j++) for(k=0;k<8;k++) CanPass[i][j][k]=0; }

void Mark_Che(int v) {//标志棋盘函数 int i,j; for(i=0;i<12+2*v;i++)//首先全部标记为0 for(j=0;j<12+v;j++) chessboard[i][j]=0; for(i=0;i<2;i++)//前面两行标记为1 for(j=0;j<12+v;j++) chessboard[i][j]=1; for(j=0;j<2;j++)//前面两列 for(i=0;i<12+2*v;i++) chessboard[i][j]=1; for(j=10+v;j<12+v;j++)//后面两列 for(i=0;i<12+2*v;i++) chessboard[i][j]=1; for(i=10+2*v;i<12+2*v;i++) for(j=0;j<12+v;j++)//后面两行 chessboard[i][j]=1; }

6

void main() {//主函数 int x,y,v; char ch='y';

while(ch=='y') { while(1){ printf(\"请选择棋盘类型(0:国际象棋，1:中国象棋):\"); scanf(\"%d\ if(v!=1&&v!=0) printf(\"输入错误，请重新输入!\\n\"); else break; } Mark_Che(v); Mark_Dir(v); while(1) { printf(\"请输入入口点横坐标：\"); scanf(\"%d\ if(x<1||x>8+2*v) printf(\"输入错误，请重新输入!(横坐标在1-%d之间)\\n\ else break; } while(1) { printf(\"请输入入口点纵坐标：\"); scanf(\"%d\ if(y<1||y>8+v) printf(\"输入错误，请重新输入!(纵坐标在1-%d之间)\\n\ else break; } Knight(x,y,v); printf(\"继续(是：y;否：其他):\"); fflush(stdin); scanf(\"%c\ } }

7

6.运行和测试：

程序运行开始时，提示用户输入棋盘类型: 首先选择3，提示“输入错误，请重新输入”；然后选择0，提示输入入口横坐标，输入0，提示“输入错误，请重新输入!（横坐标在1-8之间）”；再次输入1，提示输入纵坐标，输入9，提示“输入错误，请重新输入!（纵坐标在1-8之间）”，再次输入2；出现结果，有两种形式，第一种是坐标形式，第二种是数组形式；

提示是否继续，输入’y’。提示输入象棋类型，输入1，提示输入横坐标，输入5，提示输入纵坐标，输入6，出现结果，与上述类似。

提示是否继续，输入’n’,结束。运行结果如下图示：

8