Structures de données

L’écriture sur des exemples simples de plusieurs implémentations d’une même structure de données permet de faire émerger les notions d’interface et d’implémentation, ou encore de structure de données abstraite. Le paradigme de la programmation objet peut être utilisé pour réaliser des implémentations effectives des structures de données, même si ce n’est pas la seule façon de procéder. Le lien est établi avec la notion de modularité qui figure dans la rubrique « langages et programmation » en mettant en évidence l’intérêt d’utiliser des bibliothèques ou des API (Application Programming Interface).

Contenus	Capacités attendues	Commentaires
Structures de données, interface et implémentation.	Spécifier une structure de données par son interface. Distinguer interface et implémentation. Écrire plusieurs implémentations d’une même structure de données.	L’abstraction des structures de données est introduite après plusieurs implémentations d’une structure simple comme la file (avec un tableau ou avec deux piles).
Vocabulaire de la programmation objet : classes, attributs, méthodes, objets.	Écrire la définition d’une classe. Accéder aux attributs et méthodes d’une classe.	On n’aborde pas ici tous les aspects de la programmation objet comme le polymorphisme et l’héritage.
Listes, piles, files : structures linéaires. Dictionnaires, index et clé.	Distinguer des structures par le jeu des méthodes qui les caractérisent. Choisir une structure de données adaptée à la situation à modéliser. Distinguer la recherche d’une valeur dans une liste et dans un dictionnaire.	On distingue les modes FIFO (first in first out) et LIFO (last in first out) des piles et des files. Les listes n’existent pas de façon native en Python.
Arbres : structures hiérarchiques. Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits.	Identifier des situations nécessitant une structure de données arborescente. Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.).	On fait le lien avec la rubrique « algorithmique ».
Graphes : structures relationnelles. Sommets, arcs, arêtes, graphes orientés ou non orientés.	Modéliser des situations sous forme de graphes. Écrire les implémentations correspondantes d’un graphe : matrice d’adjacence, liste de successeurs/de prédécesseurs. Passer d’une représentation à une autre.	On s’appuie sur des exemples comme le réseau routier, le réseau électrique, internet, les réseaux sociaux. Le choix de la représentation dépend du traitement qu’on veut mettre en place : on fait le lien avec la rubrique « algorithmique ».