数据结构—马的遍历.pdf

马的遍历  问题描述 设计要求是马从棋盘上的一个位置出发，然后按照中国象棋的规则—马走日，来走 下一步，直到马走完棋盘上的每一个位置终止。  设计思路 首先将棋盘每个位置的标记为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)标志棋盘函数  程序代码 #includestdio.h #includestdlib.h 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) {//判断栈是否为空 if(p.top0) 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;i8;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