Structures de données/Enregistrements

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche
Ébauche

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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