c実装set集合
21358 ワード
集合は少しプログラミング言語がありますが、ありますか.しかし、redisの集合setはきっと聞いたことがあるか使ったことがあると思います.チェーンテーブルでsetを実現します
前の基礎があればset集合を簡単に実現できると信じています
私のチェーンテーブルのlistを導入する必要があります.cとlist.h
ヘッダファイル
インプリメンテーション
テストケース
前の基礎があれば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 <stdlib.h>
#include <string.h>
#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=%d
",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=%d
",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 empty
");
return;
}
for(item = list_head(set);item != NULL;item = list_next(item)){
printf("%d,",*(int*)list_data(item));
}
printf("
");
return;
}