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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
#include <stdlib.h>
#include "sets.h"
/* Question théorique pertinente :
Faut-il représenter les entiers par des listes d'entiers triées ou non triées ?
Coût des opérations élémentaires dans le cas trié :
- Ajout d'un élément : O(n)
- Suppression d'un élément : O(n)
- Différence de deux ensemble : O(n)
- Union de deux ensembles : O(n)
- Intersection de deux ensembles : O(n)
- Ensemble vide ? : O(1)
- Copie d'un ensemble : O(n)
- Supression d'un ensemble : O(n)
- Trouver un élément d'un ensemble non vide : O(1)
Coût des opérations élémentaires dans le cas non trié :
- Ajout d'un élément : O(1)
- Suppression d'un élément : O(n)
- Différence de deux ensembles : O(n log n)
- Union de deux ensembles : O(n log n)
- Intersection de deux ensembles : O(n log n)
- Ensemble vide ? : O(1)
- Copie d'un ensemble : O(n)
- Suppression d'un ensemble : O(n)
- Trouver un élément d'un ensemble non vide : O(1)
La seule opération qui gagne à ne pas travailler sur une liste triée
est l'insertion d'un élément, or celle-ci s'accompagne généralement d'autres
opérations telles que l'union ou l'intersection, donc l'effectuer en
temps constant ne permet pas de gagner en complexité asymptotique.
On fait donc le choix de maintenir une liste triée.
*/
typedef struct set_elt *element;
set empty_set(int n) {
set k = malloc(sizeof(t_set_descriptor));
k->first = k->last = NULL;
k->size = 0;
return k;
}
set singleton(int n, int x) {
set k = malloc(sizeof(t_set_descriptor));
element e = malloc(sizeof(struct set_elt));
e->value = x;
e->next = NULL;
k->first = k->last = NULL;
k->size = 1;
return k;
}
set copy_set(const set s) {
element iter, prev;
set t = malloc(sizeof(t_set_descriptor));
t->size = s->size;
t->first = NULL;
if (s->size) {
prev = malloc(sizeof(struct set_elt));
prev->value = s->first->value;
t->first = prev;
for (iter = s->first->next; iter != NULL; iter = iter->next) {
element e = malloc(sizeof(struct set_elt));
e->value = iter->value;
prev->next = e;
prev = e;
}
prev->next = NULL;
t->last = prev;
} else {
t->last = NULL;
}
return t;
}
void delete_set(set s) {
element iter;
for (iter = s->first; iter != NULL; ) {
element next = iter->next;
free(iter);
iter = next;
}
free(s);
}
void set_union_ip(set a, const set b) {
//TODO
}
void set_inter_ip(set a, const set b) {
//TODO
}
void set_diff_ip(set a, const set b) {
//TODO
}
bool is_set_empty(const set s) {
return (s->size == 0 ? true : false);
}
bool set_mem(int x, const set s) {
element iter;
for (iter = s->first; iter != NULL; iter = iter->next) {
if (iter->value == x) return true;
if (iter->value > x) break;
}
return false;
}
int elt_of_set(const set s) {
if (s->first != NULL) return s->first->value;
return -1; // should raise exception... hope this will be handled properly
}
void set_add_ip(int x, set s) {
element prev, iter, e;
prev = s->first;
if (prev == NULL || x < prev->value) {
e = malloc(sizeof(struct set_elt));
e->value = x;
e->next = prev;
s->first = e;
} else {
for (iter = prev->next; iter != NULL; iter = iter->next) {
if (iter->value = x) return; // element already in here
if (iter->value > x) break;
prev = iter;
}
e = malloc(sizeof(struct set_elt));
e->value = x;
e->next = iter;
prev->next = e;
}
if (e->next == NULL) s->last = e;
s->size++;
}
void set_remove_ip(int x, set s) {
element prev, iter;
prev = NULL;
for (iter = s->first; iter != NULL; iter = iter->next) {
if (iter->value == x) {
if (prev == NULL) {
s->first = iter->next;
} else {
prev->next = iter->next;
}
if (iter->next == NULL) s->last = prev;
free(iter);
s->size--;
return;
}
prev = iter;
}
}
|
