Structures de données en C/Les listes simples

Un livre de Wikilivres.

Les codes informatiques écrits en langage C dans ce livre sont placés sous licence LGPL

Structures de données en C
Structures de données en C
Structures de données en C
Sommaire
Liens
Contributeurs
Modifier ce modèle

Cours[modifier | modifier le wikicode]

Type List en C[modifier | modifier le wikicode]

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.

Représentation graphique du type List

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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) */
 }

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

Ajouts d'éléments[modifier | modifier le wikicode]

Ajout d'un élément en tête de liste[modifier | modifier le wikicode]

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

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

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]
...
List new_list=list_append(mylist,data);
...
  • instruction List **plist = &list;

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

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

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

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

  • instruction *plist = list_create(data);

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

  • instruction return list;

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

Cas où la liste d'origine est vide[modifier | modifier le wikicode]
 ...
 List *new_list=list_append(NULL,data);
 ...
  • instruction List **plist = &list;

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

  • instruction *plist = list_create(data);

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

  • instruction return list;

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

Destructions d'éléments[modifier | modifier le wikicode]

Destruction du premier élément[modifier | modifier le wikicode]

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

Résultat de la ligne List *new_list = list_remove_first(mylist);

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

Destruction de la liste entière[modifier | modifier le wikicode]

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

Appel à list_destroy(mylist)

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).

Déroulement de la boucle dans list_destroy(mylist);

Longueur d'une liste[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 */
}
...

Début de l'itération

Itération en cours

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

En travauxlink={{{link}}}

Cette page est en travaux. Tant que cet avis n'aura pas disparu, veuillez en considérer le plan et le contenu encore incomplets, temporaires et sujets à caution. Si vous souhaitez participer, il vous est recommandé de consulter sa page de discussion au préalable, où des informations peuvent être données sur l'avancement des travaux.

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[modifier | modifier le wikicode]

Listes et ensembles[modifier | modifier le wikicode]

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

Contributeurs[modifier | modifier le wikicode]