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.

🖨️ 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.

📋 Listes et tableaux

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.

# 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

# Classe Pile propre
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]

🚌 Files — FIFO

Une file (queue) suit le principe FIFO : First In, First Out (premier entré, premier sorti). Comme une file d'attente.

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'

# Classe File propre
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()

🗝️ 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

🔗 Listes chaînées

Dans une liste chaînée, chaque élément (nœud) contient une valeur et un pointeur vers le nœud suivant. Contrairement aux tableaux, les éléments ne sont pas contigus en mémoire.

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

🏋️ Exercices

def parentheses_ok(s):
    pile = []
    for c in s:
        if c == '(':
            pile.append(c)
        elif c == ')':
            if not pile:
                return False  # fermante sans ouvrante
            pile.pop()
    return len(pile) == 0  # vrai si tout est fermé

class FileAvecDeuxPiles:
    def __init__(self):
        self.entree = []   # pile pour enfiler
        self.sortie = []   # pile pour défiler

    def enfiler(self, x):
        self.entree.append(x)

    def defiler(self):
        if not self.sortie:  # si sortie vide, transvaser
            while self.entree:
                self.sortie.append(self.entree.pop())
        if not self.sortie:
            raise IndexError("file vide")
        return self.sortie.pop()

def frequences(texte):
    freq = {}
    for mot in texte.lower().split():
        freq[mot] = freq.get(mot, 0) + 1
    return freq

# Variante avec defaultdict
from collections import defaultdict
def frequences2(texte):
    freq = defaultdict(int)
    for mot in texte.lower().split():
        freq[mot] += 1
    return dict(freq)