Les listes

Prototype


Version de

Suppression d’un élément

On a l’habitude de représenter une liste chaînée par une suite de boîtes (maillons) à 2 compartiments comme dans la figure ??. Le compartiment de gauche contient une donnée (ou l’adresse d’une donnée) tandis que le compartiment de droite contient l’adresse du maillon suivant. Une structure comprenant 3 adresses autorise l’accès immédiat au maillon de tête, au maillon courant et au dernier maillon.

Rendered by QuickLaTeX.com

La suppression du maillon qui contient X s’effectue en modifiant la valeur de suivant contenue dans le prédécesseur de x : la fonction dispose restitue à la liste disponible la place libérée, celle-ci pourra être réutilisée lors de la création d’un nouveau maillon.
static BOOL
LibereObject (List * l, void * ancien)
{   
  Maillon * me = l->premier ;
  if (-1 != me)
  {
    Maillon * precedent ;
    while (-1 != me->suivant)
    {
      precedent = me   ;
      me = me->suivant ;
      /* La comparaison qui suit
       * doit etre adaptee */
      if (me->objet == ancien)
      {
        precedent->suivant = me->suivant ;
        dispose(me) ;
        return VRAI ; /* Succes */
      }
    }
  }
 /* objet non trouve ou liste vide */
  return FAUX ;
}

Insertion d’un élément

Pour insérer un élément x dans une liste L, on utilise la première cellule libre dans la liste disponible et on la place à la bonne position dans la liste L. L’élément x est ensuite placé dans le champ élément de cette cellule. Figure ??.
Insérer un nouvel élément en tête de la liste {\cal M} peut s’écrire de façon simplifiée :
inserer (M, e)
{
        temp = M ;
           M = premier_disponible() ;
  disponible = suivant(M) ;
  suivant(M) = temp ;
  element(M) = e ;
}

Rendered by QuickLaTeX.com

Affichage

Parcourir la liste pour en faire l’affichage peut se réaliser au moyen de la fonction prochain(e)/code> :
Si l'on inverse les lignes commentées (1) et (2), la liste est affichée en sens inverse.
lire(e)
{
    if (-1 == e) return ;
    afficher (e) ;       /* (1) */
    lire (suivant(e)) ;  /* (2) */
}
Les listes