数据结构及算法_马踏棋盘.doc

《数据结构及算法_马踏棋盘.doc》由会员分享，可在线阅读，更多相关《数据结构及算法_马踏棋盘.doc（11页珍藏版）》请在课桌文档上搜索。

1、. . . . . .word.资料. .计算机科学与技术系课程设计报告课程课程 数据构造与算法课程设计名称课程设计名称马踏棋盘学生学生*专业班级专业班级指导教师指导教师目目 录录数据构造课程设计报告马踏棋盘- 2 -问题描述- 2 -1、问题分析与定义- 2 -2、数据构造的选择和概要设计- 3 -数据构造的选择- 3 -概要设计- 3 -3、详细设计和编码- 4 -4、上机调试过程- 6 -5、测试结果及分析- 7 -6、用户使用说明- 9 -7、参考文献- 9 -附录源程序- 10 -. z.数据构造课程设计报告数据构造课程设计报告马踏棋盘马踏棋盘题目：题目：【问题描述】设计一个国际象棋

2、的马踏遍棋盘的演示程序。要求：将马随机放在国际象棋的 88 棋盘 Board88的*个方格中，马按走棋规则进展移动。要求每个方格只进入一次，走遍棋盘上全部 64 个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字 1，2，64 依次填入一个 88 的方阵，输出之。1 1、问题分析与定义、问题分析与定义走棋规则：马走 32 格对角线，简单的说就是走 L 形棋盘如下图，将马放在棋盘中的任意一个位置，按照马的走棋规则，我们能够发现，如果没有其他棋子的影响，它最多有 8 个出口，最少有 2 个出口。马所在位置及其出口算法核心思想：本程序的核心算法是“贪心算法。在每个结点对其子结点进展

3、选取时，优先选择出口最小的进展搜索， 出口的意思是在这些子结点中它们的可行子结点的个数，也就是子结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现死结点顾名思义就是没有出口又没有跳过的结点 ，这样对下面的搜索纯粹是徒劳，012345670811722H363454567-. z.这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的时机就更大一些。2 2、数据构造的选择和概要设计、数据构造的选择和概要设计数据构造的选择栈：本程序可以利用栈的知识来解决，当然，栈

4、也包括链栈和顺序栈，由于本程序数据有限，并且顺序栈较链栈简单，所以该程序最终选择使用顺序栈来解决。贪心算法：在算法中采用逐步构造最优解。在每个阶段，都作出一个看上去最优的决策在一定的标准下 。决策一旦作出就不可再更改。概要设计、主程序模块：void main()定义变量；承受命令；处理命令；退出；、起始坐标函数模块马儿在棋盘上的起始位置；、探寻路径函数模块马儿每个方向进展尝试，直到试完整个棋盘；、输出路径函数模块输出马儿行走的路径； 流程图如下： 输入的初始位置是否正确 否 是 3 3、详细设计和编码、详细设计和编码以下图显示了马位于方格2，3时，8 个可能的移动位置。一般来说，当马位于位置i

5、,j时，可以走到以下 8 个位置之一主程序模块起始坐标函数模块探寻路径函数模块 输出路径函数模块块 完毕-. z.012345670811722H373454567(i-2,j+1)、 i-1,j+2 、(i+1,j+2)、(i+2,j+1)(i+2,j-1)、(i+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 7Htry1 -2 -1 1 2 2 1 -1 -2 0 1 2 3 4 5 6 7Htr

6、y2 1 2 2 1 -1 -2 -2 -1位于(i,j)的马可以走到的新位置是在棋盘围的(i+Htryh,j+Htry2h),其中 h=0,1,2,7。每次在多个可走位置中选择其中一个进展试探，其余未曾试探过的可走位置必须用适当构造妥善管理，以备试探失败时的“回溯(悔棋)使用。流程图如下：-. z.开场Int i、ji=0iNBoardij=0i +输入棋子起始位置判断棋子是否出棋盘Multiple*For 循环从这个位置开场完毕4 4、上机调试过程、上机调试过程1 、本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中-. z.遇到了很多问题。首先，在开场刚编制程序的时候遇

7、到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开场时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。2 、虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式完毕程序，可能是在*些地方出现了无限死循环了，然后在仔细检查代码，发现没有标记马儿尝试的方向 director，这样的话，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。3 、标记好马儿尝试的方向后，编译运行，但是运行结果却不符合程序所要求的结果，说明在算法上肯定有错误，检查发现，马儿走的坐标没有控制后，它的横纵坐标必须控制 0 到 7 之间，否则的话马儿就会踏出棋

8、盘以外，这样输出的结果就不对。还有就是棋盘走过的位置要标记一下，以便下次走不重复走，当回溯的时候的记得把标记给清掉，这个地方有时候也很容易混淆。5 5、测试结果及分析、测试结果及分析输入数据 1：根据要求重新输入马的初始位置9,9 ，由于输入数据不再要求围之,程序要求用户重新输入;图1输入数据 2：根据要求重新输入马的初始位置1,1 ，结果如下图2图3测试结果如图1所示、当输入马的坐标为9,9时，由于该坐标不在 88 的棋盘，所以程序提示要求重新输入；如图2所示，重新输入数据位1,1满足棋盘要求，得到在该位置的马踏棋盘的结果。如图3所示，当位置选定为4,4时的结果。结果分析：如图3所示，以数字

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

10、；输入正确之后，程序会输入马儿踏遍整个棋盘的具体执行步骤。注：阿拉伯数字 1、2、3、462、63、64。下一个数字所在位置即为上一个位置马儿的出口。7 7、参考文献、参考文献1王昆仑，红.数据构造与算法.：铁道工业，2007 年 6 月第一版2.徐孝凯，荣数据构造,：机械工业，1996 年3.徐孝凯数据构造简明教程，:清华大学，1995 年4.文博，朱青数据构造与算法，：机械工业，1996 年5.许卓群，乃孝，冬青，唐世渭数据构造，高等教育，1988 年6.廉治，文清，郭福顺数据构造，理工大学，1989 年附录附录源程序源程序/1 、定义头文件和预定义#include#define MA*S

11、IZE 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; /列坐标 int director; /存储方向stackMA*SIZE; /定义一个栈数组int top=-1; /栈指针/3 、函数声明void InitLocation(int *i,int

12、 yi); /马儿在棋盘上的起始位置坐标-. z.int TryPath(int i,int j); /马儿每个方向进展尝试，直到试完整个棋盘void Display(); /输出马儿行走的路径/4 、起始坐标函数模块void InitLocation(int *i,int yi)int *,y; /定义棋盘的横纵坐标变量top+; /栈指针指向第一个栈首stacktop.i=*i; /将起始位置的横坐标进栈stacktop.j=yi; /将起始位置的纵坐标进栈stacktop.director=-1; /将起始位置的尝试方向赋初值board*iyi=top+1; /标记棋盘*=stackto

13、p.i; /将起始位置的横坐标赋给棋盘的横坐标y=stacktop.j; /将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(*,y) /调用马儿探寻函数，如果马儿探寻整个棋盘返回 1 否则返回 0Display(); /输出马儿的行走路径else printf(无解); /5 、探寻路径函数模块int TryPath(int i,int j)int find,director,number,min; /定义几个临时变量int i1,j1,h,k,s; /定义几个临时变量int a8,b18,b28,d8; /定义几个临时数组while(top-1) /栈不空时循环for(h=0;h=0

14、&i=0&j8) /如果找到下一位置for(k=0;k=0&i1=0&j18) /如果找到下一位置 number+; /记录条数 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(top=63) /如果走完整个棋盘返回 1return (1);find=0; /表示没有找到下一个位置-. z.for(h=director+1;h=0&i=0&

15、j8) /如果找到下一位置find=1; /表示找到下一个位置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,

16、j;-. z. for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d ,boardij); /输出马儿在棋盘上走过的路径printf(nn);printf(n);/5主程序模块void main()int i,j;int *,y;for(i=0;iN;i+) /初始化棋盘 for(j=0;jN;j+) boardij=0;for(;)printf(请输入棋子起始坐标(1=*=8 and 1=y=1&*=1&y=8)break;printf(Your input is worng!n);printf(从这里这个位置开场 %d :nn, 8*(*-1)+y);InitLocation(*-1,y-1); /调用起始坐标函数