C语言图结构总结（一）

typedef char[4] Vertex;// 顶点信息
typedef int Weight;// 权重
typedef int Number;// 数值类

typedef Weight** Matrix;// 矩阵
typedef struct GMatrix {// 邻接矩阵存储结构
	Vertex* data;// 一维数组存放顶点信息
	Number n;// 顶点数
	Matrix M;// 二维数组
};

typedef struct UGLBox {// 无权邻接表项
	Number v;//Vertex 顶点索引
	UGLBox* next;// 指向下一无权表项
};
typedef struct WGLBox {// 有权邻接表项
	Number v;//Vertex 顶点索引
	Weight w;
	WGLBox* next;// 指向下一有权表项
};
typedef struct GLHead {// 邻接列表头
	Vertex data;// 顶点名称
	void* B;//Box 表项
};
typedef struct GList {// 邻接列表存储结构
	Number len;// 表长
	GLHead* Head;// 指向表头数组
};

typedef struct GOBox {// 十字链表项
	Number tailV;
	Number headV;
	GOBox* tail;
	GOBox* head;
};
typedef struct GOHead {// 十字链表头
	Vertex data;
	GOBox* tail;
	GOBox* head;
};
typedef struct GOList {// 十字链表存储结构
	Number len;
	GOHead* Head;
};

typedef struct GMBox {
	Number tailV;
	GMBox* tail;
	Number headV;
	GMBox* head;
};
typedef struct GMHead {
	Vertex data;
	GMBox* first;
};
typedef struct GMList {
	Number len;
	GMHead* Head;
};

typedef struct Edge {
	Number begin;
	Number end;
	Weight w;
};
typedef struct Edges {
	Number len;
	Vertex* v;
	Edge* e;
};

typedef struct UEdge {// 无权边
	Number t;//tailVertex
	Number h;//headVertex
};
typedef struct WEdge {// 有权边
	Number t;//tailVertex
	Number h;//headVertex
	Weight w;
};
typedef struct GInput {// 图输入
	Vertex* data;// 顶点
	Number n;// 顶点数
	void* Edges;// 边的关系
	Number len;// 边的关系的数量
};

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define X 8
#define Y 8

int chess[Y][X];
int Tag;// 遍历顺序
bool isFind;
int solveCount;

// 定义两个数据结构，分别用来存放坐标信息和权值信息
typedef struct xybox {
	int x;
	int y;
};
typedef struct weightbox {
	int len;
	xybox xy[8];
	int w[8];
};
// 下一个可能跳的坐标
inline xybox nextxy(int x,int y,int count,xybox* data) {
	xybox xy;
	xy.x = x + data[count].x;
	xy.y = y + data[count].y;
	return xy;
}
// 建立马跳的格子的增量数据，总共 8 种情况 返回指针指向 xybox [8]
xybox* buildData() {
	int i;
	xybox* data = (xybox*)malloc(8 * sizeof(xybox));
	data[0].x = -1;data[0].y = -2;
	data[1].x = 1; data[1].y = -2;
	//y=x 镜像处理
	for (i = 2; i < 4; i++) {
		data[i].x = data[i - 2].y;
		data[i].y = data[i - 2].x;
	}
	//y=-x 镜像处理
	for (i = 4; i < 8; i++) {
		data[i].x = -data[i - 4].y;
		data[i].y = -data[i - 4].x;
	}
	return data;
}
// 遍历棋盘，深度优先，使用贪心算法优化
bool traverse(int x,int y,xybox* data) {
	if (Tag == X * Y) {
		// 找到解，输出
		isFind = true;// 已找到解
		printf("第%d个解：\n", ++solveCount);
		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				printf("%d\t", chess[i][j]);
			}
			printf("\n");
		}
		return false;
	}
	int i;
	xybox xy;
	weightbox weight;
	bool flag = 1;
	weight.len = 0;
	for (i = 0; i < 8; i++) {
		xy = nextxy(x, y, i, data);
		if (xy.x<0 || xy.x>=X || xy.y<0 || xy.y>=Y || chess[xy.y][xy.x]) {
			// 超出边界或已被遍历，下次循环
			continue;
		}
		else {
			// 否则标记，并继续递归
			weight.xy[weight.len++] = { xy.x,xy.y };
			flag = 0;
			chess[xy.y][xy.x] = ++Tag;
			xybox xytmp;
			// 模拟下一次遍历，并将遍历后可走格子数记为权重存入权重数组
			for (int i = 0; i < 8; i++) {
				xytmp = nextxy(xy.x, xy.y, i, data);
				if (xytmp.x < 0 || xytmp.x >= X || xytmp.y < 0 || xytmp.y >= Y || chess[xytmp.y][xytmp.x]) {
					// 超出边界或已被遍历，下次循环
					continue;
				}
				else {
					weight.w[weight.len - 1]++;
				}
			}
			chess[xy.y][xy.x] = 0;
			Tag--;
		}
	}
	if (flag) {
		// 遍历失败，回溯
		return false;
	}
	// 按权值从小到大排序
	int min, minIdx, j;
	for (i = 0; i < weight.len; i++) {
		min = weight.w[i]; minIdx = i;
		for (j = i + 1; j < weight.len; j++) {
			if (min < weight.w[j]) { min = weight.w[j]; minIdx = j; }
		}
		xybox tmp = weight.xy[i];
		int tmp2 = weight.w[i];
		weight.xy[i] = weight.xy[minIdx];
		weight.w[i] = weight.w[minIdx];
		weight.xy[minIdx] = tmp;
		weight.w[minIdx] = tmp2;
	}
	// 依次遍历（贪心算法）
	flag = 0;
	for (i = 0; i < weight.len; i++) {
		chess[weight.xy[i].y][weight.xy[i].x] = ++Tag;
		if (!traverse(weight.xy[i].x, weight.xy[i].y, data)) {
			chess[weight.xy[i].y][weight.xy[i].x] = 0;
			Tag--;
			flag = 1;
		}
	}
	if (flag) {
		// 遍历失败，回溯
		return false;
	}
	return true;
}
int main() {
	xybox* data = buildData();
	// 这边数组输入 X 和 Y 是反过来的 chess [Y][X]
	chess[0][0] = ++Tag;
	if (!traverse(0, 0, data)) {
		printf("算法失败！\n");
	}
	free(data);
	return 0;
}