集合的实现

发表于 | 更新于 | 分类于

由一个或多个确定的元素所构成的整体叫做集合。若x是集合A的元素，则记作x∈A。

集合中的元素有三个特征：

  1. 确定性（集合中的元素必须是确定的）。
  2. 互异性（集合中的元素互不相同）。例如：集合 A={1，a}，则 a 不能等于 1。
  3. 无序性（集合中的元素没有先后之分），如集合 {3, 4, 5} 和 {3, 5, 4} 算作同一个集合。

set.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#ifndef set_h
#define set_h

#include <stdio.h>
#include "list.h"

/*Implement sets as linked lists. */
typedef List Set;

/* Public Interface. */
void set_init(Set *set, int (*match)(const void *key1, const void *key2), 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 /* set_h */

set.m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <stdlib.h>
#include <string.h>
#include "set.h"
#include "list.h"

void set_init(Set *set, int (*match)(const void *key1, const void *key2), 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 *member, *prev;
    prev = NULL;

    for (member = list_head(set); member != NULL; member = list_next(member)) {
        if (set->match(*data, list_data(member))) {
            break;
        }
        prev = member;
    }

    if (member == NULL) {
        return -1;
    }

    return list_rem_next(set, prev, data);
}

int set_union(Set *setu, const Set *set1, const Set *set2) {
    ListElmt *member;
    void *data;

    set_init(setu, set1->match, NULL);
    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        data = list_data(member);
        if (list_ins_next(setu, list_tail(setu), data) != 0) {
            set_destroy(setu);
            return -1;
        }
    }

    for (member = list_head(set2); member != NULL; member = list_next(member)) {
        if (set_is_member(set1, list_data(member))) {
            continue;

        } else {
            data = list_data(member);
            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 *member;
    void *data;

    set_init(seti, set1->match, NULL);
    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        if (set_is_member(set2, list_data(member))) {
            data = list_data(member);
            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 *member;
    void *data;

    set_init(setd, set1->match, NULL);
    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        if (!set_is_member(set2, list_data(member))) {
            data = list_data(member);
            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 *member;

    for (member = list_head(set); member != NULL; member = list_next(member)) {
        if (set->match(data, list_data(member))) {
            return 1;
        }
    }

    return 0;
}

int set_is_subset(const Set *set1, const Set *set2) {
    ListElmt *member;

    if (set_size(set1) > set_size(set2)) {
        return 0;
    }

    for (member = list_head(set1); member != NULL; member = list_next(member)) {
        if (!set_is_member(set2, list_data(member))) {
            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);
}