马踏棋盘实验报告单(含代码).doc

计算机学院数据结构课程设计报告 课题名称： 马踏棋盘 课题负责人（学号/姓名）： 黎贵涛 110520121 同组成员名单（姓名）： 刘伟 110520131 林建彪 110520104 指导教师： 孔令寅 评阅成绩： 评阅意见： 提交报告时间：2020年1月3日 项目成员序号学号姓名职责任务说明1110520131刘伟小组成员1. 需求分析2. 用户使用说明3. 测试结果2110520121黎贵涛组长1. 概要设计2.详细设计3110520104林建彪小组成员 1概要设计 2.调试分析一、【问题描述】设计一个国际象棋的马踏棋盘的演示过程。基本要求:将马随机放在国际象棋的8*8棋盘Board88的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个8*8的方阵，输出之。测试数据：可自行制定一个马的初始位置（i，j），0=I,j=7。二、【实验目的】1、对数据结构基本理论和存储结构及算法设计有更深入的理解；2、了解栈的特性，以便在实际问题背景下灵活运用他们；3、提高在世纪设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力。3、 【设计过程】81726354 第1步：实现提示一般来说，当马位于位置（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) （图-1） 但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能要超出棋盘位置，成为不允许的位置。8个可能位置可以用一位数组HTry107和HTry207来表示： 0 1 2 3 4 5 6 7-2-11221-1-21221-1-2-2-1 （表-2）位于（i，j）的马可以走到新位置是在棋盘范围内的（i+HTry1h,j+HTry2h），其中h=07。第2步：需求分析（1） 输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是1,8。（2） 输出形式：以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（3） 程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。（4） 测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1=x,y=8就可以了。正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入”并且要求用户重新输入数据，直至输入正确为止。第3步，算法设计思想：1、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处1=x，y=8；2、将输入的初始值进栈；3、设置一个while循环，循环条件为count64；4、取出栈顶元素；5、定义flag标志变量的值；6、按照setpossible函数顺时针顺序优先原则，找栈顶元素周围未被占用 的新位置。7、若存在该位置，则令order的值等于该新位置的坐标，并入栈；8、否则弹出栈顶元素；9、再次回到第步while循环进行判断；10、输出一个8*8的方阵，所示数字即为相应步骤。第4步，算法框图： 开始输入初始坐标X,Y判断X,Y是否合法？Initstack建立新栈并且将初始位置入栈count64GetTop取栈顶元素；找出所有可走位置根据for循环及优先原则查找是否存在下一个坐标？调用push函数将其压缩进栈调用DleteTop函数将栈顶元素弹出输出否是否是否是第5步，存储结构设计：（1）、位置的存储表示方式typedef struct int x; int y; int from;Point;（2）、栈的存储方式#define STACKSIZE 70#define STACKINCREASE 10typedef struct Stack Point *top; Point *base; int stacksize; 第6步，设计功能分析与实现（1）、设定栈的抽象数据类型定义： ADT Stack 数据对象：D=ai | aiElemSet,i=1,2,n,n0 数据关系：R1=|ai-1, aiD,i=2,n 约定an端为栈顶，ai端为栈顶。 基本操作： InitStack(&s) 操作结果：构造一个空栈s， DestroyStack(&s) 初始条件：栈s已存在。 操作结果：栈s被销毁。 ClearStack(&s) 初始条件：栈s已存在。 操作结果：栈s清为空栈。 StackEmpty(&s) 初始条件：栈s已存在。 操作结果：若栈s为空栈，则返回OK，否则返回ERROR。 StackLength(s); 初始条件：栈s存在。 操作结果：返回s的元素个数，即栈的长度。 GetTop (s,&e); 初始条件：栈s已存在且非空。 操作结果：用e返回s的栈顶元素。 Push(&s,e) 初始条件：栈s已存在。 操作结果：插入元素e为新的栈顶元素。 DeleteTop(&s,&e) 初始条件：栈s存在且非空。 操作结果：删除栈顶元素，并用e返回。 GetDeep(s) 初始条件：栈s存在。 操作结果：返回一个int型的整数表示栈深。 stackTraverse(s,visit() 初始条件：栈s存在且非空。 操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败，则操作失败。ADT Stack（2）、选取对该程序有用的函数。 1、InitStack(&s) 用于构建空栈实现相应的操作； 2、StackEmpty(&s) 用于判断空栈情况，已确保循环体能够准确实现； 3、GetTop (s,&e) 用于取放入栈的栈顶元素，实现把放入的横纵坐标按要求取出； 4、Push(&s,e) 用于将用户输入的横纵坐标放入栈； 5、DeleteTop(&s,&e) 用于实现将要求取出的元素取出； 6、GetDeep() 用于获取栈的深度； 7、DestroyStack() 用于销毁栈。（3）、主要函数及算法说明。 1、函数：void setpossible(Point cur) 参数：Point cur 功能：找出当前位置下一步的八个位置，将其赋给g_round8; 算法：接受参数传来的值，按顺时针次序加上 g_roundi.x=-2,-1,1,2,2,1,-1,-2; g_roundi.y=1,2,2,1,-1,-2,-2,-1; 再根据getpossible函数来判断是否合法；若合法则返回OK,否则返回ERROR. 2、函数：Status getpossible(int i,Point &pt) 参数：int i,Point &pt 功能：将所在位置周围八个位置坐标赋予指针变量，并判断其合理性； 算法：用以下赋值语句pt.x=g_roundi-1.x; pt.y=g_roundi-1.y; 将现在周围8个指定位置赋予指针变量pt，并用 if(pt.x0|pt.y7|pt.y7) 条件语句判断其合理性，若合理则返回OK，否则返回ERROR. 3、语句：for(int i=cur.from+1;i=8;i+) if(getpossible(i,next)&ordernext.xnext.y=0) 语句 功能：按照顺时针优先规则，选出下一个可用的位置，通过if判断语句来判断所选的下一步是否可用，若可用，则使其进栈，否则运行下面一个语句。 4、语句：if(flag=NULL) 语句. while(j1) 语句.功能：如果当前位置不存在任何新路径，则根据while循环进行退栈，直至退到存在有最佳位置的坐标。但必须保证栈不为空。所以此出栈中设定了int GetDeep的基本操作，就是防止空栈还继续弹东西出来的情况发生。 四、【调试程序】 （1）、问题：语法错误 原因：首次运行语法错误比较多，一般都是由于粗心大意输入有误造成的，还有一些错误属于变量忘记定义之类的，经过认真一个一个调试后这类错误得以解决。下图为第一次运行时的错误 （2）、问题：运行后突然停止程序 原因：可能是输出不恰当 解决：此问题出现后，刚开始不知道为啥，看了很多遍程序就是找不出原由，于是后来请教同学，一起研究后无意中改了输出格式，将printf(%s,%2d ,|,orderij);改成了printf(%d,%f ,orderij,|);竟然成功输出了。怀疑是%s使用得不恰当。 下图为修改前的运行结果：（3）、问题：将上述问题解决后虽然不会出现程序突然终止的情况，但运行结果如下图，输出结果很乱； 原因：输出格式不符 解决：将printf(%d,%f ,orderij,|);改成printf(| %2d ,orderij);(4)、 问题：上述问题都搞定后，输入初始坐标后按下Enter键后不会出现棋盘 原因：main()函数里flag写成int flage ； 解决： 将int flage改成flag (5)、问题：上述问题都搞定后，输入初始坐标后按下Enter键后会出现棋盘，但是在棋盘上 会 出现0 0 0 0的情况，与需要的结果不符。 原因：regular.h 文件里面获得合理位置的边界位置判定，横坐标和纵坐标的范围少写了ps.x7|ps.y7|ps.y0（6）、问题：上述问题都搞定后，输入初始坐标后按下Enter键后立即退出了 原因：main()函数里有scanf()，当用户输入初始坐标后，将这两个坐标赋予给&begin.x,&begin.y，结果当用户想用Enter键进行确认操作后，Enter本身是一个字符，而这个字符不符合循环要求，所以直接退出 解决：多加一个getchar()把Enter键给吸收掉，结果如下图： 五、【用户手册】1、 运行程序，程序开始界面，如图所示：2、 输入初始值x, y，如输入（3, 7），如图所示：3、 因为（3, 7）在（18）的范围内，所以程序输出结果如下:按（y/Y）后，程序将跳到输入初始值位置，如图所示：按其他任意键后（如按（n/N）键），将退出程序，如图所示：4、 若输入的初始值没在（18）的范围内，如输入（7, 9），则将提示错误，并要求重新输入，如图所示：按任意键后，程序将跳回输入初始值的位置，如图所示：六、【实验总结与体会】 总结：马踏棋盘，作为一种经典的栈的应用例子，从大方面将，刚看到这名字就知道用栈来实现，但是，当你面对这个题目，打开编译器之后想写的时候，发现又不是那么容易，很多细节需要认真的分析，比如结构体的定义，棋子因为是二维的，所以对于用来存储棋盘的横纵坐标，需要用到两个变量，定义两整型变量x,y。刚开始只定义了这两个变量，后来发现如果找到下一个位置，而下一个位置有很多个都是符合的，如何选取最优的呢？最有的有可能是最先找到的，可找到后还得继续找下去，万一没有比他更优的，则要退回来，如果没有变量from来记录前一位置最优位置，就无法找到之前的点，所以要多加一个变量；其外就是程序的调试，调试确实需要很大的耐心，有时候只是你的大意而输错了字符或输入输出格式不符合就会出现很多看起来不可思议很难发现的错误，这也说明了编程的时候一定要认真有耐心。 体会：刚学习栈的时候，觉得并不太难，反正就是先进后出，可是到了实际运用的时候，才发现学到的理论知识要用到实际去还真是个问题，通过这次课程设计的实践，让我对栈有了更深入的理解，也发现一种理论再简单的知识，如果不实际运用一下，对于你的掌握肯定是不够的，因为实际运用中你要适当选取哪些是有用的，哪些不必用到的，而且当你很兴奋的写完代码后，会发现很多错误，当然一般是语法错误，如果你的逻辑没错的话，也有可能是你思想没错，但你的表达不妥当，这也会让你对程序的修改显得很无助；再次，世上没有完美的程序，如今社会上出现的各个软件每到一定的时候就会有升级版也正是这个原因，我承认自己这个程序存在很多漏洞和不足，但一个程序的优化可不是一朝一夕的事，只要求自己能完成基本任务就行了。 七、【参考文献】 数据结构（C语言版）-严蔚敏、吴伟民 编著 C语言设计（第三版）-谭浩强 著 C语言课程设计（第2版）-梁旭、谷晓琳、黄明 编著 C语言通用范例金典-柳盛，王国全，沈永林 编著8、 【程序清单】1.文件horse.h#ifndef _HORSE_H_#define _HORSE_H_#include#include#define OK 1#define ERROR 0#define STACKSIZE 70#define STACKINCREASE 10typedef int Status;/位置的储存typedef struct int x;int y;int from;Point;/栈的储存typedef struct Point *top;Point *base;int stacksize;Stack;/建栈Status Initstack(Stack &s)s.base=(Point*)malloc(STACKSIZE*sizeof(Point);if(s.base=NULL)return ERROR;s.top=s.base;s.stacksize=STACKSIZE;return OK;/向栈中插入元素eStatus Push(Stack &s,Point e)if(s.top-s.base=s.stacksize)s.base=(Point*)realloc(s.base,(s.stacksize+STACKINCREASE)*sizeof(Point);if(s.base=NULL)return ERROR;s.top=s.base+s.stacksize;s.stacksize+=STACKINCREASE;(*s.top).x=e.x;(*s.top).y=e.y;(*s.top).from=e.from;s.top+;return OK;/栈不为空，则删除栈顶元素Status DeleteTop(Stack &s,Point &e)if(s.top=s.base)return ERROR;s.top-;e.x=(*s.top).x;e.y=(*s.top).y;e.from=(*s.top).from;return OK;/销毁栈Status DestroyStack(Stack &s)free(s.base);/free(s);return OK;/判断栈是否为空Status StackEmpty(Stack s)if(s.base=s.top)return OK;else return ERROR;/获得栈顶元素Status GetTop(Stack s,Point &e)if(s.base=s.top)return ERROR;e.x=(*(s.top-1).x;e.y=(*(s.top-1).y;e.from=(*(s.top-1).from;return OK;/获得栈的深度int GetDeep(Stack s)return s.top-s.base;#endif2. 文件regular.h#ifndef _REGULAR_H_#define _REGULAR_H_#includehorse.hPoint h_possible8=0,0,0;/查找所有可能的位置，并存入h_possible8中void setPossible(Point con)Point round=con.x-2,con.y+1,0,con.x-1,con.y+2,0,con.x+1,con.y+2,0,con.x+2,con.y+1,0,con.x+2,con.y-1,0,con.x+1,con.y-2,0,con.x-1,con.y-2,0,con.x-2,con.y-1,0;for(int i=0;i8;i+)h_possiblei.x=roundi.x;h_possiblei.y=roundi.y;h_possiblei.from=roundi.from;/取得合理的可能位置Status getPossible(int i,Point &ps)ps.x=h_possiblei-1.x;ps.y=h_possiblei-1.y;if(ps.x7|ps.x7|ps.y0)return ERROR;else return OK;#endif3. 主函数main.c#include#include#includehorse.h#includeregular.hvoid main()int i,j,p;int s=1;char yn;Stack horseVisit;Point cur,next;H1:while(s) int order88=0;/是一个中间变量，用来记录当前位置 int count=0; Point begin; system(color 31); printf(n); printf(请输入马在棋盘上的任意初始位置x，y，根据用户习惯，其中x,y为（8），例如（7）：); scanf(%d%d,&begin.x,&begin.y); printf(n=n); begin.from=0; while(begin.x8|begin.y8|begin.x1|begin.y1) system(cls); printf(n); getchar(); getchar(); system(cls); goto H1; getchar(); begin.x-;/注意用户输入的坐标（8），而储存是（7），这里要自减 begin.y-; Initstack(horseVisit);/创建空栈 Push(horseVisit,begin);/入栈，将用户输入的坐标存入栈中 count+;/计数器加 orderbegin.xbegin.y=count; while(count64) GetTop(horseVisit,cur);/取栈顶元素存入cur中 setPossible(cur);/找出位置附近可能的八个位置 int flag=false;/标志 for(int i=cur.from+1;i=8;i+) /按照顺时针的顺序，选出下一个可走的新位置 if(getPossible(i,next)&ordernext.xnext.y=0)/next是下一个位置，这里表示下一个位置未被占领 flag = true;/代表成功 count+;/位置可用，计数器加 ordernext.xnext.y=count;/在新的位置上显示当前步数 DeleteTop(horseVisit,cu