资源描述：
《马踏棋盘程序设计.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、问题描述设计一个国际象棋的马踏棋盘的演示程序。基本要求将马随机放在国际象棋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),
2、(i-2,j-1)但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8个可能位置可以用一维数组Htry1[0…7]和HTry2[0..7]来表示：Htry101234567-2-11221-1-2Htry2012345671221-1-2-2-1位于（i,j）的马可以走到新位置是在棋盘范围内的（i+Htry1[h],j+Htry2[h]）,其中h=0,1,….7.一．需求分析1．输入的形式和输入值的范围；分开输入马的初始行坐标X和列坐标Y，X和Y的范围都是［0,7］。2．输出的形式；一共提供了2种输出方式：（1）以数组下标形式输入，代表起始
3、位置，i表示行标，j表示列标。（2）以棋盘形式输出，每一格打印马走的步数，这种方式比较直观。3．程序所能达到的功能；让马从任一起点出发都能够历遍整个8×8的棋盘。二．概要设计1．设定栈的抽象数据类型定义：ADTStack{数据对象：D={ai
4、ai∈CharSet,i=1,2..,n}数据关系:R1={
5、ai-1,ai∈D,i=2,...,n}基本操作:(这里仅列举本题中使用的操作)InitStack(&S)操作结果:构建一个空栈。Push(&S,e)操作结果:在栈顶插入新的元素。Pop（&S,&e）操作结果：将栈顶元素弹出。SetTop(S,&e)操作结
6、果：将e设为栈顶元素。GetTop(S,&e)操作结果：将栈顶元素取出。StackEmpty(S)判断栈是否为空}ADTStack2．本程序包含2个模块(1).主程序模块:Voidmain(){初始化棋盘；while(1){接受命令；处理命令；}执行Path(x,y);}(2).栈模块－实现栈抽象数据类型3．探讨每次选择位置的“最佳策略”思路1）先求出每个坐标点的权值，即是该坐标下一步有几个方向可以走2）权值越小,则被上一点选中的可能性就越大，下一个方向八个值的选择顺序保存MAP[X][Y][K]数组中，0<=K<=7，例如MAP[X][Y][0]保存的是下一步优先选择走的
7、方向，MAP[X][Y][7]就是最后才走的。边界的点最先走，然后再走中间。4．踏遍棋盘伪码算法：While（）{若已经走了64步,则{打印输出结果；}否则{若该点所有方向已走完{出栈}若该点所有方向未走完{若该点未走过且在棋盘内{入栈，已走步数加1}否则{*下一步方向加1}}}}三．详细设计1．栈类型structSElemType{inta;intb;intdi;//方向编号intflag[8];//访问过的方向数};栈的顺序存储表示typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;};栈基本操作
8、：StatusInitStack(SqStack*S){/*构造一个空栈S*/(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elser
9、eturnFALSE;}StatusGetTop(SqStackS,SElemType*e){/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR/if(S.top>S.base){*e=*(S.top-1);returnOK;}elsereturnERROR;}StatusSetTop(SqStackS,SElemType*e){if(S.top>S.base){*(S.top-1)=*e;returnOK;}elsereturnERROR;}StatusPush(SqStack*S,SElemT
