Université Bordeaux 1
Licence Semestre 2   Initiation à l'algorithmique
Dernière mise à jour effectuée le 2 Juillet 2007

Une implémentation de liste simplement chainée de caractères

Remarque préliminaire
On considèrera dans tout ce chapitre que l'on des valeurs qui correspondent à un caractère.

  1. Qu'est-ce qu'implémenter
  2. Pour certaines structures de données, l'ensemble des langages de programmation proposent une traduction immédiate. Pour d'autres, il n'existe pas de traduction immédiate. Il faut alors définir explicitement l'algoritme de chacune des primitives.
    Exemple - les listes. On doit définir le stockage de la liste, et en fonction de ce stockage comme s'effectue par exemple l'adjonction.
    L'implémentation doit respecter la complexité des primitives à part celle d'initialisation (celle-ci ne s'exécutera qu'une fois).
    Exemple - les listes. On utilise souvent les fonctions ajouter et supprimer mais une seule fois creerListe.

  3. Choix de la structure
  4. Ici nous allons choisir de ranger les éléments dans un tableau "suffisament grand".
    Chaque élément du tableau est une paire (valeurElement,pointeurSuivant). Un pointeur est la valeur d'un index du tableau ainsi l'accès au suivant est en complexité O(1). La zone de stockage peut donc être décrite par :
    elementListe=structure
                     valeur:car;
                     suivant:entier;
                 finstructure;
    
    stockListe=tableau[1..tailleStock] d'elementListe;
    
    La valeur du pointeur (champs suivant) est donc un entier compris entre 0 et tailleStock. La valeur 0 correspondant à l'absence d'élément suivant. Le premier élément doit être accessible en O(1), il faut donc conserver son index. Si la liste est vide, par convention, l'index du premier sera 0. On peut donc représenter une liste par la structure suivante :
    listeSC_Car=structure
                  tailleStock:entier;
                  premier:entier;
                  vListe:stockListe;
                finstructure;
    
    Le tableau de stockage étant grand mais pas illimité, il faudra prévoir que la l'espace de stockage puisse être saturé.

  5. Primitives d'accès
  6. Ces fonctions sont immédiates.
    fonction premier(val L:listeSC_Car):entier;
      début
        retourner L.premier;
      fin;
    finfonction
    
    fonction suivant(val L:listeSC_Car,P:entier):entier;
      début
        retourner L.vListe[P].suivant;
      fin
    finfonction
    
    fonction listeVide(val L:listeSC_Car):booléen;
      début
        retourner L.premier==0;
      fin
    finfonction
    

  7. Gestion de l'espace de stockage
  8. Pour ajouter un élément, il faut pouvoir trouver un élément "libre" dans le tableau.
    Une première solution consiste à marquer les éléments libres du tableau (par exemple champs suivant de l'élément a pour valeur -1). Dans ce cas, il faudra parcourir le tableau (complexité O(n/2) en moyenne). Par suite, la primitive insérerAprès ne sera plus en complexité O(1) puisqu'il faudra d'abord trouver un élément libre.
    Une solution compatible avec la complexité des primitives consiste à gérer cet espace de stockage en constituant la liste des cellules libres. On modifie donc en conséquence la description de listeSC_Car :
    listeSC_Car=structure
            tailleStock:entier;
            premier:entier;
            premierLibre:entier;
            vListe:stockListe;
          finstructure;
    
    Par convention, l'espace de stockage sera saturé lorsque l'index premierLibre vaut 0 (la liste des cellules libres est vide). On définit donc la fonction de test :
    fonction listeLibreVide(val L:listeSC_Car):booléen;
      début
        retourner L.premierLibre==0;
      fin
    finfonction
    
    On définit deux primitives liées à la gestion du stockage :
    • mettreCellule : met une cellule en tete d'une liste,
    • prendreCellule : supprime la cellule de tete d'une liste.
    Les opérations sont respectivement de type insererEnTete et supprimerEnTete. Préciser la liste sur laquelle s'effectue l'opération revient à préciser le pointeur de tête surlequel on travaille.
    fonction prendreCellule(ref L:listeSC_Car,ref tete:entier):entier;
      var nouv:entier;
      début
        nouv=tete;
        tete=suivant(L,nouv);
        retourner nouv;
      fin
    finfonction
    
    fonction mettreCellule(ref L:listeSC_Car,val P:entier,ref tete:entier):vide;
      début
        L.vListe[P].suivant=tete;
        tete=P;
      fin
    finfonction
    

  9. Primitives de modifications
  10. fonction créer_liste(ref L:listeSC_Car;val tailleMax:entier):vide;
      var i:entier;
      début
        L.tailleStock=tailleMax;
        L.premier=0;
        L.premierLibre=1;
        pour i allant de 1 à L.tailleStock-1 faire
           L.vListe[i].suivant=i+1;
        finpour
        L.vListe[tailleStock].suivant=0;
      fin
    finfonction
    
    fonction insérerAprès(val x:car; ref L:listeSC_Car; val P:entier):bool;
    var nouv:entier;
      début
        si listeLibreVide(L) ou P==0 alors
          retourner faux;
        sinon
          nouv=prendreCellule(L,L.premierLibre);
          L.vListe[nouv].valeur=x;
          L.vListe[nouv].suivant=suivant(L,P);
          L.vListe[P].suivant=nouv;
          retourner vrai;
        finsi
      fin
    finfonction
    
          
    fonction insérerEnTete(val x:car;ref L:listeSC_Car):bool;
    var nouv:entier;
      début
        si listeLibreVide(L) alors
          retourner faux;
        sinon
          nouv=prendreCellule(L,L.premierLibre);
          L.vListe[nouv].valeur=x;
          mettreCellule(L,nouv,L.premier);
          retourner vrai;
       finsi
      fin
    finfonction
    
          
    fonction supprimerAprès(ref L:listeSC_Car;val P:entier):bool;
      var suivP:entier;
      début
        suivP=suivant(L,P);
        si P==0 ou suivP==0 alors
          retourner faux;
        sinon
          L.vListe[P].suivant=suivant(L,suivP);
          mettreCellule(L,suivP,L.premierLibre);
          retourner vrai;
        findi
      fin
    finfonction
    
          
    fonction supprimerEnTete(ref L:listeSC_Car):bool;
      var tete:entier;
      début
        si listeVide(L) alors
          retourner faux;
        sinon
          tete=L.premier;
          L.premier=suivant(L,tete);
          mettreCellule(L,tete,L.premierLibre);
          retourner vrai;
        findi
      fin
    finfonction