Le langage Pascal

Supposons une liste de 3 entiers. On suppose connaître pour chacun l'adresse du suivant :

Si l'on veut insérer une valeur dans la liste, les modifications à apporter sont minimes :

Contrairement à l'insertion dans un tableau, il est inutile de décaler les termes suivants. Pour connaître la liste, il suffit de connaître l'adresse du premier terme.

Pour représenter un arbre, il suffit pour chaque élément de connaître l'adresse de chaque fils :

Remarque : si le nombre de fils n'est pas constant, on a intérêt à stocker uniquement le fils aîné, ainsi que le frère suivant.

En pascal, on utilise les pointeurs pour représenter ces objets. La déclaration se fait de la manière suivante :

TYPE pointeur = ^type_de_la_variable_pointée;

Exemple :

TYPE
  tpoint = ^tval;  { pointe sur des TVAL }
  tval = record
           valeur : integer;
           suivant : tpoint
         end;
VAR
  p1, p2 : tpoint;

Dans cet exemple, les variables de type tval contiendront un entier et l'adresse de la suivante (liste chaînée vue plus haut).

Contrairement aux tableaux, il n'est pas nécessaire de prévoir le nombre de variables pointées à l'avance. C'est l'allocation dynamique de mémoire : on réserve la place pour chaque variable en cours d'exécution du programme, par la commande NEW(nom_variable). On récupère la place, si la variable est devenue inutile, par DISPOSE(nom_variable).

p1 contient donc une adresse d'une variable de type tval. Cette variable sera p1^ (c'est-à-dire pointée par p1). On la "remplit" donc par des affectations du type :

P1^.valeur := 15;
P1^.suivant := P2;

Examinons un programme qui lit puis affiche une liste chaînée d'entiers :

PROGRAM liste (input,output);
TYPE
  tpoint = ^tval;
  tval = record
           valeur : integer;
           suivant : tpoint
         end;
VAR
  prem, precedent, point : tpoint;
  i, n : integer;
BEGIN
  write('Combien d''éléments comporte votre liste ?');
  readln(n);
  new(prem);
     { le 1er est particulier : si on le perd, on perd la liste }
  write('1ère valeur ? ');
  readln(prem^.valeur);
     { lecture de l'enregistrement VALEUR de la variable d'adresse (pointée par) PREM }
  precedent := prem;
  for i := 2 to n do begin
    new(point);
       { création d'une nouvelle variable }
    write(i,'ième valeur ? ');
    readln(point^.valeur);
    precedent^.suivant := point;
       { mise à jour du chaînage }
    precedent := point
       { se préparer pour la prochaine boucle }
  end;
  precedent^.suivant := NIL;
  { NIL signifie "rien" car 0 est un entier, non une adresse }
  point := prem;
     { heureusement, on se souvient du premier }
  for i := 1 to n do begin
    writeln(point^.valeur);
    point := point^.suivant
       { pour la prochaine boucle }
  end
END.

Exercicepointeurs :
Modifier le programme ci-dessus pour qu'il permette de rajouter ou supprimer des éléments. Le décomposer en routines.
Voir la correction