Les types structurés▲
Introduction▲
Dans le cours sur les tableaux, nous avons vu un premier moyen de mémoriser un ensemble de données dans une variable. Cette manière de procéder est toutefois limitée à des données de même type. Les types structurés que nous allons présenter dans ce cours permettent de lever cette limitation.
Une autre limitation importante des tableaux est qu'ils sont de dimension fixe. On est donc souvent contraint de les surdimensionner, afin de s'assurer qu'ils pourront stocker toutes les données à traiter. Dans ce cours, nous allons voir comment stocker des ensembles de données de taille variable sous formes de listes. Avec cette nouvelle représentation, il sera possible d'utiliser une place mémoire proportionnelle au nombre de données à mémoriser.
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éel, 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 :
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 :
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 :
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 :
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és 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 :
Var Bibliotheque : array [1..M] of Livre;La variable Bibliotheque est donc un tableau de structures. La notation
Bibliotheque[6].Auteurrepré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 :
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 :
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 :
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 :
En Pascal, un pointeur se déclare de la manière suivante :
Var NomDuPointeur : ^Type;où Type représente le type de donnée dont le pointeur contiendra l'adresse.
Exemple :
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 :
Type PointeurSurType = ^Type;et de déclarer ensuite le pointeur comme une variable de ce type :
Var NomDuPointeur : PointeurSurType;Avec l'exemple précédent cela donnerait :
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éée 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 :
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 :
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 :
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 chaînée contenant quatre villes :
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 :
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▲
Pour ajouter l'élément p^ au début de la liste L, il suffit de faire :
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é :
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 :
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 :
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 :
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 :
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'adresses donnée.
Appelons Curseur l'adresse de cet élément. L'instruction suivante permet de supprimer l'élément qui suit Curseur^ :
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.
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 :
Type Ville =
record
Nom : String;
CodePostal : String;
Suivant : PVille;
Precedent : Pville;
end;
PVille = ^Ville;Voici un exemple de liste doublement chaînée :
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).
p^.Suivant := L ;
p^.Precedent := NIL;
L^.Precedent := p;
L := p;Insertion après un élément▲
If Curseur^.Suivant <> NIL then
Curseur^.Suivant^.Precedent := p;
p^.Precedent := Curseur;
p^.Suivant := Curseur^.Suivant;
Curseur^.Suivant := p;Exercices▲
Téléchargez :
- les exercices sur les types structurés ;
- les exercices sur les pointeurs et les listes.
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 :
en précisant un peu qui vous êtes et les raisons pour lesquelles ce cours vous intéresse.