数据结构课程设计《马的遍历问题》

1、衡阳师范学院数据结构课程设计题 目 马的遍历问题系 另y：专 业：班 级：学生姓名：学 号：指导老师：完成日期： 目录、问题描述 . 错误 ! 未定义书签。计思二、设 路 3三、算法分析 . 31. 计算一个点周围有几个点. 32. 寻找下一个方向 . 43. 栈 的 相 关 函 数 44.马的遍历函数 55.主函数 76.棋盘初始化 87.标记初始化 8四、测试结果 . 9五、源程序 10六、课程设计心得. 15一问题描述根据中国象棋棋盘，对任一位置上放置的一个马， 均能选择一个合适的路线， 使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。要求：（1）依次输出所走过的各位置的坐标。（2

2、）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。（3）程序能方便地地移植到其它规格的棋盘上。设计思路首先，中国象棋是 10*9 的棋盘，马的走法是“马走日” ，忽略“蹩脚马”的情况。 其次，这个题目采用的是算法当中的深度优先算法和回溯法： 在“走到” 一个位置后要 寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻 找。在寻找下一步的时候，对周围的这几个点进行比较， 从而分出优劣程度，即看它们周围 可以走的点谁最少， 然后就走那条可走路线最少的那条。 经过这样的筛选后， 就会为后面的 路径寻找提供方便，从而减少回溯次数。最后， 本程序的棋盘和数组类似，因而

3、采用数组进行存储，同时因为有回溯，所以采用 栈的方法， 并且为了最后打印方便， 采用的是顺序栈的方法。 同时还有八个方向的数组，和 为栈设计的每个点周围的八个方向那些可以走的数组。三算法分析1、计算一个点周围有几个点函数 int Count(int x,int y)该函数实现的功能是在遍历的过程当中计算一个点周围有几个方向可以走， 从而为后面的筛选提供依据。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

4、count;2、寻找下一个方向函数 int Find_Direction(int x,int y)该函数的功能是在走过一个点之后， 寻找下一个适合的点， 如果找到返回正 常的方向值，否则返回 -1 。int Find_Direction(int x,int y)/ 寻找下一个方向int dire,min=9,count,d=9;for(dire=0;direcount)min=count;d=dire;if(dtop=-1;int Push_Path(path *p,pathnode t,int v)/ 压节点及其向下一位移动的方向入栈if(p-top=63+26*v)return -1;el

5、sep-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.top0) return 1;return 0;4、马的遍历函数： void Horse(int x,int y)这是该算法的精华部分， x,y 表示入口地点， v 表示棋盘类型即中国象棋， 这个函数主体是一个循环， 循环里面始终是在找下一个点， 如果找到就将该点进 栈，找不到则退栈。 直到发生栈为空时退栈或循环结束， 前一种情况时会提示找 不到路径 (虽然不会发生， 但是为逻辑严密性依然要如此 )

6、 ，后一种情况则打印出 走过的正确路径和走过之后的数组。void Horse(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*

7、v&chessboardx+1y+1=0)/ 最后一次时 t 肯定是 -1 chessboardx+1y+1=num; f.x=x;f.y=y;f.di=t; Push_Path(&p,f,v); else if(Pop_Path(&p,&f)=-1) / 出栈且栈为空的情况 printf(! 无 法 为 您 找 到 一 条 适 合 的 路 exit(0);num-=2;x=f.x;y=f.y;CanPassx+1y+1f.di=1;/end else/ 根据栈中信息打印出马行走路径 printf( 马的遍历路径如下 :n ); for(i=0;i,p.pai.x,p.pai.y);if(i+

8、1)%(8+v)=0)printf(bb n-);printf(bb n); printf( 根据数组打印结果是 :n);for(i=0;i8+2*v;i+)/ 根据棋盘数组来打印for(t=0;t8+v;t+) printf(%4d,chessboardi+2t+2);printf(n);5、主函数： int main()提示输入起点位置， 这里的起点位置就是日常生活观念中的顺序， 开始点是 (1,1), 而不是数组中的初始位置 (0,0), 输入错误则提示重新输入，时间复杂度 为。int main() / 主函数int x,y;char ch=y ;while(ch=y)printf( 中

9、国象棋马的遍历 n:);Mark_Che();Mark_Dir();while(1)printf( 请输入入口点横坐标(在案 1-10 之间)： ); scanf(%d,&x);if(y9)printf( 输入错误，请重新输入 !( 横坐标在 1-10 之间 )n); elsebreak;while(1)printf( 请输入入口点纵坐标 (在 1-9 之间) ：); scanf(%d,&y);if(y9)printf( 输入错误，请重新输入 !( 纵坐标在 1-9 之间 )n); elsebreak;Knight(x,y);Getchar();Printf(n);printf(是否继续马的遍

10、历(是：y;否：其他)：)；fflush(stdin);scanf(%c,&ch)；6、棋盘初始化函数 void Mark_Che(int v)此函数作为棋盘初始化函数， 因为每次执行程序时， 棋盘上必须是全部都没 有走过的。它会自动进行初始化棋盘，在 14*13 的棋盘上初始化。初始化后，棋 盘大小的区域全部是 0，而周围的两堵墙标志为 1，时间复杂度为。void Mark_Che(int v)int i,j； for(i=0；i12+2*v；i+)/ 首先全部标记为 0 for(j=0；j12+v；j+)chessboardij=0； for(i=0；i2；i+)/ 前面两行标记为 1 f

11、or(j=0；j12+v；j+)chessboardij=1； for(j=0；j2；j+)/ 前面两列 for(i=0；i12+2*v；i+)chessboardij=1；for(j=10+v;j12+v;j+)后面两列for(i=0;i12+2*v;i+) chessboardij=1;for(i=10+2*v;i12+2*v;i+) for(j=0;j12+v;j+)后面两行chessboardij=1;7、标记初始化函数 void Mark_Dir()此函数和上面的函数功能类似，也是初始化才用，它是为栈的实现提供帮助的。开始时全部标记为0,表示周围的八个方向都可以走，时间复杂度为。vo

12、id Mark_Dir(i nt v)/由于三维数组赋初值比较困难，因而采用单独的函数实现int i,j,k;for(i=0;i12+2*v;i+) for(j=0;j12+v;j+) for(k=0;k-(6.?.5-X 3”T-X i.5- aw X ?R1 X (l.3 f 3F?r X 5,0 c .?CAX !,!-=1 磺坐际1 1.r =7 谟F j： l-C 1,2 X力X 9PGC2- -t7.1 ( 6-? - C7.5-CU.5-5)1)132111i二i JgT-d厂q二吧5肚0p马比辰云lk亡481?_结纯（是2 V ； n7: E仇：# 灶刑援盘蝇国际象損.丄冲国象

13、棋沙0藤入入口 电轉椒fen A入口点圳座臻,?-QX-C -X 6.2-X -X 7/7-C -XX 1.5-(5-C ?-CU4-C7.8-C5,4-X3.8-C6.3C3,4-C2,4J-C2,63-(3.5)-C5,73- 1.8J-M 3.7J-K 5.8) 7.4-6.5-M 5.3-K 3P2?6.7-K 7G13 血仙1116Jibl2f874?2 4 5 1 2 fi 2曲7443924J!fi3五源程序#in clude #in clude using n amespace std;in t chessboard1413; int Ca nPass14138;棋盘每个棋子的

14、八个方向哪些可以走typedef struct/棋盘的八个方向 int y,x;directi on;directi ondir8=2,1,1,2,-1,2,-2,1,-2,-1,-1,-2,1,-2,2,-1;/个方向/栈的设计typedef structint x,y;/走过位置int di;/ 方向path no de;typedef struct pathnode pa90; int top;path;/ 顺序栈void Init_Path(path *p)/ 初始化栈p-top=-1;int Push_Path(path *p,pathnode t,int v)/ 压节点及其向下一位

15、移动的方向入栈 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

16、+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 Horse(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_Direct

17、ion(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 肯定是 -1 chessboardx+1y+1=num; f.x=x;f.y=y;f.di=t; Push_Path(&p,f,v);else if(Pop_Path(&p,&f)=-1) / 出栈且栈为空的情况 printf(! 无 法 为 您 找 到 一 条 适

18、合 的 路 径!n);exit(0); num-=2; x=f.x;y=f.y; CanPassx+1y+1f.di=1;/end else/ 根据栈中信息打印出马行走路径printf( 马的遍历路径如下 :n ); for(i=0;i,p.pai.x,p.pai.y); if(i+1)%(8+v)=0) printf(bb n-);printf(bb n);printf( 根据数组打印结果是 :n);for(i=0;i8+2*v;i+)/ 根据棋盘数组来打印 for(t=0;t8+v;t+) printf(%4d,chessboardi+2t+2);printf(n);void Mark_D

19、ir(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+)/ 前面两列for(i=0;i12+2*v;i+) chessboardij=1; for(j=10+v;j12+v;j+)/ 后面两列 for(i=0;i12+2*v;i+) chessboardij=1; for(i=10+2*v;i12+2*v;i+) for(j=0;j12+v;j+)/ 后面两行 chessboardij=1;