Une structure de données organise des informations pour qu’on puisse les manipuler efficacement. En Terminale, on distingue soigneusement ce que fait une structure (son interface) de la façon dont elle est programmée (son implémentation). Les structures linéaires — listes, piles, files — et les dictionnaires sont les briques de base de nombreux algorithmes.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Distinguer l’interface d’une structure de données de son implémentation
- Utiliser les primitives d’une liste chaînée, d’une pile et d’une file
- Implémenter une pile et une file en Python, avec une liste ou une classe
- Choisir la structure adaptée à un problème, dont le dictionnaire
1. Interface et implémentation
Type abstrait (interface) : Description des opérations disponibles sur une structure (créer, ajouter, retirer, tester si vide…) et de leur effet, sans dire comment elles sont programmées.
Implémentation : Programmation concrète de ces opérations, avec des choix (liste Python, classe, maillons…) qui influencent le coût de chaque opération.
Une liste chaînée est une suite de maillons : chaque maillon contient une valeur et une référence vers le maillon suivant (None pour le dernier). Ses primitives sont : créer une liste vide, tester si elle est vide, ajouter en tête, lire la tête (premier élément) et la queue (la liste des suivants).
class Maillon:
def __init__(self, valeur, suivant):
self.valeur = valeur
self.suivant = suivant
L = Maillon(4, Maillon(1, Maillon(7, None))) # liste 4, 1, 7
def longueur(m):
if m is None:
return 0
return 1 + longueur(m.suivant)2. Les piles (LIFO)
Pile : Structure où le dernier élément ajouté est le premier retiré (LIFO : Last In, First Out), comme une pile d’assiettes. Primitives : pile_vide(), est_vide(p), empiler(p, x), depiler(p) qui retire et renvoie le sommet.
p = [] # pile vide
p.append(1) # empiler 1
p.append(2) # empiler 2
x = p.pop() # dépiler : x vaut 2
print(p == []) # est_vide ? False- Utilisations : historique et bouton « annuler », pile d’appels des fonctions, vérification des parenthèses, évaluation d’expressions postfixées, parcours en profondeur.
- Avec une liste Python, append et pop en fin de liste se font en temps constant.
Évaluer l’expression postfixée 3 4 + 2 ×
- On lit 3 puis 4 : on les empile. Pile : 3, 4.
- On lit + : on dépile 4 et 3, on empile 3 + 4 = 7. Pile : 7.
- On lit 2 : on l’empile. Pile : 7, 2.
- On lit × : on dépile 2 et 7, on empile 14.
L’expression vaut 14 (c’est (3 + 4) × 2).
3. Les files (FIFO)
File : Structure où le premier élément ajouté est le premier retiré (FIFO : First In, First Out), comme une file d’attente. Primitives : file_vide(), est_vide(f), enfiler(f, x), defiler(f).
class File:
def __init__(self):
self.entree = []
self.sortie = []
def est_vide(self):
return self.entree == [] and self.sortie == []
def enfiler(self, x):
self.entree.append(x)
def defiler(self):
if self.sortie == []:
while self.entree != []:
self.sortie.append(self.entree.pop())
return self.sortie.pop()Quand la pile de sortie est vide, on y renverse la pile d’entrée : l’élément le plus ancien se retrouve au sommet. Chaque élément n’est transféré qu’une fois. Utilisations des files : file d’impression, traitement de requêtes dans l’ordre d’arrivée, parcours en largeur.
4. Les dictionnaires
Dictionnaire : Ensemble de couples clé → valeur, où chaque clé est unique. On accède à une valeur par sa clé et non par un indice.
stock = {"pomme": 3, "kiwi": 5}
stock["poire"] = 1 # ajout d’un couple
stock["pomme"] = 4 # modification
print("kiwi" in stock) # True : test d’appartenance d’une clé
for fruit in stock: # parcours des clés
print(fruit, stock[fruit])| Opération | Liste de n éléments | Dictionnaire |
|---|---|---|
| Rechercher une valeur / une clé | Parcours : coût proportionnel à n | Coût constant en moyenne (table de hachage) |
| Accès | Par indice entier L[i] | Par clé d[cle] |
À retenir
- L’interface décrit les opérations ; l’implémentation les programme.
- Pile : LIFO, empiler et dépiler au sommet.
- File : FIFO, enfiler à la fin, défiler au début.
- Liste chaînée : maillons reliés par des références, accès séquentiel.
- Dictionnaire : accès par clé en temps constant en moyenne.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.