Introduction¶

On va étudier dans ce chapitre la notion de structures de données. Une structure de données est une manière de stocker des données et d'interagir avec elles. On peut regrouper de grandes classes de structures de données en faisant abstraction de la manière dont les données sont stockées en se concentrant uniquement sur les interactions possibles. Cela permet de définir la notion de structure de données abstraite.

Dans un second temps, on s'intéresse à la notion d'implémentation d'une structure de données abstraite qui correspond à un choix concret de stockage et donc à une réalisation de l'interface attendue.

Structure de données abstraite¶

Définition

On appelle structure de données abstraite la donnée d'un type t et d'une interface, c'est-à-dire :

d'une liste d'opérations portant sur t, avec leur signature (types des arguments et du résultat) ;
d'une spécification décrivant le comportement attendu de chacune de ces opérations, sans faire référence à la manière dont les données sont stockées.

Le type t est alors dit abstrait : on ne le manipule qu'au travers des opérations de l'interface.

Exemple

La structure de pile, étudiée dans Piles et files, a pour interface les opérations creer_pile, est_vide, empiler et depiler. Sa spécification dit que :

est_vide(creer_pile()) est vrai ;
après empiler(p, x), la pile p n'est pas vide et un appel à depiler(p) renvoie x et redonne à p son état d'avant l'ajout ;
depiler sur une pile vide est une erreur.

C'est exactement ce qui permet d'écrire la fonction longueur_pile de ce chapitre sans savoir comment la pile est représentée.

On peut écrire une interface directement dans un langage de programmation. En OCaml, c'est le rôle d'un fichier d'interface .mli, qui donne les types des opérations sans dévoiler la définition du type. En C, c'est le rôle d'un fichier d'en-tête .h, qui déclare la structure sans ses champs et les prototypes des fonctions.

ocamlc

type 'a pile

val cree_pile : unit -> 'a pile
val est_vide : 'a pile -> bool
val empile : 'a pile -> 'a -> unit
val depile : 'a pile -> 'a

#include <stdbool.h>

struct pile;
typedef struct pile pile;

pile *pile_creer();
void pile_detruire(pile *p);
bool est_vide(pile *p);
void empiler(pile *p, int x);
int depiler(pile *p);

Remarque

La signature ne suffit pas à définir la structure. Une file a exactement la même signature qu'une pile, seule la spécification les distingue : l'ordre de retrait est LIFO pour une pile et FIFO pour une file.

D'autres structures abstraites seront étudiées dans les chapitres suivants :

les piles, les files et les files de priorité dans Piles et files ;
les ensembles finis et les dictionnaires dans Dictionnaires et ensembles finis ;
les collections d'ensembles disjoints dans Union-Find ;
les graphes dans Graphes, qu'on manipule au travers d'opérations comme l'ajout d'une arête, le test d'existence d'une arête ou le parcours des voisins d'un sommet.

Implémentation¶

Abstraction et implémentation¶

Définition

Une implémentation d'une structure de données abstraite est la donnée d'une représentation concrète du type t et d'un code pour chacune des opérations de l'interface, qui respecte la spécification.

Une même structure abstraite admet en général plusieurs implémentations. Par exemple, une pile peut être réalisée par un tableau borné et un indice de première case libre, ou par une liste chaînée. Une file peut être réalisée par un tableau circulaire ou par deux listes. Un graphe peut être représenté par une matrice d'adjacence ou par des listes d'adjacence.

L'intérêt de cette séparation est double :

le code qui utilise la structure ne dépend que de l'interface. On peut donc changer d'implémentation sans le modifier ;
le code qui implémente la structure peut maintenir des propriétés internes, appelées invariants, en étant sûr que personne d'autre ne modifie la représentation. Par exemple, pour la pile dans un tableau, l'invariant est que les éléments de la pile sont exactement ceux des cases d'indice \(0\) à fond - 1.

Remarque

En C, rien n'empêche réellement un utilisateur qui connaît la définition de struct pile d'aller modifier le champ fond. Le fichier d'en-tête ne déclarant pas les champs, un programme qui n'inclut que lui ne peut pas le faire. En OCaml, un type déclaré abstrait dans un .mli est réellement inaccessible en dehors du module.

Structures mutables et immuables¶

Il y a deux grandes manières de concevoir l'interface d'une structure.

Dans une structure mutable, les opérations modifient la structure qu'on leur passe en argument, par effet de bord. C'est le cas des piles ci-dessus : empile p x ne renvoie rien et modifie p.
Dans une structure immuable, ou persistante, les opérations ne modifient jamais leur argument mais renvoient une nouvelle structure. L'ancienne version reste utilisable.

Cela se voit dès la signature : la version immuable d'une pile renvoie la nouvelle pile.

ocaml

type 'a pile = 'a list

let pile_vide = []

let est_vide p = p = []

let empile p x = x :: p

let depile p =
  match p with
  | [] -> failwith "Erreur : dépiler sur une pile vide"
  | x :: q -> (x, q)

Ici, empile p x est de type 'a pile et non unit, et depile renvoie le sommet et la pile restante. Après let p' = empile p 3, on dispose à la fois de p et de p', sans aucune copie : la liste p est partagée.

Remarque

Les structures immuables sont naturelles en OCaml et se prêtent bien aux raisonnements par récurrence. Les structures mutables sont naturelles en C et permettent souvent des implémentations plus efficaces, par exemple à base de tableaux. Les deux points de vue cohabitent : on rencontrera dans Dictionnaires et ensembles finis une implémentation immuable (les arbres binaires de recherche) et une implémentation mutable (les tables de hachage) de la même structure abstraite.

Complexité des opérations¶

La spécification d'une structure abstraite ne dit rien du coût des opérations : c'est le choix de l'implémentation qui le détermine. En pratique, ce coût est pourtant ce qui guide le choix d'une implémentation, et on le précise toujours avec elle.

Structure abstraite	Implémentation	Complexité des opérations
Pile	tableau borné, liste chaînée	\(O(1)\)
File	tableau circulaire	\(O(1)\)
File	deux listes	\(O(1)\) amorti
Dictionnaire	arbre binaire de recherche de hauteur \(h\)	\(O(h)\)
Dictionnaire	table de hachage	\(O(1)\) en moyenne
Union-find	forêt avec union par rang et compression	\(O(\alpha(n))\) amorti

Remarque

Il faut toujours préciser de quelle complexité on parle. Pour une file réalisée avec deux listes, un retrait isolé peut coûter \(O(n)\), mais une suite de \(m\) opérations coûte \(O(m)\) : on parle de complexité amortie. Pour une table de hachage, un accès peut coûter \(O(n)\) dans le pire cas, et c'est seulement en moyenne, sous une hypothèse sur la fonction de hachage, qu'il est en \(O(1)\).