Structures de données¶
Programme officiel (B.O.)¶
B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale
| Contenus | Capacités attendues |
|---|---|
| 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. |
| 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. |
| 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. |
| Arbres : structures hiérarchiques. Arbres binaires : nœuds, racines, feuilles, sous-arbres gauches/droits. | Identifier des situations nécessitant une structure de données arborescente. Évaluer quelques mesures des arbres binaires (taille, hauteur, etc.). |
| 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 : matrice d'adjacence, liste de successeurs/prédécesseurs. Passer d'une représentation à une autre. |
1. Interface vs implémentation¶
1.1 Structure de données abstraite¶
Une structure de données est une manière d'organiser des informations pour les manipuler efficacement. On la décrit par son interface : l'ensemble des opérations qu'elle propose, sans préciser comment elles sont réalisées.
L'implémentation est le choix concret de la représentation en mémoire et de l'algorithme de chaque opération.
Analogie
L'interface est comme le mode d'emploi d'un appareil (quels boutons, quelles fonctions), tandis que l'implémentation est le circuit électronique à l'intérieur. L'utilisateur n'a pas besoin de connaître le circuit pour se servir de l'appareil.
1.2 Pourquoi cette distinction ?¶
- On peut changer l'implémentation sans modifier le code qui utilise la structure ;
- Plusieurs implémentations d'une même interface peuvent avoir des performances différentes ;
- Cela favorise la modularité et la réutilisabilité du code.
2. Programmation orientée objet : rappels¶
En Python, on utilise des classes pour implémenter les structures de données.
class Point:
def __init__(self, x, y):
self.x = x # attribut
self.y = y # attribut
def distance_origine(self): # méthode
return (self.x ** 2 + self.y ** 2) ** 0.5
p = Point(3, 4) # création d'un objet (instance)
print(p.x) # accès à un attribut → 3
print(p.distance_origine()) # appel de méthode → 5.0
| Terme | Définition |
|---|---|
| Classe | Modèle qui définit les attributs et méthodes d'un type d'objet |
| Objet (instance) | Exemplaire concret créé à partir d'une classe |
| Attribut | Variable attachée à un objet (ses données) |
| Méthode | Fonction attachée à un objet (ses comportements) |
3. Listes chaînées¶
3.1 Principe¶
Une liste chaînée est une suite d'éléments où chaque élément (appelé maillon ou nœud) contient :
- une valeur ;
- une référence vers le maillon suivant (ou
Nonesi c'est le dernier).
3.2 Comparaison avec les tableaux Python¶
| Opération | Tableau (list) | Liste chaînée |
|---|---|---|
| Accès par index | O(1) - rapide | O(n) - il faut parcourir |
| Insertion en tête | O(n) - décalage | O(1) - rapide |
| Insertion en fin | O(1) amorti | O(n) ou O(1) si on garde une réf. vers la fin |
3.3 Implémentation en Python¶
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def est_vide(self):
return self.tete is None
def ajouter_en_tete(self, valeur):
nouveau = Maillon(valeur, self.tete)
self.tete = nouveau
def __str__(self):
éléments = []
courant = self.tete
while courant is not None:
éléments.append(str(courant.valeur))
courant = courant.suivant
return " -> ".join(éléments)
# Utilisation
lst = ListeChainee()
lst.ajouter_en_tete(3)
lst.ajouter_en_tete(8)
lst.ajouter_en_tete(5)
print(lst) # 5 -> 8 -> 3
4. Piles¶
4.1 Interface¶
Une pile (stack) suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré. Comme une pile d'assiettes.
| Opération | Description |
|---|---|
empiler(x) |
Ajouter x au sommet |
depiler() |
Retirer et renvoyer l'élément du sommet |
est_vide() |
Tester si la pile est vide |
sommet() |
Consulter l'élément du sommet sans le retirer |
4.2 Implémentation avec un tableau¶
class Pile:
def __init__(self):
self.éléments = []
def empiler(self, x):
self.éléments.append(x)
def depiler(self):
return self.éléments.pop()
def est_vide(self):
return len(self.éléments) == 0
def sommet(self):
return self.éléments[-1]
def __str__(self):
return str(self.éléments)
# Utilisation
p = Pile()
p.empiler(10)
p.empiler(20)
p.empiler(30)
print(p.depiler()) # 30 (le dernier ajouté)
print(p.depiler()) # 20
4.3 Applications¶
- Historique de navigation : le bouton « retour » dépile la dernière page visitée ;
- Annulation (Ctrl+Z) : chaque action est empilée, annuler = dépiler ;
- Évaluation d'expressions avec parenthèses ;
- Appels de fonctions : chaque appel est empilé, le retour dépile.
5. Files¶
5.1 Interface¶
Une file (queue) suit le principe FIFO (First In, First Out) : le premier élément ajouté est le premier retiré. Comme une file d'attente.
| Opération | Description |
|---|---|
enfiler(x) |
Ajouter x à la fin |
defiler() |
Retirer et renvoyer l'élément du début |
est_vide() |
Tester si la file est vide |
5.2 Implémentation avec deux piles¶
Une file peut être réalisée avec deux piles :
class File:
def __init__(self):
self.entree = Pile()
self.sortie = Pile()
def enfiler(self, x):
self.entree.empiler(x)
def defiler(self):
if self.sortie.est_vide():
while not self.entree.est_vide():
self.sortie.empiler(self.entree.depiler())
return self.sortie.depiler()
def est_vide(self):
return self.entree.est_vide() and self.sortie.est_vide()
5.3 Applications¶
- File d'impression : les documents s'impriment dans l'ordre d'envoi ;
- Gestion de processus par le système d'exploitation ;
- Parcours en largeur d'un graphe ou d'un arbre.
6. Dictionnaires¶
6.1 Principe¶
Un dictionnaire associe des clés à des valeurs. Chaque clé est unique et permet d'accéder directement à la valeur associée.
élève = {
"nom": "Dupont",
"prenom": "Alice",
"age": 17,
"classe": "Terminale"
}
print(élève["prenom"]) # "Alice"
élève["moyenne"] = 15.5 # ajout d'une entrée
6.2 Comparaison avec les listes¶
| Opération | Liste | Dictionnaire |
|---|---|---|
| Recherche par valeur | O(n) - parcours | O(1) en moyenne - par la clé |
| Accès par position | O(1) - par index | Non applicable |
| Ordre des éléments | Ordonné | Ordonné (Python 3.7+) |
Quand utiliser un dictionnaire ?
Quand on veut retrouver rapidement une information à partir d'un identifiant unique (nom, code, clé).
7. Arbres¶
7.1 Définition¶
Un arbre est une structure de données hiérarchique composée de nœuds reliés par des arêtes. Il possède :
- une racine : le nœud au sommet, sans parent ;
- des feuilles : les nœuds sans enfant ;
- des nœuds internes : les nœuds qui ont au moins un enfant.
7.2 Arbres binaires¶
Un arbre binaire est un arbre où chaque nœud possède au plus deux enfants : un sous-arbre gauche et un sous-arbre droit.
7.3 Mesures d'un arbre binaire¶
| Mesure | Définition |
|---|---|
| Taille | Nombre total de nœuds |
| Hauteur | Longueur du plus long chemin de la racine à une feuille |
| Profondeur d'un nœud | Distance (nombre d'arêtes) entre la racine et ce nœud |
Dans l'arbre ci-dessus : taille = 6, hauteur = 2 (racine à profondeur 0).
7.4 Implémentation en Python¶
class Nœud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(arbre):
if arbre is None:
return 0
return 1 + taille(arbre.gauche) + taille(arbre.droit)
def hauteur(arbre):
if arbre is None:
return -1
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))
# Construction de l'arbre d'exemple
arbre = Nœud(7,
Nœud(4, Nœud(2), Nœud(5)),
Nœud(9, None, Nœud(11))
)
print(taille(arbre)) # 6
print(hauteur(arbre)) # 2
8. Graphes¶
8.1 Définition¶
Un graphe est constitué de sommets (ou nœuds) reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté).
- Graphe non orienté : les liaisons sont symétriques (A-B signifie qu'on peut aller de A à B et de B à A) ;
- Graphe orienté : les liaisons ont un sens (A→B ne signifie pas forcément B→A).
8.2 Exemples concrets¶
| Situation | Sommets | Arêtes/Arcs |
|---|---|---|
| Réseau routier | Villes | Routes |
| Réseau social | Personnes | Relations d'amitié |
| Internet | Routeurs | Liens physiques |
| Web | Pages | Liens hypertextes (orienté) |
8.3 Représentations¶
Matrice d'adjacence : un tableau 2D où la case \((i, j)\) vaut 1 si les sommets \(i\) et \(j\) sont reliés, 0 sinon.
Liste d'adjacence (dictionnaire) : chaque sommet est associé à la liste de ses voisins.
8.4 Passage d'une représentation à l'autre¶
def matrice_vers_liste(matrice, sommets):
graphe = {}
for i in range(len(sommets)):
voisins = []
for j in range(len(sommets)):
if matrice[i][j] == 1:
voisins.append(sommets[j])
graphe[sommets[i]] = voisins
return graphe
def liste_vers_matrice(graphe, sommets):
n = len(sommets)
matrice = [[0] * n for _ in range(n)]
index = {s: i for i, s in enumerate(sommets)}
for sommet in graphe:
for voisin in graphe[sommet]:
matrice[index[sommet]][index[voisin]] = 1
return matrice
# Test
sommets = ["A", "B", "C", "D"]
mat = [[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]
print(matrice_vers_liste(mat, sommets))
# {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}
9. Résumé¶
| Structure | Type | Principe | Complexité d'accès |
|---|---|---|---|
| Liste chaînée | Linéaire | Maillons reliés par des références | O(n) |
| Pile | Linéaire | LIFO (dernier entré, premier sorti) | O(1) empiler/dépiler |
| File | Linéaire | FIFO (premier entré, premier sorti) | O(1) enfiler/défiler |
| Dictionnaire | Associative | Paires clé-valeur | O(1) en moyenne |
| Arbre binaire | Hiérarchique | Nœuds avec au plus 2 enfants | O(log n) si équilibré |
| Graphe | Relationnelle | Sommets et arêtes/arcs | Dépend de la représentation |