Structures de données en Terminale
Cours complet, points clés à retenir et exercices d'entraînement de structures de données pour les élèves de Terminale. Conforme au programme officiel.
Réviser notion par notion
Ce que tu vas réviser
- Listes chaînées : implémentation et opérations
- Piles et files : LIFO, FIFO, applications
- Arbres binaires : parcours (préfixe, infixe, suffixe)
- Arbres binaires de recherche (ABR)
- Graphes : représentation (matrice d'adjacence, liste d'adjacence)
Listes chaînées : implémentation et opérations
Une liste chaînée est une structure où chaque élément (nœud) contient une valeur et un lien vers l'élément suivant. Contrairement aux listes classiques, les éléments ne sont pas contigus en mémoire.
Exemple
Un train de wagons : chaque wagon contient des passagers (données) et est attaché au wagon suivant par un attelage (lien).
À retenir : Chaque nœud contient une valeur et une référence au nœud suivant, le dernier nœud pointe vers None.
Piles : LIFO et applications
Une pile est une structure de données où on ajoute et retire les éléments par le même bout, selon le principe LIFO (Last In, First Out). Le dernier entré est le premier sorti.
Exemple
Une pile d'assiettes au restaurant : on ajoute une assiette au sommet et on la retire aussi du sommet.
À retenir : LIFO signifie que le dernier élément ajouté est le premier à être retiré.
Files : FIFO et applications
Une file est une structure de données où on ajoute les éléments à l'arrière et on les retire à l'avant, selon le principe FIFO (First In, First Out). Le premier entré est le premier sorti.
Exemple
Une file d'attente à la caisse du supermarché : le premier client arrivé est le premier servi.
À retenir : FIFO signifie que le premier élément ajouté est le premier à être retiré.
Arbres binaires : structure et définition
Un arbre binaire est une structure hiérarchique où chaque nœud a au maximum deux enfants (gauche et droit). Un nœud sans enfant est une feuille.
Exemple
L'organigramme d'une entreprise : le PDG au sommet, chaque personne peut avoir jusqu'à deux subordonnés directs.
À retenir : Un arbre binaire a une racine, et chaque nœud a 0, 1 ou 2 enfants.
Parcours d'arbres binaires : préfixe, infixe, suffixe
Les parcours permettent de visiter tous les nœuds d'un arbre dans un ordre spécifique. Préfixe (racine d'abord), infixe (enfant gauche, racine, enfant droit), suffixe (enfants d'abord, puis racine).
Exemple
Visiter tous les pièces d'une maison : on peut commencer par le salon (préfixe), ou d'abord les chambres (suffixe).
À retenir : Infixe donne l'ordre croissant pour un ABR, préfixe et suffixe sont utiles pour d'autres traitements.
Arbres binaires de recherche (ABR)
Un ABR est un arbre binaire où pour chaque nœud, tous les éléments du sous-arbre gauche sont plus petits et tous ceux du sous-arbre droit sont plus grands.
Exemple
Un dictionnaire organisé : les mots commençant par A-M à gauche, N-Z à droite, récursivement.
À retenir : Dans un ABR, la recherche, l'insertion et la suppression sont efficaces si l'arbre est équilibré.
Graphes : représentation et concepts
Un graphe est un ensemble de nœuds (sommets) reliés par des arêtes (liens). Il peut être orienté (flèches) ou non orienté (simples liens).
Exemple
Un réseau social : les personnes sont des nœuds, les amitiés sont des arêtes reliant deux nœuds.
À retenir : Un graphe se représente soit par matrice d'adjacence (tableau 2D), soit par liste d'adjacence (dictionnaire).
Matrice d'adjacence : représentation dense
Une matrice d'adjacence est un tableau 2D où chaque case [i][j] indique s'il existe une arête entre le nœud i et le nœud j (1 ou 0, ou le poids de l'arête).
Exemple
Un tableau de vols entre villes : ligne = ville de départ, colonne = ville d'arrivée, case = 1 s'il y a un vol.
À retenir : Matrice d'adjacence : accès rapide aux arêtes, mais consomme beaucoup de mémoire pour les graphes peu denses.
Liste d'adjacence : représentation creuse
Une liste d'adjacence est un dictionnaire où chaque nœud a une liste de ses voisins directs. Plus compacte qu'une matrice pour les graphes peu denses.
Exemple
Un carnet d'adresses : pour chaque personne, on liste ses amis directs au lieu de faire un tableau complet.
À retenir : Liste d'adjacence : économe en mémoire, idéale pour les graphes peu denses, mais accès aux arêtes plus lent.
Les points clés
- Les listes chaînées offrent une flexibilité en taille mais un accès plus lent qu'un tableau
- Pile (LIFO) et file (FIFO) sont des structures abstraites fondamentales en informatique
- Les arbres binaires permettent une organisation hiérarchique efficace des données
- Un ABR bien équilibré garantit des opérations en O(log n)
- Le choix entre matrice et liste d'adjacence dépend de la densité du graphe
L'essentiel
Les structures de données (listes, piles, files, arbres, graphes) sont le fondement de l'informatique : choisir la bonne structure détermine l'efficacité d'un algorithme.
Exercices d'entraînement
Entraîne-toi sur ces exercices, puis fais-toi corriger pas à pas par le tuteur.
Exercice 1
Implémentez une pile en Python avec les méthodes empiler(), dépiler() et est_vide(). Testez avec la séquence : empiler(5), empiler(3), dépiler(), empiler(7), dépiler().
Corrige cet exercice avec le tuteur →Exercice 2
Soit un ABR contenant les valeurs 50, 30, 70, 20, 40, 60, 80. Dessinez l'arbre et effectuez un parcours infixe. Quel ordre obtenez-vous ?
Corrige cet exercice avec le tuteur →