Structures de données

📊 Chapitre : Structures linéaires

Les structures linéaires sont des structures de données dans lesquelles les éléments sont organisés les uns à la suite des autres. Nous étudions ici :

• les piles,
• les files,
• les dictionnaires.

1️⃣ La pile

Une pile fonctionne selon le principe : LIFO — Last In, First Out (dernier entré, premier sorti).

• On ajoute un élément au sommet.
• On retire toujours l’élément du sommet.

• empiler (push)
• dépiler (pop)
• est_vide

Applications :

• Gestion des appels de fonctions (pile d’exécution).
• Annuler / Rétablir.
• Parcours en profondeur (DFS).

2️⃣ La file

Une file fonctionne selon le principe : FIFO — First In, First Out (premier entré, premier sorti).

• On entre par l’arrière.
• On sort par l’avant.

• enfiler (enqueue)
• défiler (dequeue)
• est_vide

Applications :

• Gestion des impressions.
• Ordonnancement des tâches.
• Parcours en largeur (BFS).

3️⃣ Les dictionnaires

Un dictionnaire associe une clé à une valeur. Contrairement aux listes, les éléments ne sont pas repérés par un indice, mais par une clé.

notes = {
    "Alice": 15,
    "Bob": 12,
    "Charlie": 18
}

Accès à une valeur : notes["Alice"] → 15

Opérations courantes :

• notes["David"] = 14 → ajoute ce nouvel élément (⚠️ pas de append dans un dictionnaire!)
• "Alice" in notes → True

🔎 Recherche : liste vs dictionnaire

Recherche dans une liste

liste = [4, 7, 12, 18]

def recherche_liste(valeur, L):
    for element in L:
        if element == valeur:
            return True
    return False

# Exemple d'appel
print(recherche_liste(12, liste))  # True
print(recherche_liste(5, liste))   # False

Recherche séquentielle → complexité \( O(n) \).

Recherche dans un dictionnaire

notes = {"Alice": 15, "Bob": 12, "Charlie": 18}

def recherche_valeur(valeur, dico):
    for v in dico.values():
        if v == valeur:
            return True
    return False

# Exemple d'appel
print(recherche_valeur(12, notes))   # True
print(recherche_valeur(20, notes))   # False

• dico.values() permet de parcourir toutes les valeurs du dictionnaire.
• On compare chaque valeur à celle recherchée.
• Si on la trouve → True
• Sinon → False

Parcourir les clés et les valeurs:

notes = {"Alice": 15, "Bob": 12, "Charlie": 18}

def afficher_dictionnaire(dico):
    for cle, valeur in dico.items():
        print(cle, ":", valeur)

# Exemple d'appel
afficher_dictionnaire(notes)

Résultat :

Alice : 15
Bob : 12
Charlie : 18

Trois parcours possibles:

• dico.keys() → parcours des clés
• dico.values() → parcours des valeurs
• dico.items() → parcours clé + valeur

🔗 À voir: cet exercice sujet zéro – 2024. Il porte sur les listes, les dictionnaires et la programmation de base en Python.