第七次实验马踏棋盘问题

1、桂林电子科技大学数学与计算科学学院综合性、设计性实验报告实验室：06406 实验日期：2015年 05月 29日院（系）信息与计算科学系年级、专业、班1300710226姓名庞文正成绩课程名称数据结构实验实验项目名 称马踏棋盘问题指导教师教师评语 教师签名： 年 月 日 一 ，实验目的加深对图的理解，培养解决实际问题的编程能力。根据数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来，培养基本的、良好的程序设计技能。二，实验原理整个棋盘可表示为一个M×N的二维数组。假若马目前在位置（i,j）则马下一步可移动的位置0、1、7可分别表示为(i-2,j+1),(i

2、-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）,有0<i<M+1,0<j<N+1）。格子具有集合性，故考虑使用无向图来表示格子及其间关系；以邻接表作为该无向图中结点与相邻8个结点（4黑4白）的存储结构；以顶点表存储格子，每格为顶点表中一结点，其指针域指向该顶点所能到达的第一个结点。表头结点：VexxylinkVex:头结点所在的序号x:头结点所在的横坐标；y:头结点所在的纵坐标；link:指向Vex下一个能够到达

3、的邻接结点链表中结点的结构同表头结点的结构同。在此不一一赘述了；假定我们按照以下方式对棋盘上的格子进行编号（如红色标注），那么编号与格子所在的坐标（如蓝色标注）位置必然存在一定关系。（留给大家思考）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）综合起来，马踏棋盘问题就可以转化为图的遍历问题。三，使用仪器，材料XP

4、系统电脑一台，vc+软件！四，实验内容与步骤#include<stdio.h>#include<stdlib.h>typedef structint x;int y; /棋盘上的坐标 Coordinate;int chessboard88; /棋盘 int curstep; /马跳的步骤序号 Coordinate fangxiang8= /马可走的方向 -2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1; void Move(Coordinate curpos) /马踏棋盘算法 Coordinate next;int i,j;if(curpo

5、s.x<0|curpos.x>7|curpos.y<0|curpos.y>7) /判断越界return ;if(chessboardcurpos.xcurpos.y) /如果已走过，直接返回return ;chessboardcurpos.xcurpos.y=curstep; /保存步骤数 curstep+;if(curstep>64) /棋盘位置都走完了for(i=0;i<8;i+) /输出走法 for(j=0;j<8;j+)printf("%5d",chessboardij);printf("n");exit

6、(0);else /棋盘位置没走完for(i=0;i<8;i+)next.x=curpos.x+fangxiangi.x;next.y=curpos.y+fangxiangi.y;if(curpos.x<0|curpos.x>7|curpos.y<0|curpos.y>7) /如果越界，不做任何处理else /否则进行移动 Move(next); chessboardcurpos.xcurpos.y=0; /清除步数序号curstep-; /减少步数 void main()int i,j;Coordinate start;printf("马踏棋盘求解！n

7、");printf("请输入马的一个起始位置（x,y）：");scanf("%d%d",&start.x,&start.y);for(;)if(start.x<1|start.x>8|start.y<1|start.y>8) /判断输入值是否越界 printf("输入数值越界，请重新输入！n"); scanf("%d%d",&start.x,&start.y); else break; for(i=0;i<8;i+) /初始化棋盘个单元位置 for(j=0;j<8;j+)c