Dans cette deuxième partie, nous allons étudier quelques structures de données
utilisées de façons intensives en informatique. Il s’agit de gérer des
ensembles de données dont le nombre n’est pas fixé a priori. On ne
s’intéresse pas aux éléments de l’ensemble considéré mais plutôt aux
<em>méthodes</em> de gestion de ces éléments.
L'<em>analyse du domaine</em> sert à décomposer les objets réels complexes et leurs
interrelations en objets et relations plus simples. Par exemple
l’objet « plan d’une maison » se décompose en plans des différents
étages et des
façades, qui eux-mêmes se décomposent en murs, portes, fenêtres, etc.
L’abstraction des données va dans l’autre sens. À partir des objets
informatiques de base (types prédéfinis, tableaux, enregistrements,
pointeurs) on construit des objets plus abstraits (listes, ensembles, …) qui
servent eux-mêmes à construire des objets encore plus abstraits (graphes,
dessins, …). Jusqu’à ce qu’on arrive au niveau où il devient simple de
représenter les objets du réel que l’on considère.
Définition de types de données
La définition d’un nouveau type de donnée, c.-à-d. d’une nouvelle abstraction,
consiste à définir l’ensemble des valeurs possibles pour les objets de
ce type et l’ensemble des opérations de traitement de ces valeurs.
La gestion des ensembles doit, pour être efficace, respecter au mieux
deux critères parfois contradictoires : un minimum de place mémoire
utilisée (cf. page Complexite}
et un minimum d’instructions pour réaliser une
opération. Pour bine faire, la place mémoire utilisée devrait être voisine du
nombre d’éléments de l’ensemble multiplié par la taille d’un élément.
Pour accueillir les valeurs du type il est nécessaire de définir une structure
interne de données construite à partir des types de base du langage et/ou
des types déjà définis. Les opérations seront définies par des procédures ou
fonctions du langage de programmation.
