文档介绍：<<数据结构>>课程设计报告题目马踏棋盘学院____计算机学院______专业_计算机科学与技术年级班别____2005级7班__学号3105007083学生姓名______林春茂指导教师______刘添添_______2007年6月问题描述设计一个国际象棋的马踏棋盘的演示程序。基本要求将马随机放在国际象棋8*8的棋盘Board[8][8]的某个方格中,马按走棋规则进行移动。要求每个方格只进入一次,走遍棋盘全部的64个方格。编制非递归程序,求出马的行走路线,并按求出的行走路线,将数字1,2,3…….64一次填入一个8*8的方阵输出之测试数据可自行指定一个马的初始位置(i,j),0<=i,j<=7.。实现提示一般说来,当马位于位置(i,j)时,可以走到下列8个位置之一(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个可能位置可以用一维数组Htry1[0…7]和HTry2[0..7]来表示:Htry101234567-2-11221-1-2Htry20**********-1-2-2-1位于(i,j)的马可以走到新位置是在棋盘范围内的(i+Htry1[h],j+Htry2[h]),其中h=0,1,….:(1)求出从某一七点出发的多条至全部行走路线。(2)探讨每次选择位置的“最佳策略”,以减少回溯的次数。(3)演示寻找行走路线的回溯过程。;分开输入马的初始行坐标X和列坐标Y,X和Y的范围都是[0,7]。;一共提供了2种输出方式:(1)以数组下标形式输入,代表起始位置,i表示行标,j表示列标。(2)以棋盘形式输出,每一格打印马走的步数,这种方式比较直观。;(1)让马从任一起点出发都能够历遍整个8×8的棋盘。(2)能寻找多条不同的行走路径。,包括正确的输入及输出结果和含有错误的输入及其输出结果。数据可以任定,只要0<=X<7&&0<=Y<7就可以了。正确的输出结果为一个2维数组,每个元素的值表示马行走的第几步。若输入有错,程序会显示“输入错误,请重新输入:”并且要求用户重新输入数据,直至输入正确为止。:ADTStack{数据对象:D={ai|ai∈CharSet,i=1,2..,n}数据关系:R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}基本操作:(这里仅列举本题中使用的操作)InitStack(&S)操作结果:构建一个空栈。Push(&S,e)操作结果:在栈顶插入新的元素。Pop(&S,&e)操作结果:将栈顶元素弹出。SetTop(S,&e)操作结果:将e设为栈顶元素。GetTop(S,&e)操作结果:将栈顶元素取出。StackEmpty(S)判断栈是否为空}(1).主程序模块:Voidmain(){初始化棋盘;while(1){接受命令;处理命令;}执行Path(x,y);}(2).栈模块-“最佳策略”思路1)先求出每个坐标点的权值,即是该坐标下一步有几个方向可以走2)权值越小,则被上一点选中的可能性就越大,下一个方向八个值的选择顺序保存MAP[X][Y][K]数组中,0<=K<=7,例如MAP[X][Y][0]保存的是下一步优先选择走的方向,MAP[X][Y][7]就是最后才走的。边界的点最先走,然后再走中间。:While(){若已经走了64步,则{打印输出结果;若要寻找多条路径,出栈,回溯到上一步,下一步方向加1*}否则{若该点所有方向已走完{出栈,回溯到上一个点,上一个点要走的方向加1}若该点所有方向未走完{若该点未走过且在棋盘内{入栈,已走步数加1}否则{*下一步方向加1}}}}{intx;//棋盘的行坐标inty;//棋盘的列坐标intz;//该点的方向值}chess;typedefchessSElemType;栈的顺序存储表示typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后,base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间,以元素为单位*/}SqStack;/*顺序栈*/栈基本操作:StatusInitStack(SqStack*S){/*构造一个空栈S*/(*S).base=(SElemTyp