马踏棋盘分析文档

《马踏棋盘分析文档》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构课程设计题目：马踏棋盘院系：班级：学号：姓名：2014-2015年度第1学期马踏棋盘一.题目：马踏棋盘3二.设计目标3三•问题描述3四.需求分析4五.概要设计4第•步：定义四个常量和•个数据类型4第二步：构造函数4六.详细设计（给出算法的伪码描述和流程图）5流程图设计5代码分析9第一步：定义常量与变量9第二步：构造函数9•定义一个结构体类型9•仓U建一个初始化函数10•创建提示输入函数10•创建产生新节点函数11•创建计算路径函数12•创建入栈函数13•创建出栈函数13•创建输出函数13第二步：在主函数屮调用其它函数15七测试分析16八.使用说明16九•测试数据16十.课程设计总结

2、17一.题目：马踏棋盘二.设计目标帮助学生熟练掌握顺序栈的基本操作，让学生深入了解栈的使用，使得更深层次的灵活运用栈。三.问题描述（©谓的马踏棋盘是：将马随机放在国际象棋的8X8棋盘的某个方格中，马按走棋规则（马走日字）进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。由用户自行指定一个马的初始位置，求出马的行走路线，并按照求出的行走路线的顺序，将数字1、2、…、64依次填入一个8X8的方阵并输出。从用户给出的初始位置开始判断，按照顺时针顺序，每次产生一个新的路点，并验证此路点的可用性，需要考虑的是当前路点是否超出棋盘范围和此路点是否已经走过。如果新路点可用，则入栈，并执行下一步

3、，重复进行如上步骤，每次按照已走路点的位置生成新路点。如果一个路点的可扩展路数为0,进行回溯，直到找到一个马能踏遍棋盘的行走路线并输出。1-需求分析1.让用户输入马的初始位置；2.按照马的行走路线，判断马是否能够走遍整个棋盘；3.输出结果（若能走遍，则输出马的行走路线，若不能，提示用户“此时不能踏遍棋盘上所有点！”）五.概要设计为了实现上述程序功能，程序包含以下几大模块:第一步：定义四个常量和一个数据类型:MAXNUM、INVALIDDIR、MAXLEN、MAXDIR、HorsePoint第二步：构造函数：voidInitial0//初始化函数；voidPushStack(HorsePoi

4、ntpositon)//入才戋函数；HorsePointGetlnitPointO//请求用户输入函数；HorsePointGetNewPoint但orscPoint^parent)//产生新节点函数；voidCalcPoint(HorsePointhh)//计算路径的函数;voidPrintChessO//输出函数；intmain(intarge,char*argv[])//主函数五.详细设计（给出算法的伪码描述和流程图）总体操作步骤如下：流程图设计：o&jsta【e三=K1O蘇庄sOTre三三输出“此时不能踏遍棋盘上所有.nf风代码分析:第一步：定义常量与变量:常量：/*横纵格数的最大

5、值*/MAXNUM8——INVAIJDDIR-1/*无路可走的情况*/MAXLKN64/*棋盘总个数*/MAXDIR8/*下一步可走的方向*/变量：HorscPointChcssPath[MAXLKN]/*模拟路径栈*/Intcount/*入栈节点个数*/intChcssBoard[MAXNUM][MAXNUM]/*标志棋盘数组*/第二步：构造函数：•为了明确马将要走的路线，我们必须定义一个结构体类型：typedefstruct{intx;/*表示横坐标*/inty;/*表示纵坐标*/intdirection;/*表示移动方向*/}HorsePoint;•创建一个初始化函数:voidIni

6、tialQintij;for(i=O;i

7、f(Hn);}while(positon.x>=MAXNUM

8、

9、positon.y>=MAXNUM

10、

11、positon.x<0

12、

13、positon.y<0);/*不超过各个边缘时*//*是初值，没走过positon.direction=INVALIDDIR;*/returnpositon;}•创建产生新节点函数：HorsePointGetNewPoint(HorsePoint^parent)inti;HorsePoi