集合的表示：
1.集合运算：交、并、补、差，判定里两个元素是否属于某一个集合
2.并查集：集合并、查某元素属于什么集合
3.并查集可以用树结构表示，树的每个结点表示一个集合元素
双亲表示法：（孩子指向双亲）
这个树结构采用数组存储形式：
数组每个元素的类型描述为：
1 typedef struct { 2 ElementType Data; 3 int Parent; 4 }SetType;
集合运算（下面的完整代码中用简化版的查，并运算，体会二者差别）
（1）查找某个元素所在集合（用根节点表示）
1 int Find(SetType s[], ElementType X) 2 { //在数组s中查找值为x的元素的所属集合 3 //MaxSize是全局变量，为数组s的最大长度 4 int i; 5 for(i = 0; i < MaxSize && S[i].Data != X; i++); 6 if(i >= MaxSize) return -1; //未找到x,返回-1 7 for(; s[i].parent >= 0; i = s[i].parent); 8 return i; //找到x所属集合，返回树根节点在数组s中的下标 9 }
（2）集合并运算
分别找到x1, x2两个元素所在集合树的根节点
如果他们不同根，则将其中一个根节点的父节点设置成另一个根节点的数组下标
1 void Union(SetType S[], ElementType x1, ElementType x2 ) 2 { 3 int Root1, Root2; 4 Root1 = Find(S, x1); 5 Root2 = Find(S, x2); 6 if(Root1 != Root2) 7 S[Root2].parent = Root1; 8 }
为了改善合并以后的查找性能，可以采用小的集合合并到相对大的集合
用根节点的parent的绝对值来表示集合的结点个数
简化版查、并运算完整代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define MaxSize 15 5 typedef int ElementType; //默认元素用非负数表示 6 typedef int SetName; //默认用根节点的下标表示集合名称 7 typedef ElementType SetType[MaxSize]; 8 9 void Initialization(SetType S, int n) 10 { 11 for (int i = 0; i < n; i++) 12 S[i] = -1; 13 } 14 15 16 SetName Find(SetType S, ElementType X) 17 { 18 //默认集合元素全部初始化为-1 19 for (; S[X] >= 0; X = S[X]); 20 return X; 21 } 22 23 24 void Union(SetType S, SetName root1, SetName root2) 25 { 26 S[root2] = root1; 27 } 28 29 void Input_connection(SetType S) 30 { 31 ElementType u, v; 32 SetName root1, root2; 33 scanf_s("%d %d", &u, &v); 34 root1 = Find(S, u - 1); 35 root2 = Find(S, v - 1); 36 if (root1 != root2) 37 Union(S, root1, root2); 38 } 39 40 void Check_connection(SetType S) 41 { 42 ElementType u, v; 43 SetName root1, root2; 44 scanf_s("%d %d", &u, &v); 45 root1 = Find(S, u - 1); 46 root2 = Find(S, v - 1); 47 if (root1 == root2) 48 printf("yes\n"); 49 else 50 printf("no\n"); 51 } 52 53 //检查是否所有结点都连通了 54 void Check_network(SetType S, int n) 55 { 56 int i, counter = 0; 57 for (i = 0; i < n; i++) 58 if (S[i] < 0) counter++; 59 if (counter == 1) 60 printf("The net work is connected.\n"); 61 else 62 printf("There are %d components.\n", counter); 63 } 64 65 int main() 66 { 67 SetType S; 68 int n; 69 char in; 70 scanf_s("%d", &n); 71 Initialization(S, n); 72 do{ 73 74 scanf_s("%c", &in); 75 switch (in) 76 { 77 case 'I': 78 Input_connection(S); 79 break; 80 case 'C': 81 Check_connection(S); 82 break; 83 case 'S': 84 Check_network(S, n); 85 break; 86 } 87 } while (in != 'S'); 88 return 0; 89 }
按秩归并（进一步优化程序）
有两种方式
（一）
1 //按秩归并 2 void Union(SetType S, SetName root1, SetName root2) 3 { 4 /*if (S[root1] < S[root2]) //S[root]中存树的高度 5 S[root2] = root1; 6 else 7 { 8 if (S[root1] == S[root2]) 9 S[root1]--; 10 S[root1] = root2; 11 }*/ 12 }
（二）
1 void Union(SetType S, SetName root1, SetName root2) 2 { 3 4 if (S[root2] < S[root1]) //S[root]中存树的结点个数 5 { 6 S[root2] += S[root1]; 7 S[root1] = root2; 8 } 9 else 10 { 11 S[root1] += S[root2]; 12 S[root2] = root1; 13 } 14 15 16 }
路径压缩（极大的减少运行时间）
1 //路径压缩 降低了输的高度，使查找过程中访问过的结点都直接指向根节点 2 SetName Find(SetType S, ElementType X) 3 { 4 if (S[X] < 0) 5 return X; 6 else 7 return S[X] = Find(S, S[X]); //先找到根，把根变成X的父节点，在返回根 8 }
