马踏棋盘 数据结构实践报告

马踏棋盘问题摘要：马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。理解栈的 “后进先出”的特性以及学会使用回溯。关键字：马踏棋盘、递归、栈、回溯1引言马踏棋盘就是在国际象棋8X8棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2.64依次填入一个8X8的方阵，并输出它的行走路线。输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。2需求分析（1）需要输出一个8X8的棋盘，可以采用二维数组的方法实现。（2）输入马的起始位置，必须保证输入的数字在规定范围内，即0=X=7,0=Y=7。（3）保证马能走遍整个棋盘，并且不重复。（4）在棋盘上输出马的行走路线,标记好数字1、2、3直到64。3数据结构设计采用栈数组为存储结构。#define maxsize 100struct int i; int j;int director;stackmaxsize;4算法设计4.1 马的起始坐标void location(int x,int y) /马的位置坐标的初始化top+;stacktop.i=x; /起始位置的横坐标进栈stacktop.j=y; /起始位置的竖坐标进栈stacktop.director=-1;axy=top+1; /标记棋盘Try(x,y); /探寻的马的行走路线4.2 路径探寻函数void Try(int i,int j) int count,find,min,director; int i1,j1,h,k,s; int b8=-2,-2,-1,1,2,2,1,-1,c8=1,-1,-2,-2,-1,1,2,2; /存储马各个出口相对当前位置行、列坐标的增量数组 int b28,b18; for(h=0;h=0&i=0&j=7&aij=0) /如果找到下一个位置 for(k=0;k=0&i1=0&j1=7&ai1j1=0) /如果找到下一个位置 count+; /记录条数b1h=count; /将条数存入b18中 for(h=0;h=7;h+) /根据可行路径条数的大小，从小到大排序，并放入数组b28中 min=9; for(k=0;kb1k) min=b1k; b2h=k; s=k; b1s=9; find=0; director=stacktop.director; for(h=director+1;h=0&i=0&j=7&aij=0)stacktop.director=h; /存储栈的寻找方向top+; /进栈stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一栈的方向 aij=top+1; find=1; /找到下一位置 break; if(find!=1)astacktop.istacktop.j=0; /清除棋盘的标记 top-; /退栈 if(top63)Try(i,j); /递归4.3输出函数void display()int i,j;for(i=0;i=7;i+) for(j=0;j=7;j+) printf(t%d ,aij); /输出马的行走路线 printf(nn);printf(n);5.程序实现5.1 主函数void main()int i,j,x,y;for(i=0;i=7;i+) /棋盘的初始化for(j=0;j=7;j+)aij=0;printf(输入X Y (0=X=7,0=Y=0&x=0&y=7) /判断输入的起始位子是否正确location(x,y); display();else printf(错误n);5.2运行结果（1）当输入不符合要求时 （2）正确输入时5.3 算法分析（1）马的起始坐标 一开始先建立一个栈数组，里面包括横坐标和竖坐标还有方向。输入马的起始位置，进入坐标起始化函数，让输入的横坐标和竖坐标进栈，并初始化方向，并且标记棋盘，指示此位置已走过，此时的位置是栈的第一个元素，进入路径探寻函数。（2）路径探寻函数 路径探寻函数中有两个分别存储马各个出口相对当前位置行、列坐标的增量数组。要使马走遍所有的棋盘，必须要有一定的行走规律。我使用的是记录当前位置的下一个位置的可行路径的条数，并对它们进行排序，按从小到大的顺序存储在一个一维数组中。开始进行探寻，分别向8个方向探寻，如果找到一个方向可行，则存储栈的寻找方向，再进栈，重新初始化栈的寻找方向，并用二维数组标记此位置，再使用递归进入下一次新的探寻。如果在某一次探寻中，没能找到方向，则清除该位置的标记，并退栈，再次递归，回到上次的寻找方向（之前已经存储过栈的寻找方向），跳过已经寻找过的方向，再进行探寻，直到全部棋盘都被走遍。（3）输出函数 当马走遍所有的棋盘时，输出马的行走路线，因为之前已经把马的行走路线记录在二维数组中了，所以此时只需把二维数组中的标记输出即可。6.设计体会 本次课程设计让我学会了很多东西，使得我对于栈的理解更深入了，使用更加熟练。是此之前，我对于回溯并不是特别了解，但是这次设计让我学会了回溯的基本概念以及基础的用法。当一件事情有很多种方法进行时，我们要将所有的方法集合起来形成一个集合，再用一定的规律去调用这个集合内的方法。刚开始的时候，我并不能让马走遍所有的棋盘，但当我知道了回溯的思想之后，我修正了我的算法，最终使马走遍所有的棋盘。我还考虑了递归与非递归的问题，在试验了两种方法之后，发现两种都可以，在时间的复杂度上也没有太大的差别（显示棋盘的时间上），但我还是使用的是递归的方法来完成本次设计。参考文献：1 严蔚敏、吴伟民编著数据结构（C语言版）北京：清华大学出版社，2 谭浩强主编C程序设计（第三版）北京：清华大学出版，20053 张蕊、吕涛主编C程序设计教程. 华中科技大学出版，2012