NSI Terminale
NSI Terminale
Une structure de données est une manière d'organiser les informations de façon à pouvoir les manipuler le plus efficacement possible selon les besoins du programme dans lequel on les utlise.
A travers l'exemple de la pile, vous avez vu comment on a pu créer une nouvelle structure de données qui n'existe pas par défaut dans le langage Python.
Vous avez vu que l'on a séparé la création d'une pile en deux étapes :
On distingue donc la définition abstraite d'une structure de données, c'est à dire en dehors de toute considération "technique" de codage, et son implémentation qui consiste à la coder concrètement.
L’abstraction consiste à penser à un objet en termes d’actions que l’on peut effectuer sur lui, et non pas en termes de représentation et d’implantation de cet objet.
La conception d’un algorithme est indépendante de toute manière de le coder.
De la même façon, la représentation des données n'est pas fixée : celles-ci peuvent être considérées de manière abstraite, en s’intéressant uniquement à l’ensemble des opérations que l'on peut faire sur les données ( ces opérations sont appelées primitives.), aux propriétés de ces opérations, sans dire comment ces opérations sont réalisées.
Par exemple, savez-vous comment une liste "fonctionne" exactement au niveau de la mémoire d'un ordinateur ? Non ? Et pourtant, vous savez très bien ce qu'est une liste ( un tableau fait d'un ensemble de "cases" contiguës ), et vous connaissez les opérations que l'on peut faire sur les données d'une liste ( en ajouter, en supprimer, accéder à une case, etc...
De même, vous pouvez très bien savoir conduire une voiture sans avoir aucune idée de la manière dont fonctionne le moteur à explosion qui fait tourner les roues...
On parle ainsi de Type Abstrait de Données ( TAD ) lorsqu'on veut décrire une structure de données sans entrer dans les détails de son codage.
Intérêt de cette façon de procéder : elle permet de se concentrer sur les fonctionnalités attendues d'une structure de données, indépendamment du langage qui sera plus tard utilisé; on fait "une chose à la fois".
De plus, le codage ne se fera pas pour traiter un problème spécifique mais sera d'une utilisation beaucoup plus générale, ce qui permet ensuite la réutilisation du code dans d'autres projets.
Voila ci-contre une manière simplifiée ( il en existe de beaucoup plus rigoureuses...) pour représenter la spécification du TAD "PILE".
L'écriture concrète d'un TAD s'appelle son implémentation.
Le codage proprement dit d'une structure de données peut se faire de différentes façons : pour un même TAD, il y a donc plusieurs implémentations possibles.
Le choix de l'implémentation doit se faire en fonction de sa simplicité, ou alors en fonction de sa performance en mémoire ou en temps.
Pour implémenter un TAD, on peut utiliser :Dans le cas de la pile, vous en avez réalisé une implémentation impérative sous forme d'une liste, et une implémentation objet.
On peut même simplement réutiliser une structure de données déjà implémentée par quelqu’un d'autre dans une bibliothèque !
On l'a vu, pas la peine de savoir ce qu'il y a "sous le capot" pour utiliser une structure de données...par contre, il faut connaître précisément toutes les possibilités qu'elle permet et comment les utiliser.
Lorsqu'on veut utiliser une structure de données ( surtout si on ne l'a pas nous-même codée ! ), il faut donc connaître son interface.
De manière générale, une interface désigne la frontière entre deux milieux entre lesquels il y a des échanges.
L'interface d'une structure de données explique la manière de l'utiliser en pratique, à savoir :
Pour une même interface, l'implémentation peut cependant toujours varier, ce qui permet de mettre à jour le code sans que l'utilisation de la structure de données soit modifiée. L'interface représente un peu le "contrat de service" que la structure de données s'engage à fournir, sans que l'on soit obligé de connaître la manière dont elle l'implémente.
Cette notion d'interface se généralise à tout programme, pour lequel on parle alors d'interface de programmation ou API ( Application Programming Interface ); la connaissance de l'API d'un logiciel ou d'un service web tiers ( = pas écrit par l'utilisateur ) suffit à l'utilisation de ce logiciel ou ce service.
Vous trouverez par exemple sur cette page les détails de l'API pour utiliser les données de cartographie du site OpenStreetMap
