Terminale · Numérique et sciences informatiques

Utiliser une implémentation : interface, mise en œuvre et coût des opérations

Utiliser une structure de données (liste, pile, file, dictionnaire) uniquement à travers son interface, en choisissant parmi plusieurs implémentations celle dont la complexité convient aux opérations les plus fréquentes.

Aperçu gratuit
Illustration de la fiche « Utiliser une implémentation : interface, mise en œuvre et coût des opérations »

Les points essentiels

  • Une interface (ou type abstrait) définit les opérations autorisées sur une structure et leur comportement attendu, sans dire comment les données sont stockées : pour une pile, créer, empiler, dépiler, consulter le sommet, tester si elle est vide.
  • Une implémentation est la réalisation concrète de l'interface : choix de la représentation (tableau dynamique, liste chaînée, dictionnaire, programmation objet) et code de chaque opération.

Les mots à connaître

Interface
Ensemble des opérations d'une structure de données avec leurs entrées, leurs sorties et leur effet attendu, indépendamment de la manière dont les données sont stockées.
Implémentation
Réalisation concrète d'une interface dans un langage : représentation choisie en mémoire et code de chacune des opérations.

Un exemple pour comprendre

On implémente une pile avec une liste Python p = []. Écrire les opérations empiler(p, x), depiler(p), est_vide(p) puis donner l'état de p après : empiler 3, empiler 8, empiler 5, depiler, et le sommet restant. Quelle est la complexité de chaque opération ?

Opérations : empiler(p, x) fait p.append(x) ; depiler(p) fait return p.pop() ; est_vide(p) fait return len(p) == 0. États : après empiler 3, p = [3] ; après empiler 8, p = [3, 8] ; après empiler 5, p = [3, 8, 5] ; depiler renvoie 5 et p = [3, 8]. Le sommet restant est 8, dernier élément de la liste. Complexité : append et pop() en fin de liste sont en O(1) (amorti pour append), len en O(1). L'implémentation par liste convient donc bien à l'interface de pile.

Première page de l’Essentiel : Utiliser une implémentation : interface, mise en œuvre et coût des opérations
Ketty