⌨ Spécialité NSI · Numérique et sciences informatiques Terminale Générale · Chapitre 2

Structures linéaires : listes chaînées, piles et files

Distinction interface / implémentation, listes chaînées (maillons, insertion en tête, parcours), piles (LIFO) et files (FIFO) : opérations, implémentations, applications (annulation, parenthésage, files d'attente).

1. Interface et implémentation

Définition

Une structure de données abstraite est définie par son interface (les opérations possibles et leur effet). Une implémentation réalise cette interface avec des outils du langage ; il peut en exister plusieurs, plus ou moins efficaces.

2. Listes chaînées

Définition

Une liste chaînée est une suite de maillons ; chaque maillon contient une valeur et une référence vers le maillon suivant (ou None pour le dernier). Ajouter en tête est immédiat ; accéder au $k$-ième élément demande de parcourir $k$ maillons.

Exemple · Implémentation

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(m):
    n = 0
    while m is not None:
        n = n + 1
        m = m.suivant
    return n

L = Maillon(1, Maillon(2, Maillon(3)))   # 1 -> 2 -> 3

3. Piles et files

ABCempilerdépiler (C)PILE (LIFO)ABCenfilerdéfiler (A)FILE (FIFO)
Une pile : dernier entré, premier sorti. Une file : premier entré, premier sorti.

Propriété · Interfaces

Pile (LIFO, last in, first out) : est_vide, empiler, depiler (renvoie le sommet), sommet. File (FIFO, first in, first out) : est_vide, enfiler, defiler. En Python, une liste fait une bonne pile (append, pop()) ; pour une file efficace, on utilise collections.deque ou deux piles.

Exemple · Applications

Pile : historique « précédent » d'un navigateur, annulation (Ctrl+Z), vérification du parenthésage, pile d'appels des fonctions. File : file d'impression, file d'attente de requêtes, parcours en largeur.

Activité · Vérifier le parenthésage

MatérielPython.
ConsigneÉcrire une fonction qui vérifie qu'une expression est bien parenthésée avec () et [].
Résultat
def bien_parenthese(s):
    pile = []
    paires = {")": "(", "]": "["}
    for c in s:
        if c in "([":
            pile.append(c)
        elif c in ")]":
            if not pile or pile.pop() != paires[c]:
                return False
    return pile == []
BilanChaque fermante doit correspondre à la dernière ouvrante non fermée : c'est exactement le comportement d'une pile.

⚠️ Une erreur dans ce cours ? Signalez-la

S'entraîner

Exercices corrigés

🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.

Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.

8

Liste chaînée

★☆☆

Que vaut L.suivant.valeur pour la liste L ci-dessous ?

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(m):
    n = 0
    while m is not None:
        n = n + 1
        m = m.suivant
    return n

L = Maillon(1, Maillon(2, Maillon(3)))   # 1 -> 2 -> 3
🔒 Correction réservée aux membres Créer un compte gratuit →
9

Longueur

★☆☆

Avec le code ci-dessous, que renvoie longueur(L) ?

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(m):
    n = 0
    while m is not None:
        n = n + 1
        m = m.suivant
    return n

L = Maillon(1, Maillon(2, Maillon(3)))   # 1 -> 2 -> 3
🔒 Correction réservée aux membres Créer un compte gratuit →
10

Ajout en tête

★★☆

Avec le code ci-dessous, comment ajouter $0$ en tête de la liste chaînée L ?

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(m):
    n = 0
    while m is not None:
        n = n + 1
        m = m.suivant
    return n

L = Maillon(1, Maillon(2, Maillon(3)))   # 1 -> 2 -> 3
🔒 Correction réservée aux membres Créer un compte gratuit →
11

Somme d'une liste chaînée

★★☆

Les listes chaînées sont construites avec la classe Maillon ci-dessous. Écrire une fonction somme(m) qui additionne les valeurs d'une liste chaînée.

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(m):
    n = 0
    while m is not None:
        n = n + 1
        m = m.suivant
    return n

L = Maillon(1, Maillon(2, Maillon(3)))   # 1 -> 2 -> 3
🔒 Correction réservée aux membres Créer un compte gratuit →
12

k-ième élément

★★☆

Les listes chaînées sont construites avec la classe Maillon ci-dessous. Écrire element(m, k) qui renvoie la valeur du $k$-ième maillon (à partir de $0$).

class Maillon:
    def __init__(self, valeur, suivant=None):
        self.valeur = valeur
        self.suivant = suivant

def longueur(m):
    n = 0
    while m is not None:
        n = n + 1
        m = m.suivant
    return n

L = Maillon(1, Maillon(2, Maillon(3)))   # 1 -> 2 -> 3
🔒 Correction réservée aux membres Créer un compte gratuit →
14

Parenthésage

★★☆

Que renvoie la fonction ci-dessous pour "([)]" ? pour "(())" ?

def bien_parenthese(s):
    pile = []
    paires = {")": "(", "]": "["}
    for c in s:
        if c in "([":
            pile.append(c)
        elif c in ")]":
            if not pile or pile.pop() != paires[c]:
                return False
    return pile == []
🔒 Correction réservée aux membres Créer un compte gratuit →
20

Vrai ou faux

★★☆

a) Dépiler une pile vide est une erreur. b) Une liste chaînée permet l'accès direct au milieu. c) Une interface peut avoir plusieurs implémentations.

🔒 Correction réservée aux membres Créer un compte gratuit →

Vérifier

Avez-vous bien compris ?

Répondez au quiz : la correction s'affiche immédiatement.