Structures de données en C/Les listes simples

Structures de données en C

• Les itérateurs
• Les listes simples

Annexes

• Ressources

Cours

Type List en C

Une liste simple est une collection d'objets accessibles les uns après les autres. Elle peut être

• vide ; et la convention pour représenter la liste vide consiste à utiliser le pointeur NULL;
• composé d'un élément et du reste de la liste.

Les déclarations nécessaires pour représenter le type des listes en langage C sont:

typedef struct s_List List;
struct s_List
{
    List *next; /* pointeur sur le reste de la liste */
    void *data; /* pointeur sur une donnée générique */
};

Initialisation

L'utilisation primaire d'une liste consiste à la déclarer et à l'initialiser à la liste vide.

List *list = NULL;

Création d'une liste d'un élément

Cette fonction est très utile et pourra être modifiée par la suite lorsqu'il s'agira d'utiliser des allocateurs de mémoire intelligents.

La création d'une liste d'un élément demande d'allouer de la mémoire au gestionnaire de mémoire. Il convient de toujours tester le retour d'un malloc car la documentation dit que le retour peut être NULL si le système ne dispose plus de mémoire suffisante. Si l'allocation a réussi, il n'y a plus qu'à affecter les champs de la structure List

List *
list_create (void *data)
{
   List *list = malloc(sizeof(list)); /* allocation (en vert sur le diagramme) et affectation à la variable list (en bleu) */
   if (list)                           /* si l'allocation a réussi */
   {
       list->data = data;              /* affectation du champ data (en rouge) */
       list->next = NULL;              /* affectation du champ next à la liste vide */
   }
   return list;                        /* retour de la liste (correctement allouée et affectée ou NULL) */
 }

Ajouts d'éléments

Ajout d'un élément en tête de liste

L'insertion d'un élément en tête de liste demande tout d'abord de créer une liste d'un élément. Si la création a réussi, il n'y a plus qu'à affecter le champ next de la structure List

List *
list_prepend(List *old, void *data)
{
    List *list = list_create(data); /* création et affectation d'une liste d'un élément (en vert sur le diagramme) */
    if (list)                       /* si l'allocation mémoire a réussi */
       list->next = old;             /*     accrochage de l'ancienne liste à la nouvelle  (en bleu sur le diagramme) */
    return list;                    /* retour de la nouvelle liste (ou NULL si l'allocation a échoué) */
}

Ajout d'un élément en fin de liste

L'algorithme est relativement simple. Il consiste à rechercher le pointeur NULL dans la liste marquant sa fin. Une fois trouvé, il est modifié en allouant une nouvelle liste de 1 élément contenant data. La difficulté principale est l'utilisation d'un pointeur de liste (un List **) permettant de traiter indifféremment le cas où la liste d'origine est vide et le cas où elle n'est pas vide.

List *
list_append(List *list, void *data)
{
    List **plist = &list;
    while (*plist)
       plist = &(*plist)->next;
    *plist = list_create(data);
    if (*plist)
       return list;
    else
       return NULL;
}

Cas où la liste d'origine n'est pas vide

...
List new_list=list_append(mylist,data);
...

• instruction List **plist = &list;

• instruction plist = &(*plist)->next;

• instruction *plist = list_create(data);

• instruction return list;

Cas où la liste d'origine est vide

 ...
 List *new_list=list_append(NULL,data);
 ...

• instruction List **plist = &list;

• instruction *plist = list_create(data);

• instruction return list;

Destructions d'éléments

Destruction du premier élément

Le retrait du premier élément consiste à libérer le pointeur utilisé pour le premier élément et à retourner le reste de la liste

List *
list_remove_first(List *list)
{
    List *first = list; /* conservation de la liste actuelle (opération en vert)*/
    list = list->next;  /* faire pointer list sur le reste (opération en bleu)*/
    free(first);        /* libérer la mémoire utilisée par la structure List précédente (opération en rouge) */
    return list;        /* retour de la nouvelle liste */
}

Lors d'un appel à list_remove_first la liste passée en argument n'est pas modifiée

...
List *new_list = list_remove_first(mylist);
...

Destruction de la liste entière

La destruction d'une liste concerne la libération de la mémoire préalablement réservée par le chainage de la liste. Je pense (et c'est discutable) que les bibliothèques ne doivent libérer que ce qu'elles ont alloué. Les données n'ont donc pas à être libérées. Elles peuvent être notamment des pointeurs vers des chaînes de caractères statiques, et je vous laisse imaginer les effets d'un free sur ce genre de pointeur.

void
list_destroy(List *list)
{
    while (list)                       /* tant que l'on n'est pas arrivé en fin de liste */
       list = list_remove_first(list); /*     retrait du premier élément de la liste */
}

Il est à noter que le pointeur original n'est pas modifié par la ligne list = list->next

Exemple, lors de la destruction de la liste mylist dans le code suivant, mylist n'est pas modifié.

...
list_destroy(mylist);
...

Lors de l'appel à list_destroy, l'argument list prend la valeur de mylist. Les deux pointeurs sont donc confondus

Dans la boucle, l'affectation de list ne modifie pas la valeur de mylist (bien que les structures de List n'existe plus (en rouge) en mémoire).

Longueur d'une liste

Pour calculer la longueur d'une liste, il suffit de compter le nombre de pointeurs de type List différents du pointeur NULL

int
list_length(List *list)
{
    int length = 0;        /* initialisation de la longueur à 0 */
    while (list)           /* tant que la fin de la liste n'est pas atteinte */
     {
       length++;          /*     incrémenter la longueur */
       list = list->next; /*     passer à l'élément suivant */
     }
     return length;       /* retourner la longueur calculée */
}

De même que pour la destruction, l'affectation de list ne modifie pas la valeur de la liste de la fonction appelante.

Itérer sur les listes

Il y a plusieurs moyens d'effectuer une itération sur les éléments d'une liste. Le plus simple étant présenté ici, mais j'enjoins les lecteurs à parcourir le chapitre consacré au concept d'itérateurs.

...
List *tmp=list; /* opération en vert sur le diagramme */
while (tmp)
{
    /* traitement de tmp->data */
    tmp = tmp->next; /* opération en bleu sur le diagramme */
}
...

Il est à noter que la modification du pointeur tmp ne modifie en rien le pointeur original list.

Un itérateur en C sur les listes est un pointeur de List * soit un List ** (la raison essentielle est que la fonction list_iterator_next modifie l'itérateur. La seule façon de procéder en C est d'utiliser en pointeur sur l'argument à modifier). Mais vu de l'extérieur des fonctions, il est préférable dans un soucis de généricité d'utiliser le pointeur void *

La fonction de création consiste à allouer un tel pointeur et à l'initialiser à la liste

Iterator *list_iterator_create(void *list)
{
    return iterator_create(list, NULL, list_iterator_has_next, list_iterator_next);
}

La fonction pour savoir si il existe un élément suivant teste simplement la valeur de *iterator

static int list_iterator_has_next(const void *list)
{
  return (int)list;
}

La fonction pour obtenir le prochain élément d'un itérateur de liste retourne la donnée et modifie l'itérateur en le faisant pointer sur la prochaine donnée.

static void *list_iterator_next(void *plist)
{
    void *data = (*(List**)plist)->data;      /* conservation de la donnée courante de l'itérateur */
    *(List**)plist = (*(List**)plist)->next;  /* modification de l'itérateur */
    return data;                              /* retour de la donnée */
}

Le code classique pour parcourir une liste devient

...
Iterator *iterator = list_iterator_create(list);
if (iterator)
{
    while (iterator_has_next(iterator))
    {
        void *data = iterator_next(iterator);
        /* traitement de data */
    }
    iterator_destroy(iterator);
}
else
    /* traitement de l'erreur d'allocation */
...

Exercices

Listes et ensembles

Les éléments n'apparaissent qu'une seule fois dans un ensemble.

• Créer la fonction cardinal retournant le nombre d'éléments d'un ensemble
• Créer l'opérateur union
• Créer l'opérateur intersection