《数据结构课程设计《马的遍历问题》(12页).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计《马的遍历问题》(12页).doc（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-数据结构课程设计马的遍历问题-第 12 页衡阳师范学院数据结构课程设计题 目： 马的遍历问题 系 别： 专 业： 班 级： 学生姓名： 学 号： 指导老师： 完成日期： 目录一、问题描述3二、设计思路. . .3 三、算法分析332.寻找下一个方向43.栈的相关函数. 4 4.马的遍历函数. 5 5.主函数. 7 6.棋盘初始化. 8 7.标记初始化. 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 count;2、寻找下一个方向函数int
4、 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;elsep-top+;p-pap-top.x=t.x;p-p
5、ap-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表示棋盘类型即中国象棋，这个函数主体是一个循环，循环里面始终是在找下一个点，如果找到就将该点进栈，找不到则退栈。直到发生栈为空时退栈或循环结束，前一种情况时会提示找不到路径(虽然不会发生，但是为逻辑严密性依然要如此)，后一种情况则打印出走过的正确路径和走过之后的数组。void Horse(int x,i
6、nt 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.
7、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 );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+)/根据棋盘
8、数组来打印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( 中国象棋马的遍历 n:);Mark_Che();Mark_Dir();while(1)printf(请输入入口点横坐标（在案1-10之间）：);scanf(%d,&x);if(y9)prin
9、tf(输入错误，请重新输入!(横坐标在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(是否继续马的遍历（是：y；否：其他）：); fflush(stdin);scanf(%c,&ch);6、棋盘初始化函数void Mark_Che(int v)此函数作为棋盘初始化函数，因为每次执行程序时，棋盘上必须是全部都没有走过的。它会自动进行初始化
10、棋盘，在14*13的棋盘上初始化。初始化后，棋盘大小的区域全部是0，而周围的两堵墙标志为1，时间复杂度为。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+)chessbo
11、ardij=1;for(i=10+2*v;i12+2*v;i+)for(j=0;j12+v;j+)/后面两行chessboardij=1;7、标记初始化函数void Mark_Dir() 此函数和上面的函数功能类似，也是初始化才用，它是为栈的实现提供帮助的。开始时全部标记为0，表示周围的八个方向都可以走，时间复杂度为。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;四 测试结果五 源程序#include#i
12、ncludeusing namespace std;int 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)/
13、初始化栈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
14、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 Horse(int x,int y,int v)/x,y表示出发位置/马的遍历函数int num=1,t,i;path p;pathnode f;Init_Path
15、(&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)/出栈且栈为空的
16、情况printf(!无法为您找到一条适合的路径!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
17、_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+)/前面两列for(i=0;i12+2*v;i+)ch
18、essboardij=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;int main()/主函数int x,y,v;char ch=y; while(ch=y)while(1) printf(请选择棋盘类型(0:国际象棋，1:中国象棋):); scanf(%d,&v); if(v!=1&v!=0) printf(输入错误，请重新输入!n); else break; Mark_Che(v); Mark
19、_Dir(v); while(1)printf(请输入入口点横坐标：);scanf(%d,&x);if(x8+2*v)printf(输入错误，请重新输入!(横坐标在1-%d之间)n,8+2*v);elsebreak;while(1)printf(请输入入口点纵坐标：);scanf(%d,&y);if(y8+v)printf(输入错误，请重新输入!(纵坐标在1-%d之间)n,8+v);elsebreak;Horse(x,y,v);printf(继续(是：y;否：其他):);fflush(stdin);scanf(%c,&ch);return 0;六 课程设计心得通过这次的课程设计，认真的看教材，网上查资料，分析总结觉得提高了不少自学方法和动手能力，加深和扩展了老师上课讲的内容，对顺序栈、深度优先搜索的关键步骤都更加熟练了，而且也学会了去思考它的实际作用，它可以应用的具体问题，它的缺点以及改进方法，它的思想精髓的应用等，还有就是在调试过程中遇到的困惑，解决后明白，遇到问题才有机会提高，一个问题的解决就又近了一步。