Thème 1 : Structures de données

En informatique, une structure de données est une manière d'organiser les données pour les traiter plus facilement. Une structure de données est une mise en œuvre concrète d'un type abstrait.

Pour un type abstrait donné, il faut absolument différencier l'interface de l'implémentation:

• interface : ensemble des méthodes qui permettent de manipuler le type abstrait;
• implémentation: code (Python en ce qui nous concerne) qui permet de construire les méthodes.

On choisit un type abstrait en fonction du problème à résoudre (choisir le bon type, c'est déjà résoudre la majeure partie du problème) et des méthodes à envisager (et de leur coût), appelées également primitives.

Différents types abstraits de données

• tableaux (vus en première)
• listes chaînées
• piles
• files
• tableaux associatifs (vus en première)
• arbres
• graphes