【0】README

0.1）本文總結(jié)于 數(shù)據(jù)結(jié)構(gòu)與算法分析， 源代碼均為原創(chuàng)， 旨在實現(xiàn) 對不相交集合的路徑壓縮操作；
0.2）對求并后的集合進行路徑壓縮，目的是降低集合（合并樹）的深度，減少find 操作的時間復(fù)雜度；
0.3） for introduction to non-intersect set ADT ,please refet to http://blog.csdn.net/PacosonSWJTU/article/details/49716905 , and for details of finding or unionSet operations towards non-intersect set , please refer to http://blog.csdn.net/pacosonswjtu/article/details/49717009

---

【1】 路徑壓縮相關(guān)

1.1）基于這樣的觀察：執(zhí)行 Union操作 的任何算法都將產(chǎn)生相同的最壞情形的樹，因為它必然會隨意打破樹間的平衡。因此，無需對整個數(shù)據(jù)結(jié)構(gòu)重新加工而使算法加速的唯一方法是： 對Find 操作做些更聰明的工作；
1.2）路徑壓縮定義：設(shè)操作是Find（X）， 此時路徑壓縮的效果是， 從X到根的路徑上的每一個節(jié)點都使它的父節(jié)點變成根；執(zhí)行find（15）后壓縮路徑的效果為：

對路徑壓縮算法的分析（Analysis）

• A1）路徑壓縮的實施在于 使用額外的兩次指針移動， 節(jié)點13和14 現(xiàn)在離根近了一個位置， 而節(jié)點15和16離根近了兩個位置；
• A2）因此， 對這些節(jié)點未來的快速訪問將由于花費 額外的工作來進行路徑壓縮而得到補償；

1.3）路徑壓縮對 基本的 Find操作改變不大。對 Find 操作來說，唯一的變化是 使得 S[X] 等于 由Find 返回的值；這樣，在集合的根被遞歸地找到以后， X 就直接指向了它， 對通向根的路徑上的每一個節(jié)點這將遞歸地出現(xiàn)，因此實現(xiàn)了路徑壓縮；
1.4）路徑壓縮可以和 大小求并完全兼容，這就使得兩個例程可以同時實現(xiàn)；
1.5）路徑壓縮不完全與 按高度求并兼容，因為路徑壓縮可以改變樹的高度；

---

【2】source code + printing results

2.1）download source code：
https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter8/p206_pathCompression.c

• souce code statements：路徑壓縮源代碼中使用的集合求并方法是： 按大小求并：

2.2）source code at a glance：

#include <stdio.h> #include <malloc.h>#define ElementType int #define Error(str) printf("\n error: %s \n",str) struct UnionSet; typedef struct UnionSet* UnionSet;// we adopt the child-sibling expr struct UnionSet {int parent;int size;ElementType value; };UnionSet makeEmpty(); UnionSet* initUnionSet(int size, ElementType* data); void printSet(UnionSet* set, int size); void printArray(ElementType data[], int size); int find(int index, UnionSet* set); void pathCompress(int, UnionSet*);// initialize the union set UnionSet* initUnionSet(int size, ElementType* data) {UnionSet* set; int i;set = (UnionSet*)malloc(size * sizeof(UnionSet));if(!set){Error("out of space, from func initUnionSet"); return NULL;} for(i=0; i<size; i++){set[i] = makeEmpty();if(!set[i])return NULL;set[i]->value = data[i];}return set; }// allocate the memory for the single UnionSet and evaluate the parent and size -1 UnionSet makeEmpty() {UnionSet temp;temp = (UnionSet)malloc(sizeof(struct UnionSet));if(!temp){Error("out of space, from func makeEmpty!"); return NULL;}temp->parent = -1;temp->size = 1;return temp; }// merge set1 and set2 by size void setUnion(UnionSet* set, int index1, int index2) {//judge whether the index1 or index2 equals to -1 ,also -1 represents the rootif(index1 != -1)index1 = find(index1, set);if(index2 != -1)index2 = find(index2, set);if(set[index1]->size > set[index2]->size){set[index2]->parent = index1;set[index1]->size += set[index2]->size;}else{set[index1]->parent = index2;set[index2]->size += set[index1]->size;} } //find the root of one set whose value equals to given value int find(int index, UnionSet* set) {UnionSet temp; while(1){temp = set[index];if(temp->parent == -1)break;index = temp->parent;}return index; } // conducting path compression towards union set with given index void pathCompress(int index, UnionSet* set) { int root;int i;int parent;//1st step: find the top root contains the element under index root = find(index, set);//2nd step: path compression beginsi = set[index]->parent;set[index]->parent = root;while(i != -1) { parent = set[i]->parent; if(parent == root)break;set[i]->parent = root;i = parent;} }int main() {int size;UnionSet* unionSet;ElementType data[] = {110, 245, 895, 658, 321, 852, 147, 458, 469, 159, 347, 28};size = 12;printf("\n\t====== test for conducting path compression towards union set by size ======\n");//printf("\n\t=== the initial array is as follows ===\n");//printArray(data, depth); printf("\n\t=== the init union set are as follows ===\n");unionSet = initUnionSet(size, data); // initialize the union set over//printSet(unionSet, size);printf("\n\t=== after union(0, 1) + union(2, 3) + union(4, 5) + union(6, 7) + union(8, 9) + union(10 ,11) ===\n");setUnion(unionSet, 0, 1);setUnion(unionSet, 2, 3);setUnion(unionSet, 4, 5);setUnion(unionSet, 6, 7);setUnion(unionSet, 8, 9); setUnion(unionSet, 10, 11); //printSet(unionSet, size);printf("\n\t=== after union(1, 3) + union(5, 7) + union(9, 11) ===\n");setUnion(unionSet, 1, 3);setUnion(unionSet, 5, 7);setUnion(unionSet, 9, 11);//printSet(unionSet, size); printf("\n\t=== after union(3, 7) + union(7, 11) ===\n");setUnion(unionSet, 3, 7);setUnion(unionSet, 7, 11); printSet(unionSet, size); printf("\n\t=== after pathCompress(0, unionSet) + pathCompress(8, unionSet) ===\n");pathCompress(0, unionSet) ;pathCompress(8, unionSet);printSet(unionSet, size); return 0; }void printArray(ElementType data[], int size) {int i;for(i = 0; i < size; i++) printf("\n\t data[%d] = %d", i, data[i]); printf("\n\n"); } void printSet(UnionSet* set, int size) {int i;UnionSet temp;for(i = 0; i < size; i++){ temp = set[i];printf("\n\t parent[%d] = %d", i, temp->parent); }printf("\n"); }

2.3）printing results：

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的不相交集合求并的路径压缩的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。