数据结构 马踏棋盘.doc

“后进先出”和队列的特性“先进先出”。仅仅认识到栈和队列是两种特殊的线性表是远远不够的,本次实验的目的在于更深入的了解栈和队列的特性,以便在实际问题背景下灵活运用他们。在了解他特性的基础上,还将巩固对这种结构的构造方法的理解。:在国际象棋8×8棋盘上面,按照国际象棋规则中马的行进规则,实现从任意初始位置,每个方格只进入一次,走遍棋盘上全部64个方格。编制程序,求出马的行走路线,并按求出的行走路线,将数字1,2,…,64依次填入一个8×8的方阵,并输出它的行走路线(棋盘如图所示)。输入:任意一个起始位置;输出:无重复踏遍棋盘的结果,以数字1-64表示行走路线。 012345670  8 1   1 7   2  2   H    3 6   3  4  5 4   5        6        7        二概要设计为了实现上述程序功能,可以采用顺序栈或者链栈来存储它的数据,本实验所需要的存储空间不是很大,不需动态的开辟很多空间,所以采用相对简单的顺序栈来存储数据,既方便有简单,而用链栈在实现上相对比顺序栈复杂的一点。:ADTStack{数据对象:D={ai|ai∈(0,1,…,9),i=0,1,2,…,n,n≥0}数据关系:R={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}}:1、主程序模块:voidmain(){定义变量;接受命令;处理命令;退出;}2、起始坐标函数模块——马儿在棋盘上的起始位置;3、探寻路径函数模块——马儿每个方向进行尝试,直到试完整个棋盘;4、输出路径函数模块——输出马儿行走的路径;:#include<>#defineMAXSIZE100#[8][8];//定义棋盘intHtry1[8]={1,-1,-2,2,2,1,-1,-2};/*存储马各个出口位置相对当前位置行下标的增量数组*/intHtry2[8]={2,-2,1,1,-1,-2,2,-1};/*存储马各个出口位置相对当前位置列下标的增量数组*/structStack{//定义栈类型 inti;//行坐标 intj;//列坐标intdirector;//存储方向}stack[MAXSIZE];//定义一个栈数组inttop=-1;//(intxi,intyi);//马儿在棋盘上的起始位置坐标intTryPath(inti,intj);//马儿每个方向进行尝试,直到试完整个棋盘voidDisplay();//(intxi,intyi){ intx,y;//定义棋盘的横纵坐标变量 top++;//栈指针指向第一个栈首 stack[top].i=xi;//将起始位置的横坐标进栈 stack[top].j=yi;//将起始位置的纵坐标进栈 stack[top].director=-1;/