Klouche-Djedid A.Département Informatique-IGMO

Pointeurs & variables dynamiques
;

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

 

 

 


P.S. notre objectif principal étant de décrire les concepts, veuillez ne pas tenir rigueur des éventuels omissions,oublis de signes ,ponctuations dans les programmes . pour d'autres coquilles soupçonnées plus sérieuses, nous comptons sur votre participation ,faisons de notre mieux!