马的遍历课程设计报告

《马的遍历课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计实验报告——马的遍历学院：长江学院班级：093212学号：09321225姓名：杨海龙指导老师：刘自强指导时间：2010.12.2810目录1.流程图：12.问题描述：23.设计思路：24.数据结构设计：25.功能函数算法分析：3（1）计算一个点周围有几个点函数intCount(intx,inty)3（2）寻找下一个方向函数intFind_Direction(intx,inty)3（3）栈的相关函数：4（4）骑士遍历函数：voidKnight(intx,inty,intv)5（5）主函数：voi

2、dmain()6（6）棋盘初始化函数voidMark_Che(intv)7（7）标记初始化函数voidMark_Dir(intv)86.运行和测试：87.心得体会：1010马的遍历问题开始输入入口点横坐标横坐标在1—10之间输入入口点纵坐标纵坐标在1—9之间显示骑士遍历路径结束1.流程图：假真假真102.问题描述：在中国象棋棋盘上，对任意位置上放置的一个马，均能选择一个合适的路线，使得该棋子（马）能按象棋的规则不重复的走过棋盘上的每一个位置。要求依次输出所有走过的各位置的坐标。3.设计思路：首先，中国象棋是10*9

3、的棋盘，马的走法是“马走日”，忽略“蹩脚马”的情况。其次，这个题目采用的是算法当中的深度优先算法和回溯法：在“走到”一个位置后要寻找下一个位置，如果发生“阻塞”的情况，就是后面走不通的情况，则向后回溯，重新寻找。在寻找下一步的时候，对周围的这几个点进行比较，从而分出优劣程度，即看它们周围可以走的点谁最少，然后就走那条可走路线最少的那条。经过这样的筛选后，就会为后面的路径寻找提供方便，从而减少回溯次数。最后，本程序的棋盘和数组类似，因而采用数组进行存储，同时因为有回溯，所以采用栈的方法，并且为了最后打印方便，采用的是

4、顺序栈的方法。同时还有八个方向的数组，和为栈设计的每个点周围的八个方向那些可以走的数组。4.数据结构设计：同上面述，棋盘采用数组形式，并且这里的数组比棋盘的数组规模稍大，因为为了判断的方便，这里在棋盘周围各加了两层“墙”。具体数据结构定义如下：intchessboard[14][13];//采用最大的中国象棋10*9制的intCanPass[14][13][8];//每个棋子的八个方向哪些可以走typedefstruct{//棋盘的八个方向inty;intx;}direction;direction10dir[8]

5、={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};//八个方向typedefstruct{//栈的节点结构intx,y;//走过位置intdi;//走向下一个方向}pathnode;typedefstruct{pathnodepa[90];//栈的容量最大为90inttop;//栈顶}path;//顺序栈5.功能函数算法分析：（1）计算一个点周围有几个点函数intCount(intx,inty)该函数实现的功能是在遍历的过程当中计算一个点周围有几个

6、方向可以走，从而为后面的筛选提供依据。时间复杂度为intCount(intx,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;}（2）寻找下一个方向函数intFind_Direction(intx,inty)该函数的功能是在走过一个点之后，寻找下一个适合的点，如果找到返回正常的方向值，否则返回-1。时间复杂度为intFind_

7、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[dire].y]==0&&CanPass[x+1][y+1][dire]==0){count=Count(x+dir[dire].x,y+dir[dire].y);10if(min>count){min=count;d=dire;}}}if(d<9)returnd;elseretu

8、rn-1;}（3）栈的相关函数：初始化栈：voidInit_Path(path*p)；p是用到得栈；判断栈是否是空：intEmpty(pathp)；p是栈，是空的话返回1，否则返回0，时间复杂度为；压栈函数：intPush_Path(path*p,pathnodet,intv)p是栈，t是压进去的节点，v是棋盘，时间复杂度为；出栈函数：intPop_Path