Mise en œuvre d'une structure chaînée

Nous voulons écrire une autre réalisation du TAD set en employant une structure de données constituée de cellules chaînées.

Nous poursuivons le principe utilisé dans la feuille précédente, en introduisant un niveau d’abstraction dans la réalisation de la structure chaînée:

  • le type link prend en charge la gestion du chaînage entre les cellules de la structure chaînée.
  • le parcours de la structure chaînée et la gestion mémoire par allocation dynamique sont prises en charge par les fonctions du type set

Cette partie se focalise sur la mise en œuvre de la structure chaînée link, muni des opérations suivantes:

type lelement; 

llm__is_end_mark  : lelement                   -> boolean
llm__next         : lelement                   -> lelement

type link; 

lnk__empty        :                               link
lnk__add_head     : link * lelement            -> link
lnk__remove_head  : link                       -> link * lelement
lnk__add_after    : link * lelement * lelement -> link
lnk__remove_after : link * lelement            -> link * lelement
lnk__first        : link                       -> lelement

Nous ne donnons pas les axiomes cette fois-ci: il est aisé de déduire le comportement attendu de ces fonctions depuis leurs noms.

Pour la mise en œuvre, la structure chainée est constituée de cellules simplement chaînées contenant une valeur de type int. La cellule est représentée par le type struct lelement contenant les deux champs traditionnellement nommés data (de type int) et next (qui est un pointeur sur la cellule suivante struct lelement). Le champ next des cellules retirées de la structure chainée a une valeur NULL.

NB: les tests structurels du type link utilisent uniquement l’allocation automatique (même pour les cellules).

Une représentation fréquente d’une structure chaînée est d’utiliser le pointeur sur la première cellule nommé head (cf. ‘‘La programmation en pratique’’ KERNIGHAN, PIKE 1999-2001 ou “L’essentiel des structures de données en C’’ HOROWITZ, SAHNI, ANDERSON-FREED, 1993).

Liste chaînée accédée directement par le pointeur de tête

L’autre représentation habituelle sépare la structure chainée en deux structures C distinctes (cf. ‘‘Mastering Algorithms with C’’ LOUDON, 1999). L’expérence des mises en œuvre précédentes, nous a montré qu’il était préférable d’effectuer cette séparation. Nous définissons un type struct link avec un champ head contenant un pointeur sur la première cellule de la structure.

Liste chaînée avec structure contenant le pointeur de tête

Il existe plusieurs manières d’encoder la fin de chaîne. Dans la suite, nous choisissons comme marque de fin une cellule sentinelle: une cellule de type struct lelement dont le champ next pointe sur elle-même.

L’allocation des structures struct link et struct lelement est prise en charge par les fonctions de l’ensemble (ou des tests). Les paramètres des fonctions sont donc considérés comme déjà alloués.

  • le fichier link/link.h contient les définitions des types struct link (qui représente la liste chaînée) et struct lelement (qui représente une cellule) ainsi que les prototypes des fonctions sur ces types. Il introduit également la constante LLM_SENTINEL_PTR qui définit la cellule sentinelle.
  • le fichier link/link.c contient la définition de la sentinelle
  • enfin, le fichier link/test_link_struc.c contient un squelette de test structurel pour le type struct link

Ajouter les trois fichiers ci-dessus dans votre dépôt (au bon endroit). Il est nécessaire de mettre à jour votre Makefile comme indiqué en annexe.

Initialisation/Cellule de tête/Marque de fin

Soit les fonctions:

  • lnk__empty initialise une structure chaînée à vide.
  • lnk__first retoune la cellule de tête, ou la marque de fin de chaînage pour une structure chaînée vide.
  • llm__is_end_mark indique si le paramètre d’entrée de type struct lelement correspond à la marque de fin de chaînage (ici la cellule sentinelle).
  1. Comment la structure chaînée vide est-elle représentée?
  2. Programmer ces fonctions dans le fichier link/link.c.
  3. Écrire des tests structurels pour ces fonctions dans le fichier link/test_link_struc.c.

Ajouter/Retirer en tête/Cellule suivante

On considère les trois fonctions:

  • lnk__add_head ajoute une cellule au début de chaînage.
  • lnk__remove_head retire la première cellule du chaînage. Elle retourne la cellule retirée ou une erreur si l’opération n’est pas possible.
  • llm__next retourne la cellule suivante de la cellule en paramètre d’entrée ou la marque de fin de chaînage.

  1. Sur un schéma, montrer les traitements à effectuer pour les fonctions lnk__add_head et lnk__remove_head. Par exemple, pour la fonction lnk__remove_head, sur une liste non vide:

    Schéma d'algorithme pour lnk__remove_head

  2. Donner la complexité de chaque opération.
  3. Programmer ces fonctions dans le fichier link/link.c.
  4. Ajouter les tests structurels dans le fichier link/test_link_struc.c permettant de vérifier vos fonctions, notamment un parcours de la structure en vérifiant que les valeurs se trouvent dans l’ordre attendu.

Ajouter/Retirer après une cellule

Soit les deux fonctions:

  • lnk__add_after qui prend au moins deux paramètres, la cellule à ajouter et la cellule après laquelle se fait l’ajout. Elle retourne une erreur si l’opération n’est pas possible.
  • lnk__remove_after retire la cellule située après la cellule passée en paramètre. Elle retourne la cellule retirée ou une erreur si l’opération n’est pas possible.
  1. Sur un schéma, montrer les traitements à effectuer pour chaque fonction.
  2. Donner la complexité de chacune.
  3. Programmer ces fonctions dans le fichier link/link.c;
  4. Ajouter les tests structurels dans le fichier link/test_link_struc.c permettant de vérifier vos fonctions.

Ajouter/Retirer en queue

Les deux fonctions suivantes ne sont pas à programmer

  1. La fonction lnk__add_tail ajoute une cellule en fin de chaînage.
    1. Sur un schéma, montrer le traitement à effectuer.
    2. Donner la complexité.
    3. Proposer une solution pour améliorer la complexité.
  2. La fonction lnk__remove_tail enlève la dernière cellule du chaînage.
    1. Sur un schéma, montrer le traitement à effectuer.
    2. Que conclure pour la réalisation de cette opération pour cette mise en œuvre de set?
    3. À quelle condition cette opération est-elle réalisable sur struct link?

Annexe

Il est nécessaire d’ajouter les directives ci-dessous à votre Makefile pour compiler les fonction développées dans cette partie.

Liste des modifications à apporter:

  • Définir la variable LNK_DIR=link
  • Ajouter la cible link_struc à la variable BIN
  • Ajouter la directive de compilation -I ${LNK_DIR} à la variable CPPFLAGS
  • Ajouter les règles suivantes pour link (attention aux tabulations!)
#link

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

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

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