Structures de données
Une structure de données est une manière d’organiser et de stocker l’information, dont l’objectif est de les traiter plus facilement.
exemple : pour en faciliter l’accès, la modification, le tri, …
Une structure de données doit avoir une interface : un ensemble de procédures pour ajouter, effacer, accéder, réorganiser, etc… les données.
Principales structures de données
- Liste chaînée : collection d’objets accessibles via leurs voisins
- Pile : collection d’objets accessible selon une politique LIFO
- File : collection d’objets accessible selon une politique FIFO
- File double : combine accès LIFO et FIFO
- Liste : collection d’objets ordonnés accessible à partir de leur position
- Vecteur : collection d’objets ordonnés accessible à partir de leur rang
- File à priorité : accès uniquement à l’élément de clé (priorité)maximale
- Dictionnaire : structure qui implémente les 3 opérations recherche, insertion, suppression
- …
Type abstrait
Une structure de données est une mise en œuvre concrète d’un type abstrait.
En informatique, un type abstrait (en anglais, abstract data type ou ADT) est une spécification mathématique :
- d’un ensemble de données
- et de l’ensemble des opérations qu’on peut effectuer sur elles.
On qualifie d’abstrait ce type de données car il correspond à un cahier des charges qu’une structure de données doit ensuite mettre en œuvre.
