Correction du TD N° 6 sur les listes

!= exprime la différence

1) Listes simplement chainées

booléen estVide()
  renvoyer (L.premier = nil)
  
supprimerPremier()
  si L.premier != nil
    L.premier <- L.premier.suivant

vider()
  L.premier <- nil

ajouterEnTete(x)
  x.suivant <- L.premier
  L.premier <- x

ajouterApres(x, y) 
  # si y est nil on ajoute en tete
  si y = nil
    L.ajouterEnTete(x)
  sinon
    x.suivant <- y.suivant
    y.suivant <- x

supprimerSuivant(x)
  # on considere que x n'est pas nil
  si x.suivant != nil
    x.suivant <- x.suivant.suivant

entier numElts()
  cpt <- 0
  e <- L.premier
  tant que e != nil
    cpt <- cpt + 1
    e <- e.suivant
  renvoyer cpt

1.1) L.taille doit être mis à jour

booléen estVide(L)
  renvoyer L.premier = nil
  
supprimerPremier(L)
  si L.premier != nil
    L.premier <- L.premier.suivant
    L.taille <- L.taille - 1

vider(L)
  L.premier <- nil
  L.taille <- 0

ajouterEnTete(x, L)
  x.suivant <- L.premier
  L.premier <- x
  L.taille <- L.taille + 1

ajouterApres(x, y, L)
  # si y est nil on ajoute en tete
  si y = nil
    ajouterEnTete(x, L)
  sinon
    x.suivant <- y.suivant
    y.suivant <- x
  L.taille <- L.taille + 1

supprimerSuivant(x, L)
  # on considere que x n'est pas nil
  si x.suivant != nil
    x.suivant <- x.suivant.suivant
    L.taille <- L.taille - 1

entier numElts(L)
  renvoyer L.taille

1.2) 
Pour pouvoir ajouter en fin de liste il est plus agréable de disposer de l'attribut L.dernier qui contient une référence au dernier de la liste. Sinon, il faut le chercher ce qui nécessite de traverser la liste
Le maintien de l'attribut dernier impacte presque toutes les méthodes. Il faut faire attention au fait que le premier peut-être aussi le dernier et donc que les méthodes modifiant le dernier peuvent aussi modifier le dernier

Les méthodes deviennent :

booléen estVide()
  renvoyer L.premier = nil

supprimerPremier()
  si L.premier != nil
    L.premier <- L.premier.suivant
    si L.premier = nil
      L.dernier <- nil

vider()
  L.premier <- nil
  L.dernier <- nil

ajouterEnTete(x)
  si L.premier = nil
    L.dernier <- x
  x.suivant <- L.premier
  L.premier <- x

ajouterApres(x, y)
  # si y est nil on ajoute en tete
  si y = nil
    L.ajouterEnTete(x)
  sinon
    si y.suivant = nil)
      # le dernier est y
      L.dernier <- x
    x.suivant <- y.suivant
    y.suivant <- x

supprimerSuivant(x)
  # on considere que x n'est pas nil
  elt <- x.suivant # on supprime elt
  si elt != nil
    si elt.suivant = nil
      L.dernier <- x
    x.suivant <- elt.suivant

entier numElts()
  cpt <- 0
  e <- L.premier
  tant que e != nil
    cpt <- cpt + 1
    e <- e.suivant
  renvoyer cpt


Insertion dans une liste triée. On considère un ordre croissant. 
algorithme classique : on cherche le premier élément plus grand et on insère juste avant. On a donc besoin de mémoriser le précédent

inserer(elt)
  prec <- nil
  e <- L.premier
  tant que e != nil et e.donnee < elt.donnee
    prec <- e
    e <- e.suivant
  L.ajouterApres(elt, prec)

On peut eviter cela en modifiant la donnée. quand on trouve l'élément qui est plus grand alors on l'échange avec l'élément courant et ont dit que l'on doit insérer cet élément. Dans ce cas, on a immédiatement sa position. Pour simplifier l'algorithme, on considérera qu'on ne va pas ajouter en fin

inserer(elt)
  e <- L.premier
  tant que e != nil et e.donnee < elt.donnee
    e <- e.suivant
  echanger e.donnee et elt.donnee
  L.ajouterApres(elt, e)

On va en profiter pour ecrire une fonction qui nous sera utile pour la fusion de listes.
Cette fonction insère dans une liste a partir d'un élément début donné.
L'insertion ne peut avoir lieu qu'apres le début.

inserer(elt, debut)
  prec <- debut
  si debut = nil
    e <- L.premier
  sinon
    e <- debut.suivant
  tant que e != nil et e.donnee < elt.donnee
    prec <- e
    e <- e.suivant
  L.ajouterApres(elt, prec)

1.3) La premiere version détruit la liste L2. L'idée est la suivante : on balaie la liste L2 et on cherche à quel endroit dans L1 on va insérer l'élément

fusion(L2) # N.B.: c'est une métode de la classe Liste, appelée pour L1
  p <- nil # référence au nœud précédent de L1, à utiliser pour l'insertion
  e1 <- L1.premier
  e2 <- L2.premier
  tant que e2 != nil
    tant que donnéePlusGrande(e2, e1)
      p <- e1
      e1 <- e1.suivant
    s <- e2.suivant # on sauvegarde en s la référence au nœud suivant de L2
    L1.ajouterAprès(e2, p)
    e2 <- s

... cependant, il faut redéfinir la fonction donnéePlusGrande comme ça :

donnéePlusGrande(x, y)
  si y = nil
    renvoyer FAUX
  sinon
    renvoyer x.donnée > y.donnée

sinon, le test de la boucle interne aurait été plus compliqué.


Pour la seconde version, la solution la plus simple est de copier la liste L2 dans une autre liste, par exemple L3 puis d'appliquer l'algorithme précédent avec L1 et L3.

2)
L'intérêt des listes doublement chaînées c'est qu'on peut revenir en arrière
et, donc, on peut ajouter, en temps constant, un élément non seulement après,
mais aussi avant un élément donné.

supprimerPremier()
  si L.premier != nil
    suiv <- L.premier.suivant
    L.premier <- suiv
    si suiv != nil
      suiv.precedent <- nil

vider()
  L.premier <- nil

ajouterEnTete(x)
  si L.premier = nil
    L.premier.precedent <- x
  x.suivant <- L.premier
  x.precedent <- nil
  L.premier <- x

ajouterApres(x, y)
  # si y est nil on ajoute en tete
  si y = nil
    L.ajouterEnTete(x)
  sinon
    x.precedent <- y
    si y.suivant != nil
      # le dernier est y
      y.suivant.precedent <- x
    x.suivant <- y.suivant
    y.suivant <- x

supprimerSuivant(x)
  # on considere que x n'est pas nil
  elt <- x.suivant # on supprime elt
  si elt != nil
    si elt.suivant != nil
      elt.suivant.precedent <- x
    x.suivant <- elt

Liste avec sentinelle: L.sentinelle contient une référence à la sentinelle de L

premier()
  renvoyer L.sentinelle.suivant

dernier()
  renvoyer L.sentinelle.precedent

booleen estVide()
  renvoyer L.premier() = L.sentinelle

supprimerPremier()
  L.premier().suivant.precedent <- L.sentinelle
  L.sentinelle.suivant <- L.premier().suivant

vider(L)
  L.sentinelle.suivant <- L.sentinele
  L.sentinelle.precedent <- L.sentinelle

ajouterEnTete(x)
  x.suivant <- L.premier()
  x.precedent <- L.sentinelle
  L.premier().precedent <- x
  L.sentinelle.suivant <- x

ajouterApres(x,y)
  # x apres y
  # si y est nil on ajoute en tete
  si y = nil
    L.ajouterEnTete(x)
  sinon
    y.suivant.precedent <- x
    x.suivant <- y.suivant
    y.suivant <- x
    x.precedent <- y

supprimer(x)
  x.precedent.suivant <- x.suivant
  x.suivant.precedent <- x.precedent

3) Operation sur les listes

ajouterEnFin(L2)
  d1 <- dernier
  p2 <- L2.premier
  d2 <- L2.dernier
  d1.suivant <- d2
  p1.precedent <- d1
  sentinelle.precedent <- d2
  d2.suivant <- sentinelle

ajouterAuDebut(L2)
  p1 <- premier
  p2 <- L2.premier
  d2 <- L2.dernier
  p1.precedent <- d2 
  d2.suivant <- p1
  sentinelle.suivant <- p2
  p2.precedent <- sentinelle

supprimerImpaireAjouterPair(L2)
  e1 <- premier
  tant que e1 != sentinelle
    suiv1 <- e1.suivant
    si e1.donnee est impaire
      supprimer(e1)
    e1 <- suiv1
  e2 <- L2.premier
  tant que e2 != L2.sentinelle
    suiv2 <- e2.suivant
    si e2.donnee est paire
      L2.supprimer(e2)
      ajouterApres(e2, dernier)
    e2 <- suiv2