Types Abstraits de Données: La liste chaînée

Les listes chainées sont des structures informatiques permettant de mémoriser des informations de manière flexible et efficace. En effet, elles sont :

  • Flexibles, car elles s’adaptent mieux que les “tableaux” aux ensembles de données dont on ne connaît pas la taille à priori.
  • Efficaces pour l’insertion et la suppression d’éléments

Cependant leur manipulation s’avère un peu plus complexe que les tableaux. En effet, les données ne sont pas mémorisées de manière contiguë en mémoire. Vous allez dans le cadre de ce TP expérimenter les mécanismes permettant de manipuler de telles structures afin de vous faire votre propre idée sur le sujet.

Explication préliminaire

Il existe plusieurs manières d’implémenter des listes chaînés, nous vous en proposons une version simple. Les listes chainées sont constituées d’éléments mémoire non contigus (maillons de la chainés link_t) et d’un en-tête (list_t) qui représentera la liste proprement dite. Dans cette version très minimale, l’en-tête ne sera constitué que d’un pointeur vers le début de la chaine des maillons. Chaque maillon est une paire, qui stocke : une valeur et la suite de la liste (c’est-à-dire, le maillon suivant) ou rien (pointeur NULL) si c’est le dernier maillon. Une telle liste est dite “simplement chaînée”, les maillons ne connaissent que leur successeurs.

3 maillons d'une liste

Pour représenter la liste (list_t) et les maillons (link_t), nous utiliserons les structures suivantes :

struct list_t {
    struct link_t *head;
};

struct link_t {
    double value;
    struct link_t* next;
};

Remarquez le type du champs suivant (next). Peut-on ignorer le fait que c’est un pointeur ?

Bien que les opérations de manipulation d’une liste puissent être plus compliquée à réaliser que les mêmes opérations sur un tableau (ce n’est pas le cas pour toutes les opérations), l’utilisateur final ne doit pas s’en rendre compte. Pour cela nous appliquons le principe de séparation des préoccupations en introduisant un Type abstrait de donnée. L’idée est que l’utilisateur manipule des listes comme une boîte noire (il ne sait pas ce qu’il y a dedans), et ne se sert que des fonctions mises à disposition par le programmeur du type (dans ce TP, bien entendu, il s’agit de vous dans les deux cas). Les opérations de manipulations sont exposés via un fichier d’en-tête (.h), l’implémentation proprement dite des opérations et des types se fait fans un fichier C classique (.c). Voir les slides associées.

Travail demandé (partie 1)

Dans ce TP vous allez devoir développer des fonctions permettant de créer, modifier et afficher une liste chainée. Vous porterez une attention particulière à bien tester votre code. Vous penserez aussi à utiliser des assertions lorsque cela est nécessaire.

  1. Dans un dossier dédié au TP, créez les fichiers : list.h, list.c et test-list.c. Le contenu du fichier list.h vous est donnée à la fin du texte du TP. Enfin rajoutez un fichier Makefile contenant les lignes suivantes (Attention rm est précédé d’une tabulation et non d’espaces). Compilez (make) et testez ! Pourquoi votre programme ne compile pas ? Remédiez à ce problème.

    CFLAGS=-std=c99 -Wall
    test-list: test-list.o list.o
    clean:
     rm -f *.o test-list
    
  2. Écrivez le corps des fonctions list_empty(), qui initialise une liste (donc vide), et le prédicat is_list_empty qui répond 1 si la liste et vide, 0 sinon. Testez ces deux fonctions à l’aide d’un programme (main).

    void list_empty(struct list_t* list)
    {
       return (*list).head = NULL;
    }
    
    int is_list_empty(struct list_t* list)
    {
       return list->head == NULL; // cf slide Structures et pointeurs
    }
    
  3. Écrivez la fonctions struct link_t* new_node(double value, struct link_t* next), qui alloue1 un nouveau maillon de liste, et list_push() qui insère un élément au début d’une liste. Les deux fonctions doivent elles êtres accessibles par votre utilisateur ? Comment s’assurer que l’utilisateur ne puisse pas s’en servir2. Améliorez votre main pour tester ces fonctions.

    void exemple()
    {
     struct link_t *new = malloc(sizeof(struct link_t));
     // ...
    }
    
  4. Développez une fonction nommée list_length() qui retourne le nombre d’éléments contenus dans la liste. Testez cette nouvelle fonction.

  5. Développez la fonction void print_node(struct link_t* l) qui affiche les informations relatives à un élément de la liste (son adresse en mémoire, la valeur qu’il contient et l’adresse de l’élément suivant). Écrivez ensuite la fonction list_print() qui affiche les mêmes informations pour tous les maillons constituant la liste. Testez bien évidemment ces fonctions.

  6. Écrivez les fonctions list_head() et list_tail() qui retournent respectivement le premier et le dernier maillon de la liste. Développez une fonction nommée list_get() qui permet de récupérer un pointeur sur le nième maillon de la liste chainée. Testez cette nouvelle fonction.

  7. Développez deux fonctions nommées list_node_before() et list_node_after() qui permettent respectivement de récupérer le pointeur sur l’élément précédent ou suivant d’un maillon spécifique. Testez ces deux nouvelles fonctions.

  8. Développez la fonction list_insert et list_append() qui permettent d’ajouter un élément respectivement, avant et après un nœud donnée. Testez ces fonctions.

  9. Développez une fonction nommée remove() qui permet de supprimer l’élément e de la liste chainée. Testez cette nouvelle fonction.

  10. Développez une fonction nommée list_clear() qui permet de supprimer l’ensemble des éléments contenus dans la liste chainée3. Testez cette nouvelle fonction.

  11. Variations autour de la liste simplement chainée. (Plutôt pour réfléchir)

  • Ajouter à la fin de la liste est couteux (il faut regarder tous les maillons), pour remédier à cela, une solution simple consiste à rajouter dans l’en-tête de la liste un pointeur sur la fin (tail). Rajoutez ce pointeur et changer les fonctions qui pourraient en tirer parti.
  • Connaître la taille de la liste est une opération couteuse. Peut on appliquer le même principe que pour l’ajout à la fin de la liste ? Dans quel cas est-ce une bonne idée ?

Pour aller un peu plus loin

Nos types sont dédiés aux nombres doubles. Le C ne permet pas de simplement de généraliser ces listes à tous les types. Cependant il est possible de généraliser à tous les types pointeurs. Pour cela, on peut se servir du type polymorphe void *. Généraliser votre liste pour qu’elle gère tous les types de pointeurs. Essayer de faire une liste d’iris struct iris {int petal_width, petal heigth; int sepal_width, sepal_height; };. Un problème se pose pour les fonctions d’affichages ? Que faudrait il faire pour que tous les types structurés s’affichent correctement4 ?

Pour aller plus loin: la liste doublement chaînée.

Comme vous avez pu le constater, les listes chainées permettent facilement l’ajout et la suppression d’informations dans un ensemble déjà existant. Toutefois certaines opérations comme l’accès à l’élément précédent requièrent le parcours complet de la liste. Afin de pallier à ce problème, une évolution de la liste “simplement” chainée a été proposée, il s’agit de la liste “doublement” chainée. Dans cette version, les maillons possèdent un pointeur vers leur successeur mais aussi sur leur prédécesseur. Cela permet de minimiser le nombre d’opérations lorsqu’on recherche par exemple l’élément précédant.

  • Une liste doublement chainée est-elle toujours préférable à une liste simplement chainée ? Citer deux raisons qui montrent que ce n’est pas le cas.
  • Développez un nouveau programme proposant les mêmes fonctionnalités que celles fournies précédemment en manipulant cette fois ci une liste doublement chainée.

Code de list.h

#ifndef LIST_H
#   define LIST_H

struct list_t {
    struct link_t *head;
};

struct link_t {
    double value;
    struct link_t* next;
};

void list_empty(struct list_t* lst);
int is_list_empty(struct list_t* lst);

// Ajoute en tête de liste
void list_push(double v, struct list_t* lst);

// Affiche le contenu de la liste
void list_print(struct list_t* e);

// Retourne la taille de la liste
int list_length(struct list_t* lst);

// Ajoute un élement après `node`
void list_append(double v, struct list_t* lst, struct link_t *node); 
// Ajoute un élement avant `node`
void list_insert(double v, struct list_t* lst, struct link_t *node); 


// retourne le premier élément
struct link_t* list_head(struct list_t* lst);
// retourne le dernier élément d'une lst
struct link_t* list_tail(struct list_t* lst);
// Retourne le n-ème element de la liste
struct link_t* list_get(struct list_t* lst, int n);

// Retourne le noeud précédent `r` dans la liste `lst`
struct link_t* node_before(struct list_t* lst, struct link_t* r);
// Retourne le noeud suivant `e` dans la liste `lst`
struct link_t* node_after(struct list_t* lst, struct link_t* e);


// Retire le noeud `e` de la liste  `lst`
void list_remove(struct list_t* lst, struct link_t* e);
// Vide toute la liste
void list_clear(struct list_t* lst);

#endif

  1. Allouer consiste à demander un bloc de mémoire (provenant du tas) pour notre programme (malloc()). Pourquoi doit on allouer une nouvelle mémoire dans ce cas la ? 

  2. Le modificateur static appliqué à une fonction, consiste à dire : cette fonction n’est pas exportée quoi qu’il arrive. Pourquoi ce n’est pas suffisant d’omettre le prototype dans le .h 

  3. La fonction inverse de malloc est free. Trois règles sont à toujours respecter : Chaque bloc alloué doit être restitué (pas de fuite mémoire), et ce, une seule fois (pas de double free), enfin le pointeur restitué doit être le même que celui fourni par malloc (pas de décalage). 

  4. Comme en mathématique pour les fonctions d’ordres supérieurs, en informatique il est possible de passer des fonctions à des fonctions. En C cela se traduit par un pointeur de fonction. Pour une fonction prenant un int et retournant un int, le type associés est int (* foo) (int)foo est le nom du paramètre ou de la variable. L’utilisation d’un tel pointeur en tant que fonction est d’une simplicité absolue : foo(42)