Ce qu’il faut retenir…
Structure de données : ensemble de données regroupées sous un nom de variable unique, et organisée d’une façon particulière les unes par rapport aux autres.
Structure concrète de données ou type concret (ou encore type structuré, ou type construit)
- tableau indexé (ou indicé)
- tableau associatif (association d’une clé et d’une valeur)
- n-uplet
- chaîne de caractères
Ces types concrets sont implémentés nativement dans un langage de programmation de haut niveau comme Python.
Structure abstraite de données ou type abstrait
Un type abstrait est une structure complexe de données. Très souvent, un type abstrait n’est pas « disponible » dans un langage de programmation de haut niveau donné : il peut – pour certains d’entre eux – être ajouté, en important une bibliothèque.
Les données sont gérées par l’intermédiaire d’opérations qui constituent l’interface de la structure. Spécifier un type abstrait c’est définir son interface.
Les opérations disponibles dans l’interface se regroupent en plusieurs catégories, dont :
- le constructeur, qui permet de déclarer une nouvelle structure de données ;
- les observateurs (ou accesseurs), qui permettent d’avoir des informations sur la structure de données : est-elle vide ? Sinon, combien de données contient elle ? Quelles sont les données contenues dans la structure de données ?
- les transformateurs (ou opérateurs), qui permettent d’ajouter, de supprimer, de modifier des données ;
Implémenter un type abstrait c’est programmer les opérations de l’interface, en s’appuyant notamment sur les types concrets. Une interface donnée peut être implémentée de plusieurs façons différentes, selon les types concrets choisis et/ou le paradigme de programmation utilisé : programmation impérative, programmation objet, programmation fonctionnelle…
On distingue :
- des types abstraits linéaires : liste chaînée, pile, file, dictionnaire ;
- des types abstraits hiérarchiques : arbres ;
- des types abstraits relationnelles : graphes.
- Cours, page 12, paragraphe 1 « Interface et implémentation »
- Cours, page 94, paragraphe 1 « Structures de données, types abstraits »