高级数据结构

前言

教程来自B站的《算法导论》，算是中间部分。

但是感觉学完这一段，作用不大…有点鸡肋，希望优质思想能沉淀在脑海里。

好吧，一个优秀的数据结构能很好的解决一个算法查找数据的麻烦，甚至决定了一个算法的时间复杂度

哈希表

链接法

//链接法
//除法哈希函数
int hash(int k, int m)
{
	return k % m;
}

//初始化除法哈希表
node** Division_Hash_Init(int m, int *n, int num)
{
	node** T;
	T = (node**)malloc(m * sizeof(node*));
	for (int i = 0; i < m; i++)
	{
		*(T + i) = NULL;
	}
	for (int i = 0; i < num; i++)
	{
		int k = hash(n[i], m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = n[i];
		p->next = T[k];
		T[k] = p;
	}
	return T;
}

//查找值
bool Division_Hash_Search(node** T, int m, int x)
{
	bool flag = 0;
	int k = hash(x, m);
	node* p;
	p = T[k];
	while (p != NULL)
	{
		if (p->element == x)
		{
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	return flag;
}

//插入值
void Division_Hash_Insert(node** T, int m, int x)
{
	if (Division_Hash_Search(T, m, x))
	{
		printf("%d 在哈希表中\n", x);
	}
	else
	{
		int k = hash(x, m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = x;
		p->next = T[k];
		T[k] = p;
	}
}

//删除值
void Division_Hash_Delete(node** T, int m, int x)
{
	bool flag = 0;
	int k = hash(x, m);
	node* p;
	p = T[k];
	while (p != NULL)
	{
		if (p->element == x)
		{
			if (p == T[k])
			{
				T[k] = p->next;
				free(p);
			}
			else
			{
				node* q;
				q = T[k];
				while (q->next != p)
				{
					q = q->next;
				}
				q->next = p->next;
				free(p);
			}
			
			printf("%d在哈希表中已被删除\n", x);
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	if (!flag)
	{
		printf("%d不在哈希表中\n", x);
	}

}

全域哈希

//全域哈希函数
typedef struct Universal_Hashing_Table
{
	int m;
	int a;
	int b;
	int prime;
	node** S;
};

// 全域哈希函数
int universal_hash(int x, int a, int b, int prime, int m)
{
	return ((a * x + b) % prime) % m;
}

//初始化全域哈希表
Universal_Hashing_Table* Universal_Hash_Init(int m, int* n, int num)
{
	Universal_Hashing_Table* T;
	T = (Universal_Hashing_Table*)malloc(sizeof(Universal_Hashing_Table));
	T->m = m;
	T->prime = find_next_prime(find_array_max(n, num));
	T->a = rand() % T->prime;
	while (T->a == 0)
	{
		T->a = rand() % T->prime;
	}
	T->b = rand() % T->prime;

	printf("哈希函数族的选取有限域的阶p为 %d\n", T->prime);
	printf("随机哈希函数为 h_{%d*x+%d}\n", T->a, T->b);

	T->S = (node**)malloc(m * sizeof(node*));
	for (int i = 0; i < m; i++)
	{
		*(T->S + i) = NULL;
	}

	for (int i = 0; i < num; i++)
	{
		int k = universal_hash(n[i], T->a, T->b, T->prime, T->m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = n[i];
		p->next = *(T->S + k);
		*(T->S + k) = p;
	}
	return T;
}

//查找值
bool Universal_Hash_Search(Universal_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k = universal_hash(x, T->a, T->b, T->prime, T->m);
	node* p;
	p = *(T->S + k);
	while (p != NULL)
	{
		if (p->element == x)
		{
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	return flag;
}

//插入值
void Universal_Hash_Insert(Universal_Hashing_Table* T, int x)
{
	if (Universal_Hash_Search(T, x))
	{
		printf("%d 在哈希表中\n", x);
	}
	else
	{
		int k = universal_hash(x, T->a, T->b, T->prime, T->m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = x;
		p->next = *(T->S + k);
		*(T->S + k) = p;
	}
}

//删除值
void Universal_Hash_Delete(Universal_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k = universal_hash(x, T->a, T->b, T->prime, T->m);
	node* p;
	p = *(T->S + k);
	while (p != NULL)
	{
		if (p->element == x)
		{
			if (p == *(T->S + k))
			{
				*(T->S + k) = p->next;
				free(p);
			}
			else
			{
				node* q;
				q = *(T->S + k);
				while (q->next != p)
				{
					q = q->next;
				}
				q->next = p->next;
				free(p);
			}

			printf("%d在哈希表中已被删除\n", x);
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	if (!flag)
	{
		printf("%d不在哈希表中\n", x);
	}

}

开放寻址哈希

//开放寻址法
typedef struct Open_Addressing_Hashing_Table{
	int m;
	int** S;
	int(*hash_function)(int, int, int);
};

//线性探查函数
int linear_probing(int x, int m, int i)
{
	int m1 = m - 1;
	return ((1 + hash(x, m1)) + i) % m;
}

//二次探查函数
int quadratic_probing(int x, int m, int i)
{
	int c1 = 1;
	int c2 = 1;
	int m1 = m - 1;
	return ((1 + hash(x, m1)) + c1*i + c2*i*i) % m;
}

//双重哈希函数
int double_hash(int x, int m, int i)
{
	int m1 = m - 1;
	int m2 = m - 2;
	return ((1 + hash(x, m1)) + i * (1 + hash(x, m2)) )% m;
}

//查找值
bool Open_Addressing_Hash_Search(Open_Addressing_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k;
	for (int i = 0; i < T->m; i++)
	{
		k = T->hash_function(x, T->m, i);
		if (*(T->S + k) == NULL)
		{
			break;
		}
		if (**(T->S + k) == x)
		{
			flag = 1;
			break;
		}
	}
	return flag;
}

//插入值
void Open_Addressing_Hash_Insert(Open_Addressing_Hashing_Table* T, int x)
{
	int k;
	int i;
	for (i = 0; i < T->m; i++)
	{
		k = T->hash_function(x, T->m, i);
		if (*(T->S + k) == NULL)
		{
			*(T->S + k) = (int*)malloc(sizeof(int));
			**(T->S + k) = x;
			break;
		}
		else if (**(T->S + k) == x)
		{
			printf("%d已在散列表中\n", x);
			break;
		}
		else
		{
			printf("%d在散列表第%d个槽位上，与待插入值%d发生第次%d冲突\n", **(T->S + k), k, x, i + 1);
		}
	}
	if (i == T->m)
	{
		printf("散列表已满\n");
	}
}

//开放寻址哈希表
Open_Addressing_Hashing_Table* Open_Addressing_Hash_Init(int m, int* n, int num, int(*hash_function)(int, int, int))
{
	Open_Addressing_Hashing_Table* T;
	T = (Open_Addressing_Hashing_Table*)malloc(sizeof(Open_Addressing_Hashing_Table));
	T->m = m;
	T->S = (int**)malloc(m * sizeof(int*));
	T->hash_function = hash_function;
	for (int i = 0; i < m; i++)
	{
		*(T->S + i) = NULL;
	}
	for (int i = 0; i < num; i++)
	{
		Open_Addressing_Hash_Insert(T, n[i]);
	}
	return T;
}

//打印开放寻址哈希表
void Print_Open_Addressing_Hash(Open_Addressing_Hashing_Table* T)
{
	for (int i = 0; i < T->m; i++)
	{
		printf("第%d个槽位:", i);
		if (*(T->S + i) != NULL)
		{
			printf("%d  ", **(T->S + i));
		}
		printf("\n");
	}
	printf("\n");
}

//删除开放寻址哈希表
void Delete_Open_Addressing_Hash(Open_Addressing_Hashing_Table* T)
{
	for (int i = 0; i < T->m; i++)
	{
		if (*(T->S + i) != NULL)
		{
			free(*(T->S + i));
		}
	}
	free(T);
	printf("哈希表已删除\n");
}

完全哈希

//完全哈希法
typedef struct Perfect_Hashing_Table
{
	int m;
	int a;
	int b;
	int prime;
	int* mm;
	Universal_Hashing_Table** S;
};

//完全哈希表初始化
Perfect_Hashing_Table* Perfect_Hash_Init(int* n, int num)
{
	Perfect_Hashing_Table* T;
	T = (Perfect_Hashing_Table*)malloc(sizeof(Perfect_Hashing_Table));
	T->mm = (int*)calloc(num, sizeof(int));
	T->S = (Universal_Hashing_Table**)malloc(num * sizeof(Universal_Hashing_Table*));

	T->prime = find_next_prime(find_array_max(n, num));
	T->m = num;
	T->a = (rand() % (T->prime - 1)) + 1;
	while (T->a == 0)
	{
		T->a = rand() % (T->prime - 1);
	}
	T->b = rand() % T->prime;

	printf("完全哈希表选取的一级表有限域的阶p为 %d\n", T->prime);
	printf("完全哈希表选取的一级表哈希函数为 h_{%d*x+%d}\n", T->a, T->b);

	int* n_site;
	n_site = (int*)calloc(num, sizeof(int));
	for (int i = 0; i < num; i++)
	{
		int k;
		k = universal_hash(n[i], T->a, T->b, T->prime, T->m);
		T->mm[k]++;
		n_site[i] = k;
	}
	int** nn;
	nn = (int**)malloc(num * sizeof(int*));
	for (int i = 0; i < T->m; i++)
	{
		if (T->mm[i] != 0)
		{
			*(nn + i) = (int*)malloc(T->mm[i] * sizeof(int));
			for (int k = 0; k < T->mm[i]; k++)
			{
				for (int j = 0; j < T->m; j++)
				{
					if (n_site[j] == i)
					{
						*(*(nn + i) + k) = n[j];
						n_site[j] = -1; // 标记为已处理
						break;
					}
				}
			}
			
		}
		else
		{
			*(nn + i) = NULL;
		}
	}


	for (int i = 0; i < num; i++)
	{
		if (T->mm[i] != 0)
		{
			*(T->S + i) = Universal_Hash_Init(T->mm[i] * T->mm[i], *(nn + i), T->mm[i]);
		}
		else
		{
			*(T->S + i) = NULL;
		}
	}

	free(n_site);
	for (int i = 0; i < T->m; i++)
	{
		if (T->mm[i] != 0)
		{
			free(*(nn + i));
		}
	}
	free(nn);
	return T;
}

//查找值
bool Perfect_Hash_Search(Perfect_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k;
	k = universal_hash(x, T->a, T->b, T->prime, T->m);
	if (T->mm[k] != 0)
	{
		flag = Universal_Hash_Search(*(T->S + k), x);
	}

	return flag;
}

void Print_Perfect_Hash(Perfect_Hashing_Table* T)
{
	printf("完全哈希表选取的一级表\n");
	for (int i = 0; i < T->m; i++)
	{
		printf("完全哈希表选取的第%d个二级表\n", i);
		if (*(T->S + i) != NULL)
		{
			Print_Hash((*(T->S + i))->S, T->mm[i] * T->mm[i]);
		}
		else
		{
			printf("空表\n");
		}
	}
}

void Delete_Perfect_Hash(Perfect_Hashing_Table* T)
{
	for (int i = 0; i < T->m; i++)
	{
		if (*(T->S + i) != NULL)
		{
			Delete_Hash((*(T->S + i))->S, T->mm[i] ^ 2);
			free(*(T->S + i));
		}
	}
	free(T->S);
	free(T);
}

总代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//链表节点
typedef struct node
{
	int element;
	node* next;
}node;

//打印哈希表
void Print_Hash(node** T, int m)
{
	for (int i = 0; i < m; i++)
	{
		node* p;
		p = T[i];
		printf("第%d个槽位:", i);
		while (p != NULL)
		{
			printf("%d  ", p->element);
			p = p->next;
		}
		printf("\n");
	}
	printf("\n");
}

//寻找下一个素数
bool is_prime(int number)
{
	if (number <= 1)
	{
		return 0;
	}

	for (int i = 2; i * i <= number; ++i)
	{
		if (number % i == 0) {
			return 0;
		}
	}

	return 1;
}

int find_next_prime(int max)
{
	while (!is_prime(max))
	{
		max++;
	}
	return max;
}

//删除哈希表
void Delete_Hash(node** T, int m)
{
	for (int i = 0; i < m; i++)
	{
		node* p;
		p = T[i];
		while (p != NULL)
		{
			T[i] = p->next;
			free(p);
			p = T[i];
		}
	}
	free(T);
	printf("哈希表已删除\n");
}

//寻找数组中最大元素
int find_array_max(int* n, int num)
{
	int max = n[0];
	for (int i = 1; i < num; i++)
	{
		if (n[i] > max)
		{
			max = n[i];
		}
	}
	return max;
}


//链接法
//除法哈希函数
int hash(int k, int m)
{
	return k % m;
}

//初始化除法哈希表
node** Division_Hash_Init(int m, int *n, int num)
{
	node** T;
	T = (node**)malloc(m * sizeof(node*));
	for (int i = 0; i < m; i++)
	{
		*(T + i) = NULL;
	}
	for (int i = 0; i < num; i++)
	{
		int k = hash(n[i], m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = n[i];
		p->next = T[k];
		T[k] = p;
	}
	return T;
}

//查找值
bool Division_Hash_Search(node** T, int m, int x)
{
	bool flag = 0;
	int k = hash(x, m);
	node* p;
	p = T[k];
	while (p != NULL)
	{
		if (p->element == x)
		{
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	return flag;
}

//插入值
void Division_Hash_Insert(node** T, int m, int x)
{
	if (Division_Hash_Search(T, m, x))
	{
		printf("%d 在哈希表中\n", x);
	}
	else
	{
		int k = hash(x, m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = x;
		p->next = T[k];
		T[k] = p;
	}
}

//删除值
void Division_Hash_Delete(node** T, int m, int x)
{
	bool flag = 0;
	int k = hash(x, m);
	node* p;
	p = T[k];
	while (p != NULL)
	{
		if (p->element == x)
		{
			if (p == T[k])
			{
				T[k] = p->next;
				free(p);
			}
			else
			{
				node* q;
				q = T[k];
				while (q->next != p)
				{
					q = q->next;
				}
				q->next = p->next;
				free(p);
			}
			
			printf("%d在哈希表中已被删除\n", x);
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	if (!flag)
	{
		printf("%d不在哈希表中\n", x);
	}

}



//全域哈希函数
typedef struct Universal_Hashing_Table
{
	int m;
	int a;
	int b;
	int prime;
	node** S;
};

// 全域哈希函数
int universal_hash(int x, int a, int b, int prime, int m)
{
	return ((a * x + b) % prime) % m;
}

//初始化全域哈希表
Universal_Hashing_Table* Universal_Hash_Init(int m, int* n, int num)
{
	Universal_Hashing_Table* T;
	T = (Universal_Hashing_Table*)malloc(sizeof(Universal_Hashing_Table));
	T->m = m;
	T->prime = find_next_prime(find_array_max(n, num));
	T->a = rand() % T->prime;
	while (T->a == 0)
	{
		T->a = rand() % T->prime;
	}
	T->b = rand() % T->prime;

	printf("哈希函数族的选取有限域的阶p为 %d\n", T->prime);
	printf("随机哈希函数为 h_{%d*x+%d}\n", T->a, T->b);

	T->S = (node**)malloc(m * sizeof(node*));
	for (int i = 0; i < m; i++)
	{
		*(T->S + i) = NULL;
	}

	for (int i = 0; i < num; i++)
	{
		int k = universal_hash(n[i], T->a, T->b, T->prime, T->m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = n[i];
		p->next = *(T->S + k);
		*(T->S + k) = p;
	}
	return T;
}

//查找值
bool Universal_Hash_Search(Universal_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k = universal_hash(x, T->a, T->b, T->prime, T->m);
	node* p;
	p = *(T->S + k);
	while (p != NULL)
	{
		if (p->element == x)
		{
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	return flag;
}

//插入值
void Universal_Hash_Insert(Universal_Hashing_Table* T, int x)
{
	if (Universal_Hash_Search(T, x))
	{
		printf("%d 在哈希表中\n", x);
	}
	else
	{
		int k = universal_hash(x, T->a, T->b, T->prime, T->m);
		node* p;
		p = (node*)malloc(sizeof(node));
		p->element = x;
		p->next = *(T->S + k);
		*(T->S + k) = p;
	}
}

//删除值
void Universal_Hash_Delete(Universal_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k = universal_hash(x, T->a, T->b, T->prime, T->m);
	node* p;
	p = *(T->S + k);
	while (p != NULL)
	{
		if (p->element == x)
		{
			if (p == *(T->S + k))
			{
				*(T->S + k) = p->next;
				free(p);
			}
			else
			{
				node* q;
				q = *(T->S + k);
				while (q->next != p)
				{
					q = q->next;
				}
				q->next = p->next;
				free(p);
			}

			printf("%d在哈希表中已被删除\n", x);
			flag = 1;
			break;
		}
		else
		{
			p = p->next;
		}
	}
	if (!flag)
	{
		printf("%d不在哈希表中\n", x);
	}

}



//开放寻址法
typedef struct Open_Addressing_Hashing_Table{
	int m;
	int** S;
	int(*hash_function)(int, int, int);
};

//线性探查函数
int linear_probing(int x, int m, int i)
{
	int m1 = m - 1;
	return ((1 + hash(x, m1)) + i) % m;
}

//二次探查函数
int quadratic_probing(int x, int m, int i)
{
	int c1 = 1;
	int c2 = 1;
	int m1 = m - 1;
	return ((1 + hash(x, m1)) + c1*i + c2*i*i) % m;
}

//双重哈希函数
int double_hash(int x, int m, int i)
{
	int m1 = m - 1;
	int m2 = m - 2;
	return ((1 + hash(x, m1)) + i * (1 + hash(x, m2)) )% m;
}

//查找值
bool Open_Addressing_Hash_Search(Open_Addressing_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k;
	for (int i = 0; i < T->m; i++)
	{
		k = T->hash_function(x, T->m, i);
		if (*(T->S + k) == NULL)
		{
			break;
		}
		if (**(T->S + k) == x)
		{
			flag = 1;
			break;
		}
	}
	return flag;
}

//插入值
void Open_Addressing_Hash_Insert(Open_Addressing_Hashing_Table* T, int x)
{
	int k;
	int i;
	for (i = 0; i < T->m; i++)
	{
		k = T->hash_function(x, T->m, i);
		if (*(T->S + k) == NULL)
		{
			*(T->S + k) = (int*)malloc(sizeof(int));
			**(T->S + k) = x;
			break;
		}
		else if (**(T->S + k) == x)
		{
			printf("%d已在散列表中\n", x);
			break;
		}
		else
		{
			printf("%d在散列表第%d个槽位上，与待插入值%d发生第次%d冲突\n", **(T->S + k), k, x, i + 1);
		}
	}
	if (i == T->m)
	{
		printf("散列表已满\n");
	}
}

//开放寻址哈希表
Open_Addressing_Hashing_Table* Open_Addressing_Hash_Init(int m, int* n, int num, int(*hash_function)(int, int, int))
{
	Open_Addressing_Hashing_Table* T;
	T = (Open_Addressing_Hashing_Table*)malloc(sizeof(Open_Addressing_Hashing_Table));
	T->m = m;
	T->S = (int**)malloc(m * sizeof(int*));
	T->hash_function = hash_function;
	for (int i = 0; i < m; i++)
	{
		*(T->S + i) = NULL;
	}
	for (int i = 0; i < num; i++)
	{
		Open_Addressing_Hash_Insert(T, n[i]);
	}
	return T;
}

//打印开放寻址哈希表
void Print_Open_Addressing_Hash(Open_Addressing_Hashing_Table* T)
{
	for (int i = 0; i < T->m; i++)
	{
		printf("第%d个槽位:", i);
		if (*(T->S + i) != NULL)
		{
			printf("%d  ", **(T->S + i));
		}
		printf("\n");
	}
	printf("\n");
}

//删除开放寻址哈希表
void Delete_Open_Addressing_Hash(Open_Addressing_Hashing_Table* T)
{
	for (int i = 0; i < T->m; i++)
	{
		if (*(T->S + i) != NULL)
		{
			free(*(T->S + i));
		}
	}
	free(T);
	printf("哈希表已删除\n");
}



//完全哈希法
typedef struct Perfect_Hashing_Table
{
	int m;
	int a;
	int b;
	int prime;
	int* mm;
	Universal_Hashing_Table** S;
};

//完全哈希表初始化
Perfect_Hashing_Table* Perfect_Hash_Init(int* n, int num)
{
	Perfect_Hashing_Table* T;
	T = (Perfect_Hashing_Table*)malloc(sizeof(Perfect_Hashing_Table));
	T->mm = (int*)calloc(num, sizeof(int));
	T->S = (Universal_Hashing_Table**)malloc(num * sizeof(Universal_Hashing_Table*));

	T->prime = find_next_prime(find_array_max(n, num));
	T->m = num;
	T->a = (rand() % (T->prime - 1)) + 1;
	while (T->a == 0)
	{
		T->a = rand() % (T->prime - 1);
	}
	T->b = rand() % T->prime;

	printf("完全哈希表选取的一级表有限域的阶p为 %d\n", T->prime);
	printf("完全哈希表选取的一级表哈希函数为 h_{%d*x+%d}\n", T->a, T->b);

	int* n_site;
	n_site = (int*)calloc(num, sizeof(int));
	for (int i = 0; i < num; i++)
	{
		int k;
		k = universal_hash(n[i], T->a, T->b, T->prime, T->m);
		T->mm[k]++;
		n_site[i] = k;
	}
	int** nn;
	nn = (int**)malloc(num * sizeof(int*));
	for (int i = 0; i < T->m; i++)
	{
		if (T->mm[i] != 0)
		{
			*(nn + i) = (int*)malloc(T->mm[i] * sizeof(int));
			for (int k = 0; k < T->mm[i]; k++)
			{
				for (int j = 0; j < T->m; j++)
				{
					if (n_site[j] == i)
					{
						*(*(nn + i) + k) = n[j];
						n_site[j] = -1; // 标记为已处理
						break;
					}
				}
			}
			
		}
		else
		{
			*(nn + i) = NULL;
		}
	}


	for (int i = 0; i < num; i++)
	{
		if (T->mm[i] != 0)
		{
			*(T->S + i) = Universal_Hash_Init(T->mm[i] * T->mm[i], *(nn + i), T->mm[i]);
		}
		else
		{
			*(T->S + i) = NULL;
		}
	}

	free(n_site);
	for (int i = 0; i < T->m; i++)
	{
		if (T->mm[i] != 0)
		{
			free(*(nn + i));
		}
	}
	free(nn);
	return T;
}

//查找值
bool Perfect_Hash_Search(Perfect_Hashing_Table* T, int x)
{
	bool flag = 0;
	int k;
	k = universal_hash(x, T->a, T->b, T->prime, T->m);
	if (T->mm[k] != 0)
	{
		flag = Universal_Hash_Search(*(T->S + k), x);
	}

	return flag;
}

void Print_Perfect_Hash(Perfect_Hashing_Table* T)
{
	printf("完全哈希表选取的一级表\n");
	for (int i = 0; i < T->m; i++)
	{
		printf("完全哈希表选取的第%d个二级表\n", i);
		if (*(T->S + i) != NULL)
		{
			Print_Hash((*(T->S + i))->S, T->mm[i] * T->mm[i]);
		}
		else
		{
			printf("空表\n");
		}
	}
}

void Delete_Perfect_Hash(Perfect_Hashing_Table* T)
{
	for (int i = 0; i < T->m; i++)
	{
		if (*(T->S + i) != NULL)
		{
			Delete_Hash((*(T->S + i))->S, T->mm[i] ^ 2);
			free(*(T->S + i));
		}
	}
	free(T->S);
	free(T);
}


int main()
{
	// //设置槽位
	// int m = 7;
	// //设置一组连续的数
	// int num = 4, min = 5;
	// int max = min + num;
	// int* n;
	// n = (int*)malloc(num * sizeof(int));
	// for (int i = 0; i < num; i++)
	// {
	// 	n[i] = min + i;
	// }
	//全域哈希表使用
	// int n[] = {10, 22, 37, 40, 52, 60, 70, 72, 75};
	// int num = sizeof(n) / sizeof(n[0]);

	// //哈希链表
	// printf("哈希链表:\n");
	// node** T;
	// T = Division_Hash_Init(m, n, num);
	// Print_Hash(T, m);
	// printf("%d \n", Division_Hash_Search(T, m, 5));
	// printf("%d \n", Division_Hash_Search(T, m, 9));
	// Print_Hash(T, m);
	// Division_Hash_Insert(T, m, 10);
	// Division_Hash_Insert(T, m, 7);
	// Division_Hash_Insert(T, m, 14);
	// Print_Hash(T, m);
	// Division_Hash_Delete(T, m, 5);
	// Division_Hash_Delete(T, m, 9);
	// Print_Hash(T, m);
	// Delete_Hash(T, m);


	// //全域哈希表
	// printf("全域哈希表:\n");
	// Universal_Hashing_Table* UT;
	// UT = Universal_Hash_Init(m, n, num);
	// Print_Hash(UT->S, UT->m);
	// printf("%d \n", Universal_Hash_Search(UT,5));
	// printf("%d \n", Universal_Hash_Search(UT, 9));
	// Print_Hash(UT->S, UT->m);
	// Universal_Hash_Insert(UT,10);
	// Universal_Hash_Insert(UT, 7);
	// Universal_Hash_Insert(UT, 14);
	// Print_Hash(UT->S, UT->m);
	// Universal_Hash_Delete(UT, 5);
	// Universal_Hash_Delete(UT, 9);
	// Print_Hash(UT->S, UT->m);
	// Delete_Hash(UT->S, UT->m);
	// free(UT);

	// //开放寻址表
	// printf("开放寻址表:\n");
	// Open_Addressing_Hashing_Table* OAT;
	// m = 2 * num;
	// //线性探查函数
	// OAT = Open_Addressing_Hash_Init(m, n, num, linear_probing);
	// //二次探查函数
	// OAT = Open_Addressing_Hash_Init(m, n, num, quadratic_probing);
	// //双重哈希函数
	// OAT = Open_Addressing_Hash_Init(m, n, num, double_hash);
	// Print_Open_Addressing_Hash(OAT);
	// printf("%d \n", Open_Addressing_Hash_Search(OAT, 5));
	// printf("%d \n", Open_Addressing_Hash_Search(OAT, 9));
	// Print_Open_Addressing_Hash(OAT);
	// Open_Addressing_Hash_Insert(OAT, 10);
	// Open_Addressing_Hash_Insert(OAT, 7);
	// Open_Addressing_Hash_Insert(OAT, 12);
	// Print_Open_Addressing_Hash(OAT);
	// Delete_Open_Addressing_Hash(OAT);
	// free(OAT);

	// // 完全哈希表
	// Perfect_Hashing_Table* PT;
	// PT = Perfect_Hash_Init(n, num);
	// Print_Perfect_Hash(PT);
	// printf("%d \n", Perfect_Hash_Search(PT, 60));
	// printf("%d \n", Perfect_Hash_Search(PT, 9));


	return 0;
}

结果

哈希链表:
第0个槽位:7  
第1个槽位:8  
第2个槽位:
第3个槽位:
第4个槽位:
第5个槽位:5  
第6个槽位:6  

1 
0 
第0个槽位:7  
第1个槽位:8  
第2个槽位:
第3个槽位:
第4个槽位:
第5个槽位:5  
第6个槽位:6  

7 在哈希表中
第0个槽位:14  7  
第1个槽位:8  
第2个槽位:
第3个槽位:10  
第4个槽位:
第5个槽位:5  
第6个槽位:6  

5在哈希表中已被删除
9不在哈希表中
第0个槽位:14  7  
第1个槽位:8  
第2个槽位:
第3个槽位:10  
第4个槽位:
第5个槽位:
第6个槽位:6  

哈希表已删除

全域哈希表:
哈希函数族的选取有限域的阶p为 11
随机哈希函数为 h_{10*x+1}
第0个槽位:5  
第1个槽位:
第2个槽位:
第3个槽位:
第4个槽位:8  
第5个槽位:7  
第6个槽位:6  

1 
0 
第0个槽位:5  
第1个槽位:
第2个槽位:
第3个槽位:
第4个槽位:8  
第5个槽位:7  
第6个槽位:6  

7 在哈希表中
第0个槽位:5  
第1个槽位:
第2个槽位:14  10  
第3个槽位:
第4个槽位:8  
第5个槽位:7  
第6个槽位:6  

5在哈希表中已被删除
9不在哈希表中
第0个槽位:
第1个槽位:
第2个槽位:14  10  
第3个槽位:
第4个槽位:8  
第5个槽位:7  
第6个槽位:6  

哈希表已删除

开放寻址表:
第0个槽位:
第1个槽位:7  
第2个槽位:8  
第3个槽位:
第4个槽位:
第5个槽位:
第6个槽位:5  
第7个槽位:6  

1 
0 
第0个槽位:
第1个槽位:7  
第2个槽位:8  
第3个槽位:
第4个槽位:
第5个槽位:
第6个槽位:5  
第7个槽位:6  

7已在散列表中
5在散列表第6个槽位上，与待插入值12发生第次1冲突
6在散列表第7个槽位上，与待插入值12发生第次2冲突
第0个槽位:12  
第1个槽位:7  
第2个槽位:8  
第3个槽位:
第4个槽位:10  
第5个槽位:
第6个槽位:5  
第7个槽位:6  

哈希表已删除

完全哈希表选取的一级表有限域的阶p为 79
完全哈希表选取的一级表哈希函数为 h_{38*x+5}
哈希函数族的选取有限域的阶p为 73
随机哈希函数为 h_{14*x+64}
哈希函数族的选取有限域的阶p为 79
随机哈希函数为 h_{41*x+33}
哈希函数族的选取有限域的阶p为 71
随机哈希函数为 h_{11*x+68}
哈希函数族的选取有限域的阶p为 37
随机哈希函数为 h_{13*x+30}
哈希函数族的选取有限域的阶p为 53
随机哈希函数为 h_{37*x+6}
完全哈希表选取的一级表
完全哈希表选取的第0个二级表
空表
完全哈希表选取的第1个二级表
第0个槽位:60  
第1个槽位:
第2个槽位:72  
第3个槽位:

完全哈希表选取的第2个二级表
第0个槽位:75  

完全哈希表选取的第3个二级表
空表
完全哈希表选取的第4个二级表
第0个槽位:70  

完全哈希表选取的第5个二级表
第0个槽位:37  

完全哈希表选取的第6个二级表
第0个槽位:
第1个槽位:
第2个槽位:40  
第3个槽位:
第4个槽位:
第5个槽位:10  
第6个槽位:52  
第7个槽位:
第8个槽位:
第9个槽位:22  
第10个槽位:
第11个槽位:
第12个槽位:
第13个槽位:
第14个槽位:
第15个槽位:

完全哈希表选取的第7个二级表
空表
完全哈希表选取的第8个二级表
空表
1 
0 

二叉搜索树

总代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef struct BTreeNode
{
	double element;		//节点元素
	BTreeNode* lchild;	//左孩子
	BTreeNode* rchild;	//右孩子
	BTreeNode* parent;	//父亲
}BTreeNode;


//输出二叉树所有节点		中序遍历
void InOrder_BST(BTreeNode* t)
{
	if (t != NULL)
	{
		InOrder_BST(t->lchild);
		printf("%lf ", t->element);
		InOrder_BST(t->rchild);
	}
}

//查找二叉搜索树中节点	未找到则返回NULL
//递归方法
BTreeNode* Search_BST(BTreeNode* t, double a)
{
	if (t == NULL || t->element == a)
	{
		return t;
	}
	else if (t->element < a)
	{
		return Search_BST(t->rchild, a);
	}
	else
	{
		return Search_BST(t->lchild, a);
	}
}

//循环方法
BTreeNode* Search_Iterative_BST(BTreeNode* t, double a)
{
	BTreeNode* p;
	p = t;
	while (p != NULL && p->element != a)
	{
		if (p->element < a)
		{
			p = p->rchild;
		}
		else
		{
			p = p->lchild;
		}
	}
	return p;
}

//寻找二叉搜树中最小元素
BTreeNode* Findmin_BST(BTreeNode* t)
{
	BTreeNode* p;
	p = t;
	while (p->lchild != NULL)
	{
		p = p->lchild;
	}
	return p;
}

//寻找二叉搜树中最大元素
BTreeNode* Findbig_BST(BTreeNode* t)
{
	BTreeNode* p;
	p = t;
	while (p->rchild != NULL)
	{
		p = p->rchild;
	}
	return p;
}

//寻找二叉搜树中元素的后驱
BTreeNode* Successor_BST(BTreeNode* x)
{
	if (x == NULL)
	{
		printf("节点为空，其后驱为NULL");
	}
	if (x->rchild != NULL)
	{
		return Findmin_BST(x->rchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的左孩子
		while (x->parent != NULL && x->parent->rchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}

//寻找二叉搜树中元素的前驱
BTreeNode* Predecessor_BST(BTreeNode* x)
{
	if (x == NULL)
	{
		printf("节点为空，其前驱为NULL");
		return x;
	}
	if (x->lchild != NULL)
	{
		return Findbig_BST(x->lchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的右孩子
		while (x->parent != NULL && x->parent->lchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}

//在二叉搜索树中插入节点
void Insertnode_BST(BTreeNode* t, double a)
{
	bool element_exist = 0;
	BTreeNode* p, * q;
	p = t;
	q = NULL;
	//寻找待插入位置的父节点
	while (p != NULL && !element_exist)
	{
		q = p;
		if (p->element < a)
		{
			p = p->rchild;
		}
		else if (p->element > a)
		{
			p = p->lchild;
		}
		else
		{
			printf("%lf 已在搜索二叉树中\n", a);
			element_exist = 1;
		}
	}

	if (!element_exist)
	{
		//插入节点
		BTreeNode* x;
		x = (BTreeNode*)malloc(sizeof(BTreeNode));
		x->element = a;
		x->lchild = NULL;
		x->rchild = NULL;
		x->parent = q;
		if (q == NULL)
		{
			t = x;
		}
		else if (q->element < a)
		{
			q->rchild = x;
		}
		else
		{
			q->lchild = x;
		}
	}

}

//二叉搜索树中删除节点
//子树替换	不考虑大小关系	q代替p的位置，p的各个指针不变
void Transplant_BTree(BTreeNode* t, BTreeNode* p, BTreeNode* q)
{
	if (p == t)							//p为根节点时
	{
		t = q;
	}
	else if (p == p->parent->lchild)	//p为左孩子时
	{
		p->parent->lchild = q;
	}
	else								//p为右孩子时
	{
		p->parent->rchild = q;
	}
	if (q != NULL)
	{
		q->parent = p->parent;
	}
}

void Deletenode_BST(BTreeNode* t, double a)
{
	BTreeNode* x;
	x = Search_Iterative_BST(t, a);
	if (x == NULL)
	{
		printf("%lf不存在，无法删除", a);
	}
	else
	{
		if (x->lchild == NULL)
		{
			Transplant_BTree(t, x, x->rchild);
		}
		else if (x->rchild == NULL)
		{
			Transplant_BTree(t, x, x->lchild);
		}
		else
		{
			BTreeNode* y;
			y = Successor_BST(x);
			if (y->parent != x)		//x的后继不在x的孩子中	构造y子树
			{
				Transplant_BTree(t, y, y->rchild);
				y->rchild = x->rchild;
				y->rchild->parent = y;
			}
			Transplant_BTree(t, x, y);
			y->lchild = x->lchild;
			y->lchild->parent = y;
		}

		free(x);
	}
}

//随机构建二叉搜索树
BTreeNode* Random_Bulid_BST(double* n, int num)
{
	BTreeNode* t;
	t = NULL;
	if (num > 0)
	{
		int random_num;
		random_num = rand() % num;

		t = (BTreeNode*)malloc(sizeof(BTreeNode));
		t->element = n[random_num];
		t->lchild = NULL;
		t->rchild = NULL;
		t->parent = NULL;

		// 将已使用的元素移至数组末尾
		double temp;
		temp = n[random_num];
		n[random_num] = n[num - 1];
		n[num - 1] = temp;

		for (int i = 1; i < num; i++)
		{
			random_num = rand() % (num - i);
			Insertnode_BST(t, n[random_num]);

			// 将已使用的元素移至数组末尾
			temp = n[random_num];
			n[random_num] = n[num - i - 1];
			n[num - i - 1] = temp;
		}

	}

	return t;
}

//求树的高度
int max(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

int HighBTree(BTreeNode* t)
{
	if (t == NULL)
	{
		return 0;
	}
	else
	{
		return (max(HighBTree(t->lchild), HighBTree(t->rchild)) + 1);
	}
}

//链队列结构类型
typedef struct QueueNode
{
	BTreeNode* btreenode;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue
{
	QueueNode* front;//队头指针
	QueueNode* rear;//队尾指针
}LinkQueue;

LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->btreenode = NULL;
	return q;
}

//空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//入队
void EnLinkQueue(LinkQueue* q, BTreeNode* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->btreenode = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

//出队
BTreeNode* DeLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		BTreeNode* btreenode;
		QueueNode* queuenode;
		queuenode = q->front->next;
		btreenode = queuenode->btreenode;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return btreenode;
	}
}

//层次展示二叉树
void LikeBTree(BTreeNode* t)
{
	if (t == NULL)
	{
		printf("树空\n");
	}
	else
	{
		LinkQueue* q;
		BTreeNode* node;
		int high = 1;
		int sumh;
		int highmax;
		int mark = 0;

		BTreeNode* emptynode;
		emptynode = (BTreeNode*)malloc(sizeof(BTreeNode));
		emptynode->element = NULL;
		emptynode->lchild = NULL;
		emptynode->rchild = NULL;

		highmax = HighBTree(t);
		q = InitLinkQueue();	//创建树节点队列

		EnLinkQueue(q, t);
		while (EmptyLinkQueue(q) == 1 && high <= highmax)		//队不为空
		{
			node = DeLinkQueue(q);

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补前面空缺
			{
				printf("  ");
			}

			if (node == emptynode)
			{
				printf("   #");
			}
			else
			{
				printf("%4.0lf", node->element);
			}

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补后面空缺
			{
				printf("  ");
			}

			if (node->lchild != NULL)
			{
				EnLinkQueue(q, node->lchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}
			if (node->rchild != NULL)
			{
				EnLinkQueue(q, node->rchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}

			mark++;
			sumh = pow(2, high) - 1;
			if (mark >= sumh)		//换层
			{
				high++;
				printf("\n");
			}
		}
		free(emptynode);
		free(q->front);
		free(q);
	}
}

//删除
BTreeNode* Delete_BST(BTreeNode* t)
{
	if (t != NULL)
	{
		t->lchild = Delete_BST(t->lchild);
		t->rchild = Delete_BST(t->rchild);
		free(t);
		return NULL;
	}
}


int main()
{
	double n[] = { 10, 22, 37, 40, 52, 60, 70, 72, 75 };
	int num = sizeof(n) / sizeof(n[0]);

	BTreeNode* T;
	T = Random_Bulid_BST(n, num);
	Findbig_BST(T);
	printf("\n");
	Findmin_BST(T);
	printf("\n");
	InOrder_BST(T);
	printf("\n");
	Insertnode_BST(T, 66);
	Insertnode_BST(T, 40);
	Deletenode_BST(T, 75);
	InOrder_BST(T);
	printf("\n");
	printf("%lf\n", Search_BST(T, 52)->element);
	printf("%lf\n", Search_Iterative_BST(T, 22)->element);
	LikeBTree(T);
	T = Delete_BST(T);

	return 0;
}

结果

10.000000 22.000000 37.000000 40.000000 52.000000 60.000000 70.000000 72.000000 75.000000 
40.000000 已在搜索二叉树中
10.000000 22.000000 37.000000 40.000000 52.000000 60.000000 66.000000 70.000000 72.000000 
52.000000
22.000000
                52              
        22              70      
    10      37      60      72  
   #   #   #  40   #  66   #   #

红黑树

总代码

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef struct RBTreeNode
{
	bool color;			//节点颜色	1-红		0-黑
	double element;		//节点元素
	RBTreeNode* lchild;	//左孩子
	RBTreeNode* rchild;	//右孩子
	RBTreeNode* parent;	//父亲
}RBTreeNode;


//输出红黑树所有节点		中序遍历
void InOrder_RBT(RBTreeNode* t)
{
	if (t->lchild != NULL && t->rchild != NULL)	//不为哨兵节点
	{
		InOrder_RBT(t->lchild);
		printf("%lf ", t->element);
		InOrder_RBT(t->rchild);
	}
}


//查找二叉搜索树中节点	未找到则返回哨兵节点
//递归方法
RBTreeNode* Search_RBT(RBTreeNode* t, double a)
{
	if ((t->lchild == NULL && t->rchild == NULL) || t->element == a)	//哨兵节点或者找到
	{
		return t;
	}
	else if (t->element < a)
	{
		return Search_RBT(t->rchild, a);
	}
	else
	{
		return Search_RBT(t->lchild, a);
	}
}

//循环方法
RBTreeNode* Search_Iterative_RBT(RBTreeNode* t, double a)
{
	RBTreeNode* p;
	p = t;
	while (!(p->lchild == NULL && p->rchild == NULL) && p->element != a)
	{
		if (p->element < a)
		{
			p = p->rchild;
		}
		else
		{
			p = p->lchild;
		}
	}
	return p;
}


//寻找红黑树中最小元素
RBTreeNode* Findmin_RBT(RBTreeNode* t)
{
	RBTreeNode* p;
	p = t;
	while (p->lchild->lchild != NULL && p->lchild->rchild != NULL)	//遇到左孩子为哨兵节点停止
	{
		p = p->lchild;
	}
	return p;
}

//寻找红黑树中最大元素
RBTreeNode* Findbig_RBT(RBTreeNode* t)
{
	RBTreeNode* p;
	p = t;
	while (p->rchild->lchild != NULL && p->rchild->rchild != NULL)
	{
		p = p->rchild;
	}
	return p;
}


//寻找二叉搜树中元素的后驱
RBTreeNode* Successor_BST(RBTreeNode* x)
{
	if (x->lchild == NULL && x->rchild == NULL)		//哨兵节点
	{
		printf("节点为空，其后驱为NULL");
	}
	if (x->rchild->lchild != NULL && x->rchild->rchild != NULL)		//x的右节点不为哨兵节点
	{
		return Findmin_RBT(x->rchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的左孩子
		while ((x->parent->lchild != NULL && x->parent->rchild != NULL) && x->parent->rchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}

//寻找二叉搜树中元素的前驱
RBTreeNode* Predecessor_RBT(RBTreeNode* x)
{
	if (x->lchild == NULL && x->rchild == NULL)		//哨兵节点
	{
		printf("节点为空，其前驱为NULL");
		return x;
	}
	if (x->lchild->lchild != NULL && x->lchild->rchild != NULL)		//x的左节点为哨兵节点
	{
		return Findbig_RBT(x->lchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的右孩子
		while ((x->parent->lchild != NULL && x->parent->rchild != NULL) && x->parent->lchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}


//左旋	将x节点的右孩子y提到x的位置，x再作为y的左孩子
RBTreeNode* LeftRotate_RBT(RBTreeNode* t, RBTreeNode* x)
{
	RBTreeNode* nilnode;
	nilnode = t->parent;
	RBTreeNode* y;
	y = x->rchild;
	if (y != nilnode)
	{
		x->rchild = y->lchild;
		if (y->lchild != nilnode)			//y->lchild的父亲指向x
		{
			y->lchild->parent = x;
		}

		y->parent = x->parent;
		if (x == t)						//x为根节点
		{
			t = y;
		}
		else if (x == x->parent->lchild)	//x为左孩子
		{
			x->parent->lchild = y;
		}
		else							//x为右孩子
		{
			x->parent->rchild = y;
		}

		y->lchild = x;
		x->parent = y;
	}
	else
	{
		printf("%lf节点无右孩子，无法左旋\n", x->element);
	}
	return t;
}

//右旋	将y节点的左孩子x提到y的位置，y再作为x的右孩子
RBTreeNode* RightRotate_RBT(RBTreeNode* t, RBTreeNode* y)
{
	RBTreeNode* nilnode;
	nilnode = t->parent;
	RBTreeNode* x;
	x = y->lchild;
	if (x != nilnode)
	{
		y->lchild = x->rchild;
		if (x->rchild != nilnode)			//x->rchild的父亲指向y
		{
			x->rchild->parent = y;
		}

		x->parent = y->parent;
		if (y == t)						//y为根节点
		{
			t = x;
		}
		else if (y == y->parent->lchild)	//y为左孩子
		{
			y->parent->lchild = x;
		}
		else							//y为右孩子
		{
			y->parent->rchild = x;
		}

		x->rchild = y;
		y->parent = x;
	}
	else
	{
		printf("%lf节点无左孩子，无法右旋\n", y->element);
	}
	return t;
}


//在红黑树中插入节点
//红黑树插入节点修正
RBTreeNode* Insert_Fixup_RBT(RBTreeNode* t, RBTreeNode* x)
{
	//若x父亲为红色节点，则进入矫正红黑树操作
	while (x != t && x->parent->color == 1)
	{
		RBTreeNode* y;
		//情况1：x的父亲是x祖父的左孩子
		if (x->parent == x->parent->parent->lchild)
		{
			y = x->parent->parent->rchild;	//x的叔叔，即x的祖父的右孩子
			//情况1.1：y为红色节点
			//操作：x与y换成黑色，祖父换成红色
			//结果：x的祖父的黑高+1，其他节点黑高不变
			if (y->color == 1)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;		//x变为其祖父继续迭代
			}
			else
			{
				//情况1.2：y为黑色节点，x为其父亲的右孩子
				//操作：左旋x的父亲，将x提至x的父亲的位置
				//结果：转化为情况1.3
				if (x == x->parent->rchild)
				{
					x = x->parent;
					t = LeftRotate_RBT(t, x);
				}
				//情况1.3：y为黑色节点，x为其父亲的左孩子
				//操作：右旋x的祖父，将x的父亲提至x的祖父的位置，再改变x的颜色
				//结果：黑高都不变
				x->parent->color = 0;
				x->parent->parent->color = 1;
				t = RightRotate_RBT(t, x->parent->parent);
			}
		}
		//情况2：x的父亲是x祖父的右孩子
		else
		{
			y = x->parent->parent->lchild;	//x的叔叔，即x的祖父的左孩子
			//情况2.1：y为红色节点
			//操作：x与y换成黑色，祖父换成红色
			//结果：x的祖父的黑高+1，其他节点黑高不变
			if (y->color == 1)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;		//x变为其祖父继续迭代
			}
			else
			{
				//情况2.2：y为黑色节点，x为其父亲的左孩子
				//操作：右旋x的父亲，将x提至x的父亲的位置
				//结果：转化为情况2.3
				if (x == x->parent->lchild)
				{
					x = x->parent;
					t = RightRotate_RBT(t, x);
				}
				//情况2.3：y为黑色节点，x为其父亲的右孩子
				//操作：左旋x的祖父，将x的父亲提至x的祖父的位置，再改变x的颜色
				//结果：黑高都不变
				x->parent->color = 0;
				x->parent->parent->color = 1;
				t = LeftRotate_RBT(t, x->parent->parent);
			}
		}
	}
	t->color = 0;
	return t;
}

RBTreeNode* Insertnode_RBT(RBTreeNode* t, double a)
{
	RBTreeNode* nilnode;
	nilnode = t->parent;
	bool element_exist = 0;
	RBTreeNode* y, * p;
	y = NULL;
	p = t;
	//寻找待插入位置的父节点y
	while (p != nilnode && !element_exist)
	{
		y = p;
		if (a > p->element)
		{
			p = p->rchild;
		}
		else if (a < p->element)
		{
			p = p->lchild;
		}
		else
		{
			printf("%lf 已在红黑树中\n", a);
			element_exist = 1;
		}
	}

	if (!element_exist)
	{
		//插入节点
		RBTreeNode* x;
		x = (RBTreeNode*)malloc(sizeof(RBTreeNode));
		x->color = 1;	//赋为红色节点
		x->element = a;
		x->lchild = nilnode;
		x->rchild = nilnode;
		x->parent = y;

		if (y == nilnode)
		{
			t = x;
		}
		else
		{
			if (y->element < a)
			{
				y->rchild = x;
			}
			else
			{
				y->lchild = x;
			}
			t = Insert_Fixup_RBT(t, x);
		}

	}
	return t;
}


//在红黑树中删除节点
// 红黑树删除节点修正
RBTreeNode* Delete_Fixup_RBT(RBTreeNode* t, RBTreeNode* x)
{
	//若x父亲为黑色节点，则进入矫正红黑树操作
	while (x != t && x->color == 0)
	{
		//情况1：x是其父亲的左孩子
		if (x == x->parent->lchild)
		{
			RBTreeNode* w;
			w = x->parent->rchild;		//x的兄弟,即x的父亲的右孩子
			//情况1.1：w为红色节点
			//操作：x的父亲与w换色，x的父亲左旋
			//结果：转化为其他情况
			if (w->color == 1)
			{
				w->color = 0;
				x->parent->color = 1;
				t = LeftRotate_RBT(t, x->parent);
				w = x->parent->rchild;		//保持w为x的兄弟,即x的父亲的右孩子
			}
			else
			{
				//情况1.2：w与w所有孩子都为黑色节点
				//操作：将w颜色变红，再将x上移讨论原x的父亲的情况
				//结果：w子树黑高 -1
				if (w->lchild->color == 0 && w->rchild->color == 0)
				{
					w->color = 1;
					x = x->parent;
				}
				//情况1.3：w与w的右孩子都为黑色节点，w的左孩子为红色节点
				//操作：将w与w左孩子换色，右旋w
				//结果：转化为情况1.4
				else if (w->rchild->color == 0)
				{
					w->lchild->color = 0;
					w->color = 1;
					t = RightRotate_RBT(t, w);
					w = x->parent->rchild;		//保持w为x的兄弟,即x的父亲的右孩子
				}
				//情况1.4：w与为黑色节点，w的右孩子为红色节点，w左孩子为任意颜色
				//操作：将x的父亲与w换色，w的右孩子变黑，左旋x的父亲
				//结果：原x的子树黑高 +1
				else
				{
					w->color = x->parent->color;
					x->parent->color = 0;
					w->rchild->color = 0;
					t = LeftRotate_RBT(t, x->parent);
					x = t;		//退出循环
				}
			}
		}
		//情况2：x是其父亲的右孩子
		else
		{
			RBTreeNode* w;
			w = x->parent->lchild;		//x的兄弟,即x的父亲的左孩子
			//情况2.1：w为红色节点
			//操作：x的父亲与w换色，x的父亲右旋
			//结果：转化为其他情况
			if (w->color == 1)
			{
				w->color = 0;
				x->parent->color = 1;
				t = RightRotate_RBT(t, x->parent);
				w = x->parent->lchild;		//保持w为x的兄弟,即x的父亲的左孩子
			}
			else
			{
				//情况2.2：w与w所有孩子都为黑色节点
				//操作：将w颜色变红，再将x上移讨论原x的父亲的情况
				//结果：w子树黑高 -1
				if (w->lchild->color == 0 && w->rchild->color == 0)
				{
					w->color = 1;
					x = x->parent;
				}
				//情况2.3：w与w的左孩子都为黑色节点，w的右孩子为红色节点
				//操作：将w与w右孩子换色，左旋w
				//结果：转化为情况1.4
				else if (w->lchild->color == 0)
				{
					w->rchild->color = 0;
					w->color = 1;
					t = LeftRotate_RBT(t, w);
					w = x->parent->lchild;		//保持w为x的兄弟,即x的父亲的右孩子
				}
				//情况2.4：w与为黑色节点，w的左孩子为红色节点，w右孩子为任意颜色
				//操作：将x的父亲与w换色，w的左孩子变黑，右旋x的父亲
				//结果：原x的子树黑高 +1
				else
				{
					w->color = x->parent->color;
					x->parent->color = 0;
					w->lchild->color = 0;
					t = RightRotate_RBT(t, x->parent);
					x = t;		//退出循环
				}
			}
		}
	}
	x->color = 0;		//若节点为红，转化为黑节点报告该子树黑高
	return t;
}

//子树替换	不考虑大小关系	q代替p的位置，p的各个指针不变
RBTreeNode* Transplant_RBTree(RBTreeNode* t, RBTreeNode* p, RBTreeNode* q)
{
	if (p == t)					//p为根节点时
	{
		t = q;
	}
	else if (p == p->parent->lchild)	//p为左孩子时
	{
		p->parent->lchild = q;
	}
	else								//p为右孩子时
	{
		p->parent->rchild = q;
	}
	q->parent = p->parent;

	return t;
}

RBTreeNode* Deletenode_RBT(RBTreeNode* t, double a)
{
	RBTreeNode* nilnode;
	nilnode = t->parent;

	RBTreeNode* z;
	z = Search_Iterative_RBT(t, a);
	if (z == nilnode)
	{
		printf("%lf不存在，无法删除", a);
	}
	else
	{
		RBTreeNode* x;
		bool deletenode_color = z->color;
		if (z->lchild == nilnode)
		{
			x = z->rchild;
			t = Transplant_RBTree(t, z, x);
		}
		else if (z->rchild == nilnode)
		{
			x = z->lchild;
			t = Transplant_RBTree(t, z, x);
		}
		else
		{
			RBTreeNode* y;
			y = Successor_BST(z);
			x = y->rchild;
			deletenode_color = y->color;
			if (y->parent == z)		//z的后继为z的孩子
			{
				x->parent = y;		//防止后续修正红黑树颜色操作，因为哨兵节点无父节点指针出错
			}
			else
			{
				t = Transplant_RBTree(t, y, x);
				y->rchild = z->rchild;
				y->rchild->parent = y;
			}
			t = Transplant_RBTree(t, z, y);
			y->lchild = z->lchild;
			y->lchild->parent = y;
			y->color = z->color;	//继承删除位置的颜色
		}
		if (deletenode_color == 0)
		{
			t = Delete_Fixup_RBT(t, x);
		}
		free(z);
	}
	return t;
}


//随机构建红黑树
RBTreeNode* Random_Bulid_RBT(double* n, int num)
{
	RBTreeNode* t;
	t = NULL;
	if (num > 0)
	{
		int random_num;
		random_num = rand() % num;

		//哨兵黑节点，只有黑色，标记为其余指针都为空
		RBTreeNode* nilnode;
		nilnode = (RBTreeNode*)malloc(sizeof(RBTreeNode));
		nilnode->color = 0;
		nilnode->lchild = NULL;
		nilnode->rchild = NULL;
		nilnode->parent = NULL;

		t = (RBTreeNode*)malloc(sizeof(RBTreeNode));
		t->element = n[random_num];
		t->lchild = nilnode;
		t->rchild = nilnode;
		t->parent = nilnode;	//此处储存nilnode的地址，方便以后直接取出
		t->color = 0;

		// 将已使用的元素移至数组末尾
		double temp;
		temp = n[random_num];
		n[random_num] = n[num - 1];
		n[num - 1] = temp;

		for (int i = 1; i < num; i++)
		{
			random_num = rand() % (num - i);
			t = Insertnode_RBT(t, n[random_num]);

			// 将已使用的元素移至数组末尾
			temp = n[random_num];
			n[random_num] = n[num - i - 1];
			n[num - i - 1] = temp;
		}

	}

	return t;
}


//删除红黑树
RBTreeNode* Delete_RBT(RBTreeNode* t)
{
	if (t->lchild != NULL && t->rchild != NULL)
	{
		t->lchild = Delete_RBT(t->lchild);		//哨兵节点会自动删除
		t->rchild = Delete_RBT(t->rchild);
		free(t);
		return NULL;
	}
}


int max(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

//输出红黑树节点的黑高
int Blackhheight(RBTreeNode* t)
{
	if (t->lchild == NULL && t->rchild == NULL)		//表示为哨兵节点
	{
		return 0;
	}
	else if (t->color == 1)
	{
		int h1 = Blackhheight(t->lchild);
		int h2 = Blackhheight(t->rchild);
		if (h1 != h2)
		{
			printf("黑高不匹配，算法估计有问题");
		}
		return (max(h1, h2));
	}
	else
	{
		int h1 = Blackhheight(t->lchild);
		int h2 = Blackhheight(t->rchild);
		if (h1 != h2)
		{
			printf("黑高不匹配，算法估计有问题");
		}
		return (max(h1, h2) + 1);
	}
}

//求树的高度
int HighBTree(RBTreeNode* t)
{
	if (t->lchild == NULL && t->rchild == NULL)	//表示为哨兵节点
	{
		return 0;
	}
	else
	{
		return (max(HighBTree(t->lchild), HighBTree(t->rchild)) + 1);
	}
}

//链队列结构类型
typedef struct QueueNode
{
	RBTreeNode* rbtreenode;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue
{
	QueueNode* front;//队头指针
	QueueNode* rear;//队尾指针
}LinkQueue;

LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->rbtreenode = NULL;
	return q;
}

//空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//入队
void EnLinkQueue(LinkQueue* q, RBTreeNode* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->rbtreenode = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

//出队
RBTreeNode* DeLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		RBTreeNode* rbtreenode;
		QueueNode* queuenode;
		queuenode = q->front->next;
		rbtreenode = queuenode->rbtreenode;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return rbtreenode;
	}
}

//层次展示二叉树
void LikeBTree(RBTreeNode* t)
{
	if (t == NULL)
	{
		printf("树空\n");
	}
	else
	{
		LinkQueue* q;
		RBTreeNode* node;
		int high = 1;
		int sumh;
		int highmax;
		int mark = 0;

		RBTreeNode* nilnode;
		nilnode = t->parent;

		RBTreeNode* emptynode;
		emptynode = (RBTreeNode*)malloc(sizeof(RBTreeNode));
		emptynode->color = 0;
		emptynode->lchild = nilnode;
		emptynode->rchild = nilnode;

		highmax = HighBTree(t);
		q = InitLinkQueue();	//创建树节点队列

		EnLinkQueue(q, t);
		while (EmptyLinkQueue(q) == 1 && high <= highmax)		//队不为空
		{
			node = DeLinkQueue(q);

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补前面空缺
			{
				printf("  ");
			}

			if (node == emptynode)
			{
				printf("   #");
			}
			else
			{
				if (node->color == 0)
				{
					printf("%4.0lf ", node->element);
				}
				else
				{
					printf("$%3.0lf", node->element);
				}
			}

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补后面空缺
			{
				printf("  ");
			}

			if (node->lchild != nilnode)
			{
				EnLinkQueue(q, node->lchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}
			if (node->rchild != nilnode)
			{
				EnLinkQueue(q, node->rchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}

			mark++;
			sumh = pow(2, high) - 1;
			if (mark >= sumh)		//换层
			{
				high++;
				printf("\n");
			}
		}
		free(emptynode);
		free(q->front);
		free(q);
	}
}


int main()
{
	double n[] = { 10, 22, 37, 40, 52, 60, 70, 72, 75, 160, 170, 172, 175 };
	int num = sizeof(n) / sizeof(n[0]);

	RBTreeNode* T;
	T = Random_Bulid_RBT(n, num);
	InOrder_RBT(T);
	printf("\n");
	LikeBTree(T);
	T = Deletenode_RBT(T, 60);
	printf("\n");
	LikeBTree(T);
	T = Deletenode_RBT(T, 70);
	printf("\n");
	LikeBTree(T);
	T = Deletenode_RBT(T, 72);
	printf("\n");
	LikeBTree(T);

	printf("黑高为%d\n", Blackhheight(T));

	T = Delete_RBT(T);

	return 0;
}

结果

10.000000 22.000000 37.000000 40.000000 52.000000 60.000000 70.000000 72.000000 75.000000 160.000000 170.000000 172.000000 175.000000 
                                52                               
                22                               75               
        10               37               70             $172      
     #       #       #    $ 40    $ 60    $ 72     170      175   
   #   #   #   #   #   #   #   #   #   #   #   #$160   #   #   #

                                52                               
                22                               75               
        10               37               70             $172      
     #       #       #    $ 40       #    $ 72     170      175   
   #   #   #   #   #   #   #   #   #   #   #   #$160   #   #   #

                                52                               
                22                               75               
        10               37               72             $172      
     #       #       #    $ 40       #       #     170      175   
   #   #   #   #   #   #   #   #   #   #   #   #$160   #   #   #

                52               
        22              172       
    10       37     $160     175   
   #   #   #$ 40  75  170    #   #
黑高为3

数据结构的扩张

顺序统计树

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

typedef struct OSTreeNode
{
	bool color;			//节点颜色	1-红		0-黑
	double element;		//节点元素
	OSTreeNode* lchild;	//左孩子
	OSTreeNode* rchild;	//右孩子
	OSTreeNode* parent;	//父亲
	int size;			//子树的大小
}OSTreeNode;


//输出顺序统计树所有节点		中序遍历
void InOrder_OST(OSTreeNode* t)
{
	if (t->lchild != NULL && t->rchild != NULL)	//不为哨兵节点
	{
		InOrder_OST(t->lchild);
		printf("%lf ", t->element);
		printf("|%d ", t->size);
		InOrder_OST(t->rchild);
	}
}


//查找二叉搜索树中节点	未找到则返回哨兵节点
//递归方法
OSTreeNode* Search_OST(OSTreeNode* t, double a)
{
	if ((t->lchild == NULL && t->rchild == NULL) || t->element == a)	//哨兵节点或者找到
	{
		return t;
	}
	else if (t->element < a)
	{
		return Search_OST(t->rchild, a);
	}
	else
	{
		return Search_OST(t->lchild, a);
	}
}

//循环方法
OSTreeNode* Search_Iterative_OST(OSTreeNode* t, double a)
{
	OSTreeNode* p;
	p = t;
	while (!(p->lchild == NULL && p->rchild == NULL) && p->element != a)
	{
		if (p->element < a)
		{
			p = p->rchild;
		}
		else
		{
			p = p->lchild;
		}
	}
	return p;
}


//寻找顺序统计树中最小元素
OSTreeNode* Findmin_OST(OSTreeNode* t)
{
	OSTreeNode* p;
	p = t;
	while (p->lchild->lchild != NULL && p->lchild->rchild != NULL)	//遇到左孩子为哨兵节点停止
	{
		p = p->lchild;
	}
	return p;
}

//寻找顺序统计树中最大元素
OSTreeNode* Findbig_OST(OSTreeNode* t)
{
	OSTreeNode* p;
	p = t;
	while (p->rchild->lchild != NULL && p->rchild->rchild != NULL)
	{
		p = p->rchild;
	}
	return p;
}


//寻找二叉搜树中元素的后驱
OSTreeNode* Successor_BST(OSTreeNode* x)
{
	if (x->lchild == NULL && x->rchild == NULL)		//哨兵节点
	{
		printf("节点为空，其后驱为NULL");
	}
	if (x->rchild->lchild != NULL && x->rchild->rchild != NULL)		//x的右节点不为哨兵节点
	{
		return Findmin_OST(x->rchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的左孩子
		while ((x->parent->lchild != NULL && x->parent->rchild != NULL) && x->parent->rchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}

//寻找二叉搜树中元素的前驱
OSTreeNode* Predecessor_OST(OSTreeNode* x)
{
	if (x->lchild == NULL && x->rchild == NULL)		//哨兵节点
	{
		printf("节点为空，其前驱为NULL");
		return x;
	}
	if (x->lchild->lchild != NULL && x->lchild->rchild != NULL)		//x的左节点为哨兵节点
	{
		return Findbig_OST(x->lchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的右孩子
		while ((x->parent->lchild != NULL && x->parent->rchild != NULL) && x->parent->lchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}


//左旋	将x节点的右孩子y提到x的位置，x再作为y的左孩子
OSTreeNode* LeftRotate_OST(OSTreeNode* t, OSTreeNode* x)
{
	OSTreeNode* nilnode;
	nilnode = t->parent;
	OSTreeNode* y;
	y = x->rchild;
	if (y != nilnode)
	{
		x->rchild = y->lchild;
		if (y->lchild != nilnode)			//y->lchild的父亲指向x
		{
			y->lchild->parent = x;
		}

		y->parent = x->parent;
		if (x == t)						//x为根节点
		{
			t = y;
		}
		else if (x == x->parent->lchild)	//x为左孩子
		{
			x->parent->lchild = y;
		}
		else							//x为右孩子
		{
			x->parent->rchild = y;
		}

		y->lchild = x;
		x->parent = y;

		//重新计算左旋后子树的规模
		y->size = x->size;
		x->size = x->lchild->size + x->rchild->size + 1;
	}
	else
	{
		printf("%lf节点无右孩子，无法左旋\n", x->element);
	}
	return t;
}

//右旋	将y节点的左孩子x提到y的位置，y再作为x的右孩子
OSTreeNode* RightRotate_OST(OSTreeNode* t, OSTreeNode* y)
{
	OSTreeNode* nilnode;
	nilnode = t->parent;
	OSTreeNode* x;
	x = y->lchild;
	if (x != nilnode)
	{
		y->lchild = x->rchild;
		if (x->rchild != nilnode)			//x->rchild的父亲指向y
		{
			x->rchild->parent = y;
		}

		x->parent = y->parent;
		if (y == t)						//y为根节点
		{
			t = x;
		}
		else if (y == y->parent->lchild)	//y为左孩子
		{
			y->parent->lchild = x;
		}
		else							//y为右孩子
		{
			y->parent->rchild = x;
		}

		x->rchild = y;
		y->parent = x;

		//重新计算右旋后子树的规模
		x->size = y->size;
		y->size = y->lchild->size + y->rchild->size + 1;
	}
	else
	{
		printf("%lf节点无左孩子，无法右旋\n", y->element);
	}
	return t;
}


//在顺序统计树中插入节点
//顺序统计树插入节点修正
OSTreeNode* Insert_Fixup_OST(OSTreeNode* t, OSTreeNode* x)
{
	//若x父亲为红色节点，则进入矫正顺序统计树操作
	while (x != t && x->parent->color == 1)
	{
		OSTreeNode* y;
		//情况1：x的父亲是x祖父的左孩子
		if (x->parent == x->parent->parent->lchild)
		{
			y = x->parent->parent->rchild;	//x的叔叔，即x的祖父的右孩子
			//情况1.1：y为红色节点
			//操作：x与y换成黑色，祖父换成红色
			//结果：x的祖父的黑高+1，其他节点黑高不变
			if (y->color == 1)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;		//x变为其祖父继续迭代
			}
			else
			{
				//情况1.2：y为黑色节点，x为其父亲的右孩子
				//操作：左旋x的父亲，将x提至x的父亲的位置
				//结果：转化为情况1.3
				if (x == x->parent->rchild)
				{
					x = x->parent;
					t = LeftRotate_OST(t, x);
				}
				//情况1.3：y为黑色节点，x为其父亲的左孩子
				//操作：右旋x的祖父，将x的父亲提至x的祖父的位置，再改变x的颜色
				//结果：黑高都不变
				x->parent->color = 0;
				x->parent->parent->color = 1;
				t = RightRotate_OST(t, x->parent->parent);
			}
		}
		//情况2：x的父亲是x祖父的右孩子
		else
		{
			y = x->parent->parent->lchild;	//x的叔叔，即x的祖父的左孩子
			//情况2.1：y为红色节点
			//操作：x与y换成黑色，祖父换成红色
			//结果：x的祖父的黑高+1，其他节点黑高不变
			if (y->color == 1)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;		//x变为其祖父继续迭代
			}
			else
			{
				//情况2.2：y为黑色节点，x为其父亲的左孩子
				//操作：右旋x的父亲，将x提至x的父亲的位置
				//结果：转化为情况2.3
				if (x == x->parent->lchild)
				{
					x = x->parent;
					t = RightRotate_OST(t, x);
				}
				//情况2.3：y为黑色节点，x为其父亲的右孩子
				//操作：左旋x的祖父，将x的父亲提至x的祖父的位置，再改变x的颜色
				//结果：黑高都不变
				x->parent->color = 0;
				x->parent->parent->color = 1;
				t = LeftRotate_OST(t, x->parent->parent);
			}
		}
	}
	t->color = 0;
	return t;
}

OSTreeNode* Insertnode_OST(OSTreeNode* t, double a)
{
	OSTreeNode* nilnode;
	nilnode = t->parent;
	bool element_exist = 0;
	OSTreeNode* y, * p;
	y = NULL;
	p = t;
	//寻找待插入位置的父节点y
	while (p != nilnode && !element_exist)
	{
		y = p;
		y->size++;
		if (a > p->element)
		{
			p = p->rchild;
		}
		else if (a < p->element)
		{
			p = p->lchild;
		}
		else
		{
			printf("%lf 已在顺序统计树中\n", a);
			element_exist = 1;
		}
	}

	if (!element_exist)
	{
		//插入节点
		OSTreeNode* x;
		x = (OSTreeNode*)malloc(sizeof(OSTreeNode));
		x->color = 1;	//赋为红色节点
		x->element = a;
		x->lchild = nilnode;
		x->rchild = nilnode;
		x->parent = y;
		x->size = 1;

		if (y == nilnode)
		{
			t = x;
		}
		else
		{
			if (y->element < a)
			{
				y->rchild = x;
			}
			else
			{
				y->lchild = x;
			}
			t = Insert_Fixup_OST(t, x);
		}

	}
	return t;
}


//在顺序统计树中删除节点
// 顺序统计树删除节点修正
OSTreeNode* Delete_Fixup_OST(OSTreeNode* t, OSTreeNode* x)
{
	//若x父亲为黑色节点，则进入矫正顺序统计树操作
	while (x != t && x->color == 0)
	{
		//情况1：x是其父亲的左孩子
		if (x == x->parent->lchild)
		{
			OSTreeNode* w;
			w = x->parent->rchild;		//x的兄弟,即x的父亲的右孩子
			//情况1.1：w为红色节点
			//操作：x的父亲与w换色，x的父亲左旋
			//结果：转化为其他情况
			if (w->color == 1)
			{
				w->color = 0;
				x->parent->color = 1;
				t = LeftRotate_OST(t, x->parent);
				w = x->parent->rchild;		//保持w为x的兄弟,即x的父亲的右孩子
			}
			else
			{
				//情况1.2：w与w所有孩子都为黑色节点
				//操作：将w颜色变红，再将x上移讨论原x的父亲的情况
				//结果：w子树黑高 -1
				if (w->lchild->color == 0 && w->rchild->color == 0)
				{
					w->color = 1;
					x = x->parent;
				}
				//情况1.3：w与w的右孩子都为黑色节点，w的左孩子为红色节点
				//操作：将w与w左孩子换色，右旋w
				//结果：转化为情况1.4
				else if (w->rchild->color == 0)
				{
					w->lchild->color = 0;
					w->color = 1;
					t = RightRotate_OST(t, w);
					w = x->parent->rchild;		//保持w为x的兄弟,即x的父亲的右孩子
				}
				//情况1.4：w与为黑色节点，w的右孩子为红色节点，w左孩子为任意颜色
				//操作：将x的父亲与w换色，w的右孩子变黑，左旋x的父亲
				//结果：原x的子树黑高 +1
				else
				{
					w->color = x->parent->color;
					x->parent->color = 0;
					w->rchild->color = 0;
					t = LeftRotate_OST(t, x->parent);
					x = t;		//退出循环
				}
			}
		}
		//情况2：x是其父亲的右孩子
		else
		{
			OSTreeNode* w;
			w = x->parent->lchild;		//x的兄弟,即x的父亲的左孩子
			//情况2.1：w为红色节点
			//操作：x的父亲与w换色，x的父亲右旋
			//结果：转化为其他情况
			if (w->color == 1)
			{
				w->color = 0;
				x->parent->color = 1;
				t = RightRotate_OST(t, x->parent);
				w = x->parent->lchild;		//保持w为x的兄弟,即x的父亲的左孩子
			}
			else
			{
				//情况2.2：w与w所有孩子都为黑色节点
				//操作：将w颜色变红，再将x上移讨论原x的父亲的情况
				//结果：w子树黑高 -1
				if (w->lchild->color == 0 && w->rchild->color == 0)
				{
					w->color = 1;
					x = x->parent;
				}
				//情况2.3：w与w的左孩子都为黑色节点，w的右孩子为红色节点
				//操作：将w与w右孩子换色，左旋w
				//结果：转化为情况1.4
				else if (w->lchild->color == 0)
				{
					w->rchild->color = 0;
					w->color = 1;
					t = LeftRotate_OST(t, w);
					w = x->parent->lchild;		//保持w为x的兄弟,即x的父亲的右孩子
				}
				//情况2.4：w与为黑色节点，w的左孩子为红色节点，w右孩子为任意颜色
				//操作：将x的父亲与w换色，w的左孩子变黑，右旋x的父亲
				//结果：原x的子树黑高 +1
				else
				{
					w->color = x->parent->color;
					x->parent->color = 0;
					w->lchild->color = 0;
					t = RightRotate_OST(t, x->parent);
					x = t;		//退出循环
				}
			}
		}
	}
	x->color = 0;		//若节点为红，转化为黑节点报告该子树黑高
	return t;
}

//子树替换	不考虑大小关系	q代替p的位置，p的各个指针不变
OSTreeNode* Transplant_OSTree(OSTreeNode* t, OSTreeNode* p, OSTreeNode* q)
{
	if (p == t)					//p为根节点时
	{
		t = q;
	}
	else if (p == p->parent->lchild)	//p为左孩子时
	{
		p->parent->lchild = q;
	}
	else								//p为右孩子时
	{
		p->parent->rchild = q;
	}

	q->parent = p->parent;

	return t;
}

OSTreeNode* Deletenode_OST(OSTreeNode* t, double a)
{
	OSTreeNode* nilnode;
	nilnode = t->parent;

	OSTreeNode* z;
	z = Search_Iterative_OST(t, a);
	if (z == nilnode)
	{
		printf("%lf不存在，无法删除", a);
	}
	else
	{
		OSTreeNode* x;
		bool deletenode_color = z->color;
		if (z->lchild == nilnode)
		{
			x = z->rchild;
			t = Transplant_OSTree(t, z, x);
			//x子树的大小不变
		}
		else if (z->rchild == nilnode)
		{
			x = z->lchild;
			t = Transplant_OSTree(t, z, x);
			//x子树的大小不变
		}
		else
		{
			OSTreeNode* y;
			y = Successor_BST(z);
			x = y->rchild;
			deletenode_color = y->color;
			if (y->parent == z)		//z的后继为z的孩子
			{
				x->parent = y;		//防止后续修正顺序统计树颜色操作，因为哨兵节点无父节点指针出错
			}
			else
			{
				t = Transplant_OSTree(t, y, x);
				//x子树的大小不变
				y->rchild = z->rchild;
				y->rchild->parent = y;
			}
			t = Transplant_OSTree(t, z, y);
			y->size = z->size;
			y->lchild = z->lchild;
			y->lchild->parent = y;
			y->color = z->color;	//继承删除位置的颜色
		}

		OSTreeNode* p;
		p = x->parent;
		while (p != nilnode)
		{
			p->size--;
			p = p->parent;
		}

		if (deletenode_color == 0)
		{
			t = Delete_Fixup_OST(t, x);
		}


		free(z);
	}
	return t;
}


//随机构建顺序统计树
OSTreeNode* Random_Bulid_OST(double* n, int num)
{
	OSTreeNode* t;
	t = NULL;
	if (num > 0)
	{
		int random_num;
		random_num = rand() % num;

		//哨兵黑节点，只有黑色，标记为其余指针都为空
		OSTreeNode* nilnode;
		nilnode = (OSTreeNode*)malloc(sizeof(OSTreeNode));
		nilnode->color = 0;
		nilnode->lchild = NULL;
		nilnode->rchild = NULL;
		nilnode->parent = NULL;
		nilnode->size = 0;

		t = (OSTreeNode*)malloc(sizeof(OSTreeNode));
		t->element = n[random_num];
		t->lchild = nilnode;
		t->rchild = nilnode;
		t->parent = nilnode;	//此处储存nilnode的地址，方便以后直接取出
		t->color = 0;
		t->size = 1;

		// 将已使用的元素移至数组末尾
		double temp;
		temp = n[random_num];
		n[random_num] = n[num - 1];
		n[num - 1] = temp;

		for (int i = 1; i < num; i++)
		{
			random_num = rand() % (num - i);
			t = Insertnode_OST(t, n[random_num]);

			// 将已使用的元素移至数组末尾
			temp = n[random_num];
			n[random_num] = n[num - i - 1];
			n[num - i - 1] = temp;
		}
	}

	return t;
}

//删除顺序统计树
OSTreeNode* Delete_OST(OSTreeNode* t)
{
	if (t->lchild != NULL && t->rchild != NULL)
	{
		t->lchild = Delete_OST(t->lchild);		//哨兵节点会自动删除
		t->rchild = Delete_OST(t->rchild);
		free(t);
		return NULL;
	}
}


//输出顺序统计树中的第i个元素的节点
OSTreeNode* Select_OS(OSTreeNode* t, int i)
{
	if (i <= t->size && i >= 0)
	{
		int rank = t->lchild->size + 1;
		if (i == rank)
		{
			return t;
		}
		else if (i < rank)
		{
			return Select_OS(t->lchild, i);
		}
		else
		{
			return Select_OS(t->rchild, i - rank);
		}
	}
	else
	{
		printf("选择范围超出\n");
	}
}

//确定元素的秩
int Rank_OS(OSTreeNode* t, double a)
{
	OSTreeNode* x;
	x = Search_Iterative_OST(t, a);
	if (x == t->parent)
	{
		printf("顺序统计树无 %g 结点， 返回 -1\n", a);
		return -1;
	}
	else
	{
		int r;
		OSTreeNode* y;
		r = x->lchild->size + 1;
		y = x;
		while (y != t)
		{
			if (y == y->parent->rchild)
			{
				r = r + y->parent->lchild->size + 1;
			}
			y = y->parent;
		}
		return r;
	}
}


int max(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

//输出顺序统计树节点的黑高
int Blackhheight(OSTreeNode* t)
{
	if (t->lchild == NULL && t->rchild == NULL)		//表示为哨兵节点
	{
		return 0;
	}
	else if (t->color == 1)
	{
		int h1 = Blackhheight(t->lchild);
		int h2 = Blackhheight(t->rchild);
		if (h1 != h2)
		{
			printf("黑高不匹配，算法估计有问题");
		}
		return (max(h1, h2));
	}
	else
	{
		int h1 = Blackhheight(t->lchild);
		int h2 = Blackhheight(t->rchild);
		if (h1 != h2)
		{
			printf("黑高不匹配，算法估计有问题");
		}
		return (max(h1, h2) + 1);
	}
}


//求树的高度
int HighBTree(OSTreeNode* t)
{
	if (t->lchild == NULL && t->rchild == NULL)	//表示为哨兵节点
	{
		return 0;
	}
	else
	{
		return (max(HighBTree(t->lchild), HighBTree(t->rchild)) + 1);
	}
}

//链队列结构类型
typedef struct QueueNode
{
	OSTreeNode* rbtreenode;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue
{
	QueueNode* front;//队头指针
	QueueNode* rear;//队尾指针
}LinkQueue;

LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->rbtreenode = NULL;
	return q;
}

//空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//入队
void EnLinkQueue(LinkQueue* q, OSTreeNode* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->rbtreenode = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

//出队
OSTreeNode* DeLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		OSTreeNode* rbtreenode;
		QueueNode* queuenode;
		queuenode = q->front->next;
		rbtreenode = queuenode->rbtreenode;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return rbtreenode;
	}
}

//层次展示二叉树
void LikeBTree(OSTreeNode* t)
{
	if (t == NULL)
	{
		printf("树空\n");
	}
	else
	{
		LinkQueue* q;
		OSTreeNode* node;
		int high = 1;
		int sumh;
		int highmax;
		int mark = 0;

		OSTreeNode* nilnode;
		nilnode = t->parent;

		OSTreeNode* emptynode;
		emptynode = (OSTreeNode*)malloc(sizeof(OSTreeNode));
		emptynode->color = 0;
		emptynode->lchild = nilnode;
		emptynode->rchild = nilnode;

		highmax = HighBTree(t);
		q = InitLinkQueue();	//创建树节点队列

		EnLinkQueue(q, t);
		while (EmptyLinkQueue(q) == 1 && high <= highmax)		//队不为空
		{
			node = DeLinkQueue(q);

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补前面空缺
			{
				printf("  ");
			}

			if (node == emptynode)
			{
				printf("   #");
			}
			else
			{
				if (node->color == 0)
				{
					printf("%4.0lf ", node->element);
				}
				else
				{
					printf("$%3.0lf", node->element);
				}
			}

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补后面空缺
			{
				printf("  ");
			}

			if (node->lchild != nilnode)
			{
				EnLinkQueue(q, node->lchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}
			if (node->rchild != nilnode)
			{
				EnLinkQueue(q, node->rchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}

			mark++;
			sumh = pow(2, high) - 1;
			if (mark >= sumh)		//换层
			{
				high++;
				printf("\n");
			}
		}
		free(emptynode);
		free(q->front);
		free(q);
	}
}


//交换数组i与j
void Swap_Array_ij(double* a, int num, int i, int j)
{
	double t;
	t = a[i];
	a[i] = a[j];
	a[j] = t;
}

//选择算法
int Random_Partition(double* a, int p, int r)
{
	//随机主元
	int random_num = rand() % (r - p + 1) + p;
	double x = a[random_num];
	Swap_Array_ij(a, r - p + 1, random_num, r);

	int i = p - 1;
	for (int j = p; j < r; j++)
	{
		if (a[j] <= x)
		{
			i++;
			//交换i与j
			Swap_Array_ij(a, r - p + 1, i, j);
		}
	}
	//交换i+1与r
	Swap_Array_ij(a, r - p + 1, i + 1, r);

	return i + 1;
}


double Randomized_Select(double* a, int p, int r, int i)
{
	if (p == r)
	{
		return a[p];
	}
	else
	{
		int q;
		q = Random_Partition(a, p, r);
		int k = q - p + 1;

		if (i == k)
		{
			return a[q];
		}
		else if (i < k)
		{
			return Randomized_Select(a, p, q - 1, i);
		}
		else
		{
			return Randomized_Select(a, q + 1, r, i - k);
		}
	}
}


//随机生成数组
double* Random_Array(int num, int maxnum)
{
	double* a;
	a = (double*)malloc(sizeof(double) * num);
	for (int i = 0; i < num; i++)
	{
		a[i] = rand() % maxnum;
	}
	return a;
}


int main()
{
	double n[] = { 10, 22, 37, 40, 52, 60, 70, 72, 75, 160, 170, 172, 175 };
	int num = sizeof(n) / sizeof(n[0]);

	OSTreeNode* T;
	T = Random_Bulid_OST(n, num);
	printf("\n");
	InOrder_OST(T);
	printf("\n");
	LikeBTree(T);
	printf("\n");
	printf("第%d个顺序统计量为 %g\n", 9, Select_OS(T, 9)->element);
	printf("顺序统计树中元素60的秩为 %d \n", Rank_OS(T, 60));
	T = Deletenode_OST(T, 60);
	printf("\n");
	LikeBTree(T);
	InOrder_OST(T);
	printf("\n");
	printf("第%d个顺序统计量为 %g\n", 9, Select_OS(T, 9)->element);
	printf("顺序统计树中元素60的秩为 %d \n", Rank_OS(T, 60));

	T = Delete_OST(T);


	num = 10000000;		//数组大小
	int oeder_statistic = num / 2;

	clock_t start, finish;
	double  duration;

	//生成数组
	double* a;
	a = (double*)malloc(sizeof(double) * num);
	for (int i = 0; i < num; i++)
	{
		a[i] = i;
	}

	printf("顺序统计树：\n");
	start = clock();
	T = Random_Bulid_OST(a, num);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("构造顺序统计树消耗的时间:  %f s\n", duration);
	start = clock();
	printf("数组第 %d 个顺序统计量为 %g\n", oeder_statistic, Select_OS(T, oeder_statistic)->element);
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("寻找顺序统计量消耗的时间:  %f s\n", duration);

	printf("随机选择：\n");
	start = clock();
	printf("数组第 %d 个顺序统计量为 %g\n", oeder_statistic, Randomized_Select(a, 0, num - 1, oeder_statistic));
	finish = clock();
	duration = (double)(finish - start) / CLOCKS_PER_SEC;
	printf("随机选择消耗的时间:  %f s\n", duration);

	free(a);
	Delete_OST(T);

	return 0;
}

10.000000 |1 22.000000 |4 37.000000 |2 40.000000 |1 52.000000 |13 60.000000 |1 70.000000 |3 72.000000 |1 75.000000 |8 160.000000 |1 170.000000 |2 172.000000 |4 175.000000 |1 
                                52                               
                22                               75               
        10               37               70             $172      
     #       #       #    $ 40    $ 60    $ 72     170      175   
   #   #   #   #   #   #   #   #   #   #   #   #$160   #   #   #

第9个顺序统计量为 75
顺序统计树中元素60的秩为 6 

                                52                               
                22                               75               
        10               37               70             $172      
     #       #       #    $ 40       #    $ 72     170      175   
   #   #   #   #   #   #   #   #   #   #   #   #$160   #   #   #
10.000000 |1 22.000000 |4 37.000000 |2 40.000000 |1 52.000000 |12 70.000000 |2 72.000000 |1 75.000000 |7 160.000000 |1 170.000000 |2 172.000000 |4 175.000000 |1 
第9个顺序统计量为 160
顺序统计树无 60 结点， 返回 -1
顺序统计树中元素60的秩为 -1 
顺序统计树：
构造顺序统计树消耗的时间:  12.046391 s
数组第 5000000 个顺序统计量为 5e+06
寻找顺序统计量消耗的时间:  0.000001 s
随机选择：
数组第 5000000 个顺序统计量为 5e+06
随机选择消耗的时间:  0.171409 s

区间树

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>


typedef struct IntervalTreeNode
{
	bool color;			//节点颜色	1-红		0-黑
	double lowendpoint;		//左端点元素
	double highendpoint;		//右端点元素
	IntervalTreeNode* lchild;	//左孩子
	IntervalTreeNode* rchild;	//右孩子
	IntervalTreeNode* parent;	//父亲
	double max;		//节点元素
}IntervalTreeNode;


//判断两个节点是否重叠
bool Overlap_Interval(IntervalTreeNode* a, IntervalTreeNode* b)
{
	//两个节点不重叠
	if (a->highendpoint < b->lowendpoint || b->highendpoint < a->lowendpoint)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//搜索区间树与区间i重叠的一个节点
IntervalTreeNode* Search_Interval(IntervalTreeNode* t, double i_low, double i_high)
{
	IntervalTreeNode* nilnode;
	nilnode = t->parent;

	IntervalTreeNode* i;
	i = (IntervalTreeNode*)malloc(sizeof(IntervalTreeNode));
	i->lowendpoint = i_low;
	i->highendpoint = i_high;

	IntervalTreeNode* x;
	x = t;
	while (x != nilnode && !Overlap_Interval(i, x))
	{
		if (x->lchild != nilnode && x->lchild->max >= i_low)
		{
			x = x->lchild;
		}
		else
		{
			x = x->rchild;
		}
	}
	free(i);
	return x;
}


//输出红黑树所有节点		中序遍历
void InOrder_IT(IntervalTreeNode* t)
{
	if (t->lchild != NULL && t->rchild != NULL)	//不为哨兵节点
	{
		InOrder_IT(t->lchild);
		//printf("[ %lf , %lf ]  %lf ", t->lowendpoint, t->highendpoint, t->max);
		printf("[ %lf , %lf ]  ", t->lowendpoint, t->highendpoint);
		InOrder_IT(t->rchild);
	}
}


//查找二叉搜索树中节点	未找到则返回哨兵节点
//递归方法
IntervalTreeNode* Search_IT(IntervalTreeNode* t, double a)
{
	if ((t->lchild == NULL && t->rchild == NULL) || t->lowendpoint == a)	//哨兵节点或者找到
	{
		return t;
	}
	else if (t->lowendpoint < a)
	{
		return Search_IT(t->rchild, a);
	}
	else
	{
		return Search_IT(t->lchild, a);
	}
}

//循环方法
IntervalTreeNode* Search_Iterative_IT(IntervalTreeNode* t, double a)
{
	IntervalTreeNode* p;
	p = t;
	while (!(p->lchild == NULL && p->rchild == NULL) && p->lowendpoint != a)
	{
		if (p->lowendpoint < a)
		{
			p = p->rchild;
		}
		else
		{
			p = p->lchild;
		}
	}
	return p;
}


//寻找红黑树中最小元素
IntervalTreeNode* Findmin_IT(IntervalTreeNode* t)
{
	IntervalTreeNode* p;
	p = t;
	while (p->lchild->lchild != NULL && p->lchild->rchild != NULL)	//遇到左孩子为哨兵节点停止
	{
		p = p->lchild;
	}
	return p;
}

//寻找红黑树中最大元素
IntervalTreeNode* Findbig_IT(IntervalTreeNode* t)
{
	IntervalTreeNode* p;
	p = t;
	while (p->rchild->lchild != NULL && p->rchild->rchild != NULL)
	{
		p = p->rchild;
	}
	return p;
}


//寻找二叉搜树中元素的后驱
IntervalTreeNode* Successor_IT(IntervalTreeNode* x)
{
	if (x->lchild == NULL && x->rchild == NULL)		//哨兵节点
	{
		printf("节点为空，其后驱为NULL");
	}
	if (x->rchild->lchild != NULL && x->rchild->rchild != NULL)		//x的右节点不为哨兵节点
	{
		return Findmin_IT(x->rchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的左孩子
		while ((x->parent->lchild != NULL && x->parent->rchild != NULL) && x->parent->rchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}

//寻找二叉搜树中元素的前驱
IntervalTreeNode* Predecessor_IT(IntervalTreeNode* x)
{
	if (x->lchild == NULL && x->rchild == NULL)		//哨兵节点
	{
		printf("节点为空，其前驱为NULL");
		return x;
	}
	if (x->lchild->lchild != NULL && x->lchild->rchild != NULL)		//x的左节点为哨兵节点
	{
		return Findbig_IT(x->lchild);
	}
	else
	{
		//一直寻找x的父亲，直到x为其父亲的右孩子
		while ((x->parent->lchild != NULL && x->parent->rchild != NULL) && x->parent->lchild == x)
		{
			x = x->parent;
		}
		return x->parent;
	}
}


//计算max元素
double max(double a, double b)
{
	if (a > b)
	{
		return a;
	}
	else
	{
		return b;
	}
}

void Max_IT(IntervalTreeNode* t, IntervalTreeNode* x)
{
	IntervalTreeNode* nilnode;
	nilnode = t->parent;

	if (x->lchild != nilnode && x->rchild == nilnode)
	{
		x->max = max(x->lchild->max, x->highendpoint);
	}
	else if (x->rchild != nilnode && x->lchild == nilnode)
	{
		x->max = max(x->rchild->max, x->highendpoint);
	}
	else
	{
		x->max = max(max(x->lchild->max, x->rchild->max), x->highendpoint);
	}
}


//左旋	将x节点的右孩子y提到x的位置，x再作为y的左孩子
IntervalTreeNode* LeftRotate_IT(IntervalTreeNode* t, IntervalTreeNode* x)
{
	IntervalTreeNode* nilnode;
	nilnode = t->parent;
	IntervalTreeNode* y;
	y = x->rchild;
	if (y != nilnode)
	{
		x->rchild = y->lchild;
		if (y->lchild != nilnode)			//y->lchild的父亲指向x
		{
			y->lchild->parent = x;
		}

		y->parent = x->parent;
		if (x == t)						//x为根节点
		{
			t = y;
		}
		else if (x == x->parent->lchild)	//x为左孩子
		{
			x->parent->lchild = y;
		}
		else							//x为右孩子
		{
			x->parent->rchild = y;
		}

		y->lchild = x;
		x->parent = y;

		Max_IT(t, x);
		Max_IT(t, y);
	}
	else
	{
		printf("[%lf , %lf]节点无右孩子，无法左旋\n", x->lowendpoint, x->highendpoint);
	}
	return t;
}

//右旋	将y节点的左孩子x提到y的位置，y再作为x的右孩子
IntervalTreeNode* RightRotate_IT(IntervalTreeNode* t, IntervalTreeNode* y)
{
	IntervalTreeNode* nilnode;
	nilnode = t->parent;
	IntervalTreeNode* x;
	x = y->lchild;
	if (x != nilnode)
	{
		y->lchild = x->rchild;
		if (x->rchild != nilnode)			//x->rchild的父亲指向y
		{
			x->rchild->parent = y;
		}

		x->parent = y->parent;
		if (y == t)						//y为根节点
		{
			t = x;
		}
		else if (y == y->parent->lchild)	//y为左孩子
		{
			y->parent->lchild = x;
		}
		else							//y为右孩子
		{
			y->parent->rchild = x;
		}

		x->rchild = y;
		y->parent = x;

		Max_IT(t, y);
		Max_IT(t, x);
	}
	else
	{
		printf("[%lf , %lf]节点无左孩子，无法右旋\n", y->lowendpoint, y->highendpoint);
	}
	return t;
}


//在红黑树中插入节点
//红黑树插入节点修正
IntervalTreeNode* Insert_Fixup_IT(IntervalTreeNode* t, IntervalTreeNode* x)
{
	//若x父亲为红色节点，则进入矫正红黑树操作
	while (x != t && x->parent->color == 1)
	{
		IntervalTreeNode* y;
		//情况1：x的父亲是x祖父的左孩子
		if (x->parent == x->parent->parent->lchild)
		{
			y = x->parent->parent->rchild;	//x的叔叔，即x的祖父的右孩子
			//情况1.1：y为红色节点
			//操作：x与y换成黑色，祖父换成红色
			//结果：x的祖父的黑高+1，其他节点黑高不变
			if (y->color == 1)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;		//x变为其祖父继续迭代
			}
			else
			{
				//情况1.2：y为黑色节点，x为其父亲的右孩子
				//操作：左旋x的父亲，将x提至x的父亲的位置
				//结果：转化为情况1.3
				if (x == x->parent->rchild)
				{
					x = x->parent;
					t = LeftRotate_IT(t, x);
				}
				//情况1.3：y为黑色节点，x为其父亲的左孩子
				//操作：右旋x的祖父，将x的父亲提至x的祖父的位置，再改变x的颜色
				//结果：黑高都不变
				x->parent->color = 0;
				x->parent->parent->color = 1;
				t = RightRotate_IT(t, x->parent->parent);
			}
		}
		//情况2：x的父亲是x祖父的右孩子
		else
		{
			y = x->parent->parent->lchild;	//x的叔叔，即x的祖父的左孩子
			//情况2.1：y为红色节点
			//操作：x与y换成黑色，祖父换成红色
			//结果：x的祖父的黑高+1，其他节点黑高不变
			if (y->color == 1)
			{
				x->parent->color = 0;
				y->color = 0;
				x->parent->parent->color = 1;
				x = x->parent->parent;		//x变为其祖父继续迭代
			}
			else
			{
				//情况2.2：y为黑色节点，x为其父亲的左孩子
				//操作：右旋x的父亲，将x提至x的父亲的位置
				//结果：转化为情况2.3
				if (x == x->parent->lchild)
				{
					x = x->parent;
					t = RightRotate_IT(t, x);
				}
				//情况2.3：y为黑色节点，x为其父亲的右孩子
				//操作：左旋x的祖父，将x的父亲提至x的祖父的位置，再改变x的颜色
				//结果：黑高都不变
				x->parent->color = 0;
				x->parent->parent->color = 1;
				t = LeftRotate_IT(t, x->parent->parent);
			}
		}
	}
	t->color = 0;
	return t;
}

IntervalTreeNode* Insertnode_IT(IntervalTreeNode* t, double a, double b)
{
	IntervalTreeNode* nilnode;
	nilnode = t->parent;
	bool element_exist = 0;
	IntervalTreeNode* y, * p;
	y = NULL;
	p = t;
	//寻找待插入位置的父节点y
	while (p != nilnode && !element_exist)
	{
		y = p;
		if (a > p->lowendpoint)
		{
			p = p->rchild;
		}
		else if (a < p->lowendpoint)
		{
			p = p->lchild;
		}
		else
		{
			printf("左端点 %lf 已在红黑树中\n", a);
			element_exist = 1;
		}
	}

	if (!element_exist)
	{
		//区间顺序
		if (a > b)
		{
			int t;
			t = b;
			b = a;
			a = t;
		}

		//插入节点
		IntervalTreeNode* x;
		x = (IntervalTreeNode*)malloc(sizeof(IntervalTreeNode));
		x->color = 1;	//赋为红色节点
		x->lowendpoint = a;
		x->highendpoint = b;
		x->lchild = nilnode;
		x->rchild = nilnode;
		x->parent = y;
		x->max = b;

		if (y == nilnode)
		{
			t = x;
		}
		else
		{
			if (y->lowendpoint < a)
			{
				y->rchild = x;
			}
			else
			{
				y->lchild = x;
			}

			while (y != nilnode)
			{
				Max_IT(t, y);
				y = y->parent;
			}

			t = Insert_Fixup_IT(t, x);
		}

	}
	return t;
}


//在红黑树中删除节点
// 红黑树删除节点修正
IntervalTreeNode* Delete_Fixup_IT(IntervalTreeNode* t, IntervalTreeNode* x)
{
	//若x父亲为黑色节点，则进入矫正红黑树操作
	while (x != t && x->color == 0)
	{
		//情况1：x是其父亲的左孩子
		if (x == x->parent->lchild)
		{
			IntervalTreeNode* w;
			w = x->parent->rchild;		//x的兄弟,即x的父亲的右孩子
			//情况1.1：w为红色节点
			//操作：x的父亲与w换色，x的父亲左旋
			//结果：转化为其他情况
			if (w->color == 1)
			{
				w->color = 0;
				x->parent->color = 1;
				t = LeftRotate_IT(t, x->parent);
				w = x->parent->rchild;		//保持w为x的兄弟,即x的父亲的右孩子
			}
			else
			{
				//情况1.2：w与w所有孩子都为黑色节点
				//操作：将w颜色变红，再将x上移讨论原x的父亲的情况
				//结果：w子树黑高 -1
				if (w->lchild->color == 0 && w->rchild->color == 0)
				{
					w->color = 1;
					x = x->parent;
				}
				//情况1.3：w与w的右孩子都为黑色节点，w的左孩子为红色节点
				//操作：将w与w左孩子换色，右旋w
				//结果：转化为情况1.4
				else if (w->rchild->color == 0)
				{
					w->lchild->color = 0;
					w->color = 1;
					t = RightRotate_IT(t, w);
					w = x->parent->rchild;		//保持w为x的兄弟,即x的父亲的右孩子
				}
				//情况1.4：w与为黑色节点，w的右孩子为红色节点，w左孩子为任意颜色
				//操作：将x的父亲与w换色，w的右孩子变黑，左旋x的父亲
				//结果：原x的子树黑高 +1
				else
				{
					w->color = x->parent->color;
					x->parent->color = 0;
					w->rchild->color = 0;
					t = LeftRotate_IT(t, x->parent);
					x = t;		//退出循环
				}
			}
		}
		//情况2：x是其父亲的右孩子
		else
		{
			IntervalTreeNode* w;
			w = x->parent->lchild;		//x的兄弟,即x的父亲的左孩子
			//情况2.1：w为红色节点
			//操作：x的父亲与w换色，x的父亲右旋
			//结果：转化为其他情况
			if (w->color == 1)
			{
				w->color = 0;
				x->parent->color = 1;
				t = RightRotate_IT(t, x->parent);
				w = x->parent->lchild;		//保持w为x的兄弟,即x的父亲的左孩子
			}
			else
			{
				//情况2.2：w与w所有孩子都为黑色节点
				//操作：将w颜色变红，再将x上移讨论原x的父亲的情况
				//结果：w子树黑高 -1
				if (w->lchild->color == 0 && w->rchild->color == 0)
				{
					w->color = 1;
					x = x->parent;
				}
				//情况2.3：w与w的左孩子都为黑色节点，w的右孩子为红色节点
				//操作：将w与w右孩子换色，左旋w
				//结果：转化为情况1.4
				else if (w->lchild->color == 0)
				{
					w->rchild->color = 0;
					w->color = 1;
					t = LeftRotate_IT(t, w);
					w = x->parent->lchild;		//保持w为x的兄弟,即x的父亲的右孩子
				}
				//情况2.4：w与为黑色节点，w的左孩子为红色节点，w右孩子为任意颜色
				//操作：将x的父亲与w换色，w的左孩子变黑，右旋x的父亲
				//结果：原x的子树黑高 +1
				else
				{
					w->color = x->parent->color;
					x->parent->color = 0;
					w->lchild->color = 0;
					t = RightRotate_IT(t, x->parent);
					x = t;		//退出循环
				}
			}
		}
	}
	x->color = 0;		//若节点为红，转化为黑节点报告该子树黑高
	return t;
}

//子树替换	不考虑大小关系	q代替p的位置，p的各个指针不变
IntervalTreeNode* Transplant_IntervalTree(IntervalTreeNode* t, IntervalTreeNode* p, IntervalTreeNode* q)
{
	if (p == t)					//p为根节点时
	{
		t = q;
	}
	else if (p == p->parent->lchild)	//p为左孩子时
	{
		p->parent->lchild = q;
	}
	else								//p为右孩子时
	{
		p->parent->rchild = q;
	}
	q->parent = p->parent;

	return t;
}

IntervalTreeNode* Deletenode_IT(IntervalTreeNode* t, double a)
{
	IntervalTreeNode* nilnode;
	nilnode = t->parent;

	IntervalTreeNode* z;
	z = Search_Iterative_IT(t, a);
	if (z == nilnode)
	{
		printf("%lf不存在，无法删除", a);
	}
	else
	{
		IntervalTreeNode* x;
		bool deletenode_color = z->color;
		if (z->lchild == nilnode)
		{
			x = z->rchild;
			t = Transplant_IntervalTree(t, z, x);
			//x子树的max元素不变
		}
		else if (z->rchild == nilnode)
		{
			x = z->lchild;
			t = Transplant_IntervalTree(t, z, x);
			//x子树的max元素不变
		}
		else
		{
			IntervalTreeNode* y;
			y = Successor_IT(z);
			x = y->rchild;
			deletenode_color = y->color;
			if (y->parent == z)		//z的后继为z的孩子
			{
				x->parent = y;		//防止后续修正红黑树颜色操作，因为哨兵节点无父节点指针出错
			}
			else
			{
				t = Transplant_IntervalTree(t, y, x);
				//x子树的max元素不变
				y->rchild = z->rchild;
				y->rchild->parent = y;
			}
			t = Transplant_IntervalTree(t, z, y);
			y->lchild = z->lchild;
			y->lchild->parent = y;
			y->color = z->color;	//继承删除位置的颜色
			Max_IT(t, y);			//修改y的max元素
		}

		IntervalTreeNode* p;
		p = x->parent;
		while (p != nilnode)
		{
			Max_IT(t, p);
			p = p->parent;
		}

		if (deletenode_color == 0)
		{
			t = Delete_Fixup_IT(t, x);
		}
		free(z);
	}
	return t;
}


//随机构建红黑树
IntervalTreeNode* Random_Bulid_IT(double n[][2], int num)
{
	IntervalTreeNode* t;
	t = NULL;
	if (num > 0)
	{
		int random_num;
		random_num = rand() % num;

		//哨兵黑节点，只有黑色，标记为其余指针都为空
		IntervalTreeNode* nilnode;
		nilnode = (IntervalTreeNode*)malloc(sizeof(IntervalTreeNode));
		nilnode->color = 0;
		nilnode->lchild = NULL;
		nilnode->rchild = NULL;
		nilnode->parent = NULL;

		t = (IntervalTreeNode*)malloc(sizeof(IntervalTreeNode));
		t->lowendpoint = n[random_num][0];
		t->highendpoint = n[random_num][1];
		t->lchild = nilnode;
		t->rchild = nilnode;
		t->parent = nilnode;	//此处储存nilnode的地址，方便以后直接取出
		t->color = 0;

		// 将已使用的元素移至数组末尾
		double temp[2];
		for (int i = 0; i < 2; i++) {
			temp[i] = n[random_num][i];
			n[random_num][i] = n[num - 1][i];
			n[num - 1][i] = temp[i];
		}


		for (int i = 1; i < num; i++)
		{
			random_num = rand() % (num - i);
			t = Insertnode_IT(t, n[random_num][0], n[random_num][1]);

			// 将已使用的元素移至数组末尾
			for (int j = 0; j < 2; j++) {
				temp[j] = n[random_num][j];
				n[random_num][j] = n[num - i - 1][j];
				n[num - i - 1][j] = temp[j];
			}
		}

	}

	return t;
}


//删除红黑树
IntervalTreeNode* Delete_IT(IntervalTreeNode* t)
{
	if (t->lchild != NULL && t->rchild != NULL)
	{
		t->lchild = Delete_IT(t->lchild);		//哨兵节点会自动删除
		t->rchild = Delete_IT(t->rchild);
		free(t);
		return NULL;
	}
}


//求树的高度
int HighBTree(IntervalTreeNode* t)
{
	if (t->lchild == NULL && t->rchild == NULL)	//表示为哨兵节点
	{
		return 0;
	}
	else
	{
		return (max(HighBTree(t->lchild), HighBTree(t->rchild)) + 1);
	}
}

//链队列结构类型
typedef struct QueueNode
{
	IntervalTreeNode* rbtreenode;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue
{
	QueueNode* front;//队头指针
	QueueNode* rear;//队尾指针
}LinkQueue;

LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->rbtreenode = NULL;
	return q;
}

//空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue* q)
{
	if (q->front == q->rear)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

//入队
void EnLinkQueue(LinkQueue* q, IntervalTreeNode* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->rbtreenode = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
}

//出队
IntervalTreeNode* DeLinkQueue(LinkQueue* q)
{
	if (EmptyLinkQueue(q) == 0)
	{
		printf("队空\n");
	}
	else
	{
		IntervalTreeNode* rbtreenode;
		QueueNode* queuenode;
		queuenode = q->front->next;
		rbtreenode = queuenode->rbtreenode;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return rbtreenode;
	}
}

//层次展示二叉树
void LikeBTree(IntervalTreeNode* t)
{
	if (t == NULL)
	{
		printf("树空\n");
	}
	else
	{
		LinkQueue* q;
		IntervalTreeNode* node;
		int high = 1;
		int sumh;
		int highmax;
		int mark = 0;

		IntervalTreeNode* nilnode;
		nilnode = t->parent;

		IntervalTreeNode* emptynode;
		emptynode = (IntervalTreeNode*)malloc(sizeof(IntervalTreeNode));
		emptynode->color = 0;
		emptynode->lchild = nilnode;
		emptynode->rchild = nilnode;

		highmax = HighBTree(t);
		q = InitLinkQueue();	//创建树节点队列

		EnLinkQueue(q, t);
		while (EmptyLinkQueue(q) == 1 && high <= highmax)		//队不为空
		{
			node = DeLinkQueue(q);

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补前面空缺
			{
				printf("     ");
			}

			if (node == emptynode)
			{
				printf("         #");
			}
			else
			{
				if (node->color == 0)
				{
					printf("[%2.0lf , %2.0lf] %2.0lf ", node->lowendpoint, node->highendpoint, node->max);
				}
				else
				{
					printf("$[%2.0lf , %2.0lf] %2.0lf ", node->lowendpoint, node->highendpoint, node->max);
				}
			}

			for (int k = 0; k < pow(2, highmax - high) - 1; k++)			//填补后面空缺
			{
				printf("     ");
			}

			if (node->lchild != nilnode)
			{
				EnLinkQueue(q, node->lchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}
			if (node->rchild != nilnode)
			{
				EnLinkQueue(q, node->rchild);
			}
			else
			{
				if (high < highmax)
				{
					EnLinkQueue(q, emptynode);
				}
			}

			mark++;
			sumh = pow(2, high) - 1;
			if (mark >= sumh)		//换层
			{
				high++;
				printf("\n");
			}
		}
		free(emptynode);
		free(q->front);
		free(q);
	}
}


int main()
{
	double n[][2] = { {10, 22}, {37, 40}, {52, 60}, {70, 72}, {75, 160}, {170, 172} , {270, 272} };
	int num = sizeof(n) / sizeof(n[0]);

	IntervalTreeNode* T;
	T = Random_Bulid_IT(n, num);
	InOrder_IT(T);
	printf("\n");
	LikeBTree(T);
	printf("\n");
	printf("\n");
	T = Deletenode_IT(T, 170);
	InOrder_IT(T);
	printf("\n");
	LikeBTree(T);
	double i_low, i_high;
	i_low = 100;
	i_high = 120;
	IntervalTreeNode* x;
	x = Search_Interval(T, i_low, i_high);
	printf("与 [%lf , %lf] 重叠的区间为[%lf , %lf]\n", i_low, i_high, x->lowendpoint, x->highendpoint);

	T = Delete_IT(T);

	return 0;
}

[ 10.000000 , 22.000000 ]  [ 37.000000 , 40.000000 ]  [ 52.000000 , 60.000000 ]  [ 70.000000 , 72.000000 ]  [ 75.000000 , 160.000000 ]  [ 170.000000 , 172.000000 ]  [ 270.000000 , 272.000000 ]  
                                   [37 , 40] 272                                    
               [10 , 22] 22                               $[70 , 72] 272                
              #                   #          [52 , 60] 60           [170 , 172] 272      
         #         #         #         #         #         #$[75 , 160] 160 $[270 , 272] 272 


[ 10.000000 , 22.000000 ]  [ 37.000000 , 40.000000 ]  [ 52.000000 , 60.000000 ]  [ 70.000000 , 72.000000 ]  [ 75.000000 , 160.000000 ]  [ 270.000000 , 272.000000 ]  
                                   [37 , 40] 272                                    
               [10 , 22] 22                               $[70 , 72] 272                
              #                   #          [52 , 60] 60           [270 , 272] 272      
         #         #         #         #         #         #$[75 , 160] 160          #
与 [100.000000 , 120.000000] 重叠的区间为[75.000000 , 160.000000]

跳跃表

总代码

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 跳跃表结构
typedef struct SkipNode
{
    double element;
    SkipNode *next;
    SkipNode *before;
    SkipNode *lowerlevel_node;
    SkipNode *upperlevel_node;
} SkipNode;

typedef struct SkipList
{
    SkipNode *head;
    int maxlevel;
} SkipList;

// 初始化跳跃表
SkipList *SkipListInit()
{
    SkipList *skiplist;
    skiplist = (SkipList *)malloc(sizeof(SkipList));
    skiplist->maxlevel = 0;
    skiplist->head = NULL;
    return skiplist;
}

// 删除跳跃表
void DeleteSkipList(SkipList *skiplist)
{
    SkipNode *node, *uppernode, *t;
    node = skiplist->head;
    uppernode = node->upperlevel_node;
    for (int k = 1; k <= skiplist->maxlevel; k++)
    {
        while (node != NULL)
        {
            t = node;
            node = node->next;
            free(t);
        }
        printf("\n");
        if (k != skiplist->maxlevel)
        {
            node = uppernode;
            uppernode = node->upperlevel_node;
        }
    }
}

// 打印跳跃表
void PrintSkipList(SkipList *skiplist)
{
    SkipNode *node, *uppernode;
    node = skiplist->head;
    uppernode = node->upperlevel_node;
    for (int k = 1; k <= skiplist->maxlevel; k++)
    {
        while (node != NULL)
        {
            printf("%lf  ", node->element);
            node = node->next;
        }
        printf("\n");
        if (k != skiplist->maxlevel)
        {
            node = uppernode;
            uppernode = node->upperlevel_node;
        }
    }
}

// 查找
SkipNode *SearchSkipLevel(SkipList *skiplist, double value)
{
    SkipNode *current_node;
    current_node = skiplist->head;
    // 寻找最上层的节点
    while (current_node->upperlevel_node != NULL)
    {
        current_node = current_node->upperlevel_node;
    }
    int current_level = skiplist->maxlevel;

    while (current_level > 0)
    {
        if (current_node->element != value)
        {
            if (current_node->next != NULL && current_node->next->element <= value)
            {
                current_node = current_node->next;
            }
            else if (current_node->lowerlevel_node != NULL)
            {
                current_node = current_node->lowerlevel_node;
                current_level--;
            }
            else
            {
                return NULL;
            }
        }
        else
        {
            return current_node;
        }
    }
    return NULL;
}

// 插入
//  插入元素存在的最高层数
int RandomLevel(SkipList *skiplist)
{
    int level = 1;
    while (rand() < RAND_MAX / 2 && level <= skiplist->maxlevel)
    {
        level++;
    }
    return level;
}

void InsertSkipNode(SkipList *skiplist, double value)
{
    if (skiplist->maxlevel == 0)
    {
        skiplist->maxlevel = 1;
        // 创建node节点
        SkipNode *node;
        node = (SkipNode *)malloc(sizeof(SkipNode));
        node->element = value;
        node->before = NULL;
        node->next = NULL;
        node->lowerlevel_node = NULL;
        node->upperlevel_node = NULL;
        skiplist->head = node;
    }
    else
    {
        SkipNode *top_node, *pre_node;
        pre_node = skiplist->head;
        // 寻找最上层的节点
        while (pre_node->upperlevel_node != NULL)
        {
            pre_node = pre_node->upperlevel_node;
        }
        top_node = pre_node;
        while (pre_node->lowerlevel_node != NULL || (pre_node->next != NULL && pre_node->next->element < value))
        {
            if (pre_node->next != NULL && pre_node->next->element < value)
            {
                pre_node = pre_node->next;
            }
            else
            {
                pre_node = pre_node->lowerlevel_node;
            }
        }
        if (pre_node->element == value)
        {
            printf("%lf 已在跳跃表中", value);
        }
        else if (pre_node->element > value) // 插入节点为最小的节点
        {
            int level;
            level = RandomLevel(skiplist);
            if (skiplist->maxlevel < level)
            {
                skiplist->maxlevel = level;
            }

            SkipNode *lowerlevel_node;
            lowerlevel_node = NULL;

            for (int k = 1; k <= skiplist->maxlevel; k++)
            {
                // 创建node节点
                SkipNode *node;
                node = (SkipNode *)malloc(sizeof(SkipNode));
                node->element = value;

                node->before = NULL;
                node->next = pre_node;
                node->lowerlevel_node = lowerlevel_node;
                node->upperlevel_node = NULL;

                pre_node->before = node;
                if (node->lowerlevel_node != NULL)
                {
                    node->lowerlevel_node->upperlevel_node = node;
                }

                pre_node = pre_node->upperlevel_node;
                lowerlevel_node = node;
            }
            skiplist->head = skiplist->head->before;
        }
        else
        {
            int level;
            level = RandomLevel(skiplist);

            if (level > skiplist->maxlevel)
            {
                // 创建node节点
                SkipNode *node;
                node = (SkipNode *)malloc(sizeof(SkipNode));
                node->element = top_node->element;
                node->before = NULL;
                node->next = NULL;
                node->lowerlevel_node = top_node;
                node->upperlevel_node = NULL;

                top_node->upperlevel_node = node;
                top_node = node;

                // 更新maxlevel
                skiplist->maxlevel++;
            }

            SkipNode *lowerlevel_node;
            lowerlevel_node = NULL;
            for (int k = 1; k <= level; k++)
            {
                // 创建node节点
                SkipNode *node;
                node = (SkipNode *)malloc(sizeof(SkipNode));
                node->element = value;

                node->before = pre_node;
                node->next = pre_node->next;
                node->lowerlevel_node = lowerlevel_node;
                node->upperlevel_node = NULL;

                pre_node->next = node;
                if (lowerlevel_node != NULL)
                {
                    lowerlevel_node->upperlevel_node = node;
                }
                if (node->next != NULL)
                {
                    node->next->before = node;
                }

                lowerlevel_node = node;

                // 更新pre节点到上一层
                if (k != level)
                {
                    while (pre_node->upperlevel_node == NULL && pre_node->before != NULL)
                    {
                        pre_node = pre_node->before;
                    }
                    pre_node = pre_node->upperlevel_node;
                    while (pre_node->next != NULL && pre_node->next->element < value)
                    {
                        pre_node = pre_node->next;
                    }
                }
            }
        }
    }
}

// 删除节点
void DeleteSkipNode(SkipList *skiplist, double value)
{
    SkipNode *delete_node;
    delete_node = SearchSkipLevel(skiplist, value);
    if (delete_node == NULL)
    {
        printf("%lf 节点不存在\n", value);
    }
    else
    {
        while (delete_node->lowerlevel_node != NULL)
        {
            delete_node = delete_node->lowerlevel_node;
        }

        // 删掉的节点为最小的节点
        if (delete_node->before == NULL)
        {
            SkipNode *next_node, *upper_node;
            skiplist->head = skiplist->head->next;
            next_node = delete_node->next;
            for (int k = 1; k <= skiplist->maxlevel; k++)
            {
                if (next_node->upperlevel_node == NULL && k != skiplist->maxlevel)
                {
                    // 创建node节点
                    SkipNode *node;
                    node = (SkipNode *)malloc(sizeof(SkipNode));
                    node->element = next_node->element;
                    node->before = NULL;
                    node->next = delete_node->next;
                    node->lowerlevel_node = next_node;
                    node->upperlevel_node = NULL;

                    next_node->upperlevel_node = node;
                    delete_node->next->before = node;
                }
                next_node = next_node->upperlevel_node;
                upper_node = delete_node->upperlevel_node;

                free(delete_node);

                delete_node = upper_node;
            }
        }
        else
        {
            SkipNode *pre_node, *upper_node;
            while (delete_node != NULL)
            {
                pre_node = delete_node->before;
                upper_node = delete_node->upperlevel_node;

                pre_node->next = delete_node->next;
                delete_node->next->before = pre_node;

                free(delete_node);

                delete_node = upper_node;
            }
        }
    }
}

// 创建跳跃表
void CreatSkipList(SkipList *skiplist, double *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        InsertSkipNode(skiplist, arr[i]);
    }
}

int main()
{
    double n[10] = {30, 64, 90, 27, 97, 11, 69, 20, 8, 65};
    SkipList *skiplist;
    skiplist = SkipListInit();
    CreatSkipList(skiplist, n, 10);
    PrintSkipList(skiplist);
    DeleteSkipNode(skiplist, 11);
    PrintSkipList(skiplist);
    DeleteSkipNode(skiplist, 8);
    PrintSkipList(skiplist);
    DeleteSkipList(skiplist);
    return 0;
}

结果

8.000000  11.000000  20.000000  27.000000  30.000000  64.000000  65.000000  69.000000  90.000000  97.000000  
8.000000  11.000000  20.000000  27.000000  30.000000  64.000000  65.000000  97.000000  
8.000000  11.000000  27.000000  65.000000  97.000000  

8.000000  20.000000  27.000000  30.000000  64.000000  65.000000  69.000000  90.000000  97.000000  
8.000000  20.000000  27.000000  30.000000  64.000000  65.000000  97.000000  
8.000000  27.000000  65.000000  97.000000  

20.000000  27.000000  30.000000  64.000000  65.000000  69.000000  90.000000  97.000000  
20.000000  27.000000  30.000000  64.000000  65.000000  97.000000  
20.000000  20.000000  27.000000  30.000000  64.000000  65.000000  97.000000  

B树

总代码

#include <stdio.h>
#include <stdlib.h>
#define T 3 //  定义B树的度

// B树结构体
typedef struct BTreeNode
{
    int n;             // 关键字数量
    double *key;       // 关键字数组的指针
    BTreeNode **child; // 子节点数组的指针
    bool leaf;         // 是否为叶节点  1-是    0-否
} BTreeNode;

// B树节点中的位置结构
typedef struct BTreeNodeElement
{
    BTreeNode *btreenode;
    int i;
} BTreeNodeElement;

// 创建B树节点
BTreeNode *BTreeNodeInit(bool leaf)
{
    BTreeNode *btreenode = (BTreeNode *)malloc(sizeof(BTreeNode));
    if (btreenode)
    {
        btreenode->key = (double *)malloc((2 * T - 1) * sizeof(double));
        btreenode->child = (BTreeNode **)malloc(2 * T * sizeof(BTreeNode *));
        for (int k = 0; k < 2 * T; k++)
        {
            btreenode->child[k] = NULL;
        }
        btreenode->n = 0;
        btreenode->leaf = leaf;
    }
    return btreenode;
}

// 删除B树
void Delete_BTreeNode(BTreeNode *t)
{
    if (t != NULL)
    {
        free(t->key);
        for (int k = 0; k < 2 * T; k++)
        {
            Delete_BTreeNode(t->child[k]);
        }
        free(t->child);
        free(t);
    }
}

// B树搜索节点
BTreeNodeElement *BTree_Search(BTreeNode *t, double x)
{
    int i = 0;
    //  寻找比x更大的节点
    while (i < t->n && x > t->key[i])
    {
        i++;
    }
    // 找到节点
    if (i < t->n && x == t->key[i])
    {
        BTreeNodeElement *element;
        element = (BTreeNodeElement *)malloc(sizeof(BTreeNodeElement));
        element->btreenode = t;
        element->i = i;

        return element;
    }
    // 叶节点返回空值
    else if (t->leaf == 1)
    {
        return NULL;
    }
    else
    {
        return BTree_Search(t->child[i], x);
    }
}

// 分裂B树节点
void BTree_Split(BTreeNodeElement *element)
{
    BTreeNode *y;
    y = element->btreenode->child[element->i];

    // 将分裂节点后半部分储存
    BTreeNode *z;
    z = BTreeNodeInit(y->leaf);
    z->n = T - 1;
    for (int k = 0; k < T - 1; k++)
    {
        z->key[k] = y->key[k + T];
    }
    if (y->leaf == 0)
    {
        for (int k = 0; k < T; k++)
        {
            z->child[k] = y->child[k + T];
        }
    }

    y->n = T - 1;

    // 孩子节点后移
    for (int k = element->btreenode->n; k >= element->i + 1; k--)
    {
        element->btreenode->child[k + 1] = element->btreenode->child[k];
    }
    element->btreenode->child[element->i + 1] = z;

    for (int k = element->btreenode->n - 1; k >= element->i - 1; k--)
    {
        element->btreenode->key[k + 1] = element->btreenode->key[k];
    }
    element->btreenode->key[element->i] = y->key[T - 1];

    element->btreenode->n++;
}

// B树插入关键字
void BTree_Insert_NonFull(BTreeNode *x, double k)
{
    int i;
    i = x->n - 1;
    if (x->leaf == 1)
    {
        while (i >= 0 && k < x->key[i])
        {
            x->key[i + 1] = x->key[i];
            i--;
        }
        x->key[i + 1] = k;
        x->n++;
    }
    else
    {
        while (i >= 0 && k < x->key[i])
        {
            i--;
        }
        i++;

        if (x->child[i]->n == 2 * T - 1)
        {
            BTreeNodeElement *element;
            element = (BTreeNodeElement *)malloc(sizeof(BTreeNodeElement));
            element->btreenode = x;
            element->i = i;

            BTree_Split(element);
            free(element);

            if (k > x->key[i])
            {
                i++;
            }
        }
        BTree_Insert_NonFull(x->child[i], k);
    }
}

BTreeNode *BTree_Insert(BTreeNode *t, double x)
{
    BTreeNode *root;
    root = t;
    if (root->n == 2 * T - 1)
    {
        BTreeNode *s;
        s = BTreeNodeInit(0);
        t = s;
        s->child[0] = root;

        BTreeNodeElement *element;
        element = (BTreeNodeElement *)malloc(sizeof(BTreeNodeElement));
        element->btreenode = s;
        element->i = 0;

        BTree_Split(element);
        free(element);

        BTree_Insert_NonFull(s, x);

        root = s;
    }
    else
    {
        BTree_Insert_NonFull(root, x);
    }
    return root;
}

// B树删除关键字
void BTree_Delete(BTreeNode *t, double e)
{
    BTreeNode *x;
    x = t;
    int i = 0;
    // 关键字在节点x中
    while (i < x->n && e > x->key[i])
    {
        i++;
    }
    if (i < x->n && e == x->key[i])
    {
        // 情况1:关键字在叶节点上
        if (x->leaf == 1)
        {
            for (int k = i; k < x->n - 1; k++)
            {
                x->key[k] = x->key[k + 1];
            }
            x->n--;
        }
        else // 情况2:关键字不在叶节点上
        {
            BTreeNode *y;
            BTreeNode *z;
            y = x->child[i];
            z = x->child[i + 1];
            // 情况2.a:关键字前面的子节点包含大于T个关键字
            if (y->n >= T)
            {
                x->key[i] = y->key[y->n - 1];
                BTree_Delete(y, y->key[y->n - 1]);
            }
            // 情况2.b:关键字后面的子节点包含大于T个关键字
            else if (z->n >= T)
            {
                x->key[i] = z->key[0];
                BTree_Delete(z, z->key[0]);
            }
            else // 情况2.c:关键字前面与后面的子节点包含T-1个关键字
            {
                // 合并y节点,k,与z节点
                y->key[y->n] = e;
                for (int k = 0; k < z->n; k++)
                {
                    y->key[(y->n + 1) + k] = z->key[k];
                }
                for (int k = 0; k < z->n + 1; k++)
                {
                    y->child[(y->n + 1) + k] = z->child[k];
                }
                y->n += z->n + 1;
                if (z->leaf == 0)
                {
                    y->leaf = 0;
                }

                for (int k = i; k < x->n - 1; k++)
                {
                    x->key[k] = x->key[k + 1];
                    x->child[k + 1] = x->child[k + 2];
                }
                x->n--;

                free(z->key);
                free(z);
                BTree_Delete(y, e);
            }
        }
    }
    else // 情况3:关键字不在节点x中
    {
        if (x->n == 0 || x->child[i] == NULL)
        {
            printf("B树中未发现%lf节点\n", e);
        }
        else if (x->child[i]->n >= T)
        {
            BTree_Delete(x->child[i], e);
        }
        else // x->child[i]中只有T - 1个关键字
        {
            // 情况3.a
            //  x->child[i]兄弟节点包含了多于T-1个关键字
            if (x->child[i + 1] != NULL && x->child[i + 1]->n > T - 1)
            {
                BTreeNode *y, *z;
                y = x->child[i];
                z = x->child[i + 1];

                y->key[y->n] = x->key[i];
                y->child[y->n + 1] = z->child[0];
                y->n++;

                x->key[i] = z->key[0];

                for (int k = 0; k < z->n - 1; k++)
                {
                    z->key[k] = z->key[k + 1];
                }
                for (int k = 0; k < z->n; k++)
                {
                    z->child[k] = z->child[k + 1];
                }
                z->n--;

                BTree_Delete(y, e);
            }
            else if (x->child[i - 1] != NULL && x->child[i - 1]->n > T - 1)
            {
                BTreeNode *y, *z;
                y = x->child[i];
                z = x->child[i - 1];

                for (int k = y->n - 1; k >= 0; k--)
                {
                    y->key[k + 1] = y->key[k];
                }
                for (int k = y->n; k >= 0; k--)
                {
                    y->child[k + 1] = y->child[k];
                }
                y->key[0] = x->key[i - 1];
                y->child[0] = z->child[z->n];
                y->n++;

                x->key[i - 1] = z->key[z->n - 1];

                z->n--;

                BTree_Delete(y, e);
            }
            else
            {
                // 情况3.b:x->child[i]所有兄弟节点都只含有T-1个关键字
                //  x->child[i + 1]含有 T-1个关键字
                if (x->child[i + 1] != NULL)
                {
                    // 合并x->child[i + 1]节点与x->child[i]节点
                    BTreeNode *y, *z;
                    y = x->child[i];
                    z = x->child[i + 1];

                    y->key[y->n] = x->key[i];
                    for (int k = 0; k < z->n; k++)
                    {
                        y->key[(y->n + 1) + k] = z->key[k];
                    }
                    for (int k = 0; k < z->n + 1; k++)
                    {
                        y->child[(y->n + 1) + k] = z->child[k];
                    }
                    y->n += z->n + 1;
                    if (z->leaf == 0)
                    {
                        y->leaf = 0;
                    }

                    free(z->key);
                    free(z);

                    for (int k = i; k < x->n - 1; k++)
                    {
                        x->key[k] = x->key[k + 1];
                    }
                    for (int k = i + 1; k <= x->n; k++)
                    {
                        x->child[k] = x->child[k + 1];
                    }
                    x->n--;

                    BTree_Delete(y, e);
                }
                else // x->child[i - 1]含有 T-1个关键字
                {
                    // 合并x->child[i - 1]节点与x->child[i]节点
                    BTreeNode *y, *z;
                    y = x->child[i];
                    z = x->child[i - 1];

                    z->key[z->n] = x->key[i - 1];
                    for (int k = 0; k < y->n; k++)
                    {
                        z->key[(z->n + 1) + k] = y->key[k];
                    }
                    for (int k = 0; k < y->n + 1; k++)
                    {
                        z->child[(z->n + 1) + k] = y->child[k];
                    }
                    z->n += y->n + 1;
                    if (y->leaf == 0)
                    {
                        z->leaf = 0;
                    }

                    free(y->key);
                    free(y);

                    for (int k = i - 1; k < x->n - 1; k++)
                    {
                        x->key[k] = x->key[k + 1];
                    }
                    for (int k = i; k < x->n + 1; k++)
                    {
                        x->child[k] = x->child[k + 1];
                    }
                    x->n--;

                    BTree_Delete(z, e);
                }
            }
        }
    }
}

// 输出B树节点
void Print_BTreeNode(BTreeNode *t)
{
    if (t != NULL)
    {
        for (int k = 0; k < t->n; k++)
        {
            printf("%lf  ", t->key[k]);
        }
    }
}

// 先序遍历B树
void PreOrder_BTree(BTreeNode *t)
{
    if (t != NULL)
    {
        for (int k = 0; k < t->n; k++)
        {
            PreOrder_BTree(t->child[k]);
            printf("%lf  ", t->key[k]);
        }
        PreOrder_BTree(t->child[t->n]);
    }
}

// 链队列结构类型
typedef struct QueueNode
{
    BTreeNode *btreenode;
    QueueNode *next;
} QueueNode;

typedef struct LinkQueue
{
    QueueNode *front; // 队头指针
    QueueNode *rear;  // 队尾指针
} LinkQueue;

LinkQueue *InitLinkQueue()
{
    LinkQueue *q;
    q = (LinkQueue *)malloc(sizeof(LinkQueue));
    q->front = (QueueNode *)malloc(sizeof(QueueNode));
    if (q->front == NULL)
    {
        printf("开辟空间失败\n");
        exit(0);
    }
    q->rear = q->front;
    q->front->next = NULL;
    q->front->btreenode = NULL;
    return q;
}

// 空队	1-非空	0-空
bool EmptyLinkQueue(LinkQueue *q)
{
    if (q->front == q->rear)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

// 入队
void EnLinkQueue(LinkQueue *q, BTreeNode *e)
{
    QueueNode *p;
    p = (QueueNode *)malloc(sizeof(QueueNode));
    if (p == NULL)
    {
        printf("开辟空间失败\n");
        exit(0);
    }
    p->btreenode = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
}

// 出队
BTreeNode *DeLinkQueue(LinkQueue *q)
{
    if (EmptyLinkQueue(q) == 0)
    {
        printf("队空\n");
    }
    else
    {
        BTreeNode *btreenode;
        QueueNode *queuenode;
        queuenode = q->front->next;
        btreenode = queuenode->btreenode;
        q->front->next = queuenode->next;
        if (queuenode == q->rear)
        {
            q->rear = q->front;
        }
        free(queuenode);
        return btreenode;
    }
}

// 层次展示B树
void Show_BTree(BTreeNode *t)
{
    if (t != NULL)
    {
        LinkQueue *q = InitLinkQueue(); // 初始化队列
        EnLinkQueue(q, t);              // 将B树的根节点入队

        // 为了区分每一层，我们可以使用一个特殊的节点
        BTreeNode *levelBreak = (BTreeNode *)malloc(sizeof(BTreeNode));
        levelBreak->n = -1;         // 设为-1来标识这是一个特殊节点
        EnLinkQueue(q, levelBreak); // 在根节点之后放入特殊节点

        while (EmptyLinkQueue(q))
        {
            BTreeNode *current = DeLinkQueue(q);

            // 如果当前节点是特殊节点
            if (current->n == -1)
            {
                printf("\n"); // 换行到下一层

                // 如果队列不为空，再次入队一个特殊节点
                if (EmptyLinkQueue(q))
                {
                    EnLinkQueue(q, levelBreak);
                }
            }
            else
            {
                // 打印当前节点的关键字
                for (int i = 0; i < current->n; i++)
                {
                    printf("%lf  ", current->key[i]);
                }
                printf("|   "); // 分隔同一层中的节点

                // 如果当前节点不是叶子节点，将它的子节点入队
                if (!current->leaf)
                {
                    for (int i = 0; i <= current->n; i++)
                    {
                        if (current->child[i])
                        {
                            EnLinkQueue(q, current->child[i]);
                        }
                    }
                }
            }
        }

        free(levelBreak); // 释放特殊节点的内存
        free(q->front);   // 释放队列的内存
        free(q);
    }
}

// 创建B树
BTreeNode *CreatBTree(double *x, int size)
{
    BTreeNode *t;
    if (size > 0)
    {
        t = BTreeNodeInit(1);
        for (int k = 0; k < size; k++)
        {
            t = BTree_Insert(t, x[k]);
        }
        return t;
    }
    else
    {
        t = NULL;
        return t;
    }
}

int main()
{
    double n[20] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100, -10, -20, -30, -40, -50, -60, -70, -80, -90, -100};
    BTreeNode *t;
    t = CreatBTree(n, 20);
    Show_BTree(t);
    PreOrder_BTree(t);
    BTree_Delete(t, 10);
    Show_BTree(t);
    PreOrder_BTree(t);
    Delete_BTreeNode(t);
    return 0;
}

结果

-70.000000  -40.000000  -10.000000  30.000000  60.000000  |   
-100.000000  -90.000000  -80.000000  |   -60.000000  -50.000000  |   -30.000000  -20.000000  |   10.000000  20.000000  |   40.000000  50.000000  |   70.000000  80.000000  90.000000  100.000000  |   
-100.000000  -90.000000  -80.000000  -70.000000  -60.000000  -50.000000  -40.000000  -30.000000  -20.000000  -10.000000  10.000000  20.000000  30.000000  40.000000  50.000000  60.000000  70.000000  80.000000  90.000000  100.000000  -70.000000  -40.000000  -10.000000  60.000000  |   
-100.000000  -90.000000  -80.000000  |   -60.000000  -50.000000  |   -30.000000  -20.000000  |   20.000000  30.000000  40.000000  50.000000  |   70.000000  80.000000  90.000000  100.000000  |   
-100.000000  -90.000000  -80.000000  -70.000000  -60.000000  -50.000000  -40.000000  -30.000000  -20.000000  -10.000000  20.000000  30.000000  40.000000  50.000000  60.000000  70.000000  80.000000  90.000000  100.000000 

斐波那契堆

总代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

// 斐波那契堆节点
typedef struct Fib_Heap_Node
{
    ElementType* x;
    Fib_Heap_Node* p;       // 父节点
    Fib_Heap_Node* child;   // 某一个孩子节点
    Fib_Heap_Node* left;    // 左兄弟
    Fib_Heap_Node* right;   // 右兄弟
    int degree;  // 孩子数目（度）
    bool mark;    // 标记
}Fib_Heap_Node;

// 斐波那契堆
typedef struct Fib_Heap
{
    int size;
    Fib_Heap_Node* min_node;
}Fib_Heap;

// 创建斐波那契堆
Fib_Heap* Create_Fib_Heap()
{
    Fib_Heap* H;
    H = (Fib_Heap*)malloc(sizeof(Fib_Heap));
    H->min_node = NULL;
    H->size = 0;
    return H;
}

// 递归删除斐波那契堆
void Free_Fib_Heap_Node(Fib_Heap_Node* node)
{
    if (node == NULL)
    {
        return;
    }

    Fib_Heap_Node* start = node;
    do {
        Fib_Heap_Node* child = node->child;
        Fib_Heap_Node* next = node->right;

        // 递归释放子节点
        Free_Fib_Heap_Node(child);

        // 释放当前节点
        free(node);

        node = next;
    } while (node != start);
}

void Free_Fib_Heap(Fib_Heap* H)
{
    if (H != NULL) {
        // 释放所有根节点
        Free_Fib_Heap_Node(H->min_node);

        // 释放堆结构本身
        free(H);
    }
}

// 斐波那契堆树根的个数
int Fib_Heap_Root_Count(Fib_Heap* H)
{
    if (H->min_node == NULL)
    {
        return 0;
    }
    else
    {
        int count = 1;
        Fib_Heap_Node* p;
        p = H->min_node->right;
        while (p != H->min_node)
        {
            count++;
            p = p->right;
        }
        return count;
    }
}

// 插入根节点   插在最小节点与根节点右边节点之间
void Fib_Heap_Insert_Root(Fib_Heap* H, Fib_Heap_Node* node)
{  
    // 只有一个根
    if (H->min_node->right == H->min_node)
    {
        H->min_node->right = node;
        H->min_node->left = node;
        node->left = H->min_node;
        node->right = H->min_node;
    }
    else
    {
        node->p = NULL;
        Fib_Heap_Node* p;
        p = H->min_node->right;

        H->min_node->right = node;
        p->left = node;
        node->left = H->min_node;
        node->right = p;
    }
    node->p = NULL;
}

// 插入节点
void Fib_Heap_Insert(Fib_Heap* H, ElementType* x)
{
    Fib_Heap_Node* node;
    node = (Fib_Heap_Node*)malloc(sizeof(Fib_Heap_Node));
    node->x = x;
    node->child = NULL;
    node->degree = 0;
    node->mark = 0;

    // 堆空
    if (H->min_node == NULL)
    {
        H->min_node = node;
        node->p = NULL;
        node->left = node;
        node->right = node;
    }
    else
    {
        // 插入节点为根
        Fib_Heap_Insert_Root(H, node);

        if (*x < *H->min_node->x)
        {
            H->min_node = node; // 改变min指针
        }
    }
    H->size ++;
}

// 合并堆
Fib_Heap* Fib_Heap_Union(Fib_Heap* H1, Fib_Heap* H2)
{
    Fib_Heap* H;
    H = Create_Fib_Heap();
    H->min_node = H1->min_node;
    H->size = H1->size + H2->size;
    // 根合并
    if (H1->min_node == NULL)
    {
        // 跳过
    }
    else if (H->min_node->right == H->min_node)   // H1只有一棵树
    {
        if (H2->min_node->right == H2->min_node)   // H2只有一棵树
        {
            H->min_node->right = H2->min_node;
            H->min_node->left = H2->min_node;
            H2->min_node->right = H->min_node;
            H2->min_node->left = H->min_node;
        }
        else
        {
            Fib_Heap_Insert_Root(H2, H->min_node);
        }
    }
    else    // H1有多棵树
    {
        if (H2->min_node->right == H2->min_node)   // H2只有一棵树
        {
            Fib_Heap_Insert_Root(H, H2->min_node);
        }
        else
        {
            Fib_Heap_Node* p,* q;
            p = H->min_node->right;
            q = H2->min_node->left;

            H->min_node->right = H2->min_node;
            H2->min_node->left = H->min_node;
            q->right = p;
            p->left = q;
        }
    }

    if ((H1->min_node == NULL) || (H2->min_node && H2->min_node->x < H1->min_node->x))
    {
        H->min_node = H2->min_node;
    }
    free(H1);
    free(H2);
    return H;
}

// 链接根节点   把y接为x的儿子
void Fib_Heap_Link(Fib_Heap* H, Fib_Heap_Node* y, Fib_Heap_Node* x)
{
    // 把y从根节点中移除
    y->left->right = y->right;
    y->right->left = y->left;

    // 把y填入x的孩子中
    y->p = x;
    Fib_Heap_Node* p;
    p = x->child;
    if (p == NULL)  // x原来没孩子
    {
        x->child = y;
        y->left = y;
        y->right = y;
    }
    else
    {
        p->right->left = y;
        y->right = p->right;
        p->right = y;
        y->left = p;
    }
    x->degree ++;

    y->mark = 0;
}

// 合并根链表
void Fib_Heap_Consolidate(Fib_Heap* H)
{
    Fib_Heap_Node** A;
    A = (Fib_Heap_Node**)malloc(sizeof(Fib_Heap_Node*) * H->size);
    for (int i = 0; i < H->size; i++)
    {
        A[i] = NULL;
    }
    Fib_Heap_Node** root_list;
    int count;
    count = Fib_Heap_Root_Count(H);
    Fib_Heap_Node* p;
    p = H->min_node;
    Fib_Heap_Node* x, *y;
    int d;
    for (int i = 0; i < count; i++)
    {
        x = p;
        p = p->right;
        d = x->degree;  // 当前节点的度数
        while (A[d] != NULL)
        {
            y = A[d];
            // 比谁小，然后交换
            if (*x->x > *y->x)
            {
                Fib_Heap_Node* t;
                t = x;
                x = y;
                y = t;
            }
            Fib_Heap_Link(H, y, x);
            A[d] = NULL;    //清空
            d++;    //存入下一个
        }
        A[d] = x;
    }

    // 根据 A 重建 H
    H->min_node = NULL;
    for (int i = 0; i < H->size; i++)
    {
        if (A[i] != NULL)
        {
            if (H->min_node == NULL)
            {
                H->min_node = A[i];
                H->min_node->right = H->min_node;
                H->min_node->left = H->min_node;
            }
            else
            {
                Fib_Heap_Insert_Root(H, A[i]);
                if (*A[i]->x < *H->min_node->x)
                {
                    H->min_node = A[i];
                }
            }
        }
    }
    
    free(A);
}

// 提取最小节点
ElementType* Fib_Heap_Extract_Min(Fib_Heap* H)
{
    Fib_Heap_Node* z;
    z = H->min_node;
    if (z != NULL)
    {
        if (z->child != NULL)
        {
            // 令z的孩子都为根
            Fib_Heap_Node* child, *next;
            child = z->child;
            for (int i = 0; i < z->degree; i++)
            {
                next = child->right;
                Fib_Heap_Insert_Root(H, child);
                child = next;
            }
        }

        ElementType* element;
        element = z->x;

        // z为唯一节点
        if (H->size == 1)
        {
            H->min_node = NULL;
        }
        else
        {
        	// 从斐波那契堆移除z
        	z->left->right = z->right;
        	z->right->left = z->left;
            
            H->min_node = z->right;
            Fib_Heap_Consolidate(H);
        }
        H->size--;

        free(z);
        return element;
    }
    else
    {
        printf("空堆");
        return NULL;
    }
}

// 切断 切断x与父节点y，使x为根节点
void Fib_Heap_Cut(Fib_Heap* H, Fib_Heap_Node* x, Fib_Heap_Node* y)
{
    // x为y的孩子指针
    if (y->child == x)
    {
        // y只有一个孩子
        if (x->right == x)
        {
            y->child = NULL;
            Fib_Heap_Insert_Root(H, x);
        }
        else
        {
            y->child = x->right;
            x->right->left = x->left;
            x->left->right = x->right;
            Fib_Heap_Insert_Root(H, x);
        }
    }
    else
    {
        x->right->left = x->left;
        x->left->right = x->right;
        Fib_Heap_Insert_Root(H, x);
    }
    x->mark = 0;
}

// 级联切断
void Fib_Heap_Cascading_Cut(Fib_Heap* H, Fib_Heap_Node* y)
{
    Fib_Heap_Node* z;
    z = y->p;
    // y非根节点
    if (z != NULL)
    {
        if (y->mark == 0)
        {
            y->mark = 1;
        }
        else
        {
            Fib_Heap_Cut(H, y, z);
            Fib_Heap_Cascading_Cut(H, z);
        }
    }
}

// 关键字减值
void Fib_Heap_Decrease_Node(Fib_Heap* H, Fib_Heap_Node* x, ElementType* k)
{
    if (*k >= *x->x)
    {
        printf("不能让值变大\n");
    }
    else
    {
        *(x->x) = *k;
        Fib_Heap_Node *y;
        y = x->p;

        if (y != NULL && *x->x < *y->x)
        {
            Fib_Heap_Cut(H, x, y);
            Fib_Heap_Cascading_Cut(H, y);
        }
        if (*x->x < *H->min_node->x)
        {
            H->min_node = x;
        }
    }
}

// 删除节点
void Fib_Heap_Delete(Fib_Heap* H, Fib_Heap_Node* x)
{
    ElementType p;
    p = -99999;
    Fib_Heap_Decrease_Node(H, x, &p);
    Fib_Heap_Extract_Min(H);
}

//链队列结构类型
typedef struct QueueNode
{
	Fib_Heap_Node* node;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue
{
	QueueNode* front;   // 队头指针
	QueueNode* rear;    // 队尾指针
    int length;         // 队列长度
}LinkQueue;

// 初始化队列
LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->node = NULL;
    q->length = 0;
	return q;
}

// 入队
void EnLinkQueue(LinkQueue* q, Fib_Heap_Node* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->node = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
    q->length++;
}

// 出队
Fib_Heap_Node* DeLinkQueue(LinkQueue* q)
{
	if (q->length == 0)
	{
		printf("队空\n");
        return NULL;
	}
	else
	{
        q->length--;
		Fib_Heap_Node* node;
		QueueNode* queuenode;
		queuenode = q->front->next;
		node = queuenode->node;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return node;
	}
}

// 输出斐波那契堆
void Print_Fib_Heap_Tree(Fib_Heap_Node* root, int treeIndex)
{
    Fib_Heap_Node *blankNode;
    blankNode = (Fib_Heap_Node*)malloc(sizeof(Fib_Heap_Node));

    LinkQueue* queue = InitLinkQueue();
    EnLinkQueue(queue, root);

    printf("第 %d 棵树:\n", treeIndex);
    while (queue->length != 0)
    {
        int levelSize = queue->length; // 当前层的节点数
        for (int i = 0; i < levelSize; i++)
        {
            Fib_Heap_Node* node;
            node = DeLinkQueue(queue);

            // 打印当前节点
            if (node == blankNode)
            {
                printf("  ");  // 空白节点打印空格
            }
            else
            {
                printf("%d ", *node->x);
            }

            // 将子节点或空白节点加入队列
            Fib_Heap_Node* child;
            child = node->child;
            if (child != NULL)
            {
                // 将孩子都入队
                EnLinkQueue(queue, child);
                Fib_Heap_Node* current = child->right;
                while (current != child)
                {
                    EnLinkQueue(queue, current);
                    current = current->right;
                }
            }
            else if (node != blankNode)
            {
                // 对于没有子节点的父节点，加入一个空白节点
                EnLinkQueue(queue, blankNode);
            }
        }
        printf("\n"); // 完成一层的打印
    }
    free(blankNode);
}

void Print_Fib_Heap(Fib_Heap* H) {
    if (H == NULL || H->min_node == NULL)
    {
        printf("堆空\n");
    }

    Fib_Heap_Node* current = H->min_node;
    int treeIndex = 1;
    do
    {
        Print_Fib_Heap_Tree(current, treeIndex++);
        current = current->right;
    } while (current != H->min_node);
}


int main() {
    // 创建斐波那契堆
    Fib_Heap* H = Create_Fib_Heap();

    // 创建并插入一系列元素
    ElementType elements[10] = {23, 7, 35, 15, 29, 8, 17, 31, 12, 20};
    for (int i = 0; i < 10; i++) {
        Fib_Heap_Insert(H, &elements[i]);
    }
    printf("Initial heap:\n");
    Print_Fib_Heap(H);

    // 提取最小元素
    ElementType* min = Fib_Heap_Extract_Min(H);
    printf("提取的最小元素为: %d\n", *min);
    printf("提取之后的堆:\n");
    Print_Fib_Heap(H);

    // 创建另一个堆并合并
    Fib_Heap* H2 = Create_Fib_Heap();
    ElementType newElement[5] = {5, 100, 120, 209, 1};
    for (int i = 0; i < 5; i++) {
        Fib_Heap_Insert(H2, &newElement[i]);
    }
    printf("堆H2:\n");
    Print_Fib_Heap(H2);
    Fib_Heap* H3 = Fib_Heap_Union(H, H2);
    // 打印合并后的堆
    printf("Heap after union:\n");
    Print_Fib_Heap(H3);
    
    // 提取最小元素
    min = Fib_Heap_Extract_Min(H3);
    printf("提取的最小元素为: %d\n", *min);
    printf("提取之后的堆:\n");
    Print_Fib_Heap(H3);

    // 减少一个节点的关键字
    ElementType decreaseKey = 2;
    Fib_Heap_Decrease_Node(H3, H3->min_node->child, &decreaseKey);
    printf("Heap after decreasing a key:\n");
    Print_Fib_Heap(H3);

    decreaseKey = 1;
    Fib_Heap_Decrease_Node(H3, H3->min_node->left->child, &decreaseKey);
    printf("Heap after decreasing a key:\n");
    Print_Fib_Heap(H3);

    // 删除一个节点
    Fib_Heap_Delete(H3, H3->min_node->child);
    printf("Heap after deleting a node:\n");
    Print_Fib_Heap(H3);

    Free_Fib_Heap(H);
    Free_Fib_Heap(H2);
    Free_Fib_Heap(H3);

    return 0;
}

结果

Initial heap:
第 1 棵树:
7 
  
第 2 棵树:
20 
  
第 3 棵树:
12 
  
第 4 棵树:
31 
  
第 5 棵树:
17 
  
第 6 棵树:
8 
  
第 7 棵树:
29 
  
第 8 棵树:
15 
  
第 9 棵树:
35 
  
第 10 棵树:
23 
  
提取的最小元素为: 7
提取之后的堆:
第 1 棵树:
8 
29 12 15 
  20 17 35 
  31   
  
第 2 棵树:
23 
  
堆H2:
第 1 棵树:
1 
  
第 2 棵树:
209 
  
第 3 棵树:
120 
  
第 4 棵树:
100 
  
第 5 棵树:
5 
  
Heap after union:
第 1 棵树:
1 
  
第 2 棵树:
209 
  
第 3 棵树:
120 
  
第 4 棵树:
100 
  
第 5 棵树:
5 
  
第 6 棵树:
23 
  
第 7 棵树:
8 
29 12 15 
  20 17 35 
  31   
  
提取的最小元素为: 1
提取之后的堆:
第 1 棵树:
5 
100 120 
  209 
  
第 2 棵树:
8 
29 12 15 
  20 17 35 
  31   
  
第 3 棵树:
23 
  
Heap after decreasing a key:
第 1 棵树:
2 
  
第 2 棵树:
8 
29 12 15 
  20 17 35 
  31   
  
第 3 棵树:
23 
  
第 4 棵树:
5 
120 
209 
  
Heap after decreasing a key:
第 1 棵树:
1 
209 
  
第 2 棵树:
8 
29 12 15 
  20 17 35 
  31   
  
第 3 棵树:
23 
  
第 4 棵树:
5 
  
第 5 棵树:
2 
  
Heap after deleting a node:
第 1 棵树:
1 
2 8 5 
23 29 12 15   
    20 17 35 
  31   
  

不相交集合

链表表示

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

// 不相交集合的链表表示
typedef struct Set_List
{
    Node* head;
    Node* tail;
    int size;
}Set_List;

typedef struct Node
{
    ElementType* x;
    Set_List* set;
    struct Node* next;
}Node;

// 建立新的集合
Node* Make_Set_List(ElementType* x)
{
    Set_List* set;
    set = (Set_List*)malloc(sizeof(Set_List));
    set->size = 1;
    Node* node;
    node = (Node*)malloc(sizeof(Node));
    node->x = x;
    node->next = NULL;
    node->set = set;
    set->head = node;

    return node;
}

// 合并动态集合
Node* Union_Set_List(Node* x, Node* y)
{
    Node* t1,* t2;  // t1 比 t2 尺寸小
    if (x->set->size < y->set->size)
    {
        t1 = x;
        t2 = y;
    }
    else
    {
        t2 = x;
        t1 = y;
    }
    t2->set->tail->next = t1;
    t2->set->tail = t1->set->tail;
    t2->set->size += t1->set->size;

    free(t1->set);

    Node* p;
    p = t1;
    while (p != NULL)
    {
        p->set = t2->set;
        p = p->next;
    }

    return t2;
}

// 返回集合代表
Node* Find_Set_List(Node* x)
{
    return x->set->head;
}


// 不相交集合森林表示
typedef struct Set_Tree_Node
{
    ElementType* x;
    struct Set_Tree_Node* p;
    int rank;
}Set_Tree_Node;

// 建立新的树
Set_Tree_Node* Make_Set_Tree(ElementType* x)
{
    Set_Tree_Node* t;
    t = (Set_Tree_Node*)malloc(sizeof(Set_Tree_Node));
    t->rank = 0;
    t->x = x;
    t->p = t;

    return t;
}

// 路径压缩
Set_Tree_Node* Find_Set_Tree(Set_Tree_Node* t)
{
    if (t->p != t)
    {
        t->p = Find_Set_Tree(t->p);
    }
    return t->p;
}

// 按秩合并 
Set_Tree_Node* Union_Set_Tree(Set_Tree_Node* x, Set_Tree_Node* y)
{
    Set_Tree_Node* t1, *t2;
    t1 = Find_Set_Tree(x);
    t2 = Find_Set_Tree(y);

    if (t1 != t2)
    {
        if (t1->rank > t2->rank)
        {
            t2->p = t1;
            return t1;
        }
        else
        {
            t1->p = t2;
            if (t1->rank == t2->rank)
                {
                    t2->rank ++;
                }
            return t2;
        }
    }
    else
    {
        return t1;
    }
    
}


int main()
{


    return 0;
}

森林表示

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;


// 不相交集合森林表示
typedef struct Set_Tree_Node
{
    ElementType* x;
    struct Set_Tree_Node* p;
    int rank;
}Set_Tree_Node;

// 建立新的树
Set_Tree_Node* Make_Set_Tree(ElementType* x)
{
    Set_Tree_Node* t;
    t = (Set_Tree_Node*)malloc(sizeof(Set_Tree_Node));
    t->rank = 0;
    t->x = x;
    t->p = t;

    return t;
}

// 路径压缩
Set_Tree_Node* Find_Set_Tree(Set_Tree_Node* t)
{
    if (t->p != t)
    {
        t->p = Find_Set_Tree(t->p);
    }
    return t->p;
}

// 按秩合并 
void Union_Set_Tree(Set_Tree_Node* x, Set_Tree_Node* y)
{
    Set_Tree_Node* t1, *t2;
    t1 = Find_Set_Tree(x);
    t2 = Find_Set_Tree(y);

    if (t1 != t2)
    {
        if (t1->rank > t2->rank)
        {
            t2->p = t1;
        }
        else
        {
            t1->p = t2;
            if (t1->rank == t2->rank)
            {
                t2->rank ++;
            }
        }
    }
}


int main()
{


    return 0;
}

斐波那契堆

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

// 斐波那契堆节点
typedef struct Fib_Heap_Node
{
    ElementType* x;
    Fib_Heap_Node* p;       // 父节点
    Fib_Heap_Node* child;   // 某一个孩子节点
    Fib_Heap_Node* left;    // 左兄弟
    Fib_Heap_Node* right;   // 右兄弟
    int degree;  // 孩子数目（度）
    bool mark;    // 标记
}Fib_Heap_Node;

// 斐波那契堆
typedef struct Fib_Heap
{
    int size;
    Fib_Heap_Node* min_node;
}Fib_Heap;

// 创建斐波那契堆
Fib_Heap* Create_Fib_Heap()
{
    Fib_Heap* H;
    H = (Fib_Heap*)malloc(sizeof(Fib_Heap));
    H->min_node = NULL;
    H->size = 0;
    return H;
}

// 递归删除斐波那契堆
void Free_Fib_Heap_Node(Fib_Heap_Node* node)
{
    if (node == NULL)
    {
        return;
    }

    Fib_Heap_Node* start = node;
    do {
        Fib_Heap_Node* child = node->child;
        Fib_Heap_Node* next = node->right;

        // 递归释放子节点
        Free_Fib_Heap_Node(child);

        // 释放当前节点
        free(node);

        node = next;
    } while (node != start);
}

void Free_Fib_Heap(Fib_Heap* H)
{
    if (H != NULL) {
        // 释放所有根节点
        Free_Fib_Heap_Node(H->min_node);

        // 释放堆结构本身
        free(H);
    }
}

// 斐波那契堆树根的个数
int Fib_Heap_Root_Count(Fib_Heap* H)
{
    if (H->min_node == NULL)
    {
        return 0;
    }
    else
    {
        int count = 1;
        Fib_Heap_Node* p;
        p = H->min_node->right;
        while (p != H->min_node)
        {
            count++;
            p = p->right;
        }
        return count;
    }
}

// 插入根节点   插在最小节点与根节点右边节点之间
void Fib_Heap_Insert_Root(Fib_Heap* H, Fib_Heap_Node* node)
{  
    // 只有一个根
    if (H->min_node->right == H->min_node)
    {
        H->min_node->right = node;
        H->min_node->left = node;
        node->left = H->min_node;
        node->right = H->min_node;
    }
    else
    {
        node->p = NULL;
        Fib_Heap_Node* p;
        p = H->min_node->right;

        H->min_node->right = node;
        p->left = node;
        node->left = H->min_node;
        node->right = p;
    }
}

// 插入节点
void Fib_Heap_Insert(Fib_Heap* H, ElementType* x)
{
    Fib_Heap_Node* node;
    node = (Fib_Heap_Node*)malloc(sizeof(Fib_Heap_Node));
    node->x = x;
    node->child = NULL;
    node->degree = 0;
    node->mark = 0;

    // 堆空
    if (H->min_node == NULL)
    {
        H->min_node = node;
        node->p = NULL;
        node->left = node;
        node->right = node;
    }
    else
    {
        // 插入节点为根
        Fib_Heap_Insert_Root(H, node);

        if (*x < *H->min_node->x)
        {
            H->min_node = node; // 改变min指针
        }
    }
    H->size ++;
}

// 合并堆
Fib_Heap* Fib_Heap_Union(Fib_Heap* H1, Fib_Heap* H2)
{
    Fib_Heap* H;
    H = Create_Fib_Heap();
    H->min_node = H1->min_node;
    H->size = H1->size + H2->size;
    // 根合并
    if (H1->min_node == NULL)
    {
        // 跳过
    }
    else if (H->min_node->right == H->min_node)   // H1只有一棵树
    {
        if (H2->min_node->right == H2->min_node)   // H2只有一棵树
        {
            H->min_node->right = H2->min_node;
            H->min_node->left = H2->min_node;
            H2->min_node->right = H->min_node;
            H2->min_node->left = H->min_node;
        }
        else
        {
            Fib_Heap_Insert_Root(H2, H->min_node);
        }
    }
    else    // H1有多棵树
    {
        if (H2->min_node->right == H2->min_node)   // H2只有一棵树
        {
            Fib_Heap_Insert_Root(H, H2->min_node);
        }
        else
        {
            Fib_Heap_Node* p,* q;
            p = H->min_node->right;
            q = H2->min_node->left;

            H->min_node->right = H2->min_node;
            H2->min_node->left = H->min_node;
            q->right = p;
            p->left = q;
        }
    }

    if ((H1->min_node == NULL) || (H2->min_node && H2->min_node->x < H1->min_node->x))
    {
        H->min_node = H2->min_node;
    }
    free(H1);
    free(H2);
    return H;
}

// 链接根节点   把y接为x的儿子
void Fib_Heap_Link(Fib_Heap* H, Fib_Heap_Node* y, Fib_Heap_Node* x)
{
    // 把y从根节点中移除
    y->left->right = y->right;
    y->right->left = y->left;

    // 把y填入x的孩子中
    y->p = x;
    Fib_Heap_Node* p;
    p = x->child;
    if (p == NULL)  // x原来没孩子
    {
        x->child = y;
        y->left = y;
        y->right = y;
    }
    else
    {
        p->right->left = y;
        y->right = p->right;
        p->right = y;
        y->left = p;
    }
    x->degree ++;

    y->mark = 0;
}

// 合并根链表
void Fib_Heap_Consolidate(Fib_Heap* H)
{
    Fib_Heap_Node** A;
    A = (Fib_Heap_Node**)malloc(sizeof(Fib_Heap_Node*) * H->size);
    for (int i = 0; i < H->size; i++)
    {
        A[i] = NULL;
    }
    Fib_Heap_Node** root_list;
    int count;
    count = Fib_Heap_Root_Count(H);
    Fib_Heap_Node* p;
    p = H->min_node;
    Fib_Heap_Node* x, *y;
    int d;
    for (int i = 0; i < count; i++)
    {
        x = p;
        p = p->right;
        d = x->degree;  // 当前节点的度数
        while (A[d] != NULL)
        {
            y = A[d];
            // 比谁小，然后交换
            if (*x->x > *y->x)
            {
                Fib_Heap_Node* t;
                t = x;
                x = y;
                y = t;
            }
            Fib_Heap_Link(H, y, x);
            A[d] = NULL;    //清空
            d++;    //存入下一个
        }
        A[d] = x;
    }

    // 根据 A 重建 H
    H->min_node = NULL;
    for (int i = 0; i < H->size; i++)
    {
        if (A[i] != NULL)
        {
            if (H->min_node == NULL)
            {
                H->min_node = A[i];
                H->min_node->right = H->min_node;
                H->min_node->left = H->min_node;
            }
            else
            {
                Fib_Heap_Insert_Root(H, A[i]);
                if (*A[i]->x < *H->min_node->x)
                {
                    H->min_node = A[i];
                }
            }
        }
    }
    
    free(A);
}

// 提取最小节点
ElementType* Fib_Heap_Extract_Min(Fib_Heap* H)
{
    Fib_Heap_Node* z;
    z = H->min_node;
    if (z != NULL)
    {
        // 令z的孩子都为根
        Fib_Heap_Node* child, *next;
        child = z->child;
        for (int i = 0; i < z->degree; i++)
        {
            next = child->right;
            Fib_Heap_Insert_Root(H, child);
            child = next;
        }

        ElementType* element;
        element = z->x;

        // 从斐波那契堆移除z
        z->left->right = z->right;
        z->right->left = z->left;

        // z为唯一节点
        if (H->size == 1)
        {
            H->min_node = NULL;
        }
        else
        {
            H->min_node = z->right;
            Fib_Heap_Consolidate(H);
        }
        H->size--;

        free(z);
        return element;
    }
    else
    {
        printf("空堆");
        return NULL;
    }
}

// 切断 切断x与父节点y，使x为根节点
void Fib_Heap_Cut(Fib_Heap* H, Fib_Heap_Node* x, Fib_Heap_Node* y)
{
    // x为y的孩子指针
    if (y->child == x)
    {
        // y只有一个孩子
        if (x->right == x)
        {
            y->child = NULL;
            Fib_Heap_Insert_Root(H, x);
        }
        else
        {
            y->child = x->right;
            x->right->left = x->left;
            x->left->right = x->right;
            Fib_Heap_Insert_Root(H, x);
        }
    }
    else
    {
        x->right->left = x->left;
        x->left->right = x->right;
        Fib_Heap_Insert_Root(H, x);
    }
    x->mark = 0;
}

// 级联切断
void Fib_Heap_Cascading_Cut(Fib_Heap* H, Fib_Heap_Node* y)
{
    Fib_Heap_Node* z;
    z = y->p;
    // y非根节点
    if (z != NULL)
    {
        if (y->mark == 0)
        {
            y->mark = 1;
        }
        else
        {
            Fib_Heap_Cut(H, y, z);
            Fib_Heap_Cascading_Cut(H, z);
        }
    }
}

// 关键字减值
void Fib_Heap_Decrease_Node(Fib_Heap* H, Fib_Heap_Node* x, ElementType* k)
{
    if (*k > *x->x)
    {
        printf("不能让值变大\n");
    }
    else
    {
        *(x->x) = *k;
        Fib_Heap_Node *y;
        y = x->p;

        if (y != NULL && *x->x < *y->x)
        {
            Fib_Heap_Cut(H, x, y);
            Fib_Heap_Cascading_Cut(H, y);
        }
        if (*x->x < *H->min_node->x)
        {
            H->min_node = x;
        }
    }
}

// 删除节点
void Fib_Heap_Delete(Fib_Heap* H, Fib_Heap_Node* x)
{
    ElementType p;
    p = -99999;
    Fib_Heap_Decrease_Node(H, x, &p);
    Fib_Heap_Extract_Min(H);
}

//链队列结构类型
typedef struct QueueNode
{
	Fib_Heap_Node* node;
	QueueNode* next;
}QueueNode;

typedef struct LinkQueue
{
	QueueNode* front;   // 队头指针
	QueueNode* rear;    // 队尾指针
    int length;         // 队列长度
}LinkQueue;

// 初始化队列
LinkQueue* InitLinkQueue()
{
	LinkQueue* q;
	q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (QueueNode*)malloc(sizeof(QueueNode));
	if (q->front == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	q->rear = q->front;
	q->front->next = NULL;
	q->front->node = NULL;
    q->length = 0;
	return q;
}

// 入队
void EnLinkQueue(LinkQueue* q, Fib_Heap_Node* e)
{
	QueueNode* p;
	p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL)
	{
		printf("开辟空间失败\n");
		exit(0);
	}
	p->node = e;
	p->next = NULL;
	q->rear->next = p;
	q->rear = p;
    q->length++;
}

// 出队
Fib_Heap_Node* DeLinkQueue(LinkQueue* q)
{
	if (q->length == 0)
	{
		printf("队空\n");
        return NULL;
	}
	else
	{
        q->length--;
		Fib_Heap_Node* node;
		QueueNode* queuenode;
		queuenode = q->front->next;
		node = queuenode->node;
		q->front->next = queuenode->next;
		if (queuenode == q->rear)
		{
			q->rear = q->front;
		}
		free(queuenode);
		return node;
	}
}

// 输出斐波那契堆
void Print_Fib_Heap_Tree(Fib_Heap_Node* root, int treeIndex)
{
    Fib_Heap_Node *blankNode;
    blankNode = (Fib_Heap_Node*)malloc(sizeof(Fib_Heap_Node));

    LinkQueue* queue = InitLinkQueue();
    EnLinkQueue(queue, root);

    printf("第 %d 棵树:\n", treeIndex);
    while (queue->length != 0)
    {
        int levelSize = queue->length; // 当前层的节点数
        for (int i = 0; i < levelSize; i++)
        {
            Fib_Heap_Node* node;
            node = DeLinkQueue(queue);

            // 打印当前节点
            if (node == blankNode)
            {
                printf("  ");  // 空白节点打印空格
            }
            else
            {
                printf("%d ", *node->x);
            }

            // 将子节点或空白节点加入队列
            Fib_Heap_Node* child;
            child = node->child;
            if (child != NULL)
            {
                // 将孩子都入队
                EnLinkQueue(queue, child);
                Fib_Heap_Node* current = child->right;
                while (current != child)
                {
                    EnLinkQueue(queue, current);
                    current = current->right;
                }
            }
            else if (node != blankNode)
            {
                // 对于没有子节点的父节点，加入一个空白节点
                EnLinkQueue(queue, blankNode);
            }
        }
        printf("\n"); // 完成一层的打印
    }
    free(blankNode);
}

void Print_Fib_Heap(Fib_Heap* H) {
    if (H == NULL || H->min_node == NULL)
    {
        printf("堆空\n");
    }

    Fib_Heap_Node* current = H->min_node;
    int treeIndex = 1;
    do
    {
        Print_Fib_Heap_Tree(current, treeIndex++);
        current = current->right;
    } while (current != H->min_node);
}


int main() {
    // 创建斐波那契堆
    Fib_Heap* H = Create_Fib_Heap();

    // 创建并插入一系列元素
    ElementType elements[10] = {23, 7, 35, 15, 29, 8, 17, 31, 12, 20};
    for (int i = 0; i < 10; i++) {
        Fib_Heap_Insert(H, &elements[i]);
    }
    printf("Initial heap:\n");
    Print_Fib_Heap(H);

    // 提取最小元素
    ElementType* min = Fib_Heap_Extract_Min(H);
    printf("提取的最小元素为: %d\n", *min);
    printf("提取之后的堆:\n");
    Print_Fib_Heap(H);

    // 创建另一个堆并合并
    Fib_Heap* H2 = Create_Fib_Heap();
    ElementType newElement[5] = {5, 100, 120, 209, 1};
    for (int i = 0; i < 5; i++) {
        Fib_Heap_Insert(H2, &newElement[i]);
    }
    printf("堆H2:\n");
    Print_Fib_Heap(H2);
    Fib_Heap* H3 = Fib_Heap_Union(H, H2);
    // 打印合并后的堆
    printf("Heap after union:\n");
    Print_Fib_Heap(H3);
    
    // 提取最小元素
    min = Fib_Heap_Extract_Min(H3);
    printf("提取的最小元素为: %d\n", *min);
    printf("提取之后的堆:\n");
    Print_Fib_Heap(H3);

    // 减少一个节点的关键字
    ElementType decreaseKey = 2;
    Fib_Heap_Decrease_Node(H3, H3->min_node->child, &decreaseKey);
    printf("Heap after decreasing a key:\n");
    Print_Fib_Heap(H3);

    decreaseKey = 1;
    Fib_Heap_Decrease_Node(H3, H3->min_node->left->child, &decreaseKey);
    printf("Heap after decreasing a key:\n");
    Print_Fib_Heap(H3);

    // 删除一个节点
    Fib_Heap_Delete(H3, H3->min_node->child);
    printf("Heap after deleting a node:\n");
    Print_Fib_Heap(H3);

    Free_Fib_Heap(H);
    Free_Fib_Heap(H2);
    Free_Fib_Heap(H3);

    return 0;
}