做水军那些网站好,发布做任务网站,软件培训学校哪家好,厦门建设银行官方网站【0】README
0.1#xff09;本文总结于 数据结构与算法分析#xff0c; 但源代码均为原创#xff0c;旨在实现 不相交集ADT的两个操作#xff1a;合并集合union查找集合find#xff1b; 0.2#xff09; 不相交集ADT 的 Introduction #xff0c; 参见 http://blog.csd…【0】README
0.1本文总结于 数据结构与算法分析 但源代码均为原创旨在实现 不相交集ADT的两个操作合并集合union查找集合find 0.2 不相交集ADT 的 Introduction 参见 http://blog.csdn.net/PacosonSWJTU/article/details/49716905 【1】灵巧求并算法——按集合大小求并
1.1大小求并法定义上面的Union执行是相当任意的 通过使第二棵树 成为第一棵树的子树而完成合并对其的改进是借助任意的方法打破现有关系 使得总让较小的树成为较大树的子树我们把这种方法叫做 大小求并法 1.2可以看到 如果Union 操作都是按照大小求并的话那么任何节点的深度均不会超过 logN 1.3首先注意节点的深度为0 然后它的深度随着一次 Union 的结果而增加的时候该节点则被置于至少是 它以前所在树两倍大的一棵树上因此它的深度最多可以增加 logN次
1.3.2 Find 操作 的运行时间为 OlogN 而连续M次操作则花费 OMlogN1.3.3 下图指出在16次Union操作后可能得到这种最坏的树而且如果所有的Union都对相等大小的树进行 那么这样的树是会得到的
1.4为了实现这种方法 我们需要记住每个树的大小。由于我们实际上只使用一个数组因此可以让每个根的数组元素包含它 的树的大小的负值 1.5已经证明若使用按大小求并则连续 M次运算需要 OM平均时间 这是因为 当随机的Union执行时 整个算法一般只有一些很小的集合通常是一个元素与 大 集合 合并
1.6souce code printing
1.6.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter8/p203_unionBySize.cSource Code Statements S1显然本源代码只对元素的size进行了加没有减因为我想的话 元素只能合并一次也即是元素C起初合并到了集合A就不能再次合并到集合B 元素C就一直属于集合A的子集了S2当然这个代码只是 大致上实现了按大小求并的思想如果元素C还可以再次合并到其他集合的话这就涉及到集合根元素的size的加减问题了需要的话添加之即可1.6.2souce 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(ElementType index, UnionSet* set);// 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(i0; isize; 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(ElementType index, UnionSet* set)
{UnionSet temp; while(1){temp set[index];if(temp-parent -1)break;index temp-parent;}return index;
} 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 union set by size \n);//printf(\n\t the initial array is as follows \n);//printArray(data, size); printf(\n\t the init union set are as follows \n);unionSet initUnionSet(size, data); // initialize the union set overprintSet(unionSet, size);printf(\n\t after union(1,5) union(2,5) union(3,4) union(4,5) \n);setUnion(unionSet, 1, 5);setUnion(unionSet, 2, 5);setUnion(unionSet, 3, 4);setUnion(unionSet, 4, 5);printSet(unionSet, size);printf(\n\t after union(9,8) union(7,6) union(3,6) \n);setUnion(unionSet, 9, 8);setUnion(unionSet, 7, 6);setUnion(unionSet, 3, 6); 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);
}1.6.3printing result 【2】灵巧求并算法——按集合高度求并
2.1按高度求并定义 另外一种方法是按照高度求并按照高度求并是按大小求并的简单修改推荐 2.2它同样保证所有的树的深入最多是 OlogN)。我们使得 浅的树 成为深 的树的子树这是一种平缓算法 因为只有当两颗相等深度的树求并时树的高度才会增加此时树的高度增加1。 2.3source code printing result
2.3.1download source code https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter8/p205_unionByHeight.c2.3.2source 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 depth-sibling expr
struct UnionSet
{int parent;int height;ElementType value;
};UnionSet makeEmpty();
UnionSet* initUnionSet(int depth, ElementType* data);
void printSet(UnionSet* set, int depth);
void printArray(ElementType data[], int depth);
int find(ElementType index, UnionSet* set);// 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(i0; isize; 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 depth -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-height 0;return temp;
}// merge set1 and set2 by depth
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]-height set[index2]-height) set[index2]-parent index1; else if(set[index1]-height set[index2]-height) set[index1]-parent index2; else{set[index1]-parent index2;set[index2]-height; // only if the height of both of subtrees is equal, the height increases one}
} //find the root of one set whose value equals to given value
int find(ElementType index, UnionSet* set)
{UnionSet temp; while(1){temp set[index];if(temp-parent -1)break;index temp-parent;}return index;
} 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 union set by depth \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 overprintSet(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); 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.3printing results
