实验报告-马踏棋盘(共13页).docx

《实验报告-马踏棋盘(共13页).docx》由会员分享，可在线阅读，更多相关《实验报告-马踏棋盘(共13页).docx（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上2.4题马踏棋盘题目：设计一个国际象棋的马踏棋盘的演示程序班级：姓名：学号：完成日期：一 需求分析（1）输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是1,8。（2）输出形式：以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（3）程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。（4）测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1=x,y=8就可以了。正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程

2、序会显示：“输入有误！请重新输入”并且要求用户重新输入数据，直至输入正确为止。二 概要设计（1） 、位置的存储表示方式（2） typedefstruct intx; inty; intfrom;Point;（2） 、栈的存储方式#defineSTACKSIZE70#defineSTACKINCREASE10typedefstructStack Point*top; Point*base;intstacksize;（1）、设定栈的抽象数据类型定义：ADTStack数据对象：D=ai|aiElemSet,i=1,2,n,n0 数据关系：R1=|ai-1,aiD,i=2,n 约定an端为栈顶，ai端

3、为栈顶。 基本操作：InitStack(&s)操作结果：构造一个空栈s，DestroyStack(&s)初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&s)初始条件：栈s已存在。 操作结果：栈s清为空栈。 StackEmpty(&s)初始条件：栈s已存在。 操作结果：若栈s为空栈，则返回TRUE，否则返回FALSE。 StackLength(s); 初始条件：栈s存在。操作结果：返回s的元素个数，即栈的长度。GetTop(s,&e);初始条件：栈s已存在且非空。 操作结果：用e返回s的栈顶元素。Push(&s,e) 初始条件：栈s已存在。操作结果：插入元素e为新的栈顶元

4、素。Pop(&s,&e)初始条件：栈s存在且非空。操作结果：删除栈顶元素，并用e返回。stackTraverse(s,visit() 初始条件：栈s存在且非空。操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败， 则 操作失败。ADTStack本程序包含模块：1、 主程序模块：voidmain()定义变量；接受命令；处理命令；退出；2、 起始坐标函数模块马儿在棋盘上的起始位置；3、 探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘；4、 输出路径函数模块输出马儿行走的路径；三 详细设计1.函数声明Void InitLocation(int xi,intyi

5、);/马儿在棋盘上的起始位置标intTryPath(inti,intj);/马儿每个方向进行尝试，直到试完整个棋盘voidDisplay();/输出马儿行走的路径2.起始坐标函数模块voidInitLocation(intxi,intyi)intx,y;/定义棋盘的横纵坐标变量top+;/栈指针指向第一个栈首stacktop.i=xi;/将起始位置的横坐标进栈stacktop.j=yi;/将起始位置的纵坐标进栈stacktop.director=-1;/将起始位置的尝试方向赋初值boardxiyi=top+1;/标记棋盘x=stacktop.i;/将起始位置的横坐标赋给棋盘的横标y=stack

6、top.j;/将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(x,y)/调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则0Display();/输出马儿的行走路径elseprintf(无解);3.探寻路径函数模块intTryPath(inti,intj)intfind,director,number,min;/定义几个临时变量inti1,j1,h,k,s;/定义几个临时变量inta8,b18,b28,d8;/定义几个临时数组while(top-1)/栈不空时循环 for(h=0;h=0&i=0&j8)/如果找到下一位置for(k=0;k=0&i1=0&j18)/如果找到下一位置numb

7、er+;/记录条数 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;/表示没有找到下一个位置for(h=director+1;h=0&i=0&j8)/如果找到下一位置find=1;/表示找到下一个位置Break;if(find=1)/如果找到下一个位置进栈stacktop.director=dir

8、ector;/存储栈结点的方向top+;/栈指针前移进栈stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一栈结点的尝试方向boardij=top+1;/标记棋盘 else/否则退栈 boardstacktop.istacktop.j=0;/清除棋盘的标记top-;/栈指针前移退栈 return(0);4.输出路径函数模块voidDisplay()inti,j;for(i=0;iN;i+)for(j=0;jN;j+)printf(t%d,boardij);/输出马儿在棋盘上走过的路径printf(nn);printf(n);四、测试数据

9、及测试结果测试数据：x=2,y=3测试结果如下：五 原程序代码#include#defineMAXSIZE100#defineN8intboard88;/定义棋盘intHtry18=1,-1,-2,2,2,1,-1,-2;/*存储马各个出口位置相对当前位置行下标的*/intHtry28=2,-2,1,1,-1,-2,2,-1;/*存储马各个出口位置相对当前位置列下标的增量数组*/structStack/定义栈类型inti;/行坐标intj;/列坐标intdirector;/存储方向stackMAXSIZE;/定义一个栈数组inttop=-1;/栈指针voidInitLocation(intxi

10、,intyi);/马儿在棋盘上的起始位置坐标intTryPath(inti,intj);/马儿每个方向进行尝试，直到试完整个棋盘voidDisplay();/输出马儿行走的路径voidInitLocation(intxi,intyi)intx,y;/定义棋盘的横纵坐标变量top+;/栈指针指向第一个栈首stacktop.i=xi;/将起始位置的横坐标进栈stacktop.j=yi;/将起始位置的纵坐标进栈stacktop.director=-1;/将起始位置的尝试方向赋初值boardxiyi=top+1;/标记棋盘x=stacktop.i;/将起始位置的横坐标赋给棋盘的横坐标y=stackto

11、p.j;/将起始位置的纵坐标赋给棋盘的纵坐标if(TryPath(x,y)/调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0Display();/输出马儿的行走路径elseprintf(无解);intTryPath(inti,intj)intfind,director,number,min;/定义几个临时变量inti1,j1,h,k,s;/定义几个临时变量inta8,b18,b28,d8;/定义几个临时数组while(top-1)/栈不空时循环for(h=0;h=0&i=0&j8)/如果找到下一位置 for(k=0;k=0&i1=0&j18) /如果找到下一位置number+;/记录条数

12、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;/表示没有找到下一个位置for(h=director+1;h=0&i=0&j8)/如果找到下一位置 find=1;/表示找到下一个位置 break; if(find=1)/如果找到下一个位置进栈 stacktop.director=directo

13、r;/存储栈结点的方向top+;/栈指针前移进栈stacktop.i=i;stacktop.j=j;stacktop.director=-1;/重新初始化下一栈结点的尝试方向boardij=top+1;/标记棋盘else/否则退栈boardstacktop.istacktop.j=0;/清除棋盘的标记top-;/栈指针前移退栈 return(0);voidDisplay() inti,j; for(i=0;iN;i+) for(j=0;jN;j+)printf(t%d,boardij);/输出马儿在棋盘上走过的路径printf(nn); printf(n);intmain()inti,j;intx,y;for(i=0;iN;i+)/初始化棋盘for(j=0;jN;j+)boardij=0;for(;)printf(Pleaseinputimportpoint(1=x=8and1=y=1&x=1&y=8)break;printf(Yourinputisworng!n);printf(beginwith%dboard:nn,8*(x-1)+y);InitLocation(x-1,y-1);/调用起始坐标函数专心-专注-专业