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

• Qu'est-ce qu'implémenter
• Choix de la structure
• Primitives d'accès
• Gestion de l'espace de stockage
• Primitives de modifications

Qu'est-ce qu'implémenter

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.

---

Choix de la structure

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é.

Primitives d'accès

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

---

Gestion de l'espace de stockage

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

---

Primitives de modifications

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