Réalisation du type `set` avec la liste chaînée

Pour la mise en œuvre, la structure struct set contient une liste chaînée. Les fonctions de manipulation de l’ensemble effectuent l’allocation des cellules struct lelement.

Le fichier en-tête

1. La structure struct set va contenir un champ correspondant à la liste chaînée. On propose deux définitions de struct set:

    struct set {
        struct link l;
    };
   

   ou

    struct set {
        struct link * l;
    };
   

   Quels sont les avantages et inconvénients de ces deux approches?

2. On choisit la définition contenant un pointeur sur struct link. Quelles fonctions de l’ensemble s’occupent de la gestion mémoire des cellules?

La définition des fonctions

Ajouter le fichier link/set_link.h à votre dépôt. Comme pour les mises en œuvre précédentes, nous introduisons la fonction outil find ci-dessous déclarée dans le fichier link/set_link.h.

// Returns NULL if l is empty, or if f is smaller than or equal to the first 
// value in l
// Otherwise, returns the cell e such that:
// - f is the data of the next cell of e,
// - or f should be inserted after e (if e is not in l)
// pre-condition: l is sorted in increasing order
struct lelement * find(struct link *l, int f);

Dans le fichier link/set_link.c, programmer la fonction outil find. Puis, l’utiliser pour mettre en œuvre les fonctions déclarées dans set/set.h avec la structure chaînée (définie dans link/link.h) et l’allocation dynamique. Vos fonctions maintiendront un tri croissant des entiers dans la strucure chaînée.

Quelle indication d’erreurs ne faut-il pas oublier d’ajouter? Précisez dans quelle fonctions?

Dans le fichier link/test_link_struc.c, ajouter les tests structurels permettant de vérifier votre mise en œuvre.

Il est nécessaire de mettre à jour votre Makefile comme indiqué en annexe.

Annexe

Après avoir ajouté le fichier link/set_link.c à votre dépôt, ajouter la directive ci-dessous à votre fichier Makefile (attention aux tabulations!)

set_link.o: ${LNK_DIR}/set_link.c ${LNK_DIR}/set_link.h
	${CC} ${CPPFLAGS} ${CFLAGS} ${LNK_DIR}/set_link.c -c

Modifier également les règles ci-dessous dans votre Makefile (prise en compte des dépendances sur set_link.h et set_link.o. Attention aux tabulations!).

test_link_struc.o : ${LNK_DIR}/test_link_struc.c ${LNK_DIR}/set_link.h ${LNK_DIR}/link.h
	${CC} ${CPPFLAGS} ${CFLAGS} ${LNK_DIR}/test_link_struc.c -c

link_struc: test_link_struc.o set_link.o link.o
	${CC} test_link_struc.o set_link.o link.o -o $@ ${LDFLAGS}