目录一、QuickFind​二、QuickUnion三、代码实现四、路径压缩一、QuickFindunion1union2union(x,y)查找x的组id w查找y的组id u,把组id是w的更新为ufind(x,y)查找x的组di w,查找y的组id u,相等为true,不相等为false二、QuickUnionquickunion(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元素对应的组ida元素的组id可能是a元素本身也可能是其他元素四、路径压缩或者如果我的内容对你有帮助请点赞评论收藏。创作不易大家的支持就是我坚持下去的动力