Les types structurés

Généralités indépendantes du langage de programmation

Les concepts manipulés par l'être humain peuvent souvent être décrits par des attributs : un rectangle est caractérisé par sa largeur et sa longueur ; un livre peut être décrit par son titre, son auteur, son année de publication ; une voiture par sa marque, sa couleur, son kilométrage, sa puissance, etc.

Pour pouvoir représenter informatiquement de tels concepts, les langages de programmation permettent de définir des types structurés. Contrairement à un type prédéfini du langage (entier, réels, booléen, etc.), le nom d'un type structuré est défini par le programmeur. Il pourra par exemple définir un type « Livre », puis déclarer ensuite des variables de ce type.

Déclaration

Déclaration d'un type structuré

Prenons l'exemple du concept « Livre ». Pour représenter informatiquement un livre dans un programme Pascal, on pourra définir un nouveau type de la manière suivante :

 
Sélectionnez
 Type Livre =
    record
      Titre : String;
      Auteur : String;
      AnneePublication : Integer;
    end ;

On a ainsi défini un nouveau type de variable nommé « Livre ». « Titre », « Auteur » et « AnneePublication » sont les champs de ce type.

Les champs représentent les attributs du concept que l'on veut définir. Chaque champ est défini par son type. Dans notre exemple, Titre et Auteur sont des chaînes de caractères et AnneePublication est un entier.

Déclaration de variables de type structuré

À partir du moment où un nouveau type a été défini, il est possible de déclarer des variables de ce type. Une variable de type structuré est appelée une structure ou un enregistrement. Cette déclaration se fait comme pour un type prédéfini.

Par exemple, pour déclarer deux variables l1, l2 de type Livre on écrira :

 
Sélectionnez
  Var l1, l2 : Livre;

Manipulation des champs d'une structure

Pour accéder aux champs d'une structure, on utilise l'opérateur « . ».

Par exemple, pour affecter la valeur « Visual Basic 6 − Le Guide du programmeur » au titre du livre l1, on écrira :

 
Sélectionnez
  l1.Titre := 'Visual Basic 6 - Le Guide du programmeur' ;

Un champ se manipule exactement comme une variable du même type. Par exemple, l1.AnneePublication se manipule exactement comme un entier. Pour obtenir l'âge du livre l1, on peut très bien écrire :

 
Sélectionnez
  Var Age : Integer;
  Age := AnneeActuelle - l1.AnneePublication;

Définition de types complexes par combinaison

Il est possible de définir des types complexes en combinant tableaux et structures, ou bien en combinant les types structurés entre eux. Donnons quelques exemples.

Tableaux de structures : les tables

Le type des éléments d'un tableau peut être quelconque. On peut donc définir un tableau dont les éléments sont des types structurés, ou autrement dit un tableau de structures.

Les tableaux de structures sont également appelé tables. Ils jouent un rôle important en informatique, puisqu'on les retrouve dans les bases de données. Nous verrons ultérieurement qu'une base de données n'est rien d'autre qu'un ensemble de tables stockées dans des fichiers.

Pour représenter l'ensemble des livres présents dans une bibliothèque, on peut par exemple utiliser un tableau dont les éléments sont de type Livre :

 
Sélectionnez
   Var Bibliotheque : array [1..M] of Livre;

La variable Bibliotheque est donc un tableau de structures. La notation

 
Sélectionnez
   Bibliotheque[6].Auteur

représente alors l'auteur du 6e livre.

Structure avec champs de type structuré

Enrichissons un peu notre représentation d'un livre. Pour la gestion d'une bibliothèque, il serait intéressant d'associer une date d'emprunt à chaque livre :

 
Sélectionnez
   Type Livre =
     record 
        Titre : String;
        Auteur : String;
        AnneePublication : Integer;
        DateEmprunt  : TDate ;
     end;

Le type TDate étant lui même un type structuré défini par :

 
Sélectionnez
  Type TDate =
     record
      Jour : Integer;
      Mois : Integer;
      Annee : Integer;
     end;

Supposons que L soit une variable de type Livre. Pour définir la date d'emprunt de L comme le 27 janvier 2009, on écrira :

 
Sélectionnez
   L.DateEmprunt.Jour := 27;
   L.DateEmprunt.Mois := 1;
   L.DateEmprunt.Annee := 2009;

Les pointeurs

Déclaration d'un pointeur

Un pointeur est une variable contenant une adresse.

Rappelons (cf. le chapitre sur les premières notions), qu'une adresse est un entier qui représente la position d'un octet en mémoire. Cet entier permet donc en particulier de repérer la position, ou autrement dit l'adresse, d'une plage mémoire :

Image non disponible

En Pascal, un pointeur se déclare de la manière suivante :

 
Sélectionnez
 Var NomDuPointeur : ^Type;

Type représente le type de donnée dont le pointeur contiendra l'adresse.

Exemple :

 
Sélectionnez
Type
Ville = record
  Nom : String;
  CodePostal : Integer;
  End;
Var PVille : ^Ville;

Dans cet exemple, la variable PVille est un pointeur sur une donnée de type Ville.

Une autre manière de déclarer un pointeur est de définir tout d'abord un type pointeur de la manière suivante :

 
Sélectionnez
 Type PointeurSurType = ^Type;

et de déclarer ensuite le pointeur comme une variable de ce type :

 
Sélectionnez
 Var NomDuPointeur : PointeurSurType;

Avec l'exemple précédent cela donnerait :

 
Sélectionnez
Type
Ville = record
  Nom : String;
  CodePostal : Integer;
  End;
  
PointeurSurVille = ^ Ville;

Var PVille : PointeurSurVille;

Allocation dynamique de mémoire

Un pointeur permet de créer une variable sans nom, repérée uniquement par l'adresse qu'il contient.

Cette variable est créé par un mécanisme d'allocation dynamique de mémoire, que nous allons décrire à présent.

Les variables générées dynamiquement sont stockées dans une zone spéciale de la mémoire appelée le tas (heap en anglais).

En Pascal, l'allocation dynamique de mémoire se fait grâce à l'opérateur new.

Si p est un pointeur sur un type T, new(p) va allouer de la place mémoire dans le tas pour une variable de ce type et affecter à p l'adresse de cette variable.

Avec notre exemple précédent, new(p) réserverait de la place pour une structure de type Ville et affecterait l'adresse de cette structure à p. Par exemple, si la plage mémoire réservée pour la structure commence à l'adresse 1961, p contiendra cette adresse :

Image non disponible

Une fois que la variable est créée, il est possible d'y accéder par l'opérateur ^. Si p est un pointeur, p^ représente la variable pointée par p.

Avec notre exemple, pour affecter « Strasbourg » au nom de la ville pointé par p, on écrirait :

 
Sélectionnez
 p^.Nom := 'Strasbourg';

Tout se passe donc comme si p^ était une variable de type Ville.

Listes simplement chaînées

Pour l'instant, le seul moyen dont vous disposez pour représenter un ensemble de données est le tableau. Dans un tableau, chaque donnée (de même type) possède un indice définissant sa position dans le tableau.

Les listes sont une autre manière de représenter un ensemble de données n'utilisant pas d'indice et basée sur les pointeurs.

Représentation

Une liste simplement chaînée se représente par un ensemble de structures de même type possédant un champ contenant l'adresse de l'élément suivant.

Il serait assez difficile et peu pédagogique de présenter les listes chaînées dans un cas général abstrait. Nous allons donc baser toutes nos explications sur un exemple qui sera facile à généraliser : une liste de structures de type Ville dont voici la déclaration :

 
Sélectionnez
Type
PVille = ^Ville;

Ville = record 
          Nom : String;
          CodePostal : String;
          Suivant : PVille;
        end;

Le champ Suivant sert à mémoriser l'adresse de l'élément suivant de la liste. Dans le cas général, il peut porter n'importe quel nom, mais il doit exister un champ jouant ce rôle.

La liste, quant-à elle, est également un pointeur qui contient l'adresse de son premier élément.

Dans notre exemple, on pourrait donc représenter une liste de villes par une variable L de type PVille.

Voici par exemple une liste simplement chainée contenant quatre villes :

Image non disponible

L contient l'adresse de la première ville (Ribeauvillé). Le champ Suivant de la première ville contient l'adresse de la seconde (Kingersheim), etc.

Le dernier élément de la liste (Nancy) n'a pas d'élément suivant. Son champ Suivant contient la valeur NIL, qui représente en Pascal une adresse inexistante.

Une liste vide se représente simplement par un pointeur de liste égal à NIL (L = NIL dans notre exemple).

Parcours

Pour effectuer un traitement sur chaque élément d'une liste, il est nécessaire de savoir parcourir ses éléments. On utilisera pour cela un pointeur, qui prendra successivement la valeur des adresses de chaque élément de la liste. Voici par exemple comment parcourir une liste de villes dont l'adresse est contenue dans le pointeur L :

 
Sélectionnez
Var p : PVille;
p := L;
While p <> NIL Do
begin

     { Traitement de l'élément pointé par p }

     p := p^.Suivant;
end;

Adjonction d'un élément

Considérons le problème suivant : on dispose d'une liste de villes L et d'une structure de type Ville pointée par un pointeur p. Comment procéder pour ajouter cette structure dans la liste ?

En début de liste

Ajouter l'élément p^ au début de la liste L, il suffit de faire :

 
Sélectionnez
  p^.Suivant := L;
  L := p;

La première affectation « accroche » la structure à la liste et la deuxième met à jour l'adresse de la liste, qui devient celle de p.

Cette méthode fonctionne également avec une liste vide. En effet, dans ce cas L vaut NIL avant l'adjonction. Après l'adjonction, on aura bien une liste d'un élément (p^) avec L = p et p^.Suivant = NIL.

La figure suivante illustre l'adjonction en début de liste de la ville Ribeauvillé :

Image non disponible

Avant l'adjonction :

  • la liste L contient les trois villes Kingersheim, Strasbourg et Nancy ;
  • L contient l'adresse de la structure représentant Kingersheim.

Après l'adjonction :

  • le champ Suivant de la structure représentant Ribeauvillé contient l'adresse de la structure représentant Kingersheim ;
  • L contient l'adresse de la structure représentant Ribeauvillé ;
  • L contient donc à présent les quatre villes Ribeauvillé, Kingersheim, Strasbourg et Nancy.

Insertion après un élément

Supposons à présent que la liste n'est pas vide et que l'on souhaite insérer un élément après un certain élément de la liste.

Soit p l'adresse du nouvel élément que l'on souhaite insérer, et Curseur l'adresse de l'élément après lequel on souhaite insérer p^. Les instructions suivantes permettent d'obtenir ce que l'on souhaite :

 
Sélectionnez
p^.Suivant := Curseur^.Suivant;
Curseur^.Suivant := p;

La figure suivante illustre l'insertion d'une structure représentant Strasbourg, après la structure représentant Kingersheim :

Image non disponible

Suppression d'un élément

Suppression du premier élément

Pour supprimer le premier élément d'une liste simplement chaînée, il suffit de remplacer l'adresse de la liste par l'adresse de l'élément qui suit le premier.

Avec notre exemple, cela se traduit par l'instruction suivante :

 
Sélectionnez
 L := L^.Suivant;

Si la liste ne contient qu'un seul élément, ce dernier n'a pas d'élément suivant, mais l'instruction précédente convient également car, dans ce cas, L^.Suivant contient NIL et la liste devient par conséquent vide.

La figure suivante illustre la suppression du premier élément dans une liste de villes :

Image non disponible

Avant la suppression, L pointe sur Ribeauvillé et la liste contient quatre villes.

Après la suppression, L pointe sur la ville qui suivait Ribeauvillé, c'est-à-dire Kingersheim. De ce fait, elle ne contient plus que les trois villes Kingersheim, Strasbourg et Nancy.

Suppression du suivant

Supposons à présent que l'on souhaite supprimer l'élément qui suit un certain élément de la liste d'adresse donnée.

Appelons Curseur l'adresse de cet élément. L'instruction suivante permet de supprimer l'élément qui suit Curseur^ :

 
Sélectionnez
 Curseur^.Suivant := Curseur^.Suivant^.Suivant;

La figure suivante illustre ce mécanisme. On supprime ici la ville Strasbourg, en faisant pointer la ville précédente (Kingersheim) sur la ville qui suit Strasbourg (Nancy). De ce fait, Strasbourg n'existe plus dans la liste.

Image non disponible

Listes doublement chaînées

Dans une liste doublement chaînée, chaque élément est lié non seulement au suivant, mais également au précédent. Cela facilite la suppression d'un élément, puisqu'il faut pour cela avoir l'adresse du précédent. Il devient également plus simple d'insérer un élément avant un élément donné.

Représentation

Reprenons notre exemple de liste de villes. Voici comment la représenter avec un chaînage double :

 
Sélectionnez
Type
Ville = record 
          Nom : String;
          CodePostal : String;
          Suivant : PVille;
          Precedent : Pville;
          end;

PVille = ^Ville;

Voici un exemple de liste doublement chaînée :

Image non disponible

Adjonction d'un élément

En début de liste

L'adjonction d'un élément en début de liste nécessite deux instructions supplémentaires, puisqu'il faut mémoriser le fait que cet élément n'a pas d'élément précédent et qu'il devient à présent le précédent du premier élément de la liste (avant l'adjonction).

 
Sélectionnez
  p^.Suivant := L ;
  p^.Precedent := NIL;
  L^.Precedent := p;
  L := p;

Insertion après un élément

 
Sélectionnez
If Curseur^.Suivant <> NIL then
  Curseur^.Suivant^.Precedent := p;
p^.Precedent := Curseur;
p^.Suivant := Curseur^.Suivant;
Curseur^.Suivant := p;

Exercices

Téléchargez :

Pour obtenir les corrigés, le téléchargement n'est possible que via un login et un mot de passe, que vous pouvez obtenir en envoyant un mail à l'adresse suivante :

Image non disponible

en précisant un peu qui vous êtes et les raisons pour lesquelles ce cours vous intéresse.