本文主要是介绍C.Interface.And.Implementations—set的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、A set is an unordered collection of distinct members.
2、The basic operations on a set are testing for membership, adding members, and removing members.
3、Other operations include set union, intersection, difference, and symmetric difference.
set实现类似于table(key-value系统)的实现，采用类似的“哈希表和链表”的底层数据结构。可以参看上一章的内容。
=============================set.h==============================
#ifndef SET_INCLUDED
#define SET_INCLUDED#define T Set_T
typedef struct T *T;//exported functions
extern T Set_new (int hint,int cmp(const void *x, const void *y),unsigned hash(const void *x));extern void Set_free (T *set);
extern int Set_length(T set);
extern int Set_member(T set, const void *member);
extern void Set_put (T set, const void *member);
extern void *Set_remove(T set, const void *member);
extern void Set_map (T set,void apply(const void *member, void *cl), void *cl);
extern void **Set_toArray(T set, void *end);
extern T Set_union (T s, T t);
extern T Set_inter (T s, T t);
extern T Set_minus (T s, T t);
extern T Set_diff (T s, T t);#undef
#endif
=============================set.c============================
#include <limits.h>
#include <stddef.h>
#include "mem.h"
#include "assert.h"
#include "arith.h"
#include "set.h"#define T Set_T//types
struct T{int length;unsigned timestamp;int (*cmp)(const void *x, const void *y);unsigned (*hash)(const void *x);int size;struct member{struct member *link;const void *member;} **buckets;
}//static functions
static int cmpatom(const void *x, const void *y){return x != y;
}static unsigned hashatom(const void *x){return (unsigned long)x>>2;
}static T copy(T t, int hint){T set;assert(t);set = Set_new(hint, t->cmp, t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}return set;
}//functions
T Set_new(int hint,int cmp(const void *x, const void *y),unsigned hash(const void *x)){T set;int i;static int primes[] = { 509, 509, 1021, 2053, 4093,8191, 16381, 32771, 65521, INT_MAX };assert(hint >= 0);for(i = 1; primes[i] < hint; ++i){;set = ALLOC(sizeof(*set) +primes[i-1]*sizeof(set->buckets[0]));set->size = primes[i-1];set->cmp = cmp ? cmp : cmpatom;set->hash = hash ? hash : hashatom;set->buckets = (struct member **)(set + 1);for(i = 0; i < set->size; ++i){set->buckets[i] = NULL;}set->length = 0;set->timestamp = 0;return set;
}int Set_member(T set, const void *member){int i;struct member *p;assert(set);assert(member);//search set for memberi = (*set->hash)(member)%set->size;for(p = set->buckets[i]; p; p = p->link){if((*set->cmp)(member, p->member) == 0)break;}return p != NULL;
}void Set_put(T set, const void *member){int i;struct member *p;assert(set);assert(member);//search set for memberi = (*set->hash)(member)%set->size;for(p = set->buckets[i]; p; p = p->link){if((*set->cmp)(member, p->member) == 0)break;}if(p == NULL){//add member to setNEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}else{p->member = member;}set->timestamp++;
}void *Set_remove(T set, const void *member){int i;struct member **pp;assert(set);assert(member);set->timestamp++;i = (*set->hash)(member)%set->size;for(pp = &set->buckets[i]; *pp; pp = &(*pp)->link){if((*set->cmp)(member, (*pp)->member) == 0){struct member *p = *pp;*pp = p->link;member = p->member;FREE(p);set->length--;retunr (void *)member;}}return NULL;
}int Set_length(T set){assert(set);return set->length;
}void Set_free(T *set){assert(set && *set);if((*set)->length > 0){int i;struct member *p; *q;for(i = 0; i < (*set)->size; ++i){for(p = (*set)->buckets[i]; p; p = q){q = p->link;FREE(p);}}}FREE(*set);
}void Set_map(T set,void apply(const void *member, void *cl), void *cl){int i;unsigned stamp;struct member *p;assert(set);assert(apply);stamp = set->timestamp;for(i = 0; i < set->size; ++i){for(p = set->buckets[i]; p; p = p->link){apply(p->member, cl);assert(set->timestamp == stamp);}}
}void **Set_toArray(T set, void *end){int i, j = 0;void **array;struct member *p;assert(set);array = ALLOC((set->length + 1)*sizeof(*array));for(i = 0; i < set->size; ++i){for(p = set->buckets[i]; p; p = p->link){array[j++] = (void *)p->member;}}array[j] = end;return array;
}T Set_union(T s, T t){if(s == NULL){assert(t);return copy(t, t->size);}else if( t == NULL){return copy(s, s->size);}else{T set = copy(s, Arith_max(s->size, t->size));assert(s->cmp == t->cmp && s->hash == t->hash);{//for each member q in tint i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){Set_put(set, q->member);}}}return set;}
}T Set_inter(T s, T t){if(s == NULL){assert(t);return Set_new(t->size, t->cmp, t->hash);}else if( t == NULL){return Set_new(s->size, s->cmp, s->hash);}else if(s->length < t->length){return Set_inter(t, s);}else{T set = Set_new(Arith_min(s->size, t->size), s->cmp, s->hash);assert(s->cmp == t->cmp && s->hash == t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(Set_member(s, q->member)){struct member *pconst void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}return set;}
}T Set_minus(T t, T s){if(t == NULL){assert(s);return Set_new(s->size, s->cmp, s->hash);}else if(s == NULL){return copy(t, t->size);}else{T set = Set_new(Arith_min(s->size, t->size),s->cmp, s->hash);assert(s->cmp == t->cmp && s->hash == t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(!Set_member(s, q->member)){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}return set;}
}T Set_diff(T s, T t){if(s == NULL){assert(t);return copy(t, t->size);}else if(t == NULL){return copy(s, s->size);}else{T set = Set_new(Arith_min(s->size, t->size),s->cmp, s->hash);assert(s->cmp == t->cmp && s->hash == t->hash);{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(!Set_member(s, q->member)){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}{T u = t; t = s; s = u;}{int i;struct member *q;for(i = 0; i < t->size; ++i){for(q = t->buckets[i]; q; q = q->link){if(!Set_member(s, q->member)){struct member *p;const void *member = q->member;int i = (*set->hash)(member)%set->size;NEW(p);p->member = member;p->link = set->buckets[i];set->buckets[i] = p;set->length++;}}}}return set;}
}
这篇关于C.Interface.And.Implementations—set的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
