集合有点语言会带有,有的没有。但是我想redis的集合set你一定听说过或者用过。下面咱们用链表来实现set
相信有了前面的基础我们可以很容易的实现set集合
需要引入我的链表的list.c和list.h
头文件
// // set.h // set // // created by bikang on 16/9/18. // copyright (c) 2016年 bikang. all rights reserved. // #ifndef __set__set__ #define __set__set__ #include #include "list.h" typedef list set; void set_init(set *set,int(*match)(const void *k1,const void *k2),void(*destroy)(void*data)); #define set_destroy list_destroy //插入 int set_insert(set *set,const void *data); //删除 int set_remove(set *set,void **data); //并集 int set_union(set *setu,const set *set1,const set *set2); //交集 int set_intersection(set *seti,const set *set1,const set *set2); //差集 int set_difference(set *setd,const set *set1,const set *set2); //是否是他的成员 int set_is_member(const set *set,const void *data); //是否是子集 int set_is_subset(const set *set1,const set *set2); //是否相等 int set_is_equal(const set *set1,const set *set2); #define set_size(set) ((set)->size) #endif /* defined(__set__set__) */
实现
// // set.c // set // // created by bikang on 16/9/18. // copyright (c) 2016年 bikang. all rights reserved. // #include #include #include "set.h" //初始化集合 void set_init(set *set,int(*match)(const void *k1,const void *k2),void(*destroy)(void*data)){ list_init(set,destroy); set->match = match; return; } //插入数据 int set_insert(set *set,const void *data){ if(set_is_member(set, data)){ return 1; } return list_ins_next(set, list_tail(set), data); } //删除数据 int set_remove(set *set,void **data){ listelmt *item,*pre; pre = null; for(item = list_head(set);item != null;item = list_next(item)){ if(set->match(*data,list_data(item))) break; pre = item; } if(item == null) return -1; return list_rem_next(set, pre, data); } //并集 int set_union(set *setu,const set *set1,const set *set2){ listelmt *item; void *data; set_init(setu, set1->match, null); for(item = list_head(set1);item != null;item = list_next(item)){ data = list_data(item); if(list_ins_next(setu, list_tail(setu), data) != 0){ set_destroy(setu); return -1; } } for(item = list_head(set2);item != null;item = list_next(item)){ data = list_data(item); if(!set_is_member(setu, list_data(item))){ if(list_ins_next(setu, list_tail(setu), data) != 0){ set_destroy(setu); return -1; } } } return 0; } //交集 int set_intersection(set *seti,const set *set1,const set *set2){ listelmt *item; void *data; set_init(seti, set1->match, null); for(item = list_head(set1);item != null;item = list_next(item)){ if(set_is_member(set2, list_data(item))){ data = list_data(item); if(list_ins_next(seti, list_tail(seti), data) != 0){ set_destroy(seti); return -1; } } } return 0; } //差集 int set_difference(set *setd,const set *set1,const set *set2){ listelmt *item; void *data; set_init(setd, set1->match, null); for(item = list_head(set1);item != null;item = list_next(item)){ if(!set_is_member(set2, list_data(item))){ data = list_data(item); if(list_ins_next(setd, list_tail(setd), data) != 0){ set_destroy(setd); return -1; } } } return 0; } //是否是他的成员 int set_is_member(const set *set,const void *data){ listelmt *item; for(item = list_head(set);item != null;item = list_next(item)){ if(set->match(data,list_data(item))) return 1; } return 0; } //set1是否是set2的子集 int set_is_subset(const set *set1,const set *set2){ listelmt *item; // set1 if(set_size(set1) > set_size(set2)) return 0; for(item = list_head(set1);item != null;item = list_next(item)){ if(!set_is_member(set2, list_data(item))) return 0; } return 1; } //是否相等 int set_is_equal(const set *set1,const set *set2){ if(set_size(set1) != set_size(set2)) return 0; return set_is_subset(set1, set2); return 0; }
测试用例
// // main.c // set // // created by bikang on 16/9/18. // copyright (c) 2016年 bikang. all rights reserved. // #include #include "set.h" int match_data(const void *d1 ,const void *d2); void t_match(); void tset();//测试set void print_set(set *set);//打印set int main(int argc, const char * argv[]) { //t_match(); tset(); return 0; } void tset(){ //初始化set1 set *set1 = (set*)malloc(sizeof(set)); set_init(set1, match_data, null); //插入 int i = 1; int *pi = &i; int i2 = 2;int *pi2 = &i2; int i3 = 3; int *pi3 = &i3; int i4 = 4;int *pi4 = &i4; int i5 = 5; int *pi5 = &i5; int i6 = 6;int *pi6 = &i6; int i7 = 2;int *pi7 = &i7; set_insert(set1, pi); set_insert(set1, pi2); set_insert(set1, pi3); set_insert(set1, pi4); set_insert(set1, pi5); set_insert(set1, pi6); set_insert(set1, pi7); print_set(set1); //集合大小 printf("set_size=%dn",set_size(set1)); //删除 set_remove(set1, (void**)&pi5); print_set(set1); //初始化set2 set *set2 = (set*)malloc(sizeof(set)); set_init(set2, match_data, null); int i8 = 6; int *pi8 = &i8; int i9 = 7;int *pi9 = &i9; int i10 = 8;int *pi10 = &i10; set_insert(set2, pi8); set_insert(set2, pi9); set_insert(set2, pi10); print_set(set2); //并集 set *setu = (set*)malloc(sizeof(set)); set_init(setu, match_data, null); set_union(setu, set1, set2); print_set(setu); //交集 set *seti = (set*)malloc(sizeof(set)); set_init(seti, match_data, null); set_intersection(seti, set1, set2); print_set(seti); //差集 set *setd = (set*)malloc(sizeof(set)); set_init(setd, match_data, null); set_difference(setd, set1, set2); print_set(setd); //是否是子集 printf("set_is_sub=%dn",set_is_subset(setd, set1)); //摧毁集合 set_destroy(set1); set_destroy(set2); } int match_data(const void *d1 ,const void *d2){ if(*(int*)d1 == *(int*)d2) return 1; return 0; } void t_match(){ int i = 1; int *pi = &i; int i2 = 2;int *pi2 = &i2; printf("match_result:%d",match_data(pi, pi2)); } void print_set(set *set){ listelmt *item; if(set_size(set) == 0) { puts("set is emptyn"); return; } for(item = list_head(set);item != null;item = list_next(item)){ printf("%d,",*(int*)list_data(item)); } printf("n"); return; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/608016.html