文档介绍：桂林电子科技大学
计算科学与数学学院《数据结构》实验报告
实验室:06406 实验日期: 2011 年 1 月 3 日
院(系)
7院
年级、专业、班
0800710225
姓名
韦增棵
成绩
课程
名称
数据结构
实验项目
名称
马踏棋盘问题
指导
教师
宁黎华
教师
评语
教师签名:
年月日
一、实验目的
1、加深对图的理解,培养解决实际问题的编程能力。
2、根据数据对象的特性,学会数据组织的方法,把现实世界中的实际问题在计算机内部表示出来。
3、培养基本的、良好的程序设计技能。
二、实验内容,
1) 给出马从任意一个位置出发遍历整个棋盘的一条路径。
2) 在1)的基础上给出从该位置出发的所有遍历路径
三、使用仪器,材料
电脑,windowx XP + Visual Studio C++
四、实验方法与步骤
1、设计思想:
整个棋盘可表示为一个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),有0<i<M+1,0<j<N+1)。
格子具有集合性,故考虑使用无向图来表示格子及其间关系;以邻接表作为该无向图中结点与相邻8个结点(4黑4白)的存储结构;以顶点表存储格子,每格为顶点表中一结点,其指针域指向该顶点所能到达的第一个结点。
表头结点:
Vex
x
y
link
Vex:头结点所在的序号
x:头结点所在的横坐标;
y:头结点所在的纵坐标;
link:指向Vex下一个能够到达的邻接结点
链表中结点的结构同表头结点的结构同。
2、程序代码:
#include <iostream>
#include ""
using namespace std;
#define edgetype int
#define vextype int
#define MAX 8
typedef struct node
{
int vextex;//序号
struct node *next;
}edgenode;
typedef struct
{
int vextex;
int x,y;
edgenode *link;
}vexnode;
const int px[8]={1,2,2,1,-1,-2,-2,-1};
const int py[8]={2,1,-1,-2,-2,-1,1,2};
const int L=8,H=8;
vexnode ga[L*H]; //图
int visited[L*H]={0}; //全局地图标志是否走过
typedef struct /*顺序栈的结构体类型定义*/
{
int stack[L*H];
int top;
}seqstack;
seqstack s; //全局栈
void setnull(seqstack *s)
{s->top=-1;}