Notebook associé
Le notebook constitue le support principal de cette séance. Il permet de lire les explications, modifier le code et exécuter les cellules pas à pas.
Consultez le mode d’emploi Jupyter.
Pourquoi organiser les données ?
Un programme manipule souvent plusieurs données qui doivent être organisées afin de pouvoir être utilisées efficacement.
En Première, nous avons déjà utilisé différentes structures fournies par Python :
- les listes ;
- les tuples ;
- les dictionnaires.
Le choix d’une structure dépend notamment des opérations que l’on souhaite effectuer sur les données.
Qu’est-ce qu’une structure de données ?
Une structure de données est une manière d’organiser un ensemble de données afin de permettre certaines opérations.
Selon la structure considérée, on pourra par exemple :
- ajouter un élément ;
- retirer un élément ;
- consulter un élément ;
- tester si la structure est vide ;
- connaître le nombre d’éléments qu’elle contient.
Les opérations disponibles caractérisent en grande partie le comportement de la structure.
L’interface d’une structure
L’interface d’une structure décrit les opérations que l’utilisateur peut effectuer sur celle-ci.
On peut par exemple imaginer une structure proposant les opérations suivantes :
créer une structure vide
ajouter un élément
retirer un élément
consulter un élément
tester si la structure est videCette description indique ce que l’on peut faire, mais elle ne précise pas encore comment les données sont réellement stockées.
L’implémentation
L’implémentation correspond à la manière concrète dont une structure et ses opérations sont réalisées dans un programme.
Une même structure abstraite peut parfois être implémentée de plusieurs façons.
En Python, une structure peut par exemple être construite à partir d’une liste :
donnees = []
donnees.append(12)
donnees.append(7)
donnees.append(25)La liste Python constitue ici un moyen de stockage. Elle ne définit pas à elle seule les règles d’utilisation de la structure que l’on souhaite construire.
Interface et implémentation
Il faut donc distinguer deux niveaux.
- L’interface décrit les opérations disponibles et leur comportement.
- L’implémentation décrit la manière dont ces opérations sont effectivement programmées.
Cette distinction permet d’utiliser une structure sans avoir besoin de connaître tous les détails de son fonctionnement interne.
Une structure de données abstraite
On parle de structure de données abstraite lorsqu’on définit une structure principalement par les données qu’elle manipule et les opérations qu’elle autorise, indépendamment de son implémentation particulière.
Deux programmes peuvent donc proposer la même interface tout en utilisant des représentations internes différentes.
L’utilisateur de la structure peut alors raisonner sur les opérations disponibles sans dépendre de la manière dont elles ont été programmées.
Vers les piles et les files
Les piles et les files sont deux structures de données linéaires.
Elles permettent toutes les deux de stocker plusieurs éléments, mais elles se distinguent par la règle utilisée pour déterminer quel élément peut être retiré.
- Dans une pile, le dernier élément ajouté est le premier retiré.
- Dans une file, le premier élément ajouté est le premier retiré.
Ces deux comportements seront étudiés dans les séances suivantes.
À retenir
- Une structure de données organise des informations afin de permettre certaines opérations.
- L’interface indique les opérations disponibles.
- L’implémentation indique comment ces opérations sont programmées.
- Une même structure abstraite peut disposer de plusieurs implémentations.
- Les piles et les files sont deux structures de données linéaires dont les règles d’accès sont différentes.