资源描述：
《数据结构—马的遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、马的遍历·问题描述设计要求是马从棋盘上的一个位置出发，然后按照中国象棋的规则—马走日，来走下一步，直到马走完棋盘上的每一个位置终止。·设计思路首先将棋盘每个位置的标记为0，然后对棋盘周围的两个格子标记为1，用于检测，相当于棋盘的边界。每个节点的包含马走过的位置以及方向。将节点以及下一次要走的方向压入栈中，然后对每个节点可以走的方向进行判断，然后找出最佳的方向。·数据结构设计将节点走过的位置以及方向封装到一起，利用栈的特点实现马的遍历。·功能函数设计voidInit_Path(path*p)初始化栈int
2、Push_Path(path*p,pathnodet,intv)将节点以及下一次走的方向压入栈中intEmpty(pathp)判断栈是否为空intPop_Path(path*p,pathnode*t)出栈intCount(intx,inty)计算节点周围可以移动的所有方向intFind_Direction(intx,inty)寻找下一次移动的方向voidRound(intx,inty,intv)马的遍历函数voidMark_Dir(intv)标志方向函数voidMark_Che(intv)标志棋盘函数·
3、程序代码#include#includeintchessboard[14][13];//二维数组表示棋盘每个棋子位置,其中棋盘四周有两个格子，用于检测intCanPass[14][13][8];//每个棋子的八个方向哪些可以走typedefstruct{//棋盘的八个方向inty,x;}direction;directiondir[8]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};//八个方向/
4、/栈的设计typedefstruct{intx,y;//走过位置intdi;//方向}pathnode;typedefstruct{pathnodepa[90];inttop;}path;//顺序栈voidInit_Path(path*p){//初始化栈p->top=-1;}intPush_Path(path*p,pathnodet,intv){//压节点及其向下一位移动的方向入栈if(p->top>=63+26*v)return-1;else{p->top++;p->pa[p->top].x=t.x;
5、p->pa[p->top].y=t.y;p->pa[p->top].di=t.di;return1;}}intEmpty(pathp){//判断栈是否为空if(p.top<0)return1;return0;}intPop_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;return1;}}intCount(i
6、ntx,inty){//计算每个节点周围有几个方向可以走intcount=0,i=0;for(i=0;i<8;i++)if(chessboard[x+1+dir[i].x][y+1+dir[i].y]==0)count++;returncount;}intFind_Direction(intx,inty){//寻找下一个方向intdire,min=9,count,d=9;for(dire=0;dire<8;dire++){if(chessboard[x+1+dir[dire].x][y+1+dir[di
7、re].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)returnd;elsereturn-1;}voidRound(intx,inty,intv)//x,y表示出发位置{//马的遍历函数intnum=1,t,i;pathp;pathnodef;Init_Path(&p);for(num=1;num<=64+26*v;
8、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;}elseif(num==64+26*v&&chessboard[x+1][y+1]==0){//最后一次时t肯定是-1chessboard[x+1][y+1]
