Structures de données linéaires
Cours · NSI (terminale), chapitre 1 · terminale, spécialité numérique et sciences informatiques · le début du chapitre, la suite sur Adloun
L'écriture d'un programme efficace ne dépend pas seulement de la qualité des algorithmes : elle repose tout autant sur la manière dont les données sont organisées en mémoire. Une structure de données décrit la façon dont des informations sont rangées, reliées entre elles et rendues accessibles. Selon que l'on souhaite parcourir des éléments dans l'ordre, ajouter ou retirer rapidement une valeur, ou encore accéder à n'importe quel élément directement, certaines structures se révèlent bien plus adaptées que d'autres.
Dans ce chapitre, nous étudions les structures de données linéaires, dans lesquelles les éléments sont organisés les uns à la suite des autres. Nous commencerons par une distinction fondamentale, celle entre le type abstrait de données (ce que la structure permet de faire) et son implémentation (comment elle le fait concrètement). Nous étudierons ensuite trois structures emblématiques du programme de Terminale NSI : les listes, les piles (LIFO) et les files (FIFO). Pour chacune, nous présenterons son interface, ses applications, ses implémentations en Python et le coût de ses opérations.
1.1 Type abstrait de données : interface et implémentation
1.1.1 La notion de type abstrait de données
Lorsqu'un programmeur utilise une structure de données, il a besoin de savoir ce qu'elle fait, mais pas nécessairement comment elle le fait. Cette séparation est au cœur de la notion de type abstrait de données.
Un type abstrait de données (TAD) est une description d'un ensemble de valeurs et des opérations que l'on peut effectuer sur ces valeurs, indépendamment de toute représentation concrète en mémoire. Un TAD définit quoi (les opérations et leur comportement) sans préciser comment (la manière dont les données sont stockées).
L'ensemble des opérations offertes par un TAD, accompagné de la description de leur comportement, constitue son interface.
L'interface d'un type abstrait est la liste des opérations disponibles, avec leurs paramètres, leur valeur de retour et leur effet, tels qu'un utilisateur les perçoit.
L'implémentation est la réalisation concrète de ce type dans un langage de programmation : choix d'une représentation en mémoire et écriture du code de chaque opération.
Un même type abstrait peut admettre plusieurs implémentations différentes. Tant que l'interface est respectée, on peut remplacer une implémentation par une autre sans modifier les programmes qui utilisent la structure. Seules les performances (le coût des opérations) peuvent changer.
Le type abstrait pile fournit notamment les opérations : créer une pile vide, tester si elle est vide, empiler une valeur, dépiler la valeur du sommet. Le programmeur qui empile puis dépile n'a pas besoin de savoir si, en mémoire, la pile est rangée dans un tableau dynamique ou dans une liste chaînée : seule l'interface l'intéresse.
1.1.2 Pourquoi distinguer les deux ?
Cette séparation présente plusieurs avantages essentiels en informatique :
- Abstraction : on raisonne sur les opérations sans se perdre dans les détails de stockage.
- Modularité : on peut améliorer l'implémentation (la rendre plus rapide) sans toucher au reste du programme.
- Réutilisation : une même structure peut servir dans de nombreux contextes.
- Fiabilité : en limitant les manipulations aux opérations de l'interface, on évite de corrompre la structure.
1.2 Les listes
1.2.1 Le type abstrait liste
Une liste est une collection ordonnée et de taille variable d'éléments, dans laquelle chaque élément occupe une position (un indice). Contrairement à un ensemble, une liste peut contenir plusieurs fois la même valeur et l'ordre des éléments y est significatif.
Exercices du chapitre
- Inverser une liste à l'aide d'une pile corrigé
- Vérification du parenthésage corrigé
- Convertir une file en pile corrigé
- Problème — File implémentée à deux piles corrigé
- Somme et moyenne d'une liste corrigé
- Simulation d'une file d'attente corrigé