Structures de données/Enregistrements

Cette page est considérée comme une ébauche à compléter . Si vous possédez quelques connaissances sur le sujet, vous pouvez les partager en éditant dès à présent cette page (en cliquant sur le lien « modifier »).

Ressources suggérées : Aucune (vous pouvez indiquer les ressources que vous suggérez qui pourraient aider d'autres personnes à compléter cette page dans le paramètre « ressources » du modèle^? engendrant ce cadre)

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