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
139
140
141
142
143
144
145
146
147
148
149
150
| #include "set.h"
#include <stdio.h>
#include <string.h>
/* subsets里存的是Set* 指针数据。 （未测试，待完善）*/
int cover(Set *members, Set *subsets, Set *covering) {
Set *setd = (Set*) malloc (sizeof(Set));
while (list_size(members) > 0 && list_size(subsets) >0) {
SetElement *pos = list_head(subsets);
SetElement *max_pos = NULL;
int max = 0;
for (; pos != NULL; pos = list_next(pos)) {
int temp = 0;
SetElement *mems = list_head(members);
for (; mems != NULL; mems = list_next(mems)) {
if (set_ismember((Set*)(list_data(pos)), list_data(mems)) == 1) {
++temp;
}
}
if (temp > max) {
max = temp;
max_pos = pos;
}
}
if (max_pos == NULL) {
break; //无法覆盖
}
if (set_insert(covering, max_pos->data) == -1) return -1;
void *data = max_pos->data;
if (set_remove(subsets, (void**)&data) == -1) return -1;//max_pos这个SetElement已经被释放，但data还在。不能再用max_pos->data了。
if (set_difference(setd, members, (Set*)(data)) == -1) return -1;
memcpy(members, setd, sizeof(Set));
}
if (list_size(members) == 0) { free(setd); return 0;} //有解
if (list_size(members) > 0 && list_size(subsets) == 0) { free(setd); return 1; } //无法覆盖
free(setd);
return -1;
}
void print(Set *set) {
SetElement *elem;
for (elem = list_head(set); elem != NULL; elem = list_next(elem)) {
printf("%p\t", list_data(elem));
}
printf("\n");
}
void printint(Set *set, const char *set_name) {
SetElement *elem;
printf("%s : ", set_name);
for (elem = list_head(set); elem != NULL; elem = list_next(elem)) {
printf("%d\t", *(int*)list_data(elem));
}
printf("\n");
}
int match(const void *data1, const void *data2) {
const int *id1 = (const int*)data1;
const int *id2 = (const int*)data2;
if (*id1 > *id2) return 1;
else if (*id1 < *id2) return -1;
return 0;
}
int matchptr(const void *data1, const void *data2) {
if (data1 == data2) return 0;
return -1;
}
int main()
{
Set *set1 = (Set*)malloc(sizeof(Set));
Set *set2 = (Set*)malloc(sizeof(Set));
Set *set3 = (Set*)malloc(sizeof(Set));
Set *set4 = (Set*)malloc(sizeof(Set));
Set *allElem = (Set*)malloc(sizeof(Set));
set_init(set1, match, NULL);
set_init(set2, match, NULL);
set_init(set3, match, NULL);
set_init(set4, match, NULL);
set_init(allElem, match, NULL);
int all[] = {1,2,3,4,5,6};
int arr1[] = {3,4,1};
int arr3[] = {2,5,6};
int arr2[] = {2,1};
int arr4[] = {1,3,4,5};
int i;
for (i = 0; i < 6; i++) {
set_insert(allElem, (const void*)(all + i));
}
for (i = 0; i < 3; i++) {
set_insert(set1, (const void*)(arr1 + i));
set_insert(set2, (const void*)(arr2 + i));
}
for (i = 0; i < 2; i++) {
set_insert(set3, (const void*)(arr3 + i));
}
for (i = 0; i < 4; i++) {
set_insert(set4, (const void*)(arr4 + i));
}
printint(set1, "set1");
printint(set2, "set2");
printint(set3, "set3");
printint(set4, "set4");
printint(allElem, "all");
Set *subsets = (Set*)malloc(sizeof(Set));
set_init(subsets, matchptr, free);
if (set_insert(subsets, set1) != 0 || set_insert(subsets, set2) != 0 ||
set_insert(subsets, set3) != 0 || set_insert(subsets, set4) != 0) {
set_destory(set1);
set_destory(set2);
set_destory(set3);
set_destory(set4);
set_destory(allElem);
set_destory(subsets);
printf("插入失败\n");
return -1;
}
print(subsets);
Set *covers = (Set*)malloc(sizeof(Set));
set_init(covers, match, free);
i = cover(allElem, subsets, covers);
if (i == 0) {
printf("找到了可覆盖的子集序列\n");
print(covers);
} else {
printf("没能找到可覆盖的子集序列\n");
}
set_destory(set1);
set_destory(set2);
set_destory(set3);
set_destory(set4);
set_destory(allElem);
set_destory(covers);
set_destory(subsets);
return 0;
}
|
