数据结构实验五——马踏棋盘问题

桂林电子科技大学数学与计算科学学院综合性、设计性实验报告实验室：06303实验日期：2014年7月1日院（系）数学与计算科学年级专业、班12007301姓名成绩课程名称数据结构实验实验项目名称马踏棋盘问题指导教师张慧敏教师评语教师签名：年月日一、实验目的和要求加深对图的理解，培养解决实际问题的编程能力。根据数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来，培养基本的、良好的程序设计技能。2、马踏棋盘的问题描述国际象棋马的走法：先直走或横走一格，再沿离开原来格子的方向斜走二格，合起来为一步棋；国际象棋棋盘黑白交错，格数8×8。3、基本要求1)给出马从任意一个位置出发遍历整个棋盘的一条路径。2)在1)的基础上给出从该位置出发的所有遍历路径4、设计思想整个棋盘可表示为一个M×N的二维数组。假若马目前在位置（i,j）则马下一步可移动的位置0、1、……、7可分别表示为(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)。当然，这些位置一定在棋盘边界以内（保证下一步移动位置坐标（i，j）,有0iM+1,0jN+1）。格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域指向该顶点所能到达的第一个结点。表头结点：VexxylinkVex:头结点所在的序号x:头结点所在的横坐标；y:头结点所在的纵坐标；link:指向Vex下一个能够到达的邻接结点链表中结点的结构同表头结点的结构同。在此不一一赘述了；假定我们按照以下方式对棋盘上的格子进行编号（如红色标注），那么编号与格子所在的坐标（如蓝色标注）位置必然存在一定关系。（留给大家思考）21（1，5）22（2，5）23（3，5）24（4，5）25（5，5）16（1，4）17（2，4）18（3，4）19（4，4）20（5，4）11（1，3）12（2，3）13（3，3）14（4，3）15（5，3）6（1，2）7（2，2）8（3，2）9（4，2）10（5，2）1（1，1）2（2，1）3（3，1）4（4，1）5（5，1）综合起来，马踏棋盘问题就可以转化为图的遍历问题。5、算法设计#includestdio.h#includestdlib.h#definen8#definemaxsize100typedefintelemtype;typedefstruct/*栈的结构*/{elemtypedata[maxsize];inttop;}stack;typedefstructnode{intvex;/*头结点所在的序号*/structnode*next;/*边表结点*/}edgenode;typedefstruct{intx,y;intvex;//顶点信息edgenode*link;//指向Vex下一个能够到达的邻接结点}vexnode;/*顶点表结点*/vexnodega[n*n];intvisited[n*n];stacks;intpx[8]={1,2,2,1,-1,-2,-2,-1};intpy[8]={2,1,-1,-2,-2,-1,1,2};voidcreatadjlist(vexnodeg[])/*创建无向图的邻链表*/{inti,j,k;edgenode*s;for(i=0;in;i++)//读入顶点信息for(j=0;jn;j++){g[n*i+j].x=j;g[n*i+j].y=i;g[n*i+j].vex=n*i+j;g[n*i+j].link=NULL;//边表头指针初始化}for(k=0;kn*n;k++)//建立边表{for(i=0;i8;i++)if((g[k].x+px[i]=0)&&(g[k].x+px[i]n)&&(g[k].y+py[i]=0)&&(g[k].y+py[i]n)){s=malloc(sizeof(edgenode));s-vex=n*(g[k].y+py[i])+g[k].x+px[i];s-next=g[k].link;g[k].link=s;}}}intemptystack(stack*s)//判空栈{if(s-top==-1)return1;elsereturn0;}intpush_stack(stack*s,elemtypex)//把元素x压入栈中{if(s-top==maxsize-1){printf(overflow!);//栈满上溢return0;}elses-data[++s-top]=x;//栈顶指针上移，数据元素入栈return1;}elemtypepop_stack(stack*s)//弹出当前栈s的栈顶元素{if(emptystack(s))return-1;elsereturns-data[s-top--];}voidclear_stack(stack*s){s-top=-1;}voidprintlist(stack*s){inti;for(i=0;i=s-top;i++)printf(%d,s-data[i]);}intdfs(intvex)/*深度优先搜索遍历*/{intx;//此处暂时屏蔽edgenode*p;visited[vex]=1;printf(+%d,vex);push_stack(&s,vex);p=ga[vex].link;while(p){if(!visited[p-vex]){visited[p-vex]=1;dfs(p-vex);}p=p-next;}if(s.top==n*n-1)return1;if(emptystack(&s))return0;x=pop_stack(&s);visited[x]=0;return0;}voidclear_vflag(){inti;for(i=0;in*n;i++)visited[i]=0;}intmain(){inti;intk=0;edgenode*p;clear_stack(&s);for(i=0;in*n;i++)visited[i]=0;creatadjlist(ga);for(i=0;in*n;i++){printf(%d-,ga[i].vex);p=ga[i].link;while(p!=NULL){printf(%d,p-vex);p=p-next;}printf(\n);}for(i=0;in*n;i++){if(dfs(i)){printf(form%d:,i);printlist(&s);printf(\n);clear_stack(&s);clear_vflag();}//elseprintf(form%d:error!\n,i);printlist(&s);}return0;}/*主函数*/二、实验总结：本次实验需要搜集相关的资料才能完成。注重对遍历的理解与应用，要付出一定的时间与耐心。