Structures de données linéaires

Cours complet · NSI (terminale), chapitre 1 · terminale, spécialité numérique et sciences informatiques

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

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.

Définition 1.1Type abstrait de données (TAD)

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.

Définition 1.2Interface et implémentation

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.

Proposition 1.3Indépendance interface / implémentation

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.

Exemple 1.4Une pile vue comme un TAD

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

Définition 1.5Liste

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.

Les opérations usuelles de l'interface d'une liste sont :

créer une liste vide ;
connaître la longueur (le nombre d'éléments) ;
accéder à l'élément situé à un indice donné ;
modifier l'élément situé à un indice donné ;
ajouter un élément (en fin, ou à une position donnée) ;
supprimer un élément (en fin, ou à une position donnée) ;
parcourir tous les éléments.

En Python, le type list fournit une implémentation très commode de ce type abstrait.

Exemple 1.6Opérations de base sur une liste Python


notes = [12, 15, 9, 18]   # creation d'une liste
print(len(notes))          # longueur : 4
print(notes[2])            # acces a l'indice 2 : 9
notes[2] = 11              # modification de l'element d'indice 2
notes.append(20)           # ajout en fin : [12, 15, 11, 18, 20]
notes.insert(1, 14)        # insertion a l'indice 1
valeur = notes.pop()       # suppression et recuperation du dernier element

1.2.2 Le parcours d'une liste

Parcourir une liste consiste à examiner successivement chacun de ses éléments. C'est l'opération la plus fréquente : recherche d'une valeur, calcul d'une somme, affichage, etc.

Méthode : Parcourir une liste en Python

Deux parcours sont à connaître :

le parcours par élément, lorsque l'on n'a pas besoin de l'indice ;
le parcours par indice, lorsque l'on a besoin de la position (par exemple pour modifier les éléments).


notes = [12, 15, 9, 18]

# Parcours par element
for note in notes:
    print(note)

# Parcours par indice
for i in range(len(notes)):
    print("indice", i, ":", notes[i])

Exemple 1.7Recherche d'un maximum par parcours


def maximum(liste):
    """Renvoie le plus grand element d'une liste non vide."""
    plus_grand = liste[0]          # on suppose le premier maximal
    for valeur in liste:           # parcours de tous les elements
        if valeur > plus_grand:
            plus_grand = valeur    # mise a jour si on trouve mieux
    return plus_grand

1.2.3 Coût des opérations sur une liste

Le coût d'une opération mesure le nombre d'opérations élémentaires effectuées en fonction de la taille $n$ de la structure. Il s'exprime à l'aide de la notation $O$ .

Proposition 1.8Coût des opérations sur une liste Python

Pour une liste Python (implémentée par un tableau dynamique), de longueur $n$ :

accès ou modification à un indice donné : $O (1)$ ;
ajout en fin (append) : $O (1)$ en moyenne ;
insertion ou suppression en début ou au milieu : $O (n)$ , car il faut décaler les éléments suivants ;
recherche d'une valeur par parcours : $O (n)$ ;
connaître la longueur (len) : $O (1)$ .

Exemple 1.9Pourquoi l'insertion en début coûte

O (n)

Insérer une valeur en position $0$ d'une liste de $n$ éléments oblige à décaler tous les éléments d'un cran vers la droite pour libérer la première case : on effectue donc de l'ordre de $n$ déplacements. À l'inverse, append se contente d'écrire dans la première case libre disponible en fin de tableau, d'où un coût $O (1)$ .

1.3 Les piles (LIFO)

1.3.1 Le type abstrait pile

Définition 1.10Pile (stack)

Une pile est une structure linéaire dans laquelle on n'ajoute et ne retire des éléments que par une seule extrémité, appelée le sommet. Le dernier élément ajouté est le premier à être retiré : on parle de structure LIFO (Last In, First Out, « dernier entré, premier sorti »).

L'interface d'une pile comporte typiquement les opérations suivantes :

creer_pile() : créer une pile vide ;
est_vide(p) : indiquer si la pile est vide ;
empiler(p, x) (push) : ajouter x au sommet ;
depiler(p) (pop) : retirer et renvoyer l'élément du sommet ;
sommet(p) : consulter le sommet sans le retirer.

Exemple 1.11Une image mentale de la pile

On peut se représenter une pile comme une pile d'assiettes : on pose toujours une assiette sur le dessus, et on enlève toujours celle du dessus. Il est impossible de retirer une assiette au milieu sans passer par le sommet.

1.3.2 Applications des piles

Les piles sont omniprésentes en informatique :

gestion des appels de fonctions (la pile d'exécution) ;
fonction « annuler » (undo) dans les logiciels ;
navigation « page précédente » d'un navigateur ;
vérification du bon parenthésage d'une expression ;
évaluation d'expressions en notation postfixée.

1.3.3 Implémentations d'une pile en Python

Méthode : Implémentation d'une pile par une liste Python

On utilise une liste Python en convenant que le sommet est la fin de la liste. append joue alors le rôle de empiler et pop celui de depiler, tous deux en $O (1)$ .


def creer_pile():
    return []                 # une pile vide est une liste vide

def est_vide(p):
    return len(p) == 0

def empiler(p, x):
    p.append(x)               # ajout au sommet (fin de liste)

def depiler(p):
    return p.pop()            # retrait du sommet (fin de liste)

def sommet(p):
    return p[-1]              # consultation sans retrait

Méthode : Implémentation d'une pile par une classe

Une approche plus propre encapsule les données dans une classe : l'utilisateur ne manipule alors que les méthodes de l'interface, sans accéder directement à la liste interne.


class Pile:
    def __init__(self):
        self._contenu = []        # attribut interne, prive par convention

    def est_vide(self):
        return len(self._contenu) == 0

    def empiler(self, x):
        self._contenu.append(x)

    def depiler(self):
        if self.est_vide():
            raise IndexError("depiler sur une pile vide")
        return self._contenu.pop()

    def sommet(self):
        return self._contenu[-1]

    def taille(self):
        return len(self._contenu)

Proposition 1.12Coût des opérations sur une pile

Avec une implémentation par liste Python (sommet en fin), les opérations empiler, depiler, sommet et est_vide s'effectuent toutes en temps constant $O (1)$ .

1.4 Les files (FIFO)

1.4.1 Le type abstrait file

Définition 1.13File (queue)

Une file est une structure linéaire dans laquelle les éléments sont ajoutés à une extrémité (la queue) et retirés à l'autre extrémité (la tête). Le premier élément ajouté est le premier retiré : on parle de structure FIFO (First In, First Out, « premier entré, premier sorti »).

L'interface d'une file comporte typiquement :

creer_file() : créer une file vide ;
est_vide(f) : indiquer si la file est vide ;
enfiler(f, x) : ajouter x en queue ;
defiler(f) : retirer et renvoyer l'élément de tête.

Exemple 1.14Une image mentale de la file

Une file correspond exactement à une file d'attente à un guichet : la première personne arrivée est servie en premier, et toute nouvelle personne se place à la fin.

1.4.2 Applications des files

gestion des tâches en attente (impression, processus d'un système d'exploitation) ;
mise en mémoire tampon de données (buffer) ;
parcours en largeur d'un graphe ou d'un arbre ;
simulation de files d'attente.

1.4.3 Implémentations d'une file en Python

Méthode : Implémentation naïve d'une file par une liste

On peut enfiler en fin avec append et défiler en tête avec pop(0). C'est correct, mais pop(0) doit décaler tous les éléments restants : son coût est $O (n)$ .


def creer_file():
    return []

def est_vide(f):
    return len(f) == 0

def enfiler(f, x):
    f.append(x)               # ajout en queue : O(1)

def defiler(f):
    return f.pop(0)           # retrait en tete : O(n) (decalage)

Pour obtenir des opérations efficaces, on utilise plutôt une structure dédiée. Le module collections fournit deque, conçue pour ajouter et retirer aux deux extrémités en temps constant.

Méthode : Implémentation efficace d'une file par une classe


from collections import deque

class File:
    def __init__(self):
        self._contenu = deque()       # double-ended queue

    def est_vide(self):
        return len(self._contenu) == 0

    def enfiler(self, x):
        self._contenu.append(x)       # ajout en queue : O(1)

    def defiler(self):
        if self.est_vide():
            raise IndexError("defiler sur une file vide")
        return self._contenu.popleft()  # retrait en tete : O(1)

    def taille(self):
        return len(self._contenu)

◆Théorème 1.15Coût des opérations d'une file selon l'implémentation

Soit $n$ le nombre d'éléments d'une file.

Implémentation par liste Python (pop(0)) : enfiler en $O (1)$ , mais defiler en $O (n)$ .
Implémentation par deque : enfiler et defiler en $O (1)$ .

La deque est donc strictement préférable pour une file dont on retire fréquemment les éléments de tête.

Exemple 1.16Récapitulatif LIFO / FIFO

Si l'on insère successivement les valeurs $1, 2, 3$ :

dans une pile (LIFO), les dépiler donne $3, 2, 1$ ;
dans une file (FIFO), les défiler donne $1, 2, 3$ .

Continuer sur Adloun : animation, QCM, fiches, exercices