1、 计算机科学与技术系 课程设计报告 2011 2012 学年第 二 学期 课程课程 数据结构与算法 课 程 设 计 名 称课 程 设 计 名 称 骑士游历 学生姓名学生姓名 学号学号 专业专业班级班级 指导教师指导教师 2012 年 6 月 10 日 题目：题目： 名称：骑士游历 内容： 给你一个 8*8 的棋盘,骑士的开始位置,结束位置,让你求得骑士从开始位置开始走到结束 位置需要最小的步数是多少？（注意,骑士走日字） 要求： （1）输入：输入包含多组数据，每一行都是一组开始位置和结束位置,位置由两个字符组成, 一个是小写字母(a-h),一个是数字(1-8),起始位置结束位置由一个空格隔开.
2、 （2）输出：输出从起始位置到结束位置,骑士所要走过的最小的步数. （3）所设计的数据结构应尽可能节省存储空间。 （4）程序的运行时间应尽可能少。 一、 问问题分析和任务定义题分析和任务定义 此程序需要完成如下要求： 给你一个 8*8 的棋盘,骑士的开始位置,结束位置,让你求得骑士 从开始位置开始走到结束位置需要最小的步数是多少？（注意,骑士走日字） 实现本程序需要解决以下几个问题： 1、 如何表示 8*8 的棋盘，确定棋盘上各点的位置。 2、 马在棋盘上的各种行走方法怎样来表示，行走过程如何实现。 3、 如何表示位置由两个字符组成,一个是小写字母(a-h),一个是数字(1-8)。 4、 如何
3、找到一条满足条件的路径。 5、 如何确定这条路径是最短的。 本问题的关键和难点是如何根据骑士的走法规则，找出一条最短路径。 h g f e d c b a|0 1 2 3 4 5 6 7 图 1:8*8 的棋盘 如图，建立如上的坐标系，于是每个点的位置就可以用一个有序数对来表示。如： （a,3）, （b,6）,（h,2） 。 对于任意一点的马最多有 8 中走法可以选择。根据马行走后行列坐标数值大小的增加和 减少情况的变化，用有序数组对来表示其走法。 static int bx8 = 2,1,-1,-2,-2,-1,1,2; static int by8 = 1,2,2,1,-1,-2,-2,-
4、1; 其中，bx 数组与 by 数组下标相同的变量表示一种走法。 骑士在棋盘中的位置可由结构体类型 typedef struct int n,m; /n 记录行数，m 记录列数 int ch; node; 来表示。 对于骑士的起始与终点位置可由有序对(x0,y0),(x1,y1)来表示。 另外建立一个队列， typedef struct /定义顺序队列类型 node datamaxlen; int front; int rear; Sequeue; 把骑士从起点到终点的每一步入队，前一步出对。 二、 概要设计与数据结构选择概要设计与数据结构选择 对于所提出的关键问题，即找出从起点到终点的最短步数，这里所用到的方法是遍历起 点与终点的所有路径，记录下其步数，然后比较其中最小的步数，即为最短步数。 1、 输入起点和终点的坐标，起点先入对； 2、 按照上述的 8 走法分别走一步，如果到达终点，计步器加一，如果未到终点，计 步器加一并入对； （所有走法均入队） 3
