数据结构与算法_马踏棋盘#参考资料

1、严选内容#- 0 - 合肥学院 计算机科学与技术系 课程设计报告 20122013 学年第 2 学期 课程课程 数据结构与算法 课程设计名称课程设计名称马踏棋盘 学生姓名学生姓名 学号学号 专业班级专业班级 指导教师指导教师 2013 年 6 月 严选内容#- 1 - 目目 录录 数据结构课程设计报告马踏棋盘.- 2 - 问题描述.- 2 - 1、问题分析与定义.- 2 - 2、数据结构的选择和概要设计.- 3 - 数据结构的选择 .- 3 - 概要设计 .- 3 - 3、详细设计和编码.- 4 - 4、上机调试过程.- 6 - 5、测试结果及分析.- 7 - 6、用户使用说明.- 9 - 7

2、、参考文献.- 9 - 附录源程序.- 10 - 严选内容#- 2 - 数据结构课程设计报告数据结构课程设计报告 马踏棋盘马踏棋盘 题目：题目：【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。 要求：将马随机放在国际象棋的 88 棋盘 Board88的某个方格中，马按走棋规则 进行移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。编制非递归程序，求出 马的行走路线，并按求出的行走路线，将数字 1，2，64 依次填入一个 88 的方阵， 输出之。 1 1、问题分析与定义、问题分析与定义 走棋规则：马走 32 格对角线，简单的说就是走 L 形 棋盘如图所示，将马放在棋盘中的任意一个位

3、置，按照马的走棋规则，我们能够发现， 如果没有其他棋子的影响，它最多有 8 个出口，最少有 2 个出口。 马所在位置及其出口 算法核心思想：本程序的核心算法是“贪心算法” 。在每个结点对其子结点进行选取时， 优先选择出口最小的进行搜索， 出口的意思是在这些子结点中它们的可行子结点的 个数，也就是孙子结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优 的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现 01234567 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 严选内容#- 3 - 死结点（顾名思义就是没有出口又没有跳过的结点） ，这样

4、对下面的搜索纯粹是徒劳， 这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结 点就会越来越少，这样跳成功的机会就更大一些。 2 2、数据结构的选择和概要设计、数据结构的选择和概要设计 数据结构的选择 栈：本程序可以利用栈的知识来解决，当然，栈也包括链栈和顺序栈，由于本程序数 据有限，并且顺序栈较链栈简单，所以该程序最终选择使用顺序栈来解决。贪心算法：在 算法中采用逐步构造最优解。在每个阶段，都作出一个看上去最优的决策（在一定的标准 下） 。决策一旦作出就不可再更改。 概要设计 、主程序模块： void main() 定义变量； 接受命令； 处理命令； 退出； 、起始

5、坐标函数模块马儿在棋盘上的起始位置； 、探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘； 、输出路径函数模块输出马儿行走的路径； 流程图如下： 输入的初始位置是否正确 否 是 主程序模块 起始坐标函数模 块 探寻路径函数模 块 严选内容#- 4 - 3 3、详细设计和编码、详细设计和编码 下图显示了马位于方格（2，3）时，8 个可能的移动位置。 一般来说，当马位于位置（i,j）时，可以走到下列 8 个位置之一 01234567 081 172 2H 373 454 5 6 7 (i-2,j+1)、 （i-1,j+2） 、(i+1,j+2)、(i+2,j+1) (i+2,j-1)、(i+

6、1,j-2)、(i-1,j-2)、(i-2,j-1) 但是，如果(i,j)靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的 位置。8 个可能位置可以用两个一维数组 Htry10.7和 Htry20.7来表示： 0 1 2 3 4 5 6 7 Htry1 -2 -1 1 2 2 1 -1 -2 0 1 2 3 4 5 6 7 Htry2 1 2 2 1 -1 -2 -2 -1 输出路径函数模 块块 结束 严选内容#- 5 - 位于(i,j)的马可以走到的新位置是在棋盘范围内的(i+Htryh,j+Htry2h),其中 h=0,1,2,7。 每次在多个可走位置中选择其中一个进行试探，其余

7、未曾试探过的可走位置必须用 适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。 流程图如下： 严选内容#- 6 - 开始 Int i、j i=0 iN Boardij=0 i + 输入棋子起始位置 判断棋子是否出棋盘 Multiplex For 循环 从这个位置开始 结束 4 4、上机调试过程、上机调试过程 严选内容#- 7 - （1） 、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中 遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主 要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢 调试，编译都能通过，没

8、有错误和警告。 （2） 、虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结 束程序，可能是在某些地方出现了无限死循环了，然后在仔细检查代码，发现没有标记马 儿尝试的方向 director，这样的话，马儿回溯的时候，下一次又有可能走那个方向，这样 就出现了死循环。 （3） 、标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结 果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须 控制 0 到 7 之间，否则的话马儿就会踏出棋盘以外，这样输出的结果就不对。还有就是棋 盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记

9、给清掉，这 个地方有时候也很容易混淆。 5 5、测试结果及分析、测试结果及分析 输入数据 1：根据要求重新输入马的初始位置（9,9） ，由于输入数据不再要求范围之 内,程序要求用户重新输入; 图（1） 输入数据 2：根据要求重新输入马的初始位置（1,1） ，结果如下 严选内容#- 8 - 图（2） = = 图（3） 测试结果 严选内容#- 9 - 如图（1）所示、当输入马的坐标为（9,9）时，由于该坐标不在 88 的棋盘内，所以 程序提示要求重新输入；如图（2）所示，重新输入数据位（1,1）满足棋盘要求，得到在 该位置的马踏棋盘的结果。如图（3）所示，当位置选定为（4,4）时的结果。 结果分析

10、：如图（3）所示，以数字递增顺序表示马的下一个出口位置。如图中，1 表 示初始位置，按照国际象棋中马的走棋规则并选择最优位置，即为 2 位置；3 表示 2 位置 的马的下一个出口位置。以此循环下去，直到数字遍及整个棋盘。 注：马 的走棋路线即为图中白线标记部分（仅标记了前 4 个位置） 测试数据 1:输入马的初始位置(9，9)，由于不符合要求，程序要求重新输入 6 6、用户使用说明、用户使用说明 用户需将源程序清单输入可运行 C+的编辑平台，例如 vc+, c+ Builder 等等，然 后进行编译，然后用户根据提示输入马的初始位置，程序会提示所输入马的初始位置必须 在 1-8 之间，否则需要

11、重新输入，直至输入的位置符合要求为止；输入正确之后，程序会 输入马儿踏遍整个棋盘的具体执行步骤。 注：阿拉伯数字 1、2、3、462、63、64。下一个数字所在位置即为上一个位置马 儿的出口。 7 7、参考文献、参考文献 1王昆仑，李红.数据结构与算法.北京：铁道工业出版社，2007 年 6 月第一版 2.徐孝凯，魏荣数据结构,北京：机械工业出版社，1996 年 3.徐孝凯数据结构简明教程 ，北京:清华大学出版社，1995 年 4.陈文博，朱青数据结构与算法 ，北京：机械工业出版社，1996 年 5.许卓群，张乃孝，杨冬青，唐世渭数据结构 ，高等教育出版社，1988 年 6.李廉治，姜文清，郭

12、福顺数据结构 ，大连理工大学出版社，1989 年 附录附录 严选内容#- 10 - 源程序源程序 /（1） 、定义头文件和预定义 #include #define MAXSIZE 100 #define N 8 /（2） 、数据类型定义 int board88; /定义棋盘 int Htry18=1,-1,-2,2,2,1,-1,-2; /*存储马各个出口位置相对当前位置行下标的增量数组*/ int Htry28=2,-2,1,1,-1,-2,2,-1; /*存储马各个出口位置相对当前位置列下标的增量数组*/ struct Stack /定义栈类型 int i; /行坐标 int j; /列坐

13、标 int director; /存储方向 stackMAXSIZE; /定义一个栈数组 int top=-1; /栈指针 /（3） 、函数声明 void InitLocation(int xi,int yi); /马儿在棋盘上的起始位置坐标 int TryPath(int i,int j); /马儿每个方向进行尝试，直到试完整个棋盘 void Display(); /输出马儿行走的路径 /（4） 、起始坐标函数模块 void InitLocation(int xi,int yi) int x,y; /定义棋盘的横纵坐标变量 top+; /栈指针指向第一个栈首 stacktop.i=xi; /

14、将起始位置的横坐标进栈 stacktop.j=yi; /将起始位置的纵坐标进栈 stacktop.director=-1; /将起始位置的尝试方向赋初值 严选内容#- 11 - boardxiyi=top+1; /标记棋盘 x=stacktop.i; /将起始位置的横坐标赋给棋盘的横坐标 y=stacktop.j; /将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y) /调用马儿探寻函数，如果马儿探寻整个棋盘返回 1 否则返 回 0 Display(); /输出马儿的行走路径 else printf(无解); /（5） 、探寻路径函数模块 int TryPath(int i,i

15、nt j) int find,director,number,min; /定义几个临时变量 int i1,j1,h,k,s; /定义几个临时变量 int a8,b18,b28,d8; /定义几个临时数组 while(top-1) /栈不空时循环 for(h=0;h=0k=0 /记录条数 ah=number; /将条数存入数组 a8中 for(h=0;h8;h+) /根据可行路径条数小到大按下表排序放入数组 d8中 min=9; for(k=0;kak) min=ak; dh=k; /将下表存入数组 d8中 s=k; as=9; director=stacktop.director; if(to

16、p=63) /如果走完整个棋盘返回 1 return (1); find=0; /表示没有找到下一个位置 for(h=director+1;h=0 /表示找到下一个位置 严选内容#- 13 - break; if(find=1) /如果找到下一个位置进栈 stacktop.director=director; /存储栈结点的方向 top+; /栈指针前移进栈 stacktop.i=i; stacktop.j=j; stacktop.director=-1; /重新初始化下一栈结点的尝试方向 boardij=top+1; /标记棋盘 else /否则退栈 boardstacktop.istacktop.j=0; /清除棋盘的标记 top-; /栈指针前移退栈 return (0); /（6）输出路径函数模块 void Display() int i,j; for(i=0;iN;i+) for(j=0;jN;j+) printf(t%d ,boardij); /输出马儿在棋盘上走过的路径 pri