Pointeurs et listes chaînées.

Un peu de théorie

Intérêt des pointeurs.

Quand un programmeur veut stocker/traiter des données de manière répétitive, il n'a souvent pas le choix et doit utiliser un tableau ou des tableaux. Ceux-ci sont très faciles d'emploi et permettent d'accéder à tout élément, d'une manière directe (non séquentielle). Le seul vrai problème posé par l'usage d'un tableau est sa taille. En effet, celui-ci doit être dimensionné dans la partie déclarative (avant compilation) et doit donc avoir une taille fixée à l'avance et celle-ci est souvent trop grande (sinon toujours). Il y a donc un gaspillage de mémoire non négligeable qui dans certains cas pose des problèmes.

Définition.

Une variable du type 'pointeur' est une variable appelée à contenir une adresse (et donc 4 octets) mais l'adresse de quoi me direz-vous? Et bien, l'adresse de la donnée que nous désirons stocker. En effet, les pointeurs sont entre autres utilisés pour contourner le problème décrit ci-dessus à propos des tableaux. Revenons-en donc à ce que nous désirons stocker. Par exemple, un WORD (2 octets), une chaîne, un Etudiant, ....
pointeur: p, Tete, q
permet de déclarer des variables amenées à conserver les adresses nécessaires.
q ß L
permet d'indiquer au compilateur que la variable q ne possède pas d'adresse valable. Si vous désirez accéder à la donnée de l'adresse q, vous aurez un message d'erreur mais aucun dommage ne sera fait à un emplacement mémoire peut-être primordial pour le bon fonctionnement de votre PC.
p <-- nouveau (WORD)
q <-- nouveau (chaîne)
Tete <-- nouveau (Etudiant)
indiquent au compilateur qu'il doit chercher et stocker dans
   p une adresse où il pourra stocker un WORD
   q une adresse où il pourra stocker une chaîne
   Tete une adresse où il pourra stocker une entité du type Etudiant

Pour accéder à cette partie de mémoire réservée, nous utiliserons
[p] <-- 270
[q] <-- "bonjour"
Nom de [Tete] <-- "dupont"
Prenom de [Tete] <-- "andré"

En Pascal/Delphi.

pointeur: p, Tete, q
n'existe pas tel quel (sauf si on veut 'laisser' une marque dans la mémoire en vue d'une 'libération' prochaine). Il faut toujours indiquer quel type de 'donnée' sera stockée à l'adresse mémorisée dans la variable du type pointeur. Il s'agit donc en fait d'une combinaison de la déclarative et de l'instruction 'nouveau' du pseudo-code.
VAR p: ^WORD; ^ placé devant le type est donc la manière choisie par Pascal pour indiquer à quel type de donnée le pointeur donne accès
    Tete :^STRING;
    q: ^Etudiant;
q ß L
se traduit par:
q:=NIL;
Et
p <-- nouveau (WORD)
q <-- nouveau (chaîne)
Tete <-- nouveau (Etudiant)
se traduisent par:
NEW(p);
NEW(q);
NEW(Tete);
Il n'est plus nécessaire de préciser vers quoi le pointeur doit pointer puisque cela a été fait dans la partie déclarative.

Pour accéder à cette partie de mémoire réservée, en pseudo-code, nous utilisons:
[p] <-- 270
[q] <-- "bonjour"
Nom de [Tete] <-- "dupont"
Prenom de [Tete] <-- "andré"
et en Pascal/Delphi:
Tete^.Nom:='dupont';  et le nom de la variable suivie de ^ indique donc que l'on accède à la variable stockée à l'adresse mémorisée dans le pointeur
Tete^.Prenom:='andré';
Dans le cas plus complexe de:
entité Etudiant
 composantes: Nom: chaîne    
              Nr: entier
fent

entité EtudiantPtr
 composantes: Data: Etudiant
              Pr, Svt: pointeur
fent

pointeur: Tete, q, Last, Curr
...
q ß nouveau EtudiantPtr
...
on a:
TYPE Etudiant=RECORD
                Nom:STRING;
                Nr:WORD;
              END;
     PtrEtudiant=^EtudiantPtr; On utilise donc EtudiantPtr qui n'est pas encore défini!
     EtudiantPtr=RECORD
                   Data:Etudiant;
                   Pr,Svt:PtrEtudiant;  On définit donc EtudiantPtr à partir de PtrEtudiant qui est défini lui-même par EtudiantPtr....
                 END;

VAR Tete,q,Last,Curr:PtrEtudiant;
...
NEW(q);
...

Usage.

Si nous voulons par exemple stocker en mémoire le contenu d'un fichier de chaînes pour le trier ou lui faire subir un quelconque traitement, nous devrons écrire:
lire S sur FichIn
si NOT EOF(FichIn) alors p <-- nouveau (chaîne)
                         [p] <-- S
                         lire S sur FichIn
                         si NOT EOF(FichIn) alors q <-- nouveau (chaîne)
                                                  [q] <-- S
                         ....
.....
et le problème auquel nous sommes ramenés est la génération automatique de noms de variables p, q, ... Ce problème classique est résolu par la constitution d'un tableau .... que nous voulions justement éviter. Notons cependant que cette solution du tableau de pointeurs est une solution qui ne doit pas être rejetée à priori parce que le gaspillage de mémoire ainsi généré est souvent nettement moindre qu'avec un autre tableau (un tableau de pointeurs prend nettement moins de place qu'un tableau de chaînes par exemple).
L'autre solution est le chaînage des informations stockées: chaque donnée stockée sera composée de la donnée brute (par exemple celle lue dans un fichier) et de l'adresse de la donnée suivante (un pointeur).

Cette manière de faire passe nécessairement par la constitution d'une entité:
entité DataPtr
  composantes: Data: chaîne si la donnée à stocker est du type chaîne
               Ptr: pointeur
fent


On obtient une chaîne du type suivant:



Dans ce type de chaînage, chaque maillon contient une donnée et l'adresse du maillon suivant. Il est donc impossible de revenir au maillon précédent et il est primordial de ne pas perdre l'adresse du premier maillon que personnellement je stocke toujours dans la variable Tete.

Pour palier au problème du déplacement limité à un sens, il faut utiliser une entité qui contient une donnée et 2 adresses: celle du maillon précédent et celle du maillon suivant. Il devient ainsi possible d'aller en avant et en arrière.
entité DataPtr
  composantes: Data: chaîne si la donnée à stocker est du type chaîne
               Prec,Svt: pointeur
fent

Il ne faut pas oublier de mettre L dans l'adresse du maillon précédent le premier maillon. En effet il n'y en a pas. Le dessin est trompeur et laisse croire qu'il faut y mettre p. Ce qui est faux puisque p contient l'adresse du premier maillon.

On obtient une chaîne du type suivant:


Liste simplement chaînée.

Voici une implémentation de liste simplement chaînée qui réalise la lecture d'un fichier de Etudiant et recherche ensuite si un étudiant s'y trouve.
entité Etudiant
 composantes: Nom: chaîne
              Nr: entier
fent

entité EtudiantPtr
 composantes: Data: Etudiant
              Ptr: pointeur
fent

fichier de Etudiant: FIn
Etudiant: S
pointeur: Tete,  Mémorisera l'adresse du premier maillon 
          q,  Servira de pointeur temporaire, le temps de créer le maillon 
         Last  Mémorisera l'adresse du dernier maillon

FIn ß "student.dat"
ouvrir FIn
lire S sur FIn
Tete ß L Comme aucune donnée n'a encore été stockée, nous n'avons pas d'adresse valable.
q ß L Idem pour q qui sera mis dans Last (adresse du dernier maillon qui n'existe pas).
tant que NOT EOF(FIn) faire 
 Last ß q Last prend la valeur de q (qui est l'adresse du dernier maillon créé).
 q ß nouveau EtudiantPtr Nous créons un nouveau maillon qui, quand il sera attaché, deviendra le dernier comme écrit à la ligne ci-dessus. Cette ligne est FONDAMENTALE et permet de réserver la place nécessaire au stockage d'une entité EtudiantPtr
 Data de [q] ß S On stocke la donnée.
 Ptr de [q] ß L Il n'y a pas de suivant et donc pas d'adresse à mémoriser.
 si Tete=L alors Tete ß q L'adresse du premier maillon doit être mise dans Tete. Si Tete=L, aucune adresse valable n'est stockée et par conséquent, aucun maillon n'a encore été créé.
 sinon Ptr de [Last] ß q On attache le maillon créé au dernier de la chaîne.
 fsi 
 lire S sur FIn
ftant
fermer FIn
écrire "Introduisez le nom à chercher:"
lire NomE
si Tete =L alors écrire "Liste vide!"
sinon q ß Tete
      tant que NOT ((Ptr de [q]=L) ou (Nom de Data de [q]=NomE)) faire 
       q ß Ptr de [q]
      ftant 
      si Nom de Data de [q]=NomE alors écrire NomE, " a le numéro ", Nr de Data de [q]
      sinon écrire NomE, "n'est pas dans la liste!"
      fsi
fsi

Liste doublement chaînée.

Voici une implémentation de liste doublement chaînée qui réalise la lecture d'un fichier de Etudiant et permet ensuite la navigation dans cette liste.
entité Etudiant
 composantes: Nom: chaîne    
              Nr: entier
fent

entité EtudiantPtr
 composantes: Data: Etudiant
              Pr, Svt: pointeur
fent

fichier de Etudiant: FIn
Etudiant: S
pointeur: Tete, q, Last, Curr
caractère: C

FIn ß "student.dat"
ouvrir FIn
lire S sur FIn
Tete ß L
q ß L
tant que NOT EOF(FIn) faire
  Last ß q
  q ß nouveau EtudiantPtr
  Data de [q] ß S
  Pr de [q] ß L
  Svt de [q] ß L
  si Tete=L alors Tete ß q
  sinon  Svt de [Last] ß q
         Pr de [q] ß Last
  fsi
  lire S sur FIn
ftant
fermer FIn
écrire "'+' avance, '-' recule, 'd' = début de liste, 'f' = fin de liste et 'q' quitte"
lire C
si Tete=L  alors tant que NOT (C="q") faire 
                   écrire "Liste vide!"
                   lire C
                 ftant
sinon Last ß q
      Curr ß Tete
      tant que NOT (C="q") faire 
        selon que   
            C="d" faire Curr ß Tete
                        écrire Nom de Data de [Curr]
         oq C="f" faire Curr ß Last
                        écrire Nom de Data de [Curr]
         oq C="+" faire si Svt de [Curr]= L alors écrire "Fin de liste!"
                        sinon Curr ß Svt de [Curr]
                              écrire Nom de Data de [Curr]
                        fsi 
         oq C="-" faire si Pr de [Curr]= L alors écrire "Début de liste!"
                        sinon Curr ß Pr de [Curr]
                              écrire Nom de Data de [Curr]
                        fsi 
       fselon    
       lire C
     ftant
fsi


Cliquez ici pour charger une archive contenant une implémentation en Delphi d'une liste doublement chaînée.


Voici une contribution de Melle Adnane:

un programme qui inverse une liste chainée circulaire

(*exercice: ecrire le programme qui inverse une liste circulaire simplement chainée. *)

program  inverse_circulair;
type element=string[20];
     ptr=^node;
     node=record
      data:string[20];(* le champ qui contient l'information*)
      link:ptr;(* le champ qui contient lèadresse du suivant*)
     end;

var  f:ptr;    
     elt,inserer:string[20];

procedure insert (var f:ptr;  mot:element);
var  x,y,z:ptr;
begin
new(x); 
x^.data:=mot;
if (f=nil) then begin
                f:=x;
                x^.link:=f;
                end
else begin
     if f^.data>= mot then begin
                           x^.link:=f; y:=f;
                           while y^.link <>f  do        
                             y:=y^.link;
                           y^.link:=x;
                           f:=x;
                           end
     else begin
          z:=f;   
          y:=f^.link;
          while (y<>f) and (y^.data<=mot) do
            begin
            z:=y;
            y:=y^.link;
            end;
          x^.link:=y;
          z^.link:=x;
         end;
    end;
end;

procedure lecture(var   f:ptr);
var   i,n:integer; x:string[20];
begin
write('donner le nombre d''elements de votre liste: ');
readln (n);
for i:=1 to n do
  begin
  writeln ('l''element nø',i,' est= ');
  readln (x);
  insert (f,x);
  end;
end;

procedure affiche (var f:ptr);
var y:ptr;
begin
y:=f;
while (y^.link<>f) do
  begin
  writeln('  ', y^.data);
  y:=y^.link;
  end;
writeln('  ',y^.data);
writeln(' ****************');
end;

procedure inverse(var f:ptr);
var x,y,z:ptr;
begin
x:=f; y:=f^.link;
while y<>f do
  begin
  z:=y^.link;
  y^.link:=x;
  x:=y;
  y:=z;
  end;
f^.link:=x;
f:=x;
end;

begin
f:=nil;
writeln('lecture de la liste');
lecture(f);
write ('voulez vous inserer un element dans votre liste? oui ou non ---- ');
readln (inserer) ;
while inserer <>'non' do
  begin
  write('donner l''element  a inserer:  ');
  readln(elt);
  insert(f,elt);
  write ('voulez vous inserer un autre element dans votre liste? oui ou non ---- ');
  readln (inserer);
  end;
if f= nil then writeln(' liste vide ')
else begin
     writeln (' la liste est: ');
     affiche(f);
     writeln (' la liste invers‚ est: ');
     inverse(f);
     affiche(f);
     end;
readln;
end.



Voici une autre contribution de Melle Adnane:

un programme qui propose la représentaion, sous forme d'arbre, d'une liste entrée sous la forme: (a(b,c(f,k),m)) où b,c et m sont des frères et b est le fils de a.

program arbres;
uses crt;
const n=20;
type treepointer=^treenode;
     treenode=record
                data:char;
                fils,frer:treepointer;
              end;
     pile=array[1..n] of treepointer;
     mot=string[30];

var f:treepointer; 
    exp,fin:mot;

FUNCTION  depiler (var s:pile;var top:integer):treepointer;
    BEGIN
      depiler:=s[top];
      top:=top-1;
    END;

PROCEDURE empiler (var s:pile; var top:integer; z:treepointer);
    BEGIN
     top:=top+1;
     s[top]:= z;
   END;

function creat(l:mot):treepointer;
 var y,z:treepointer;
     n,i,top:integer;
     p:pile;
 begin
  i:=2; top:=0; n:=length(l);
  new(y);  creat:=y;
  while (i<=n) do
   begin
     case l[i] of
               '(': begin
                     empiler(p,top,y);
                     new(z);
                     y^.fils:=z;
                     y:=z;
                    end;
               ',': begin
                     new(z);
                     y^.frer:=z;
                     y:=z;
                    end;
               ')': y:=depiler(p,top)
     else
      begin
       y^.data:=l[i];
       y^.fils:=nil;
       y^.frer:=nil;
      end;
    end;
    i:=i+1;
   end;
end;

procedure affiche(f:treepointer);
 begin
   write(f^.data);
   if (f^.fils<>nil) then
    begin
     write('(');
     affiche(f^.fils);
    end;
   if (f^.frer<>nil) then
    begin
     write(',');
     affiche(f^.frer);
    end
   else  write(')');
 end;

begin
 fin:='non';
 while (fin<>'yes') do
  begin
   clrscr;
   readln(exp);
   f:=creat(exp);
   writeln(' affichage apres la representation:');
   write('(');
   affiche(f);
   writeln('voulez vous arreter? yes ou non');
   readln(fin);
  end;
 readln;
end.

Page d'accueil.