企业官网建设流程全解析

目录

一、QuickFind​

二、QuickUnion

三、代码实现

四、路径压缩

一、QuickFind

union1：

union2：

union(x,y)：查找x的组id w，查找y的组id u,把组id是w的更新为u

find(x,y)：查找x的组di w,查找y的组id u,相等为true,不相等为false

二、QuickUnion

quickunion(0,2):

quickunion(3,1):

quickunion(0,1):

2.1 基于size的算法改进

避免退化成链表，将元素少的树嫁接到元素多的树

2.2 基于rank的算法改进

避免复杂度高，将矮的树嫁接到高的树

三、代码实现

C static int findIndex(QuickFindSet *setQF,Element e) { for (int i = 0; i < setQF->n; ++i) { if (setQF->data[i] == e) { return i; } } return -1; }

此静态函数找元素e的下标

C int isSameQF(QuickFindSet* setQF, Element a, Element b) { int aIndex = findIndex(setQF,a); int bIndex = findIndex(setQF,b); if (aIndex == -1 || bIndex == -1) { return 0; } return setQF->groupID[aIndex] == setQF->groupID[bIndex]; // 组id是否一样 }

用a、b元素的下标找对应的组id

组id初始自己指向自己

0-7号元素的groupid分别是0-7,自己指自己

组id一样说明，在同一个组中

C void unionQF(QuickFindSet* setQF, Element a, Element b) { // 把b的老大管理的人，都合并到a上面(有些a到b) int aIndex = findIndex(setQF,a); int bIndex = findIndex(setQF,b); int gID = setQF->groupID[bIndex]; for (int i = 0; i < setQF->n; ++i) { if (setQF->groupID[i] == gID) // 满足跟b是同一个老大 { setQF->groupID[i] = setQF->groupID[aIndex]; // 把满足条件对应元素的老大，改为a的老大 } } }

gID存b元素对应组id，可能是b元素本身，也可能是其他元素

接下来进行遍历，如果仍存在与b同组id的元素，则将对应元素的组id改为a元素对应的组id，a元素的组id可能是a元素本身，也可能是其他元素

四、路径压缩

或者

如果我的内容对你有帮助，请点赞，评论，收藏。创作不易，大家的支持就是我坚持下去的动力！