980网站,建站视频网站,内网门户网站 建设方案,云南网站制作需求一.集合的表示 一个重要的操作是查某个元素属于哪个集合#xff0c;另一个操作是合并操作
从这个树的节点去找树根也就是从下往上找,要把树并起来只需把两个根并在一起就可以了
不存在已知一个节点去找孩子节点#xff0c;根重要的是已知一个节点找它的父亲节点,与之前的二…一.集合的表示 一个重要的操作是查某个元素属于哪个集合另一个操作是合并操作
从这个树的节点去找树根也就是从下往上找,要把树并起来只需把两个根并在一起就可以了
不存在已知一个节点去找孩子节点根重要的是已知一个节点找它的父亲节点,与之前的二叉树一个节点指向孩子不同这个是一个节点指向父亲 Data是值Parent是父节点的下标
二.集合运算 if(iMaxSize)return -1;
表示没有找到
for(;s[i].Parent0;is[i].Parent);
找父亲到Parent等于-1时找到,退出了i等于父亲节点的下标 不断做并这个操作树会越来越大越来越高,会导致查找效率变低因为需要从下往上找
如果在结构体里增加一个记录个数只有根节点需要记录元素个数,别的无所谓导致空间浪费
根节点的Parent用负数表示可以利用这一点比如一个集合元素有3个根节点的Parent用-3表示三个
#includeiostream
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;
}
