Pointeurs : chaînage et arbres

Pointeurs

• La taille des tableaux est fixée ou sur-estimée au départ : manque de souplesse.
• Les décalages sont couteux dans les insertions-suppressions (tableaux triés).
• Faire un dessin symbolisant les "cases" de la mémoire. Notion d'adresse.
• Les pointeurs permettent les structures extensibles par allocation dynamique.

procedure PFract is
  type Fraction is record
        Num : Integer;
        Den : Positive;
  end record;
     
  -- Pointeur sur une case mémoire contenant une variable de type Fraction.
  type Pfraction is access Fraction;
  
  -- Allocation de mémoire avec new, qui renvoie l'adresse de la mémoire allouée.
  P : Pfraction;
  Q : Pfraction := new Fraction;
  R : Pfraction := new Fraction'(1,2);  -- Remarquez le "'"
  
begin
    -- Allocation de nouvelle mémoire au milieu du programme.
    P := new Fraction;

    -- Pointeur.all réfère la variable pointée.
    -- Elle est du type "accessé" par le pointeur (Fraction ici)
    P.all := (1,2);

    -- Accès à la mémoire via le pointeur, avec "." pour les records
    -- Notation simplifiée de (P.all).Num et (P.all).Den
    P.Num := 3; P.Den := 5;
    Put(P.Num); Put(P.Den);
end PFract;

• Valeur spéciale null d'un pointeur qui ne pointe vers rien. Valeur par défaut avant un new
• Déréférencer (utiliser) un pointeur null provoque une erreur : garantir que ça n'arrivera pas.
• Deux pointeurs sur une même case. Affectation de pointeurs. Dessin.
• En pratique, les structures peuvent occuper plusieurs "cases", mais le compilateur le gère.
• Allocation statique : définie par la portée

F : fraction -- réserve de la place mémoire pour F 
begin
    F := (1, 2);
end;
-- ici F n'existe plus, on peut réutiliser la place mémoire qu'elle occupait.

• Allocation dynamique

pF : pfraction -- réserve de la place memoire pour pF, mais pas pour une fraction !  
               -- pF est initialisé automatiquement à null. 
begin
    -- ici, pF.all := ... ; provoque une ERREUR dynamique : null.all n'existe pas.
    pF := new Fraction'(1, 2);  -- trouve une case libre dans la mémoire, de la taille
                   -- nécéssaire pour y ranger une fraction (et l'initialise avec 1,2)
                   -- affecte à pF l'adresse de cette case libre.
end;
-- ici pF n'existe plus, on peut réutiliser la place mémoire qu'elle occupait. 
-- En revanche, la case mémoire de la taille d'une fraction, allouée précédemment, existe toujours ! 
-- On a perdu son adresse, mais on n'a jamais dit qu'on voulait la libérer.

• Ramasse-miette : la mémoire qui n'est plus pointée est libérée automatiquement.

Liste chainée

• Structure.

procedure Listes is
  type Elem;          -- On dit qu'un type "Elem" sera déclaré plus tard.
  type Liste is access Elem;  -- Ce qui permet d'écrire ceci.
  type Elem is record
        Val  : Integer;
        Suiv : Liste;
  end record;

  L : liste;
begin
  L := new Elem'(3, null);  -- Faire un dessin.
  L := new Elem'(5, L);
end Liste;

• La valeur spéciale null indique la fin de la liste. Liste vide.
• Parcours de la liste : il suffit de l'adresse du début.

procedure Afficher(L : in Liste) is
   P : Liste := L; -- On doit utiliser un autre pointeur que L !
begin
   while P /= null loop
      Put(P.Val, 3);  -- ou tout autre traitement sur cet élément
      P := P.Suiv;
   end loop;
   New_Line;
end Afficher;

• Recherche dans la liste.

procedure Rechercher(L : in Liste; X : in Integer) is
   P : Liste := L; -- On doit utiliser un autre pointeur que L !
begin
   while P /= null loop
      exit when P.Val=X;  -- Ou toute autre propriété sur l'élément de la liste
      P := P.Suiv;
   end loop;

   -- Ici, si P=null on n'a PAS trouvé l'élément, sinon P.all satisfait la propriété
end Rechercher;

• Exercice : Construction de la liste avec des get, 0 pour finir. Idem à l'endroit.
• Exercice : Inversion d'une liste. Concaténation de deux liste.
• Exercice : Insertion - Suppression dans une liste triée. Version récursive.
• Introduction de l'élément Fictif : miracle !
• Passage en in out de paramètres : modification du pointeur ou des éléments.
• Listes doublement chaînées : boucles, fictif, parcours.

Arbres

• Dessin, vocabulaire (racine, feuille, noeud, hauteur, branche, fils...)
• Arbre binaire, équilibré, complet (0 ou 2 fils)

Implémentation

type Elem;
type Arbre is access Elem;
type Elem is record
      Val    : MonType;
      Fg, Fd : Arbre;
end record;

Type abstrait : package

-- Les constructeurs : 
type Arbre is private; 
function AVide return Arbre; 
function ABin (val : MonType; G, D : Arbre) return Arbre;

-- Les sélecteurs : 
function EstVide (a : Arbre) return boolean; 
function FilsG (a : Arbre) return Arbre; 
function FilsD (a : Arbre) return Arbre; 
function Val (a : Arbre) return MonType;

Utilisation du type abstrait

• Nombre de noeuds, de feuilles. Calcul de la hauteur.
• Impression indentée.
• Impression du mot des feuilles, de tous les chemins.

Arbre binaire de recherche

• Définition, intérêt (tri, recherche : coûts).
• Insertion dans un ABR, équilibrage, vérification qu'on a bien un ABR.
• Arbres n-aire, forêts, graphes...