Les listes, les Piles et les Listes Circulaires

 

Maintenant nous allons aborder tout ce qui touche aux pointeurs. Les pointeurs permettent l'existence de structures en mémoire que les tableaux ne permettent pas. Voyons les grands types :

 

1. Les listes chaînées

Suite à ma petite introduction aux pointeurs, j'ai introduit le type Liste chaînée comme suit:

        Type
              Liste   = ^Cellule;
              Cellule = Record
                elt  : byte;
                Suiv : Liste;
              End;

On définit ainsi des opérations :

    liste_vide : ==> liste
    tête       : ==> element
    suite      : liste ==> liste
    est_vide   : liste ==> boolean
    cons       : element x liste ==> liste

et des conditions :

tete(L) et suite(L) sont définies si et seulement si NOT est_vide(L)

et des axiomes :

pour tout e element, L liste,
suite(cons(e,L))=L
tete(cons(e,L))=L

L'accès à un élément d'une liste n'est pas direct on est obligé de passer par des fonctions. La fonction CONS permet de rajouter un élément dans une liste, et de la créer si celle-ci est vide :

function cons(e:element;L:liste);
var ptr:liste;
begin
    new(ptr);
    ptr^.elet:=e;
        ptr^.suiv:=L;
    cons:=ptr;
end;

Un schéma est très parlant :{LISTE1}

Ici on voit bien comment procède la fonction CONS, pour rajouter une valeur dans la liste. Remarquez que L et Ptr ne sont pas en eux-mêmes des listes, mais des pointeurs sur liste. Quand on rajoute le chapeau après le L, (i.e. L^), là on désigne la liste physique, sans c'est la liste logique (le pointeur qui dit où elle est ).

La fonction tete renvoie la valeur de 1° élement dans la liste, et suite fait pointer L sur l'élément suivant, d'où besoin de préserver l'adresse physique de début d'une liste quand on veut la parcourir. Ensuite viendra les déclarations de listes vides :

    function tete(L : liste):element;
    begin
        tete := L^.elt;
    end;

    function suite(L : liste):liste;
    begin
        suite := L^.suiv;
    end;

    function est_vide(L : liste):boolean;
    begin
        est_vide:=(L=Nil);
    end;

    CONST liste_vide = NIL;

Maintenant des fonctions de bases pour calculer la longueur, obtenir le dernier élément, et rechercher un élément:

    function longueur(L : liste):element;
    begin
        if est_vide(L) then longueur:=0
        else longueur:=longueur(suite(L))+1);
    end;

    function dernier(L : liste):element;
    begin
        if est_vide(suite(L)) then dernier:=tete(L)
        else dernier:=last(suite(L));
    end;

    function recherche(E : element;L : liste):boolean;
    var ;
    begin
        while (L<>liste_vide) do
        begin
            if (L^.suiv=nil) then recherche:=true
            else L:=L^.suiv;
        end;
        recherche := false;
    end;

    function insert(e : element;L : liste):liste;
    begin
        if est_vide(L) then insert:=cons(e,L)
        else if (e<=tete(L)) then insert:=cons(e,L)
            else insert:=cons(tete(L),insert(e,suite(L)));
    end;

On remarque, avec une connaissance des tableaux, que l'accès aux tableaux, c'est à dire à une représentation continue de la mémoire, l'accès est plus rapide, mais la mise à jour difficile, et l'insertion impossible sans modifier la structure.

Pour une liste chaînée, pour accéder au k° élément, on parcourt les (k-1) éléments précédents, mais la mise à jour est plus facile, l'insertion aussi.

 

2. Les piles

Une pile est une liste où insertion et suppression se font à une seule extrémité appelée SOMMET de la pile (on appelle une pile aussi une gestion LIFO Last In First Out).

Opérations sur la pile:

Opérations :

    pile_vide: ==> pile
    empiler: pile x element ==> pile
    dépiler: pile ==> element
    sommet: pile ==> element
    est_vide: pile ==> booléen

Conditions :

sommet et depiler sont définis si NOT pile_vide.

Axiomes :

sommet(empiler( P , e ))=e
depiler(empiler( P , e ))=P

 

1. les piles contiguës

type :

    TYPE  Pile = RECORD
            som  : integer;
            elem : array[1..N] of element;
          END;

    procedure pile_vide(var P: pile);
    begin
      P.som:=0;
    end;

Voyons maintenant comment on empile et on dépile; empiler c'est ajouter un élément sur la pile, i.e. au sommet :

      +----------------------+
      |                      |
      +-+--------------------+
        |
        |   Empile
        V
      + - - - - - - - - - - -+
                               som + 1
      + - - - - - - - - - - -+
      |        sommet        | som
      +----------------------+
      |                      |
      +----------------------+
      |                      |
      +----------------------+
      |                      |
      +----------------------+
      |                      | 1
      +----------------------+

Voici comment on procède:

    Procedure empiler(var P : pile; e : element);
    Begin
      if P.som=N
        then write('Pile Pleine')
        else begin
          P.som:=P.som+1;
          P.elem[P.som]:=e;
        end;
    end;

et voici le reste : dépiler, sommet et est_vide :

    procedure depiler(var  : pile);
    begin
      if P.som = 0
        then write('pile vide')
        else P.SOM/+P.som-1;
    end;

    function sommet(P : pile): element;
    begin
        if est_vide(P) then write('pile vide')
        else sommet:=P.elem[P.som];
    end;

    function est_vide(P :  pile): boolean;
    begin
        est_vide:=(P.som=0);
    end;

 

2. représentation chaînée des piles

    type  pile = ^Cellule
          cellule = RECORD
            valeur : element;
            suivant : pile;
          END;

    procedure Pile_vide(var P : pile);
    begin
        P:=Nil;
    end;

    procedure empiler(var P : pile; X : element);
    begin
        new(E);
        E^.valeur:=X;
        E^.suivant:=P;
        P:=E;
    end;

On remarque que pour empiler et dépiler, on utilise directement l'adressage des pointeurs.

    procedure depiler(var P: pile);
    var C:liste;
    begin
        if est_vide(P) then write('Pile vide')
        else begin
            C:=P;
            P:=P^.suivant;
            dispose(C);
        end;
    end;

pour dépiler, on passe par variable l'adresse de la pile, car elle va être modifiée, comme on en détruit un de ses éléments.

    function sommet(P : pile): element;
    begin
        if est_vide(P) then write('pile vide')
        else sommet:=P^.valeur;
    end;

    function est_vide(P :  pile): boolean;
    begin
        est_vide:=(P=Nil);
    end;

    procedure vide_pile(var P :  pile);
    begin
        while (P<>nil) then depiler(L);
    end;

Les listes dynamiques n'ont virtuellement aucune limite, puisque il n'est pas besoin de spécifier la taille de la pile.

 

3. Les Files d'attente

Les files sont des listes circulaires, dont l'ajout se fait à une extrémité, et les accès/suppression à l'autre extrémité. C 'est un type FIFO ( First In First Out ). On peut se les représenter par des files d'attente à un guichet ( SNCF en temp de grève ).

Opérations à faire:

opérations :

    pile_vide : ==> file
    ajouter   : file x element ==> file
    retirer   : file ==> file
    premier   : file ==> element
    est_vide  : file ==> booléen

conditions :

premier et retirer sont définis ssi NOT pile_vide

axiomes :

pour tout f file, e element :

    est_vide(f) = vrai ( premier(ajouter(f,e))=e
    est_vide(f) = faux ( premier(ajouter(f,e))=premier(f)
    est_vide(f) = vrai ( retirer(ajouter(f,e))=file_vide
    est_vide(f) = faux ( retirer(ajouter(f,e))=ajouter(retirer(f),e )
    est_vide(file_vide) =  vrai

On peut la représenter de deux façons:

par 2 pointeurs tete et queue :

              +----+----+   +----+----+   +----+----+   +----+----+
      tête -->|    |  --+-->|    |  --+-->|    |  --+-->|    |    |<--- Queue
              +----+----+   +----+----+   +----+----+   +----+----+

par liste circulaire :

         +----+----+   +----+----+   +----+----+   +----+----+
      +->|    |  --+-->|    |  --+-->|    |  --+-->|    |    |<--- Queue
      |  +----+----+   +----+----+   +----+----+   +----+----+
      +----------------------------------------------------+

c'est cette deuxième représentation que nous étudierons, puisque d'un seul pointeur on peut accéder à la queue ( queue ) et à la tête (queue^.suiv). Pour la première représentation, c'est un peu plus compliqué, mais vous y arriverez facilement à partir de ce qui suit. Une file, c'est une suite de liste chaînées :

    TYPE file_circ = list;

Pour ajouter, soit la queue est vide ( = Nil ), à ce moment là on initialise la liste, sinon on insère en disant que il y a encore un élément qui s'ajoute à la queue, donc il devient lui-même la queue ( on ajoute à la fin le dernier arrivé ) :

    procedure ajouter(e : element; var F : file_circ);
    var ptr : file_circ;
    begin
        if est_vide(F) then
        begin
            new(ptr);
            F^.elem:=e;
            F^.suiv:=ptr;
        end else
        begin
            new(ptr);
            ptr^.elem:=e;
            ptr^.suiv:=F^.suiv;
            F^.suiv:=ptr;
            F:=ptr;
        end;
    end;

Pour supprimer, on retire la tête (F^.suiv), le premier de la file vient de passer. Si il n'y en a qu'un, on vide la file.

    procedure supprime(var F : file_circ);
    var ptr : file_circ;
    begin
        if est_vide(F) then write('File vide')
        else if (F^.suiv=F) then
            begin
                dispose(F);
                F:=nil;
            end
            else begin
                ptr:=F^.suiv; (* la tête*)
                F^.suiv:=F^.suiv^.suiv;
                dispose(ptr);
            end;
    end;

    function premier(F : file_circ):element;
    begin
        premier:=F^.suiv^.elem;
    end;

    function est_vide(F : file_circ):boolean;
    begin
    vide:=(F==nil);
    end;

Les files sont souvent utilisées pour les claviers, avec un nombre fixe, pour limiter le nombre d'entrées. l'avantage est que quand on arrive à la fin, on peut écraser le début et ainsi de suite.

 

Conclusion

Voici que s'achève cette deuxième partie de notre périple sur les pointeurs, vous voici en main avec des procédures pour réaliser vos rêves. Vous pouvez maintenant relire mes articles sur les grands nombres, cela vous semblera d'une clarté limpide.

Pour ce qui suivra, je pense traiter des arbres, ce qui s'avérera une tache ardue, puisque les arbres sont, entre autre à la base de la compression Huffman. D'ailleurs je vous détaillerais un projet entier basé sur les arbres et Huffman. Si j'ai du courage, je pourrais même vous récupérer un programme qui prend une chaîne symbolique mathématique comme 3x^2+12x+3, qui le dérive et l'intègre n-fois. Intéressant non ?

Pour aller plus loin ...

Principes fondamentaux de l'informatique, A.Aho, J.Ullman ed.DUNOD

Famous last words :

" Two roads diverged in a wood and I-
I took the one less travelled by
And that has made all the difference "
R.FROST