合肥学院。
计算机科学与技术系。
课程设计报告。
2011 ～2012 学年第二学期。
2012 年6 月10 日。
题目：名称：骑士游历。
内容：给你一个8*8的棋盘，骑士的开始位置，结束位置，让你求得骑士从开始位置开始走到结束位置需要最小的步数是多少？（注意，骑士走日字）
要求：1）输入：输入包含多组数据，每一行都是一组开始位置和结束位置，位置由两个字符组成，一个是小写字母(a-h),一个是数字(1-8),起始位置结束位置由一个空格隔开。
2）输出：输出从起始位置到结束位置，骑士所要走过的最小的步数。
3）所设计的数据结构应尽可能节省存储空间。
4）程序的运行时间应尽可能少。
一、 问题分析和任务定义。
此程序需要完成如下要求：给你一个8*8的棋盘，骑士的开始位置，结束位置，让你求得骑士从开始位置开始走到结束位置需要最小的步数是多少？（注意，骑士走日字）
实现本程序需要解决以下几个问题：
1、 如何表示8*8的棋盘，确定棋盘上各点的位置。
2、 马在棋盘上的各种行走方法怎样来表示，行走过程如何实现。
3、 如何表示位置由两个字符组成，一个是小写字母(a-h),一个是数字(1-8)。
4、 如何找到一条满足条件的路径。
5、 如何确定这条路径是最短的。
本问题的关键和难点是如何根据骑士的走法规则，找出一条最短路径。
图1:8*8的棋盘。
如图，建立如上的坐标系，于是每个点的位置就可以用一个有序数对来表示。如：（a,3）,（b,6）,（h,2）。
对于任意一点的马最多有8中走法可以选择。根据马行走后行列坐标数值大小的增加和减少情况的变化，用有序数组对来表示其走法。
static int bx[8] =
static int by[8] =
其中，bx数组与by数组下标相同的变量表示一种走法。
骑士在棋盘中的位置可由结构体类型。
typedef struct
int n,m; /n 记录行数，m 记录列数。
int ch;
node;
来表示。对于骑士的起始与终点位置可由有序对(x0,y0),(x1,y1)来表示。
另外建立一个队列，typedef struct定义顺序队列类型。
node data[maxlen];
int front;
int rear;
sequeue;
把骑士从起点到终点的每一步入队，前一步出对。
二、 概要设计与数据结构选择。
对于所提出的关键问题，即找出从起点到终点的最短步数，这里所用到的方法是遍历起点与终点的所有路径，记录下其步数，然后比较其中最小的步数，即为最短步数。
1、 输入起点和终点的坐标，起点先入对；
2、 按照上述的8走法分别走一步，如果到达终点，计步器加一，如果未到终点，计步器加一并入对；（所有走法均入队）
3、 出对，以步骤2中的如对顺序分别把其作为新起点，重复步骤2；
4、 判断是否对空，对空则以走过全部路径，对未空，重复步骤3；对空，转到步骤5；
5、 比较每种路径的步数，选出最小的数值，即为最小步数。
以上操作相当于对于一棵8个结点的完全树进行遍历，查找满足条件的结点，并找出这些结点中结点高度最低的结点。
以上过程可由树来表示。树如图2：
图2：骑士游历的树结构。
如图3，先找到起点，即根节点，并进行入队操作。由起点逐次访问起点的各个子树的根节点，比较是否等于终点的坐标，若相等，则保存路径长度；若不相等，则把不相等的子树的根节点进行入队操作。访问完所有子树的根节点后，进行一次出队操作；即把根节点出队。
此后顺次访问队头节点的子树的根节点，即顺次访问根节点的子树的根节点的各个子树的根节点，比较是否等于终点的坐标，若相等，则保存路径长度；若不相等，则把不相等的子树的根节点进行入队操作。直到队为空为止。
访问顺序如下：
图3：游历的访问顺序。
数据结构如下：
typedef struct //骑士位置结构体。
int n,m; /n 记录行数，m 记录列数。
int ch;
node;typedef struct顺序队列类型结构体。
node data[maxlen];
int front;
int rear;
sequeue;
图4：详细设计流程图。
三、 详细设计和编码。
首先，对于在问题分析和任务定义中所提出的问题逐个进行解决。
定义棋盘和走法，并对其进行初始化。
int way[8][8] 表示棋盘每一点的位置，例如，way[2][2]表示第三行，第三列的坐标，way[3][6]表示第四行，第七列的坐标。因为在本实验中并没有要求骑士行走的路径，所以棋盘可不显示的定义。
对于走法，我们前面已经提到了，对于马在棋盘中的任意位置，最多有8种走法，用有序数对表示即：(2,1),(2,-1)(1,2),(1.-2)(-2,1),(2,-1),(1,2),(1,-2)。
故，我们可以做如下定义：
根据马行走后行列坐标数值大小的增加和减少情况的变化，用有序数组对来表示其走法。
static int bx[8] =
static int by[8] =
其中，bx数组与by数组下标相同的变量表示一种走法。所以在骑士的行走过程中，只要让骑士的位置即坐标加上或减去上述8中走法的数组表示。
对于骑士的起点和终点的位置表示，根据要求位置由两个字符组成，一个是小写字母(a-h),一个是数字(1-8)。所以有如下的表示方法：
int x0,y0,x1,y1; char xa，xb；x0=xa-‘a’; x1=xb-‘a’;
其中，x0、y0表示起点坐标，x1、y1表示终点坐标，输入的xa，xb为字符，减去‘a’，便可转换成数字。这样便可以把输入的字符坐标转换成用数字表示的坐标。
在得到骑士的起点终点坐标之后，便可以把起点入队，入队函数如下所示：
void add(sequeue *s,int x,int y,int z) /入队函数。
if(s->rearrear>=0)
else printf("error");
这里的参数x，y，z分别表示行坐标，列坐标，和到达该坐标从起点所走的步数。它们的值分别保存在队列的n，m，ch中。
在对起点进行入队之后，便可进行运动了，即骑士可以按规则(8种走法)走向下一位置。
此后，在一个while循环中进行如下的操作，while循环的条件为：s->frontrear，保证在队列不为空的情况下进行循环。
对于骑士的8种走法，可以通过for(i=0;i<8;i++)循环进行逐个试探。这里可以定义两个证型变量x3、y3；用以存放骑士走一步后的位置，即坐标。则有如下定义：
x3=bx[i]+x0; y3=by[i]+y0;
又由实际情况可知，x3、y3应该满足x3、y3同时大于等于0且小于8；在此时设置标记数组step[maxlen][maxlen]=0;标记数组用以标记该位置是否已经走过，走过则置1；所以x3、y3还应满足step[x3][y3]==0;即(x3,y3)这个位置还未走过。若满足以上条件，则可以定义node *p；并为其申请内存空间。有如下一段程序：
p=(node *)malloc(sizeof(node));
p->ch=s->data[s->front+1].ch+1;
p->n=x3;
p->m=y3;
step[x3][y3]=1;
把(x3,y3)的值放入指针p指向的空间的（n，m）中，用以保存此位置；因为ch存放的是从起点到该位置所走的步数，故p->ch=s->data[s->front+1].ch+1;即它表示的意思是从起点x3、y3所走的步数。此时并把x3y3的标记置为1，说明此位置已经被访问过了。
这时便可以对x3、y3进行判断了。
若p->n==x1 &&p->m==y1，即比较x3、y3与终点的坐标是否相同。若相同则找到一种走法。此时定义 int a=0；int count[maxlen]; count[a]数组的作用就是记录下每一种走法的步数；令 count[a]=p->ch即可。
若不满足条件的话则把x3、y3入队；
算法与数据结构课程设计报告
福建工程学院软件学院。题目。专业。姓名。学号。同组其他学生 学号。2015年月日。目录。一 需求分析 3 二 总体设计 3 三 详细设计 3 四 调试与测试 3 五 测试结果 3 六 用户手册 3 七 附录 3 描述问题。简述课题要解决的问题是什么，有什么要求和限制条件。二 总体设计。必须包含程序设...
《数据结构与算法课程设计》报告
你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。命运如同手中的掌纹，无论多曲折，终掌握在自己手中。数据结构与算法课程设计 harbin institute of technology 数据结构与算法。课程设计报告。2014年度秋季学期 设计题目。小组成员 11337...
算法与数据结构课程设计报告
算法与数据结构。课程设计指导书。题目 校园导游咨询系统。2012年5月23日。一 课程性质与教学目的。算法与数据结构课程设计 是计算机科学中一门综合性的专业基础课。主要介绍如何合理地组织数据 有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。本课程设计旨在加深对数据结构的逻辑结构和物理结构...