« Programmation algorithmique/Listes doublement chaînées » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Tavernierbot (discussion | contributions)
m Robot : Changement de type cosmétique
Ligne 54 : Ligne 54 :
LISTE.TETE := NOUVEL_ELEMENT
LISTE.TETE := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT = ELEMENT
NOUVEL_ELEMENT.SUIVANT = ELEMENT
NOUVEL_ELEMENT.PRECEDENT = ELEMENT
NOUVEL_ELEMENT.PRECEDENT = NIL
'''SI''' LISTE.QUEUE = '''NIL''' '''ALORS'''
'''SI''' LISTE.QUEUE = '''NIL''' '''ALORS'''
LISTE.QUEUE := NOUVEL_ELEMENT
LISTE.QUEUE := NOUVEL_ELEMENT
'''FIN SI'''
'''FIN SI'''
'''FIN FONCTION'''
'''FIN FONCTION'''



=== Insertion d'un élément NOUVEL_ELEMENT dans une liste après un élément ELEMENT ===
=== Insertion d'un élément NOUVEL_ELEMENT dans une liste après un élément ELEMENT ===

Version du 1 décembre 2009 à 21:29

Introduction

Permet de gagner en complexité sur l'insertion et la suppression par rapport à la liste simplement chaînée, en plus de permettre un parcours des elements à l'envers. Mais utilise un pointeur supplémentaire par élément. Il faut donc maintenir cohérent deux fois plus de variables que dans une liste simplement chaînée

ELEMENT : ENREGISTREMENT
   CLEF
   SUIVANT   : ELEMENT
   PRECEDENT : ELEMENT
FIN ENREGISTREMENT
LISTE : ENREGISTREMENT
   TETE  : ELEMENT
   QUEUE : ELEMENT
FIN ENREGISTREMENT

Recherche dans une liste chaînée

Recherche d'un élément ayant une clée CLEF dans une liste

(Idem listes simplement chaînées) Complexité : O(N)

FONCTION DOUBLE_LISTE:RECHERCHER(LISTE, CLEF)
   ELEMENT := LISTE.TETE
   TANT QUE ELEMENT != NIL ET ELEMENT.CLEF != CLEF
      ELEMENT := ELEMENT.SUIVANT
   FIN TANT QUE'
   RETOURNER ELEMENT
FIN FONCTION

Recherche de l'élément suivant un élément ELEMENT dans une liste

(Idem listes simplement chaînées) Complexité : O(1)

FONCTION DOUBLE_LISTE:SUIVANT(LISTE, ELEMENT)
   RETOURNER ELEMENT.SUIVANT
FIN FONCTION

Recherche de l'élément précédent un élément ELEMENT dans une liste

Complexité : O(1)

FONCTION DOUBLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   RETOURNER ELEMENT.PRECEDENT
FIN FONCTION

Insertion

Insertion d'un élément NOUVEL_ELEMENT en début de liste

Complexité O(1)

FONCTION DOUBLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)
   ELEMENT := LISTE.TETE
   LISTE.TETE := NOUVEL_ELEMENT
   NOUVEL_ELEMENT.SUIVANT = ELEMENT
   NOUVEL_ELEMENT.PRECEDENT = NIL
   SI LISTE.QUEUE = NIL ALORS
      LISTE.QUEUE := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

Insertion d'un élément NOUVEL_ELEMENT dans une liste après un élément ELEMENT

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       LISTE.QUEUE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.PRECEDENT := NIL
       NOUVEL_ELEMENT.SUIVANT := NIL
   SINON
       NOUVEL_ELEMENT.PRECEDENT := ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT.SUIVANT
       SI ELEMENT.SUIVANT != NIL ALORS
         ELEMENT.SUIVANT.PRECEDENT := NOUVEL_ELEMENT
       SINON
         LISTE.QUEUE := NOUVEL_ELEMENT
       FIN SI
       ELEMENT.SUIVANT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

Insertion d'un élément NOUVEL_ELEMENT dans une liste avant un élément ELEMENT

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       LISTE.QUEUE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := NIL
       NOUVEL_ELEMENT.PRECEDENT := NIL
   SINON
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
       NOUVEL_ELEMENT.PRECEDENT := ELEMENT.PRECEDENT
       SI ELEMENT.PRECEDENT != NIL ALORS
          ELEMENT.PRECEDENT.SUIVANT := NOUVEL_ELEMENT
       SINON
          LISTE.TETE := NOUVEL_ELEMENT
       FIN SI
       ELEMENT.PRECEDENT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION


Suppression

Suppression d'un élément ELEMENT_SUPPRIME d'une liste

Complexité : O(1)

FONCTION DOUBLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)
   SI ELEMENT_SUPPRIME.PRECEDENT != NIL ALORS
      ELEMENT_SUPPRIME.PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT
   SINON
      LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT
   FIN SI

   SI ELEMENT_SUPPRIME.SUIVANT != NIL ALORS
      ELEMENT_SUPPRIME.SUIVANT.PRECEDENT := ELEMENT_SUPPRIME.PRECEDENT
   SINON
      LISTE.QUEUE := ELEMENT_SUPPRIME.PRECEDENT
   FIN SI
FIN FONCTION