S01 — Structures de données

🎯 Introduction

Les structures de données permettent d'organiser et de stocker les informations en mémoire. Le choix d'une structure adaptée est crucial pour l'efficacité d'un algorithme.

🎮 Cours ↔ TP2 — Piles et files

Observe ici les opérations, puis programme-les dans NSI Arcade : Bataille et PyLand pour FIFO, Hanoï pour LIFO. Les aides sont facultatives et les premières missions ne demandent ni classes ni récursion.

🖨️ Du chapitre S01 à l’objet réel : NSI Maker

Fabrique des disques en Python et OpenSCAD, puis utilise-les pour manipuler trois piles de Hanoï et le tri de crêpes de l’exercice 6. Une file FIFO interactive fait aussi le lien avec les activités sur les files.

🔁 Rappels

Nous avons vu l'année dernière comment étaient codées les données au sein d'un ordinateur, et nous avons utilisé des types simples et composés de Python. De nombreux algorithmes « classiques » manipulent des structures de données plus complexes que de simples nombres.

Les types simples

Un objet de type simple ne stocke qu'une donnée.

Les types construits

Les types construits permettent de stocker des collections de données.

Méthodes d'itération

On peut itérer sur une liste par les valeurs ou par les index ; sur un dictionnaire, par les clés, les valeurs, ou les deux à la fois.

# Itération sur les valeurs d'une liste
for val in ma_liste:
    print(val)

# Itération sur les index (on a aussi accès à la valeur)
for i in range(len(ma_liste)):
    val = ma_liste[i]
    print("indice:", i, "valeur:", val)

# Itération sur les clés d'un dictionnaire
for key in D:          # équivalent à : for key in D.keys():
    print(key)

# Itération sur les valeurs
for value in D.values():
    print(value)

# Itération sur les paires clé/valeur
for key, value in D.items():
    print(key, '=>', value)

📋 Listes et tableaux

Le type abstrait liste (au sens Lisp)

Le langage Lisp (John McCarthy, 1958 — Lisp signifie list processing) a introduit la notion de liste comme type abstrait : une liste L se décompose en sa tête (car, le dernier élément ajouté) et sa queue (cdr, le reste de la liste). Cinq opérations suffisent à la spécifier :

Exemple (les instructions s'enchaînent) :

L = vide()                          # L est vide
estVide(L)                            # renvoie True
L1 = cons(12, L)                     # L1 contient 12
estVide(L1)                           # renvoie False
L1 = cons(15, L1)                    # L1 contient 15 et 12
L1 = cons(1, cons(11, L1))            # L1 contient 1, 11, 15 et 12 (on peut enchaîner les cons)
car(L1)                                # renvoie 1 — L1 reste inchangée
L2 = cdr(L1)                           # L2 contient 11, 15 et 12 — L1 reste inchangée

On implémente facilement ce type abstrait en Python avec des tuples :

def vide(): return None
def estVide(L): return L is None
def cons(x, L): return (x, L)
def car(L): return L[0]
def cdr(L): return L[1]

En pratique : les listes Python (tableaux dynamiques)

En Python, le type list est un tableau dynamique : les éléments sont stockés de façon contiguë en mémoire, et Python gère automatiquement le redimensionnement.

# Création et opérations courantes
tab = [3, 1, 4, 1, 5]
tab.append(9)         # [3,1,4,1,5,9]
tab.insert(0, 0)      # [0,3,1,4,1,5,9] — O(n) !
tab.pop()             # retire 9, O(1)
tab.pop(0)            # retire 0, O(n) !

# Compréhension de liste
carres = [x**2 for x in range(5)]  # [0,1,4,9,16]
pairs  = [x for x in tab if x % 2 == 0]

📚 Piles — LIFO

Une pile (stack) suit le principe LIFO : Last In, First Out (dernier entré, premier sorti). Comme une pile d'assiettes : la seule assiette directement accessible est la dernière posée.

L'interface d'une pile se résume à quatre opérations : estVide(P), push(P, val) (empiler), pop(P) (dépiler — renvoie le sommet et le supprime) et taille(P).

Exemple — soit une pile P composée de 12, 14, 8, 7, 19 et 22 (le sommet est 22). Pour chaque ligne ci-dessous, on repart de la pile d'origine :

# Implémentation d'une pile avec une liste Python
pile = []

# Empiler (push)
pile.append('A')   # pile = ['A']
pile.append('B')   # pile = ['A','B']
pile.append('C')   # pile = ['A','B','C']

# Dépiler (pop) — retire le DERNIER élément
sommet = pile.pop()   # sommet = 'C', pile = ['A','B']

# Consulter sans dépiler (peek)
if pile:              # vérifier non-vide avant !
    sommet = pile[-1]  # 'B' sans modifier la pile

def compte_a_rebours(n):
    # Précondition : n est un entier positif ou nul.
    if n == 0:
        print("Départ !")
        return
    print(n)
    compte_a_rebours(n - 1)

compte_a_rebours(3)  # affiche 3, 2, 1, puis Départ !

Définir l’interface avec des fonctions

Dans les activités, push(P, x) correspond à empiler(P, x) et pop(P) à depiler(P). Le sommet est à droite dans notre liste Python.

def pileVide():
    return []

def estVide(P):
    return len(P) == 0

def empiler(P, valeur):
    P.append(valeur)

def depiler(P):
    # Précondition : P n'est pas vide.
    return P.pop()

def taille(P):
    return len(P)

P = pileVide()
empiler(P, 34)
empiler(P, 76)
if not estVide(P):
    a = depiler(P)  # a = 76 ; P = [34]

Exécute chaque exemple dans son propre fichier : le nom estVide sera aussi utilisé pour les listes chaînées, avec une représentation différente.

🚌 Files — FIFO

Une file (queue) suit le principe FIFO : First In, First Out (premier entré, premier sorti). Comme une file d'attente : on ajoute à une extrémité (enqueue, enfiler) et on retire à l'autre (dequeue, défiler).

L'interface d'une file : estVide(F), enqueue(F, val) (enfiler), dequeue(F) (défiler — renvoie l'élément le plus ancien et le supprime) et taille(F).

Exemple — soit une file F composée de 12, 14, 8, 7, 19 et 22, où 22 est le premier élément entré et 12 le dernier. Pour chaque ligne ci-dessous, on repart de la file d'origine :

from collections import deque

file = deque()          # file vide

# Enfiler (enqueue) — ajouter en queue
file.append('A')         # file = deque(['A'])
file.append('B')         # file = deque(['A','B'])

# Défiler (dequeue) — retirer en tête — O(1) !
premier = file.popleft() # premier = 'A'

Définir l’interface avec des fonctions

Dans cette représentation Python, la sortie (le plus ancien) est à gauche et l’entrée à droite. Le dessin précédent utilise l’orientation inverse : la règle FIFO reste la même.

from collections import deque

def fileVide():
    return deque()

def estVide(F):
    return len(F) == 0

def enqueue(F, valeur):
    F.append(valeur)

def dequeue(F):
    # Précondition : F n'est pas vide.
    return F.popleft()

def taille(F):
    return len(F)

F = fileVide()
enqueue(F, 67)
enqueue(F, 34)
if not estVide(F):
    a = dequeue(F)  # a = 67 ; F contient encore 34

Exécute chaque exemple dans son propre fichier : le nom estVide sera aussi utilisé pour les listes chaînées, avec une représentation différente.

🗝️ Dictionnaires

Un dictionnaire (table de hachage) associe des clés à des valeurs. Les clés doivent être hashables (immuables : str, int, tuple).

# Création
notes = {'Alice': 18, 'Bob': 14, 'Chloe': 16}

# Accès (KeyError si absent → utiliser get)
n = notes.get('David', 0)   # renvoie 0 par défaut

# Test d'appartenance
if 'Alice' in notes:
    print(notes['Alice'])      # 18

# Parcours
for nom, note in notes.items():
    print(f"{nom} : {note}")

# Compréhension de dictionnaire
maj = {k.upper(): v for k, v in notes.items()}

# setdefault / defaultdict
from collections import defaultdict
freq = defaultdict(int)
for c in "bonjour": freq[c] += 1

🔗 Type abstrait et représentation concrète

Les listes, les piles et les files vues plus haut sont des types abstraits : des « vues de l'esprit », indépendantes de tout support informatique. Les implémenter, c'est les traduire dans un langage compréhensible par un ordinateur — et il existe plusieurs façons concrètes de le faire, selon le langage.

Deux grandes familles de représentation :

• Tableau : une suite contiguë de cases mémoire. Simple et rapide en accès direct, mais de taille fixe : insérer un élément suppose de recréer un tableau plus grand et d'y recopier les données.
• Tableau dynamique : un tableau dont la taille peut varier, ce qui facilite l'insertion. Les « listes Python » sont des tableaux dynamiques — pas le type abstrait liste vu plus haut (encore ces fameux faux amis).
• Liste chaînée : chaque élément (nœud) occupe deux cases mémoire, une pour la valeur et une pour l'adresse de l'élément suivant. Les éléments ne sont pas contigus en mémoire, mais l'insertion y est très simple : il suffit de rediriger quelques pointeurs.

Une représentation avec des tuples, sans classes

Comme dans l’activité 6, une cellule est un couple (valeur, suite) ; None termine la chaîne. cons crée une nouvelle cellule sans modifier la suite existante. Il faut une liste non vide pour appeler car ou cdr.

def vide():
    return None

def estVide(L):
    return L is None

def cons(x, L):
    return (x, L)

def car(L):
    # Précondition : L n'est pas vide.
    return L[0]

def cdr(L):
    # Précondition : L n'est pas vide.
    return L[1]

L = cons(12, cons(5, cons(32, vide())))
courant = L
while not estVide(courant):
    print(car(courant))  # affiche 12, puis 5, puis 32
    courant = cdr(courant)

Exemple : (12, (5, (32, None))). Parcourir cette chaîne signifie suivre successivement les seconds éléments des couples. Une autre implémentation, avec des classes, sera étudiée après la POO.

📝 Activités

Neuf activités de prise en main, à faire dans l'ordre : elles s'appuient les unes sur les autres.

L = vide()
L = cons(12, cons(5, cons(32, L)))
a = car(L)
L1 = cdr(L)
L1 = cons(42, cons(23, L1))

L = vide()                                 # L devient une liste vide
L = cons(12, cons(5, cons(32, L)))       # L devient [12, 5, 32]
a = car(L)                                # a = 12, le premier élément de L
L1 = cdr(L)                               # L1 devient [5, 32]
L1 = cons(42, cons(23, L1))               # L1 devient [42, 23, 5, 32]

push(P, 34)
push(P, 76)
push(P, 43)
a = pop(P)
push(P, 42)
b = taille(P)

push(P, 34)   # P devient [34]
push(P, 76)   # P devient [76, 34]
push(P, 43)   # P devient [43, 76, 34]
a = pop(P)     # a = 43, P devient [76, 34]
push(P, 42)   # P devient [42, 76, 34]
b = taille(P)  # b = 3

enqueue(F, 67)
enqueue(F, 34)
enqueue(F, 78)
a = dequeue(F)
enqueue(F, 23)
b = taille(F)

enqueue(F, 67)  # F devient [67]
enqueue(F, 34)  # F devient [67, 34]
enqueue(F, 78)  # F devient [67, 34, 78]
a = dequeue(F)   # a = 67, F devient [34, 78]
enqueue(F, 23)  # F devient [34, 78, 23]
b = taille(F)   # b = 3

def vide(): return None
def estVide(L): return L is None
def cons(x, L): return (x, L)
def car(L): return L[0]
def cdr(L): return L[1]

P = []
P.append(34)
P.append(76)
P.append(43)
a = P.pop()   # a = 43
P.append(42)
b = len(P)   # b = 3

from collections import deque
F = deque()
F.append(67)
F.append(34)
F.append(78)
a = F.popleft()   # a = 67
F.append(23)
b = len(F)       # b = 3

# Avec len() — le plus simple
def taille(L): return len(L)

# Sans len(), sur le type abstrait liste (cons/cdr)
def taille(L):
    compteur = 0
    while L is not None:
        compteur += 1
        L = cdr(L)   # passe à l'élément suivant
    return compteur

def taille_pile(P):
    compteur = 0
    temporaire = []
    while P:
        compteur += 1
        element = P.pop()
        temporaire.append(element)
    while temporaire:
        P.append(temporaire.pop())   # restaure l'ordre initial
    return compteur

def taille_file(F):   # F est une deque
    compteur = 0
    temporaire = deque()
    while F:
        compteur += 1
        element = F.pop()
        temporaire.append(element)
    while temporaire:
        F.append(temporaire.pop())   # restaure l'ordre initial
    return compteur

🏋️ Exercices

Six exercices, du plus simple au sujet 0 du bac NSI (tri d'une pile de crêpes).

L = vide()
L = cons(2, cons(15, cons(23, L)))
L1 = cdr(L)
a = car(L1)
L1 = cons(4, cons(3, L1))

push(P, 4)
push(P, 7)
a = pop(P)
b = taille(P)
c = pop(P)
push(P, 3)
push(P, 2)
d = taille(P)

enqueue(F, 6)
enqueue(F, 3)
a = dequeue(F)
enqueue(F, 9)
b = taille(F)
enqueue(F, 17)
c = dequeue(F)
enqueue(F, 2)
d = taille(F)

pile = []
tab = [5, 8, 6, 1, 3, 7]
pile.append(5)
pile.append(10)
pile.append(8)
pile.append(15)
for i in tab:
    if i > 5:
        pile.pop()

from collections import deque
file = deque([])
tab = [2, 78, 6, 89, 3, 17]
file.append(5)
file.append(10)
file.append(8)
file.append(15)
for i in tab:
    if i > 50:
        file.popleft()

Q = pileVide()
while not estVide(P):
    empiler(Q, depiler(P))

def hauteur_pile(P):
    Q = pileVide()
    n = 0
    while not(estVide(P)):
        ???
        x = depiler(P)
        empiler(Q, x)
    while not(estVide(Q)):
        ???
        empiler(P, x)
    return ???

def hauteur_pile(P):
    Q = pileVide()
    n = 0
    while not(estVide(P)):
        n += 1                  # incrémente le compteur
        x = depiler(P)
        empiler(Q, x)
    while not(estVide(Q)):
        x = depiler(Q)              # restaure P
        empiler(P, x)
    return n

def max_pile(P, i):
    Q = pileVide()
    max_value = None
    position = 1
    max_position = 1
    for j in range(i):
        x = depiler(P)
        empiler(Q, x)
        if max_value is None or x > max_value:
            max_value = x
            max_position = position
        position += 1
    while not estVide(Q):
        empiler(P, depiler(Q))
    return max_position

def retourner(P, j):
    Q = pileVide()
    R = pileVide()
    for _ in range(j):
        empiler(Q, depiler(P))
    while not estVide(Q):
        empiler(R, depiler(Q))
    while not estVide(R):
        empiler(P, depiler(R))

def tri_crepes(P):
    n = hauteur_pile(P)
    for i in range(n, 1, -1):
        max_pos = max_pile(P, i)
        retourner(P, max_pos)   # amène la plus grande crêpe restante au sommet
        retourner(P, i)          # puis tout en bas des i premières

📦 Partie 2 — À lire après avoir étudié la POO

Cette partie n’est pas à travailler au début de l’année. Termine d’abord la partie sans classes. Reviens ici après le chapitre sur la programmation orientée objet, lorsque tu connais classe, instance, attribut, méthode, self et __init__.

def retirer(file):
    if not file:
        raise ValueError("La file est vide")
    return file.pop(0)

try:
    retirer([])
except ValueError as erreur:
    print(erreur)  # affiche La file est vide

class Pile:
    def __init__(self): self._data = []
    def est_vide(self): return len(self._data) == 0
    def empiler(self, x): self._data.append(x)
    def depiler(self):
        if self.est_vide(): raise IndexError("pile vide")
        return self._data.pop()
    def sommet(self): return self._data[-1]

from collections import deque

class File:
    def __init__(self): self._data = deque()
    def est_vide(self): return len(self._data) == 0
    def enfiler(self, x): self._data.append(x)
    def defiler(self):
        if self.est_vide(): raise IndexError("file vide")
        return self._data.popleft()

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

class ListeChainee:
    def __init__(self):
        self.tete = None

    def inserer_tete(self, val):         # O(1)
        n = Noeud(val)
        n.suivant = self.tete
        self.tete = n

    def parcourir(self):
        courant = self.tete
        while courant is not None:
            print(courant.valeur)
            courant = courant.suivant