马踏棋盘数据结构报告.docxVIP

数据结构课程设计报告课程设计题目：马踏棋盘姓 名：张程浩院 系：通信工程专 业：信息安全年 级：2011学 号：11225104指导教师：任雪萍2012年 11 月 26 日(任雪萍编写)目 录一、课程设计目的3二、任务分析3三、分析设计3四、调试分析5五、测试结果5六、小结6七、用户手册6八、附录6九、参考文献8一、课程设计目的(1) 熟练使用C语言编写程序，强化模块设计理念；(2) 设计一个国际象棋马踏棋盘的演示程序。(3) 理解栈的特性“后进先出” 和队列的特性“先进先出”。(4) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；二、任务分析（1）要求：在国际象棋88棋盘上面，按照国际象棋规则中马的行进规则，实现从任意初始位置，每个方格只进入一次，走遍棋盘上全部64个方格。编制程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64依次填入一个88的方阵，并输出它的行走路线。（2）输入：任意一个起始位置；输出：无重复踏遍棋盘的结果，以数字1-64表示行走路线。三、分析设计l 需要处理的数据的逻辑结构：线性结构l 合适的存储结构：顺序储存l 设计好的数据类型：#define BS8/棋盘大小typedef int Status; int step; int board88=0; /定义棋盘 int mayway9;/储存可能的路径 int Htry18=-2,-1,1,2,2,1,-1,-2,Htry28=1,2,2,1,-1,-2,-2,-1;/*存储马各个出口位置相对当前位置列下标的增量数组*/typedef struct /位置存储表达方式 int i;/行坐标int j;/列坐标int from; /存储下一步所选方向SElemType;typedef struct SElemType*base;/在栈构造之前和销毁之后，base的值为NULLSElemType*top;/栈顶指针intstacksize;/当前已经分配的储存空间，以元素为单位Stack;Stack Path;l 本程序包含模块：1、主程序模块：void main()定义变量；接受命令；处理命令；退出；输入的初始位置是否正确主程序模块起始坐标函数模块探寻路径函数模块 结束输出路径函数模块块 是否2、起始坐标函数模块马儿在棋盘上的起始位置；3、探寻路径函数模块马儿每个方向进行尝试，直到试完整个棋盘；4、输出路径函数模块输出马儿行走的路径； 各模块之间的调用关系： l 与功能对应的模块划分定义：/构造一个空栈SStatus InitStack(Stack &s);/若栈不空，则用e返回s的栈顶元素，返回OK；否则返回ERRORStatus GetTop(Stack s,SElemType &e);/插入元素e为新的栈顶元素Status Push(Stack &s,SElemType e);/若栈不空，则删除s的栈顶元素，并用e返回其值，并返回OK；否则返回ERRORStatus Pop(Stack &s,SElemType &e);/从栈底到栈顶依次对栈中每个元素输出。Status StackTraverse(Stack s);/若当前坐标在有效棋盘内返回OK；否则返回ERRORStatus InBoard(int i,int j);/贪心法判断下一步的可能选位置，并把可选的最佳位置依次存入mayway，并返回OK；/若找不到位置返回ERRORStatus TryPath(SElemType s, int mayway);Status NextPath(SElemType &cur,int mayway);l 函数调用关系： 四、调试分析1、调试中的问题（1）调试问题：本程序设计过程中采用多文件组件工程的方式进行。在头文件中定义了全局变量，解决方案：将全局变量 定义为staic型变量。或者在声明中使用extern关键字（2）调试问题：虽然编译都能通过，但是运行时却出错，程序不能终止，只有通过人工方式结束程序，可能是在某些地方出现了无限死循环了，马儿回溯的时候，下一次又有可能走那个方向，这样就出现了死循环。解决方案：标记马儿选择的方向director。在结点结构设计上加入director（3）调试问题：在调试过程中，对变量的监视发现栈顶元素中director无法更新，我原本的程序代码设计是cur. director= k解决方案：(Path.top-1)-from=k;/保存下一步 所选最佳路径 下标（4）调试问题：当走到边界时，有可走的路，但是程序却回溯了。解决方案：for (int k = 1+direction; k 9, k = s.stacksize)s.base = (SElemType*)realloc(s.base, (s.stacksize+ STACKINCREMENT) *sizeof(SElemType) );if (!s.base)exit(OVERFLOW);s.top= s.base+ s.stacksize;s.stacksize += STACKINCREMENT;*s.top+= e;return OK;Status Pop(Stack &s,SElemType &e)/若栈不空，则删除s的栈顶元素，并用e返回其值，并返回OK；否则返回ERRORif(s.top = s.base)return ERROR;e = * -s.top;return OK;Status StackTraverse(Stack s)/从栈底到栈顶依次对栈中每个元素输出。int x,y;cout开始s.base)x=s.base-i;y=s.base-j; cout(x,y);s.base+;cout结束=0 & i=0 & j=7 )return OK;elsereturn ERROR;Status TryPath(SElemType s, int mayway)/贪心法判断下一步的可能选位置，并把可选的最佳位置依次存入mayway，并返回OK；/若找不到位置返回ERRORint choices,count=0;int stepchoices9=10,10,10,10,10,10,10,10,10;/储存第二步后的可能路径数,初始化为9int ni=s.i;int nj=s.j;int i,t;for ( i = 1; i = 8; i+)maywayi=i-1;for (int k=0; k8; k+) int find=0;if( InBoard( (ni+Htry1k),(nj+Htry2k) ) &( board ni+Htry1k nj+Htry2k =0) ) /第一步成功choices=9;for (int h=0; h8; h+) if( InBoard( (ni+Htry1k+Htry1h),(nj+Htry2k+Htry2h) ) &( board ni+Htry1k+Htry1h nj+Htry2k+Htry2h =0) )/第二步仍满足if (choices=9)/第一步成功后，第一次 第二步仍成功choices=0;find=1;choices+;/累积第二步的路径数if (BS*BS-1 = step)/若为最后一步，无贪心法第二步stepchoicesk+1=0;count+;elsestepchoicesk+1=choices;/第二步后的可走路径数存入stepchoices8if (find)count+;mayway0=count;/*贪心法全部计算后，对路径数进行排序*/for( i=1;i=9;i+)/冒泡排序 /根据可走路径数由小到大排序将 走法存入数组mayway8for(int m=1;mstepchoicesm+1)t=stepchoicesm;/可走路径数进行排序stepchoicesm=stepchoicesm+1;stepchoicesm+1=t;t=maywaym;/可走路径进行排序maywaym=maywaym+1;maywaym+1=t;return OK;Status NextPath(SElemType &cur,int mayway)/贪心法寻找可行路径int direction=cur.from;/初始位置尝试的位置方向设为-1SElemType p;for (int k = 1+direction; k 9, k from=k;/保存下一步 所选最佳路径 下标/Path.top-1cur.from= k p.i=xt;p.j=yt;p.from=0;Push(Path,p); return OK;return ERROR;void main()SElemType origin,pope,cur;/起点元素int curx,cury;/初始位置 x行坐标，y列坐标/int mayway9;/储存可能的路径step=0;InitStack(Path);H1:cout请输入马的起始位置坐标（x,y）0x7 0y7，中间用空格隔开，例如（2，3）请输入： 2 3curxcury;if (curx8|cury8)cout输入错误，请重新输入！endl;goto H1;origin.i=curx;origin.j=cury;origin.from=0;/初始位置尝试的位置方向设为0boardcurxcury=+step;Push(Path,origin);while (step64)GetTop(Path,cur);TryPath(cur,mayway);/贪心法寻找可行路径if (!NextPath(cur,mayway)StackTraverse(Path);boardcur.icur.j=0;/清除棋盘的标记step-;/回溯if( !Pop(Path,pope) )/退栈，若栈为空，无路可走cout无法找到可走路径，请重新开始！endl;goto H1;printf( 0 1 2 3 4 5 6 7n) ;printf( +-+-+-+-+-+-+-+-+n);for(int i=0;i8;i+) printf( ); printf(%2d,i); for(