précédent suivant haut Contents

POINTEURS


Un pointeur est une variable qui stocke l'adresse (c.a.d la position en mémoire) d'une variable.

LES LISTES CHAINEES ET ARBRES

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

liste

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

insertion

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 :

arbre

Rq : 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.

LES POINTEURS EN PASCAL

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

ex : 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.a.d 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.

EXERCICE (pointeurs) modifier ce programme pour qu'il permette de rajouter ou supprimer des éléments. Décomposez le en routines.


précédent suivant haut Contents