数据结构课程设计-马踏棋盘实验报告(仅供参考).doc

1、一、【问题描述】设计一个国际象棋的马踏棋盘的演示过程。基本要求:将马随机放在国际象棋的8*8棋盘Board88的某个方格中，马按走棋规则进行移动，要求每个方格只进行一次，走遍整个棋盘的全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个8*8的方阵，输出之。测试数据：可自行制定一个马的初始位置（i，j），0=I,j=7。二、【实验目的】1、对数据结构基本理论和存储结构及算法设计有更深入的理解；2、了解栈的特性，以便在实际问题背景下灵活运用他们；3、提高在世纪设计操作中系统分析、结构确定、算法选择、数学建模和信息加工的能力。三、【设计过程】第1步：

2、实现提示一般来说，当马位于位置（i,j）时，可以走到下列8个位置之一：81726354（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

3、步：需求分析（1） 输入的形式和输入值的范围：输入马的初始行坐标X和列坐标Y，X和Y的范围都是1,8。（2） 输出形式：以数组下表的形式输入，i为行标，j为列标，用空格符号隔开。以棋盘形式输出，每一格打印马走的步数，这种方式比较直观（3） 程序所能达到的功能：让马从任意起点出发都能够遍历整个8*8的棋盘。（4） 测试数据，包括正确输入及输出结果和含有错误的输入及其输出结果。数据可以任定，只要1=x,y=8就可以了。正确的输出结果为一个二维数组，每个元素的值表示马行走的第几步，若输入有错，则程序会显示：“输入有误！请重新输入”并且要求用户重新输入数据，直至输入正确为止。第3步，算法设计思想：1、

4、输入马所在初始位置的坐标值，考虑到用户的输入习惯，此处1=x，y=8；2、将输入的初始值进栈；3、设置一个while循环，循环条件为count64；4、取出栈顶元素；5、定义flag标志变量的值；6、按照SetRound函数逆时针顺序优先原则，找栈顶元素周围未被占用 的7、新位置。若存在该位置，则令order的值等于该新位置的坐标，并入 栈；8、否则弹出栈顶元素；9、再次回到第步while循环进行判断；10、输出一个8*8的方阵，所示数字即为相应步骤。 第4步，算法框图： 开始输入初始坐标X,Y判断X,Y是否合法？Initstack建立新栈并且将初始位置入栈count64GetTop取栈顶元素

5、；找出所有可走位置根据for循环及优先原则查找是否存在下一个坐标？调用push函数将其压缩进栈调用Pop函数将栈顶元素弹出输出否是否是否是第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=

6、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为空栈，则返回TRUE，否则返回FALSE。 StackLength(s); 初始条件：栈s存在。 操作结果：返回s的元素个数，即栈的长度。 GetTop (s,&

7、e); 初始条件：栈s已存在且非空。 操作结果：用e返回s的栈顶元素。 Push(&s,e) 初始条件：栈s已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(&s,&e) 初始条件：栈s存在且非空。 操作结果：删除栈顶元素，并用e返回。 stackTraverse(s,visit() 初始条件：栈s存在且非空。 操作结果：从栈底到栈顶依次对s的每个元素调用visit()。一旦visit()失败，则操作失败。ADT Stack（2）、选取对该程序有用的函数。 1、InitStack(&s) 用于构建空栈实现相应的操作； 2、StackEmpty(&s) 用于判断空栈情况，已确保循环体能够准

8、确实现； 3、GetTop (s,&e) 用于取放入栈的栈顶元素，实现把放入的横纵坐标按要求取出； 4、Push(&s,e) 用于将用户输入的横纵坐标放入栈； 5、Pop(&s,&e) 用于实现将要求取出的元素取出；（3）、主要函数及算法说明。 1、函数：void SetRound(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; 再根据GetRound函数来判断是

9、否合法；若合法则返回TRUE,否则返回FALSE. 2、函数：Status GetRound(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) 条件语句判断其合理性，若合理则返回TRUE，否则返回FALSE. 3、语句：for(int i=cur.from+1;i=8;i+) if(GetRound(i,next)&erder

10、next.xnext.y=0) 语句 功能：按照逆时针优先规则，选出下一个可用的位置，通过if判断语句来判断所选的下一步是否可用，若可用，则使其进栈，否则运行下面一个语句。 4、语句：if(!flag) 语句. while(j1) 语句.功能：如果当前位置不存在任何新路径，则根据while循环进行退栈，直至退到存在有最佳位置的坐标。蛋必须保证栈不为空。所以此出栈中设定了int GetDeep的基本操作，就是防止空栈还继续弹东西出来的情况发生。 四、【调试程序】 （1）、问题：语法错误 原因：首次运行语法错误比较多，一般都是由于粗心大意输入有误造成的，还有一些错误属于变量忘记定义之类的，经过认真

11、一个一个调试后这类错误得以解决。下图为第一次运行时的错误 （2）、问题：运行后突然停止程序 原因：可能是输出不恰当 解决：此问题出现后，刚开始不知道为啥，看了很多遍程序就是找不出原由，于是后来请教同学，一起研究后无意中改了输出格式，将printf(%s,%2d ,|,orderij);改成了printf(%d,%f ,orderij,|);竟然成功输出了。怀疑是%s使用得不恰当。 下图为修改前的运行结果：（3）、问题：将上述问题解决后虽然不会出现程序突然终止的情况，但运行结果如下图，输出结果很乱； 原因：输出格式不符 解决：将printf(%d,%f ,orderij,|);改成printf(

12、| %2d ,orderij);（4）、问题：上述问题都搞定后，输入初始坐标后按下Enter键后立即退出了 原因：main()函数里有scanf()，当用户输入初始坐标后，将这两个坐标赋予给&begin.x,&begin.y，结果当用户想用Enter键进行确认操作后，Enter本身是一个字符，而这个字符不符合循环要求，所以直接退出 解决：多加一个getchar()把Enter键给吸收掉，结果如下图：五、【用户手册】 （1）、用户界面，如下图：（2）、按照提示，输入1 2进行数据测试，如下图：（3）、输入y则继续回到主界面，如果输入n则退出系统，如下图：（4）、若在主界面输入x和y不在确定范围，

13、或者输入格式不正确，出现如下图：六、【实验总结与体会】 总结：马踏棋盘，作为一种经典的栈的应用例子，从大方面将，刚看到这名字就知道用栈来实现，但是，当你面对这个题目，打开编译器之后想写的时候，发现又不是那么容易，很多细节需要认真的分析，比如结构体的定义，棋子因为是二维的，所以对于用来存储棋盘的横纵坐标，需要用到两个变量，定义两整型变量x,y。刚开始只定义了这两个变量，后来发现如果找到下一个位置，而下一个位置有很多个都是符合的，如何选取最优的呢？最有的有可能是最先找到的，可找到后还得继续找下去，万一没有比他更优的，则要退回来，如果没有变量from来记录前一位置最优位置，就无法找到之前的点，所以要

14、多加一个变量；其外就是程序的调试，调试确实需要很大的耐心，有时候只是你的大意而输错了字符或输入输出格式不符合就会出现很多看起来不可思议很难发现的错误，这也说明了编程的时候一定要认真有耐心。 体会：刚学习栈的时候，觉得并不太难，反正就是先进后出，可是到了实际运用的时候，才发现学到的理论知识要用到实际去还真是个问题，通过这次课程设计的实践，让我对栈有了更深入的理解，也发现一种理论再简单的知识，如果不实际运用一下，对于你的掌握肯定是不够的，因为实际运用中你要适当选取哪些是有用的，哪些不必用到的，而且当你很兴奋的写完代码后，会发现很多错误，当然一般是语法错误，如果你的逻辑没错的话，也有可能是你思想没错

15、，但你的表达不妥当，这也会让你对程序的修改显得很无助；再次，世上没有完美的程序，如今社会上出现的各个软件每到一定的时候就会有升级版也正是这个原因，我承认自己这个程序存在很多漏洞和不足，但一个程序的优化可不是一朝一夕的事，只要求自己能完成基本任务就行了。 七、【参考文献】 数据结构（C语言版）-严蔚敏、吴伟民 编著 C语言设计（第三版）-谭浩强 著 C语言课程设计（第2版）-梁旭、谷晓琳、黄明 编著 C语言通用范例金典-柳盛，王国全，沈永林 编著八、【程序清单】#include#include#define OK 1#define TRUE 1#define FALSE 0#define ERR

16、OR 0#ifndef STACK_H #define STACK_H/-位置的存储表达方式 typedef struct int x; int y; int from;Point; /-栈的存储表达方式 #define STACKSIZE 70#define STACKINCREASE 10typedef struct Stack Point *top; Point *base; int stacksize;#endif/-栈一一些数据类型操作函数 typedef int Status; Status Initstack(Stack &s)/-构造一个空栈S s.base=(Point*)m

17、alloc(STACKSIZE*sizeof(Point); if(!s.base) return false; s.top=s.base; s.stacksize=STACKSIZE; return OK; Status Push(Stack &s,Point e)/-插入元素 e 为栈顶元素 if(s.top-s.base=s.stacksize) s.base=(Point*)realloc(s.base, (s.stacksize+STACKINCREASE)*sizeof(Point); if(!s.base) return false; s.stacksize+=STACKINCR

18、EASE; s.top=s.base+s.stacksize; (*s.top).x=e.x; (*s.top).y=e.y; (*s.top).from=e.from; s.top+; return OK; Status Pop(Stack &s,Point &e)/-若栈不空，则删除S的栈顶元素 if(s.top=s.base) return false; e.x=(*-s.top).x; e.y=(*s.top).y; e.from=(*s.top).from; return OK; Status DestroyStack(Stack &s)/-销毁栈s,s不再存在 free(s.bas

19、e); Status StackEmpty(Stack s)/-若栈s为空栈，则返回 true,否则返回 false； if(s.base=s.top) return true; else return false; Status GetTop(Stack s,Point &e)/-若栈不空，则取栈顶元素 if(StackEmpty(s) return false; else e.x=(*(s.top-1).x; e.y=(*(s.top-1).y; e.from=(*(s.top-1).from; return true; int GetDeep(Stack s)/-取栈的深度 return

20、(s.top-s.base); Point g_round8=0,0,0; void SetRound(Point cur)/-查找所在位置所有可走位置的坐标，将其赋给 g_round8 Point round= cur.x-2,cur.y+1,0,cur.x-1,cur.y+2,0, cur.x+1,cur.y+2,0,cur.x+2,cur.y+1,0, cur.x+2,cur.y-1,0,cur.x+1,cur.y-2,0, cur.x-1,cur.y-2,0,cur.x-2,cur.y-1,0, ; for(int i=0;i8;i+) g_roundi.x=roundi.x; g_r

21、oundi.y=roundi.y; Status GetRound(int i,Point &pt) pt.x=g_roundi-1.x; pt.y=g_roundi-1.y; if(pt.x0|pt.y7|pt.y7) /-判断合理性 return false; else return true; 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(c

22、olor 2E); printf( =马踏棋盘程序设计演示=nn); printf( 请输入马在棋盘上的初始位置 x 和 y n); printf( （其中 x为17,y也为17;用空格符号隔开;例如：4 7）请输入：); scanf(%d %d,&begin.x,&begin.y); begin.from=0; while(begin.x8|begin.y8|begin.x1|begin.y1) system(cls); printf( =马踏棋盘程序设计演示=nn); printf( 输入有误，按任意键重新输入.nn); getchar(); getchar(); system(cls);

23、 goto H1; getchar(); begin.x-; begin.y-; Initstack(horseVisit); Push(horseVisit,begin); orderbegin.xbegin.y=+count; while(count64) GetTop(horseVisit,cur); SetRound(cur); int flag=false; for(i=cur.from+1;i=8;i+) /-按照逆时针的优先规则，选出下一个可用的新位置 if(GetRound(i,next)&ordernext.xnext.y=0) /-可用位置未曾使用，则进栈，计数器加 1 f

24、lag=true; ordernext.xnext.y=+count; Pop(horseVisit,cur); cur.from=i; Push(horseVisit,cur); next.from=0; Push(horseVisit,next); break; if(!flag) /-如果当前位置周围没有路径，则退栈，直至退到存在有最佳位置的坐标 j=0; if(begin.x=2&begin.y=6) p=4; else p=5; while(j1) Pop(horseVisit,cur); ordercur.xcur.y=0; count-; j+ ; DestroyStack(ho

25、rseVisit); /-完成后销毁栈 printf(n 棋盘表示n); printf( 1 2 3 4 5 6 7 8n) ; printf( +-+-+-+-+-+-+-+-+n); for(i=0;i8;i+) printf( ); printf(%2d,i+1); for(j=0;j8;j+) printf(| %2d ,orderij); printf(|); printf(n); if(i=7) printf( +-+-+-+-+-+-+-+-+); else printf( +-+-+-+-+-+-+-+-+); printf(n); printf( ); printf(你是否需要继续运行改、该程序（y或Y-继续：按其他任意键退出）); scanf(%c,&yn); printf(n); if(yn=y|yn=Y) s=1; else s=0; system(cls); printf(nnnnnnnnn =谢谢使用！=); printf(nnn ); system(pause); system(cls);