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

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

1、衡阳师范学院《数据结构》课程设计题目：马的遍历问题系别：专业：班级：学生姓名：学号：指导老师：完成日期：2015.1.6第15页共15页目录一、问题描述3二、设计思路..................................................................................................................................3三、算法分析31.计算一个点周围有几个点32.寻找下一个方向43.栈的相关函数.......................

2、.................................................................................................44.马的遍历函数........................................................................................................................55.主函数............................................

3、........................................................................................76.棋盘初始化............................................................................................................................87.标记初始化................................................

4、............................................................................8四、测试结果9五、源程序10六、课程设计心得15第15页共15页一．问题描述根据中国象棋棋盘，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按象棋的规则不重复地走过棋盘上的每一位置。要求：（1）依次输出所走过的各位置的坐标。（2）最好能画出棋盘的图形形式，并在其上动态地标注行走过程。（3）程序能方便地地移植到其它规格的棋盘上。二．设计思路首先，中国象棋是10*9的棋盘，马的走法是

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

6、每个点周围的八个方向那些可以走的数组。三．算法分析1、计算一个点周围有几个点函数intCount(intx,inty)该函数实现的功能是在遍历的过程当中计算一个点周围有几个方向可以走，从而为后面的筛选提供依据。intCount(intx,inty){//计算每个节点周围有几个方向可以走intcount=0,i=0;for(i=0;i<8;i++)第15页共15页if(chessboard[x+1+dir[i].x][y+1+dir[i].y]==0)count++;returncount;}2、寻找下一个方向函数intFind_Direction

7、(intx,inty)该函数的功能是在走过一个点之后，寻找下一个适合的点，如果找到返回正常的方向值，否则返回-1。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[dire].y]==0&&CanPass[x+1][y+1][dire]==0){count=Count(x+dir[dire].x,y+dir[dire].y);if(min>cou

8、nt){min=count;d=dire;}}}if(d<9)returnd;elsereturn-1;}3、栈的相关函数初始化栈：vo