NSI · Terminale · Structures de données
Conteneurs de données
Choisir la boîte selon l’opération.
En bref
Une structure de données se choisit d’après les opérations qu’on va lui demander, jamais d’après ce qu’elle contient.
Type abstrait et implémentation
| Type abstrait | Implémentation | |
|---|---|---|
| Il définit | Un jeu d’opérations et leur comportement | La façon dont la promesse est tenue |
| Exemple | Une pile promet d’empiler, dépiler, tester le vide | Un tableau ou une liste chaînée |
| Qui le voit | L’utilisateur | Seulement l’auteur de la structure |
C’est le principe d’encapsulation appliqué aux données.
Pile et file
| Pile (LIFO) | File (FIFO) | |
|---|---|---|
| La règle | Dernier entré, premier sorti | Premier entré, premier sorti |
| Les opérations | empiler, dépiler, sommet, est_vide | enfiler, défiler, est_vide |
| Les usages | Parenthésage, historique, pile d’appels d’un programme récursif | File d’attente, tampon d’impression, parcours en largeur |
Tableau ou liste chaînée — l’arbitrage
| Opération | Tableau (liste Python) | Liste chaînée |
|---|---|---|
| Accès au i-ième élément | Constant | Linéaire : il faut parcourir |
| Insertion en tête | Coûteuse : tout décaler | Constante |
Dans une liste chaînée, chaque maillon contient une valeur et une référence vers le suivant.
Le dictionnaire
Il associe une clé à une valeur. Grâce au hachage, recherche, insertion et suppression se font en temps constant en moyenne.
C’est la structure à choisir dès qu’on cherche « la valeur associée à » plutôt que « le i-ième élément ».
Le tableau de décision
| Ce dont le programme a besoin | La structure |
|---|---|
| Beaucoup d’accès par indice | Le tableau |
| Insertions et suppressions aux extrémités | Liste chaînée, pile ou file |
| Recherche par identifiant | Le dictionnaire |
| Une relation hiérarchique | L’arbre |
| Une relation quelconque | Le graphe |
Une structure mal choisie ne rend pas un programme faux : elle le rend lent — et sur des données réelles, c’est la même chose.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Qu’est-ce qu’un type abstrait de données ?
2.Quelle structure fonctionne en « dernier entré, premier sorti » ?
3.Quelle structure est utilisée pour un parcours en largeur ?
4.Quel est le coût d’accès au i-ième élément d’une liste chaînée ?
5.Quel est le coût moyen d’une recherche dans un dictionnaire ?
6.Insérer un élément en tête d’une liste chaînée coûte un temps constant.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Conteneurs de données » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
