Structures de données/Enregistrements

Vous devez déjà être familier avec la notion de type enregistrement qui a du être abordée lors de l'étude de l'algorithmique impérative. Voici néanmoins un rappel :

Première approche

L'enregistrement est une façon de créer un nouveau type, ou encore un méta-type c'est-à-dire un type qui contient d'autres variables (appelées champs) de types déjà définis.

Toute variable déclarée avec ce nouveau type utilise alors une zone mémoire suffisante pour y stocker tous les champs de l'enregistrement.

Spécification

On déclare un nouveau type dans la partie Types comme suit :

identifiant_du_type = enregistrement
  identifiant_premier_champ : type_premier_champ
  identifiant_deuxième_champ : type_deuxième_champ
  ...
fin

on peut ensuite déclarer les variables de ce nouveau type enregistrement normalement :

identifiant_variable : identifiant_du_type

Pour accéder à un champ de la variable enregistrement, nous utiliserons l'expression :

identifiant_variable.identifiant_champ

Cette expression est du type de identifiant_champ soit type_champ.

Exemple

Supposons que nous voulons un nouveau type couple (de deux entiers). Nous allons déclarer le type couple comme suit :

couple = enregistrement
  a : entier
  b : entier
fin

Supposons maintenant que nous avons le lexique suivant :

Lexique
  c : couple

Si nous assignons :

c.a ← 1
c.b ← 2
afficher(c.a) (* affichera 1 *)

Un exemple d'implémentation : les rationnels

Nous souhaitons implémenter le type rationnel. Pour cela, nous allons utiliser un type enregistrement composé de deux champs de types entier : numérateur et dénominateur.

Ensuite, nous réaliserons :

• un constructeur, permettant de créer un rationnel à partir de son numérateur et de son dénominateur,
• deux "accesseurs" c'est à dire des fonctions retournant la valeur des champs d'un enregistrement. Elles renvoient le numérateur ou le dénominateur d'un rationnel passé en paramètre,
• prédicat de nullité d'un rationnel, d'égalité de deux rationnels,
• somme, différence, produit et quotient de deux rationnels,
• réduction renvoyant sous sa forme réduite un rationnel donné.

rationnel = enregistrement
  num : entier (* numérateur *)
  den : entier (* dénominateur *)
fin

(* Constructeur *)
fonction creerRationnel(a, b : entiers)
lexique
  nouveauRationnel : rationnel
debut
  si b=0 alors
    erreur("le dénominateur ne peut être nul")
  sinon
      nouveauRationnel.num ← a
      nouveauRationnel.den ← b
  finsi
fin

(* Accesseur *)
fonction numerateur(r : rationnel)
  retourner r.num
fin

(* Accesseur *)
fonction dénominateur(r : rationnel)
  retourner r.den
fin

fonction calculPgcd(a,b : entier)
lexique
  t : entier
debut
  si a < b alors
    t ← a
    a ← b
    b ← t
  finsi
  tant que b > 1
    t ← a modulo b
    si t=0 alors
      retourner b
    finsi
    a ← b
    b ← t
  fin tant que
  retourner b
fin

(* Simplifier la fraction *)
fonction reduire(r : rationnel)
lexique
  pgcd : entier
debut
  pgcd ← calculPgcd(r.num, r.den)
  r.num ← r.num / pgcd
  r.den ← r.den / pgcd
  retourner r
fin

(* Prédicat d'égalité *)
fonction sontEgaux(p,q : rationnel)
lexique
  p_reduit : rationnel (* forme réduite de p *)
  q_reduit : rationnel (* forme réduite de q *)
début
  p_reduit ← reduire(p)
  q_reduit ← reduire(q)
  retourner (p_reduit.num = q_reduit.num) et (p_reduit.den = q_reduit.den)
fin

(* Prédicat de nullité *)
fonction estNul(r : rationnel)
debut
  retourner (r.num = 0)
fin

(* Calcul de la somme *)
fonction somme(p, q : rationnel)
debut
  (* a/b + c/d = ( a*d+c*b)/(b*d) *)
  retourner reduire(creerRationnel(p.num*q.den+q.num*p.den, p.den*q_den))
fin