数据结构笔记（一）

今天花了很多时间去实现学校布置的作业，所以我突然想到我是否可以将这些经历写到网络上，以便更好的分享出去

本次实现的具体内容是：用C语言实现邻接矩阵存储的无向图，判断是否为连通图，并且实现最小生成树Prim算法

（引用的话不重要）在此之前已经有过一段开发基础了，但大部分都是用C++和其他语言，而用C语言很少，主要原因是其太灵活并且自身觉得困难，努力完成了上述内容后，我忽然发现其实也还好，无非就是需要思考的事情多了。

参考上述要求，我使用了并查集实现图是否为连通图，使用了堆排序（优先队列）实现了Prim算法。其实这些在C++当中很简单，但是使用C语言就很麻烦，需要手动实现。具体整体逻辑如下

1. 无向图部分

使用结构体定义
其中有很多实现方法。其中最核心的是UG_IsConnectedGraph()是否为连通图、UG_GetMST()获取最小生成树。这俩分别使用到了并查集与堆排序。下方是无向图部分代码，并查集和堆排序在后面

/*以下无向图定义*/
const int INF = 1e9; //代表邻接表未连接
struct UG { //无向带权图 Undirected Graph
	int n;//元素个数
	int* s; //邻接矩阵，动态创建
};
typedef UG* UGPoi;

UGPoi UG_Init(int n);//创建无向图
void UG_Link(UGPoi ug, int p, int q, int val);//将两条边连接起来
void UG_PrintGraph(UGPoi ug);//打印图（邻接矩阵）
bool UG_IsConnectedGraph(UGPoi ug);//是否是连通图
UGPoi UG_GetMST(UGPoi ug);//获取最小生成树
struct __UG_HeapNode { //UG_GetMST()函数中需使用到的类型
        //边长，目标结点，原始节点
	int len, poi, fro; 
};
void* __UG_getheapnode(int fro, int poi, int len);//创建__UG_HeapNode结构体
bool __UG_heapcompare(void* a, void* b);//堆排序比较函数




/*其中实现如下*/
UGPoi UG_Init(int n) {
	//申请UG结构体内存
	UGPoi ug = (UGPoi)malloc(sizeof(UG));
	//为s创建n*n的邻接矩阵空间
	ug->s = (int*)malloc(sizeof(int) * n * n);
	for (int i = 0;i < n;i++)for (int j = 0;j < n;j++)
		ug->s[i * n + j] = INF;
	for (int i = 0;i < n;i++)ug->s[i * n + i] = 0;
	ug->n = n;
	return ug;
}
void UG_Link(UGPoi ug, int p, int q, int val) {
	p--;q--;
	ug->s[p * ug->n + q] = val;
	ug->s[q * ug->n + p] = val;
}
void UG_PrintGraph(UGPoi ug) {
	printf("(∞表示没有连接)\n");
	int n = ug->n;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (ug->s[i * n + j] == INF) printf(" ∞ ");
			else  printf("%3d ", ug->s[i * n + j]);
		}
		printf("\n");
	}
}
bool UG_IsConnectedGraph(UGPoi ug) {
	//使用并查集来判断是否为连通图
	int n = ug->n;
	int rest = n;
	int* uf = UnionFind_Init(n);
	for (int i = 0;i < n;i++)
		for (int j = i + 1;j < n;j++)
			if (ug->s[i * n + j] != INF && 
				UnionFind_Find(uf, i+1)!=UnionFind_Find(uf, j+1)
			) {
				UnionFind_Union(uf, i + 1, j + 1);
				rest--;
			}
	if (rest == 1)return 1;
	else return 0;
}
UGPoi UG_GetMST(UGPoi ug) {
	//使用优先队列存放Prim遍历到的结点，每次取出最小的。优先队列使用堆实现
	int n = ug->n;
	UGPoi res = UG_Init(n);
	//创建堆，堆的最大大小与比较函数传进去
	HeapPoi heap = Heap_Init(n * n, sizeof(__UG_HeapNode), __UG_heapcompare);
	//是否已遍历到
	int* isok = (int*)malloc(sizeof(int) * n);
	memset(isok, 0, sizeof(int) * n);
	Heap_Ins(heap, __UG_getheapnode(0, 0, 0));
	while (!Heap_Empty(heap)) {
		__UG_HeapNode* t = (__UG_HeapNode*)malloc(sizeof(__UG_HeapNode));
		memcpy(t, Heap_Top(heap), sizeof(__UG_HeapNode));
		Heap_Pop(heap);

		//如果该节点已经遍历过了，跳过
		if (isok[t->poi])continue;
		isok[t->poi] = 1; //如果没有遍历过，将其设为已遍历，防止后续循环遍历到

		//将其该边加入到res结果当中
		UG_Link(res, t->fro+1, t->poi+1 , t->len);
		
		//找与之相邻的结点，将其加入堆当中
		for (int i = 0;i < n;i++) {
			if (i == t->poi) continue;
			if (ug->s[t->poi * n + i] != INF && isok[i] == 0) {
				__UG_HeapNode* readyins = (__UG_HeapNode*)__UG_getheapnode(t->poi, i, ug->s[t->poi * n + i]);
				Heap_Ins(heap, readyins);
			}
		}
	}
	return res;
}
void* __UG_getheapnode(int fro, int poi, int len) {
	__UG_HeapNode* res = (__UG_HeapNode*)malloc(sizeof(__UG_HeapNode));
	res->len = len;
	res->poi = poi;
	res->fro = fro;
	return (void*)res;
}
bool __UG_heapcompare(void* a, void* b) {
	int p = ((__UG_HeapNode*)a)->len;
	int q = ((__UG_HeapNode*)b)->len;
	return p < q;
}

2. 并查集部分

在无向图中，UG_IsConnectedGraph()函数中使用到了并查集，代码如下

/*以下为并查集定义*/
int* UnionFind_Init(int n); //创建森林，返回森林首指针
int UnionFind_Find(int* s, int n); //Find查找
void UnionFind_Union(int* s, int a, int b); //Union合并

/*以下为并查集实现*/
int* UnionFind_Init(int n) {
	int* s = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 0;i <= n;i++) {
		s[i] = i;
	}
	return s;
}
int UnionFind_Find(int *s, int n) {
	if (s[n] != n)return s[n] = UnionFind_Find(s,s[n]);
	return n;
}
void UnionFind_Union(int *s, int a, int b) {
	if (UnionFind_Find(s,a) != UnionFind_Find(s,b)) {
		s[UnionFind_Find(s,a)] = UnionFind_Find(s,b);
	}
}

3. 堆排序部分

在无向图中，UG_GetMST()函数中使用到了堆排序，代码如下

/*以下为堆定义*/
struct Heap {
	int n; //堆中元素数量
	void* s;//堆数据元素，使用预先申请好的内存线性存储
	bool (*compare)(void* a, void* b);//堆数据元素比较函数
	int node_size;//堆数据元素类型字节大小
};
typedef Heap* HeapPoi;
//初始化堆。需填好可能使用的最大数量、数据元素类型字节大小、数据元素比较函数
HeapPoi Heap_Init(int n, int node_size, bool(*compare)(void* a, void* b)); 
void Heap_Ins(HeapPoi h, void* v);//向堆中添加元素并自动排序
void* Heap_Top(HeapPoi h);//取堆顶
void Heap_Pop(HeapPoi h);//弹出堆顶，并自动排序
bool Heap_Empty(HeapPoi h);//堆是否为空
void* __Heap_getattr(HeapPoi h, int shifting);//取堆中第shifting个数据元素，相当于偏移量
void __Heap_swap(HeapPoi h, int a, int b);//交换两个数据元素


/*以下为堆实现*/
void* __Heap_getattr(HeapPoi h, int shifting) {
	return (void*)((char*)h->s + shifting * h->node_size);
}
void __Heap_swap(HeapPoi h, int a, int b) {
	void* t = malloc(h->node_size);
	memcpy(t, __Heap_getattr(h, a), h->node_size);
	memcpy(__Heap_getattr(h, a), __Heap_getattr(h, b), h->node_size);
	memcpy(__Heap_getattr(h, b), t, h->node_size);
}
HeapPoi Heap_Init(int n, int node_size, bool(*compare)(void *a,void *b)) {
	HeapPoi h = (HeapPoi)malloc(sizeof(Heap));
	h->compare = compare;
	h->s = (void*)malloc(node_size * n);
	h->node_size = node_size;
	h->n = 0;
	return h;
}
void Heap_Ins(HeapPoi h, void* v) {
	memcpy(__Heap_getattr(h, h->n), v, h->node_size);
	h->n++;
	int p = h->n - 1;
	while (p > 0) {
		//获取到 p的双亲结点
		int f = (p & 1) ? p / 2 : (p - 1) / 2;
		//判断s[p]是否不小于s[f]，如果是break
		if (!h->compare(__Heap_getattr(h, p), __Heap_getattr(h, f))) break;
		//将s[p]和s[f]交换
		__Heap_swap(h, p, f);
		p = f;
	}
}
void* Heap_Top(HeapPoi h){
	return __Heap_getattr(h, 0);
}
void Heap_Pop(HeapPoi h) {
	h->n--;
	if (h->n == 0)return;
	//将s[0]替换为s[n]
	memcpy(__Heap_getattr(h, 0), __Heap_getattr(h, h->n), h->node_size);
	int p = 0;
	while (1) {
		int son = -1;
		if (p * 2 + 1 < h->n) son = p * 2 + 1;
		if (p * 2 + 2 < h->n && h->compare(__Heap_getattr(h, p*2+2), __Heap_getattr(h, son) ) ) {
			son = p * 2 + 2;
		}
		if (son == -1 || h->compare(__Heap_getattr(h, p), __Heap_getattr(h, son)))break;
		__Heap_swap(h, son, p);
		p = son;
	}
}
bool Heap_Empty(HeapPoi h) {
	return h->n == 0;
}