c实现set集合

发布时间：2020-12-13 21:14:28 所属栏目：PHP教程来源：网络整理

导读：集合有点编程语言会带有，有的没有。但是我想redis的集合set你1定听说过或用过。下面我们用链表来实现set 相信有了前面的基础我们可以很容易的实现set集合需要引入我的链表的list.c和list.h 头文件 // // set.h // set // // Created by bikang on 16/9/18.

集合有点编程语言会带有，有的没有。但是我想redis的集合set你1定听说过或用过。下面我们用链表来实现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 <stdlib.h>
#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 *set2);
//差集
int set_difference(Set *setd,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,data) != 0){
                set_destroy(setu);
                return -1;
            }
        }
    }
    return 0;
}

//交集
int set_intersection(Set *seti,const Set *set2){
    ListElmt *item;
    void *data;
    set_init(seti,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 *set2){
    ListElmt *item;
    void *data;
    set_init(setd,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 <stdio.h>
#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,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,NULL);
    set_union(setu,set1,set2);
     print_set(setu);
    //交集
    Set *seti = (Set*)malloc(sizeof(Set));
    set_init(seti,NULL);
    set_intersection(seti,set2);
    print_set(seti);
    //差集
    Set *setd = (Set*)malloc(sizeof(Set));
    set_init(setd,NULL);
    set_difference(setd,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;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!