数据结构-集合

一.集合的表示

一个重要的操作是查某个元素属于哪个集合，另一个操作是合并操作

从这个树的节点去找树根也就是从下往上找,要把树并起来只需把两个根并在一起就可以了

不存在已知一个节点去找孩子节点，根重要的是已知一个节点找它的父亲节点,与之前的二叉树一个节点指向孩子，不同这个是一个节点指向父亲

Data是值Parent是父节点的下标

二.集合运算

if(i>=MaxSize)return -1;

表示没有找到

for(;s[i].Parent>=0;i=s[i].Parent);

找父亲到Parent等于-1时找到,退出了i等于父亲节点的下标

不断做并这个操作树会越来越大越来越高,会导致查找效率变低，因为需要从下往上找

如果在结构体里增加一个记录个数，只有根节点需要记录元素个数,别的无所谓，导致空间浪费

根节点的Parent用负数表示，可以利用这一点比如一个集合元素有3个根节点的Parent用-3表示三个

#include<iostream>
using namespace std;
typedef int ElementType;
#define MaxSize 1000
typedef struct {ElementType Data;//存值int Parent;//指向父亲结点
}SetType;
int Find(SetType s[], ElementType X) {/*在数组s中查找值为x的元素所属的集合*//*MaxSize是全局变量，为数组s的最大长度*/int i;for (i = 0; i < MaxSize && s[i].Data != X; i++);if (i >= MaxSize)return -1;/*未找到X,返回-1*/for (; s[i].Parent >= 0; i = s[i].Parent);return i;/*找到X所属集合,返回树根结点在数组s中的下标*/
}
void Union(SetType s[], ElementType X1, ElementType X2) {int Root1, Root2;Root1 = Find(s, X1);//找到X1的根节点下标Root2 = Find(s, X2);//找到X2的根节点下标//如果根节点的下标不同，说明是一个集合if (Root1 != Root2) {if (s[Root1].Parent >s[ Root2].Parent) {//将小集合挂载到大集合s[Root1].Parent = Root2;//x1挂载到x2的集合s[Root2].Parent += -1;}elses[Root2].Parent = Root1; // x2挂载到x1的集合s[Root1].Parent += -1;}}
int main()
{SetType s[MaxSize];//初始化集合,所有结点都是父节点for (int i = 0; i < MaxSize; i++) {s[i].Data = i + 1;s[i].Parent = -1;}cout << Find(s, 5) << endl;Union(s, 3, 5);cout << Find(s, 4) << endl;cout << Find(s, 3) << endl;Union(s, 1, 3);Union(s, 2, 4);Union(s, 8, 6);cout << Find(s, 6) << endl;cout << Find(s, 8) << endl;return 0;
}