diff options
| -rw-r--r-- | README | 2 | ||||
| -rw-r--r-- | set_linked_lists.c | 172 | ||||
| -rw-r--r-- | sets.h | 7 |
3 files changed, 177 insertions, 4 deletions
@@ -1,5 +1,5 @@ Projet d'Algorithmique et Programmation -Alex AUVOLAT, Mendès OULAMARA +Alex AUVOLAT, Mendes OULAMARA 2013-2014 Sujet : Algorithme de Bron-Kerbosch pour Maximum-Clique diff --git a/set_linked_lists.c b/set_linked_lists.c index f37773f..05ed4ca 100644 --- a/set_linked_lists.c +++ b/set_linked_lists.c @@ -1,3 +1,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; + } +} @@ -25,11 +25,12 @@ struct set_elt { int value; struct set_elt *next; }; -struct set { +typedef struct { struct set_elt *first, *last; -}; + int size; // number of elements +} t_set_descriptor; -typedef struct set *set; +typedef t_set_descriptor *set; #endif #ifdef TREAPS |