retour vers la page d'accueil

STS IG 2 - année 2002/2003
Allocation dynamique : chaînage double

Définitions globales

// Définition visible par l'utilisateur
T_Element est une structure quelconque

// Définitions invisibles par l'utilisateur
TP_Element est une structure
                                 Info est un T_Element
                                 Suivant, Precedent sont des pointeurs de TP_Element
                         fin structure
données
  Ptr_Racine,
  Ptr_Dernier,

  Ptr_Nouveau,
  Ptr_Courant,
  Ptr_Ancien sont des pointeurs de TP_Element

Algorithmes

algorithme InitialiserChainage
début
  Ptr_Racine <-- PTR_VIDE
  Ptr_Dernier <-- PTR_VIDE
fin

Jeu de test : aucun , simplement vérification que la valeur de Ptr_Racine et Ptr_Dernier sont "vides"

algorithme ViderChainage

début
  si (Ptr_Racine <> PTR_NUL) alors
    Ptr_Courant <-- Ptr_Racine

    tant que (Ptr_Courant^.Suivant <> PTR_NUL) faire
      Ptr_Ancien <-- Ptr_Courant
      Ptr_Courant <-- Ptr_Courant^.Suivant
      liberer (Ptr_Ancien)
    fin tant que

    Ptr_Ancien <-- Ptr_Courant
    liberer (Ptr_Ancien)

    Ptr_Racine <-- PTR_NUL
    Ptr_Dernier <-- PTR_NUL
  fin si
fin

Jeu de test :
  Test 1 : Chainage vide (test du SI)
  Test 2 : Chainage comportant 1 élément (test de l'effacement sans passer dans la boucle TANT QUE)
  Test 3 : Chainage comportant 2 éléments (test de l'effacement dans la boucle TANT QUE)

algorithme AjouterElement (E: Element est un T_Element)

début
  allouer (Ptr_Nouveau)

  avec Ptr_Nouveau^ faire
    info <-- Element

    precedent <-- PTR_NUL
    suivant <-- PTR_NUL
  fin avec

  si (Ptr_Racine = PTR_NUL) alors
    Ptr_Racine <-- Ptr_Nouveau
    Ptr_Dernier <-- Ptr_Nouveau
  sinon
    si (Element <= Ptr_Racine^.Info) alors
      Ptr_Nouveau^.Suivant <-- Ptr_Racine
      Ptr_Racine^.Precedent <-- Ptr_Nouveau
      Ptr_Racine <-- Ptr_Nouveau
    sinon
      si (Element >= Ptr_Dernier^.Info) alors
        Ptr_Nouveau^.Precedent <-- Ptr_Dernier
        Ptr_Dernier^.Suivant <-- Ptr_Nouveau
        Ptr_Dernier <-- Ptr_Nouveau
      sinon
        Ptr_Courant <-- Ptr_Racine

        tant que (Element > Ptr_Courant^.info) faire
          Ptr_Courant <-- Ptr_Courant^.Suivant
        fin tant que

        Ptr_Nouveau^.Suivant <-- ptr_Courant
        Ptr_Nouveau^.Precedent <-- ptr_Courant^.Precedent

        Ptr_Courant^.Precedent^.Suivant <-- Ptr_Nouveau
        Ptr_Courant^.Precedent <-- Ptr_Nouveau
      fin si
    fin si
  fin si
fin

Jeu de test :
  On prendra comme T_element des chaines de caractères

  Test 1 : Ajout de "Les oiseaux chantent" (test du 1er élément du chainage)
  Test 2 : Ajout de "Bonjour le monde," (test de l'ajout en début de chainage)
  Test 3: Ajout de "Salut, à la prochaine." (test de l'ajout en fin de chainage)
  Test 4: Ajout de "Perchés sur les branches." (test de l'ajout milieu de chainage, 3ème élément)

  On doit donc obtenir le chaînage suivant :
    Bonjour le monde,
    Les oiseaux chantent
    Perchés sur les branches.
    Salut, à la prochaine.