马踏棋盘(原创).doc

桂林电子科技大学计算科学与数学学院 数据结构实验报告实验室：06406 实验日期： 2011 年 1 月 3 日院（系）7院年级、专业、班0800710225姓名韦增棵成绩课程名称数据结构实验项目名 称马踏棋盘问题指导教师宁黎华教师评语 教师签名： 年 月 日 一、实验目的1、加深对图的理解，培养解决实际问题的编程能力。2、根据数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来。3、培养基本的、良好的程序设计技能。二、实验内容，1) 给出马从任意一个位置出发遍历整个棋盘的一条路径。2) 在1)的基础上给出从该位置出发的所有遍历路径三、使用仪器，材料电脑，windowx XP + Visual Studio C+ 6.0四、实验方法与步骤1、设计思想：整个棋盘可表示为一个MN的二维数组。假若马目前在位置（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下一个能够到达的邻接结点链表中结点的结构同表头结点的结构同。2、程序代码：#include #include conio.husing namespace std;#define edgetype int#define vextype int#define MAX 8typedef struct nodeint vextex;/序号 struct node *next;edgenode;typedef struct int vextex;int x,y;edgenode *link;vexnode;const int px8=1,2,2,1,-1,-2,-2,-1;const int py8=2,1,-1,-2,-2,-1,1,2;const int L=8,H=8;vexnode gaL*H; /图int visitedL*H=0; /全局地图标志是否走过 typedef struct /*顺序栈的结构体类型定义*/ int stackL*H;int top; seqstack; seqstack s; /全局栈 void setnull(seqstack *s) s-top=-1; /*置空栈-由于c语言的数组下标是从0开始的，所以置空栈操作时将栈顶指针放在下标为0之前，即-1处。*/ int empty(seqstack *s) /*判断当前栈是否为空栈*/ if(s-toptopL*H-1) printf(stack overflow!n); /*发生上溢*/return 0; else s-stack+s-top = x; /*栈顶指针上移，数据元素入栈*/ return 1; int pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ if(s-toptop-; return(s-stacks-top+1); /*由于return语句的特点，必须先使top减1，然后再执行return语句。而此时栈顶元素的表示应该为s-top+1.*/ void init()int n;for (int i=0;iH;i+)for (int j=0;jL;j+)n=L*i+j;gan.vextex=n;gan.x=j;gan.y=i;gan.link=NULL;for (i=0;iL*H;i+) /列出邻接链表edgenode *p;for (int k=0;kMAX;k+)int tx=gai.x+pxk;int ty=gai.y+pyk;if(tx0|ty=L|ty=H) continue; /出界了else /采用前插法p=(edgenode*)malloc(sizeof(edgenode);p-vextex=ty*L+tx;p-next=gai.link;gai.link=p;/printf(%d ,gai.link-vextex);void show() /打印邻接表int i;printf(n);for (i=0;i,gai.vextex);edgenode *p;p=(edgenode*)malloc(sizeof(edgenode);p=gai.link;while (p!=NULL)printf(%d ,p-vextex);p=p-next;printf(n);void showanswer() /打印路径矩形图int rankL*H;int tag=s.top;for (int i=L*H-1;i=0;i-)ranks.stacktag-=i;/rankpop(&s)=i;for (i=0;i,n);push(&s,gan.vextex); /结点入栈p=gan.link;visitedn=1;while (p!=NULL)if (!visitedp-vextex)/printf(%d,p-vextex);/if(HFS(p-vextex) return 1; HFS(p-vextex);p=p-next;if (s.top=L*H-1) /找到路径printf(answer %d:n,sum+); /统计有一点出发的路径个数showanswer();printf(n);/return 1; visiteds.stacks.top=0;pop(&s);if (empty(&s) /没有return 0; return 0; int main()int n;for (n=0;nH*L;n+) /循环查找每个点出发的路径memset(visited,0,sizeof(visited); /初始化visited数组init(); /初始化show(); /打印邻接表setnull(&s); HFS(n); /开始搜索/if (HFS(n) /只输出一个路径时用/printf(nStar From %d:n,n);/ printf(answer:n);/ showanswer();/ / /else printf(nNo Answer!nn);/getch();return 0;五、实验结果分析或总结从第0号格子开始的邻接表为： 从第0出发的路径有上千条，所以这里只列出一些（矩阵元素表示本格子第几步走，从0开始）： 算到第823个答案的时候，我忍不住把程序Kill掉了，实在太多。3、结果分析：程序由于算法的不足，只能计算出从第0格子出发的路径，其他格子出发的路径无法算出来六、总结：通过本次综合实验，