LES POINTEURS

POINTEURS

LES LISTES CHAINEES ET ARBRES
LES POINTEURS EN PASCAL

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