数据结构—马的遍历

马的遍历 问题描述设计要求是马从棋盘上的一个位置出发，然后按照中国象棋的规则马走日，来走下一步，直到马走完棋盘上的每一个位置终止。 设计思路首先将棋盘每个位置的标记为0，然后对棋盘周围的两个格子标记为1，用于检测，相当于棋盘的边界。每个节点的包含马走过的位置以及方向。将节点以及下一次要走的方向压入栈中，然后对每个节点可以走的方向进行判断，然后找出最佳的方向。 数据结构设计将节点走过的位置以及方向封装到一起，利用栈的特点实现马的遍历。 功能函数设计void Init_Path(path *p)初始化栈int Push_Path(path *p,pathnode t,int v)将节点以及下一次走的方向压入栈中int Empty(path p)判断栈是否为空int Pop_Path(path *p,pathnode *t)出栈int Count(int x,int y)计算节点周围可以移动的所有方向int Find_Direction(int x,int y)寻找下一次移动的方向void Round(int x,int y,int v)马的遍历函数void Mark_Dir(int v)标志方向函数void Mark_Che(int v)标志棋盘函数 程序代码#include#includeint chessboard1413;/二维数组表示棋盘每个棋子位置,其中棋盘四周有两个格子，用于检测int CanPass14138;/每个棋子的八个方向哪些可以走typedef struct/棋盘的八个方向int y,x;direction;direction dir8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1;/八个方向/栈的设计typedef structint x,y;/走过位置int di;/方向pathnode;typedef structpathnode pa90;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;elsep-top+;p-pap-top.x=t.x;p-pap-top.y=t.y;p-pap-top.di=t.di;return 1;int Empty(path p)/判断栈是否为空if(p.topx=p-pap-top.x;t-y=p-pap-top.y;t-di=p-pap-top-.di;return 1;int Count(int x,int y)/计算每个节点周围有几个方向可以走int count=0,i=0;for(i=0;i8;i+)if(chessboardx+1+diri.xy+1+diri.y=0)count+;return count;int Find_Direction(int x,int y)/寻找下一个方向int dire,min=9,count,d=9;for(dire=0;direcount)min=count;d=dire;if(d9)return d;elsereturn -1;void Round(int x,int y,int v)/x,y表示出发位置/马的遍历函数int num=1,t,i;path p;pathnode f;Init_Path(&p);for(num=1;num=64+26*v;num+)t=Find_Direction(x,y);if(t!=-1)/正常找到下一个方向的情况下chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);x=x+dirt.x;y=y+dirt.y;else if(num=64+26*v&chessboardx+1y+1=0)/最后一次时t肯定是-1chessboardx+1y+1=num;f.x=x;f.y=y;f.di=t;Push_Path(&p,f,v);elseif(Pop_Path(&p,&f)=-1)/出栈且栈为空的情况printf(!无法为您找到一条适合的路径!n);exit(0);num-=2;x=f.x;y=f.y;CanPassx+1y+1f.di=1;/end else/根据栈中信息打印出骑士行走路径printf(马的遍历结果如下:n );printf(bb n);for(i=0;i8+2*v;i+)/根据棋盘数组来打印for(t=0;t8+v;t+)printf(%4d,chessboardi+2t+2);printf(n);void Mark_Dir(int v)/由于三维数组赋初值比较困难，因而采用单独的函数实现int i,j,k;for(i=0;i12+2*v;i+)for(j=0;j12+v;j+)for(k=0;k8;k+)CanPassijk=0;void Mark_Che(int v)/标志棋盘函数int i,j;for(i=0;i12+2*v;i+)/首先全部标记为0for(j=0;j12+v;j+)chessboardij=0;for(i=0;i2;i+)/前面两行标记为1for(j=0;j12+v;j+)chessboardij=1;for(j=0;j2;j+)/前面两列标记为1for(i=0;i12+2*v;i+)chessboardij=1;for(j=10+v;j12+v;j+)/后面两列标记为1for(i=0;i12+2*v;i+)chessboardij=1;for(i=10+2*v;i12+2*v;i+)for(j=0;j12+v;j+)/后面两行标记为1chessboardij=1;void main()/主函数int x,y,v=1;char ch=y; while(ch=y) Mark_Che(v);Mark_Dir(v);while(1)printf(请输入入口点横坐标：);scanf(%d,&x);if(x8+2*v)printf(输入错误，请重新输入!(横坐标在1-%d之间)n,8+2*v);elsebreak;while(1)printf(请输入入口点纵坐标：)