Klouche-Djedid A.Département Informatique-IGMO | ![]() |
---|
Pointeurs et variables dynamiques.
Une variable est dite
statique si elle est déclarée dans un programme et associée à un
identificateur.
Mais une variable peut
être créée en cours d’exécution (par la procédure NEW ) :c’est une
variable dynamique.
Les variables dynamiques
ne sont donc pas déclarées, et ne sont donc pas repérées par des
identificateurs, mais par des entités mémoires (ou variables ) de type pointeur
qui ne sont rien d’autres que l’adresse
mémoire de la variable générée.
Ø le type
pointeur
Consiste en un nombre
« infini » de valeurs pointant sur des éléments d’un type unique .
le pointeur permet de
repérer la variable qu’il référence.
exemple :
type COUPLE = record A , B : integer end ;
REF = @couple (*
le symbole @ indique le type
pointeur sur *)
var R1, R2 : REF
pour créer une variable
dynamique de type couple pointée par la variable pointeur R1 on écrit
NEW(R1), ceci peut être schématisé comme suit :
R1 couple
*
R1 pointe sur une variable de type couple notée
par R1@.
Si on refait NEW (R1) on
crée une autre variable de type couple mais on perd l’ancienne valeur de R1 qui
était le seul moyen d’accès à l’ancienne variable.
R1 R1@ ancien R1@ irrécupérable
*
de cette manière ,il faudrait déclarer autant de variables pointeur que de
variables dynamiques , ce qui n’est pas commode.
Comment procéder, pour éviter cet inconvénient ?
Il suffit simplement de construire la variable dynamique, en y incluant un
ou plusieurs champs pointeurs .De ce fait on génère une définition récursive
d’une structure de données, dans laquelle exceptionnellement, un objet est
utilisé avant sa définition.
dont voici un exemple :
type LIEN = @OBJET
OBJET =
record INFO :
real SUIVANT : lien end ;
Ceci nous amène à l’introduction des
Ø listes
chainées
voici le schéma d’une liste chaînée
construite à partir d’un seul pointeur
sommet et de trois éléments de
type OBJET
sommet Z Y X
Initialement la liste est vide et la valeur du pointeur sommet est NIL. ce
qui signifie ne pointe sur rien.Les étapes de construction de la liste sont
schématisées par
1) sommet nil 2)
P X sommet nil P 3)
Y X sommet nil
etc………….
La variable P nous permet de créer au fur et à mesure un nouveau maillon,et
de conserver la valeur de sommet
intacte.
Exercice1 Écrire
un programme Pascal de génération d’une liste.
program liste ;
type lien = @objet ;
objet = record info : real
suivant : lien
end ;
var sommet, P : lien ; i :
integer ;
begin
sommet := nil ;
for i := 1 to N do begin
NEW(P); read(P@.info);
P@.suivant :=
sommet;
sommet := P
end.
Exercice3 Écrire un programme qui lit une chaîne de
caractères, les stocke dans une liste et les imprime en sens inverse.
program liste-inverse ;
type lien = @objet ;
objet = record info : char
suivant : lien
end ;
var sommet, p : lien
begin
sommet := nil ; while not eof do
begin
NEW(p)
p@.suivant
:= sommet;
sommet
:= p
end;
p := sommet;
while p <> nil do begin
write(p@.info);
p
:= p@.suivant
end
end;
Exercice4 Écrire un programme qui permet de supprimer, d’insérer et de
localiser un élément dans une liste simple ordonnée.
procedure supprime (x) ;
type lien = @objet ;
objet = record info : char
suivant : lien
end ;
var sommet, p,q : lien ;
trouve : boolean ;
begin
if sommet = nil then write(liste vide suppression
impossible’) ;
p := sommet ;
trouve := false ;
while p <> nil and not
trouve do begin
if p@.info <> x then begin
q := p;
p:=
p@.suivant;
end
else trouve := true;
end;
if trouve then
q@.suivant := p@.suivant ;
dispose(p)
else write(‘l element n’existe pas’)
end;
procedure insere(x)
type lien = @objet ;
objet = record info : char
suivant : lien
end ;
var sommet, p , q , pr :
lien ;
if sommet = nil
then begin NEW(p);
p@.info
:= x
p@.suivant := sommet;
sommet := p
end;
p := sommet;
while p@.info < x
and p <> nil do begin
q
:= p;
p
:= p@.suivant
end;
NEW(pr) ; pr@.info
:= x ; q@.suivant :=
pr; p@.suivant := p
end ;
A B D H J K nil
nouveau lien sommet suppression du maillon D B E F K L Y nil nouveau
lien I nouveau lien sommet insertion du maillon I