Listes Chaînées

1.12 Listes Chaînées

1.12.1 Le problème

Plusieurs problèmes surviennent lorsque l’on utilise des tableaux pour stocker des valeurs :

En cas de redimensionnement, il faut refaire une allocation dynamique et recopier tout le tableau.
En cas d’insertion ou de suppression d’un élément, il faut décaler vers la gauche ou vers la droite tous les successeurs.
Concaténer ou fusionner des tableaux est une opération lourde au niveau mémoire.
Tous les éléments doivent être stockés dans des zones contigües, l’allocation est donc un lourd travail lorsque la mémoire est fragmentée.
Bref, de nombreuses opérations sont lourdes en temps d’exécution.

Nous définirons dans ce cours un autre moyen de stocker les données en formant un ensemble ordonné, le listes chaînées.

1.12.2 Pointeurs et structures

Soit T un type structuré défini comme suit :

typedef struct T
{
        int i;
        char c;
}T;

Si p est un pointeur de type T*, alors p contient l’adresse mémoire d’un élément de type T. Soit t une variable de type T, et soit l’affectation p = &t. Alors, p pointe sur t. De ce fait *p et t sont des alias, et nous pourrons indifférement utiliser t.i (resp. t.c) et (*p).i (resp (*p).c). Par exemple, réecrivons le programme de l’exemple du cours sur les structures :

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct point
{
  double abs;
  double ord;
}point;

/**************************************************************/

point nextPoint(point* previous)
{
  point result;
  result.ord = (*previous).ord + 1.;
  result.abs = (*previous).abs + 2.;
  return result;
}

/**************************************************************/

void initTableauPoints(point* p, int n)
{
  int i;
  (*p).ord = 0;
  (*p).abs = 1;
  for(i = 1 ; i < n ; i++)
    *(p + i) = nextPoint(p + i - 1);
}

/**************************************************************/

void affichePoint(point* p)
{
  printf("(%f, %f)", (*p).abs, (*p).ord);
}

/**************************************************************/

void afficheTableauPoints(point* p, int n)
{
  int i;
 for(i = 1 ; i < n ; i++)
    {
      printf("p[%d] = ", i);
      affichePoint(p + i);
      printf("\n");
    }  
}

/**************************************************************/

int main()
{
  point* p;
  p = (point*)malloc(N * sizeof(point));
  if (p == NULL)
    return -1;
  initTableauPoints(p, N);
  afficheTableauPoints(p, N);  
  free(p);
  return 0;
}

Télécharger le fichier

L’écriture (*p).i permet de désigner le champ i de la variable pointée par p. Cette écriture, peu commode, peut être remplacée par p−>i, par exemple :

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct point
{
  double abs;
  double ord;
}point;

/**************************************************************/

point nextPoint(point* previous)
{
  point result;
  result.ord = previous->ord + 1.;
  result.abs = previous->abs + 2.;
  return result;
}

/**************************************************************/

void initTableauPoints(point* p, int n)
{
  int i;
  p->ord = 0;
  p->abs = 1;
  for(i = 1 ; i < n ; i++)
    *(p + i) = nextPoint(p + i - 1);
}

/**************************************************************/

void affichePoint(point* p)
{
  printf("(%f, %f)", p->abs, p->ord);
}

/**************************************************************/

void afficheTableauPoints(point* p, int n)
{
  int i;
 for(i = 1 ; i < n ; i++)
    {
      printf("p[%d] = ", i);
      affichePoint(p + i);
      printf("\n");
    }  
}

/**************************************************************/

main()
{
  point* p;
  p = (point*)malloc(N * sizeof(point));
  if (p == NULL)
    return -1;
  initTableauPoints(p, N);
  afficheTableauPoints(p, N);  
  free(p);
}

Télécharger le fichier

Attention ! Les opérateurs d’accès aux champs . et -> ont une priorité supérieure à celles de tous les autres opérateurs du langage ! Si vous manipulez un tableau de structures t et que vous souhaitez accéder au champ t du i-ème élément, est-il intelligent d’écrire *(i + t).c ? Absolument pas ! . est prioritaire sur *, donc le parenthèsage implicite est *((i + t).c), essayez de vous représenter ce que cela fait, et vous comprendrez pourquoi votre programme plante ! En écrivant (i + t)->c, vous obtenez une expression équivalente à (*(i + t)).c, qui est déjà bien plus proche de ce que l’on souhaite faire.

1.12.3 Un premier exemple

Considérons le type suivant :

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

On appelle cette forme de type un type récursif, c’est-à-dire qui contient un pointeur vers un élément du même type. Observons l’exemple suivant :

#include<stdio.h>

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

/**************************************************************/

int main()
{
  maillon m, p;
  maillon* ptr;
  m.data = 1;
  m.next = &p;
  p.data = 2;
  p.next = NULL;
  for (ptr = &m ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
  return 0;
}

Télécharger le fichier

m et p sont deux maillons, et m->next pointe vers p, cela signifie que lorsque l’on initialise ptr à &m, alors ptr pointe sur m. Donc, lors de la première itération de la boucle for, la valeur prt->data est m.data, à savoir 1. Lorsque le pas de la boucle est exécuté, ptr reçoit la valeur ptr->next, qui n’est autre que m->next, ou encore &p. Donc ptr pointe maintenant sur p. Dans la deuxième itération de la boucle, ptr->data est la valeur p.data, à savoir 2. Ensuite le pas de la boucle est exécuté, et ptr prend la valeur ptr->next, à savoir p->next, ou encore NULL. Comme ptr == NULL, alors la boucle s’arrête. Ce programme affiche donc :

data = 1
data = 2

1.12.4 Le chaînage

La façon de renseigner les valeurs des pointeurs next observée dans l’exemple précédent s’appelle le chaînage. Une liste de structures telle que chaque variable structurée contienne un pointeur vers vers une autre variable du même type s’appelle une liste chaînée. Utilisons un tableau pour stocker les éléments d’une liste chaînée à 10 éléments.

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

/**************************************************************/

void printData(maillon* ptr)
{
  for( ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
}

/**************************************************************/

int main()
{
  maillon* l;
  int i;
  l = (maillon*)malloc(N * sizeof(maillon));
  if (l == NULL)
    return -1;
  l->data = 0;
  for(i = 1 ; i < N ; i++)
    {
      (l + i)->data = i;
      (l + i - 1)->next = l + i;
    }
  (l + N - 1)->next = NULL;
  printData(l);
  free(l);
  return 0;
}

Télécharger le fichier

Les 10 maillons de la liste chaînée ont été placés dans le tableau l, la première boucle dispose le chaînage des éléments dans le même ordre que dans le tableau, l’affichage de la liste est fait dans le sous-programme printfData, et seul le chaînage y est utilisé. Comme le champ data du i-ème élément de la liste contient la valeur i, alors ce programme affiche :

data = 0
data = 1
data = 2
data = 3
data = 4
data = 5
data = 6
data = 7
data = 8
data = 9

Pour modifier l’ordre de parcours des maillons, il suffit de modifier le chaînage, par exemple,

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

/**************************************************************/

void printData(maillon* ptr)
{
  for( ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
}

/**************************************************************/

int main()
{
  maillon* l;
  int i;
  l = (maillon*)malloc(N * sizeof(maillon));
  if (l == NULL)
    {
      printf("Plus de mémoire");
      return 1;
    }
  l->data = 0;
  (l + 1)->data = 1;
  (l + N - 2)->next = l + 1;
  (l + N - 1)->next = NULL;
  for(i = 2 ; i < N ; i+=1)
    {
      (l + i)->data = i;
      (l + i - 2)->next = l + i;
    }
  printData(l);
  free(l);
  return 0;
}

Télécharger le fichier

Ce programme affiche

data = 0
data = 2
data = 4
data = 6
data = 8
data = 1
data = 3
data = 5
data = 7
data = 9

1.12.5 Utilisation de malloc

Pour le moment, nous avons stocké les éléments dans un tableau, les maillons étaient donc regroupés dans des zones mémoire contigües. Il est possible de stocker les maillons dans les zones non contigües, tous peuvent être retrouvés à l’aide du chaînage. Par exemple,

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

void printData(maillon* ptr)
{
  for( ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
}

/**************************************************************/

void freeLL(maillon* l)
{
  maillon* n;
  while(l != NULL)
    {
      n = l->next;
      free(l);
      l = n;
    }
}

/**************************************************************/

int main()
{
  maillon* l;
  maillon* current;
  maillon* previous;
  int i;
  l = (maillon*)malloc(sizeof(maillon));
  if(l == NULL)
    return -1;
  l->data = 0;
  previous = l;
  for(i = 1 ; i < N ; i++)
    {
      current = (maillon*)malloc(sizeof(maillon));
      if(current == NULL)
 exit(0);
      current->data = i;
      previous->next = current;
      previous = current;
    }
  current->next = NULL;
  printData(l);
  freeLL(l);
  return 0;
}

Télécharger le fichier

Ce programme affiche

data = 0
data = 1
data = 2
data = 3
data = 4
data = 5
data = 6
data = 7
data = 8
data = 9

Pour plus de clarté, on placera l’initialisation de la liste dans une fonction :

#include<stdio.h>
#include<stdlib.h>

#define N 10

/**************************************************************/

typedef struct maillon
{
        int data;
        struct maillon* next;
}maillon;

/**************************************************************/

void printLL(maillon* ptr)
{
  for( ; ptr != NULL ; ptr = ptr->next)
    printf("data = %d\n", ptr->data);
}

/**************************************************************/

maillon* initLL(int n)
{
  maillon* first;
  maillon* current;
  maillon* previous;
  int i;
  first = (maillon*)malloc(sizeof(maillon));
  if(first == NULL)
    return NULL;
  first->data = 0;
  previous = first;
  for(i = 1 ; i < n ; i++)
    {
      current = (maillon*)malloc(sizeof(maillon));
      if(current == NULL)
 exit(0);
      current->data = i;
      previous->next = current;
      previous = current;
    }
  current->next = NULL;
  return first;
}

/**************************************************************/

void freeLL(maillon* l)
{
  maillon* n;
  while(l != NULL)
    {
      n = l->next;
      free(l);
      l = n;
    }
}

/**************************************************************/

int main()
{
  maillon* l;
  l = initLL(N);
  if (l == NULL)
    return -1;
  printLL(l);
  freeLL(l);
  return 0;
}

Télécharger le fichier

1.12.6 Opérations

Observons de quelle façon il est possible d’effectuer certaines opérations sur une liste chaînée. Les sous-programmes ci-dessous ont été pensé et combinés pour être les plus simples possibles...

Création d’un maillon

maillon* creeMaillon(int n)
{
  maillon* l;
  l = (maillon*)malloc(sizeof(maillon));
  if(l == NULL)
    exit(0);
  l->data = n;
  l->next = NULL;
  return l;
}

Insertion au début d’une liste chaînée

maillon* insereDebutLL(maillon* l, int n)
{
  maillon* first = creeMaillon(n);
  first->next = l;
  return first;
}

Création d’une liste chaînée {0, …, n−1}

 maillon* initLL(int n)
{
  maillon* l = NULL;
  int i;
  for(i = n - 1 ; i >= 0 ; i--)
    l = insereDebut(l, i);
  return l;
}

1.12.7 Listes doublement chaînées

Un maillon d’une liste doublement chaînée contient deux pointeurs, un vers le maillon précédent, et un vers le maillon suivant.

typedef struct dmaillon
{
  int data;
  struct dmaillon* previous;
  struct dmaillon* next;
}dmaillon;

Aussi paradoxal que cela puisse paraître, bon nombre d’opérations sont davantage aisées sur des listes doublement chaînées. Pour se faciliter la tâche, nous manipulerons les listes chaînées à l’aide de deux pointeurs, un vers son premier élément, et un vers son dernier :

typedef struct dLinkedList
{
  struct dmaillon* first;
  struct dmaillon* last;
}dLinkedList;

Le soin d’ecrire les opérations sur ces listes vous est laissé dans le TP...