madamasterclass.com
Connaître les structures de données
Dans ce cours, nous allons découvrir les structures de données fondamentales en informatique. Nous explorerons les notions de pile et de file, ainsi qu'une introduction aux graphes et à leurs parcours. Ces concepts sont essentiels pour organiser et manipuler efficacement les données dans nos programmes.
Les structures de données sont des façons d'organiser et de stocker les informations en mémoire pour permettre un accès et une manipulation efficaces. Chaque structure a ses propres règles et ses avantages selon le contexte d'utilisation.
🥞 Exemple d'utilisation d'une pile : Pile vide : [] push(5) → [5] push(3) → [5, 3] ← 3 est au sommet push(8) → [5, 3, 8] ← 8 est au sommet pop() → retourne 8, pile devient [5, 3] pop() → retourne 3, pile devient [5] Applications courantes : • Fonction "Annuler" (Ctrl+Z) dans les logiciels • Gestion des appels de fonctions en programmation • Vérification des parenthèses équilibrées
🚶♂️ Exemple d'utilisation d'une file : File vide : [] enqueue(A) → [A] (A arrive en premier) enqueue(B) → [A, B] (B arrive après A) enqueue(C) → [A, B, C] (C arrive en dernier) dequeue() → retourne A, file devient [B, C] dequeue() → retourne B, file devient [C] Applications courantes : • Files d'attente d'impression • Gestion des tâches dans un système d'exploitation • Traitement des requêtes sur un serveur web
| Critère | Pile (Stack) | File (Queue) |
|---|---|---|
| Principe | LIFO (Last In, First Out) | FIFO (First In, First Out) |
| Insertion | Au sommet (push) | À la fin (enqueue) |
| Suppression | Du sommet (pop) | Du début (dequeue) |
| Analogie | Pile d'assiettes | File d'attente |
Éducation
🗺️ Exemple simple de graphe :
A ---- B
| |
| |
C ---- D
Sommets : {A, B, C, D}
Arêtes : {A-B, A-C, B-D, C-D}
On peut représenter ce graphe par :
• Liste d'adjacence : A:[B,C], B:[A,D], C:[A,D], D:[B,C]
• Matrice d'adjacence : tableau 4×4 avec 1 si connexion, 0 sinon
| Type de parcours | Structure utilisée | Principe |
|---|---|---|
| Parcours en largeur (BFS) | File (Queue) | Explorer niveau par niveau |
| Parcours en profondeur (DFS) | Pile (Stack) | Explorer le plus loin possible avant de revenir |
🔍 Parcours en largeur (BFS) avec une file :
Graphe : A connecté à B et C, B connecté à D
A
/ \
B C
|
D
1. Commencer par A, l'ajouter à la file : [A]
2. Défiler A, visiter ses voisins B,C : file=[B,C], visités={A}
3. Défiler B, visiter son voisin D : file=[C,D], visités={A,B}
4. Défiler C (pas de nouveaux voisins) : file=[D], visités={A,B,C}
5. Défiler D (pas de nouveaux voisins) : file=[], visités={A,B,C,D}
Ordre de visite : A → B → C → D (niveau par niveau)
| Structure | Applications courantes |
|---|---|
| Pile | Ctrl+Z, navigation web (bouton Précédent), vérification parenthèses |
| File | Impression, gestion processus, serveurs web |
| Graphes | GPS (plus court chemin), réseaux sociaux, moteurs de recherche |
Les structures de données sont les fondations de l'informatique moderne. La pile et la file, avec leurs principes simples mais puissants, permettent de résoudre de nombreux problèmes. Les graphes, omniprésents dans notre monde connecté, nécessitent des algorithmes de parcours efficaces qui s'appuient justement sur ces structures fondamentales. Comprendre ces concepts vous donnera les clés pour analyser et concevoir des solutions informatiques élégantes.
Implémentez une pile simple en Python en utilisant une liste.
1. Créez une pile vide
2. Ajoutez (push) les éléments 10, 20, 30 dans la pile
3. Retirez (pop) un élément et affichez-le
4. Affichez le contenu restant de la pile
# Solution :
# 1. Création d'une pile vide
pile = []
# 2. Ajout d'éléments (push)
pile.append(10) # [10]
pile.append(20) # [10, 20]
pile.append(30) # [10, 20, 30]
# 3. Retrait d'un élément (pop)
element_retire = pile.pop() # retire 30
print(f"Élément retiré : {element_retire}") # Affiche 30
# 4. Contenu restant
print(f"Pile restante : {pile}") # [10, 20]
# Note : Le dernier élément ajouté (30) est le premier retiré (LIFO)
Implémentez une file simple en Python en utilisant une liste.
1. Créez une file vide
2. Ajoutez (enqueue) les éléments 'A', 'B', 'C' dans la file
3. Retirez (dequeue) deux éléments et affichez-les
4. Vérifiez si la file est vide
# Solution :
# 1. Création d'une file vide
file = []
# 2. Ajout d'éléments (enqueue) - ajout à la fin
file.append('A') # ['A']
file.append('B') # ['A', 'B']
file.append('C') # ['A', 'B', 'C']
# 3. Retrait d'éléments (dequeue) - retrait du début
premier = file.pop(0) # retire 'A'
deuxieme = file.pop(0) # retire 'B'
print(f"Éléments retirés : {premier}, {deuxieme}")
# 4. Vérification si vide
print(f"File restante : {file}") # ['C']
print(f"File vide ? {len(file) == 0}") # False
# Note : Le premier élément ajouté (A) est le premier retiré (FIFO)
Vérifiez si une expression avec parenthèses est équilibrée en utilisant une pile.
Testez les expressions suivantes :
1. "(()())" - équilibrée
2. "(()" - non équilibrée
3. ")(" - non équilibrée
4. "" - équilibrée (vide)
# Solution :
def parentheses_equilibrees(expression):
pile = []
for caractere in expression:
if caractere == '(':
pile.append(caractere) # Push parenthèse ouvrante
elif caractere == ')':
if len(pile) == 0: # Pas de parenthèse ouvrante correspondante
return False
pile.pop() # Pop parenthèse ouvrante
return len(pile) == 0 # Pile vide = équilibrée
# Tests
expressions = ["(()())", "(()", ")(", ""]
for expr in expressions:
resultat = parentheses_equilibrees(expr)
print(f"'{expr}' est équilibrée : {resultat}")
# Résultats :
# '(()())' est équilibrée : True
# '(()' est équilibrée : False
# ')(' est équilibrée : False
# '' est équilibrée : True
Représentez un graphe simple et effectuez un parcours en largeur (BFS).
Graphe : A connecté à B et C, B connecté à D, C connecté à E
1. Représentez le graphe avec un dictionnaire
2. Implémentez l'algorithme BFS en partant de A
3. Affichez l'ordre de visite des sommets
# Solution :
from collections import deque
# 1. Représentation du graphe (liste d'adjacence)
graphe = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B'],
'E': ['C']
}
# 2. Algorithme BFS
def bfs(graphe, sommet_depart):
visites = set() # Sommets déjà visités
file = deque([sommet_depart]) # File pour BFS
ordre_visite = []
while file:
sommet_actuel = file.popleft() # Dequeue
if sommet_actuel not in visites:
visites.add(sommet_actuel)
ordre_visite.append(sommet_actuel)
# Ajouter les voisins non visités à la file
for voisin in graphe[sommet_actuel]:
if voisin not in visites:
file.append(voisin) # Enqueue
return ordre_visite
# 3. Test du parcours
ordre = bfs(graphe, 'A')
print(f"Ordre de visite BFS : {ordre}") # ['A', 'B', 'C', 'D', 'E']
Implémentez un système de gestion de tâches utilisant une file de priorité.
1. Créez une classe Task avec nom et priorité (1=haute, 5=basse)
2. Implémentez une file de priorité qui traite les tâches par ordre de priorité
3. Ajoutez les tâches : ("Email", 2), ("Réunion", 1), ("Pause", 5), ("Code", 3)
4. Traitez toutes les tâches dans l'ordre de priorité
# Solution :
import heapq
# 1. Classe Task
class Task:
def __init__(self, nom, priorite):
self.nom = nom
self.priorite = priorite
def __lt__(self, other):
return self.priorite < other.priorite # Pour la comparaison dans heapq
def __repr__(self):
return f"Task('{self.nom}', {self.priorite})"
# 2. File de priorité
class FilePriorite:
def __init__(self):
self.heap = []
def ajouter(self, tache):
heapq.heappush(self.heap, tache)
def traiter(self):
if self.heap:
return heapq.heappop(self.heap)
return None
def est_vide(self):
return len(self.heap) == 0
# 3. Ajout des tâches
file_taches = FilePriorite()
taches = [
Task("Email", 2),
Task("Réunion", 1),
Task("Pause", 5),
Task("Code", 3)
]
for tache in taches:
file_taches.ajouter(tache)
# 4. Traitement par ordre de priorité
print("Traitement des tâches par priorité :")
while not file_taches.est_vide():
tache = file_taches.traiter()
print(f"Traitement : {tache.nom} (priorité: {tache.priorite})")
# Ordre de traitement : Réunion(1), Email(2), Code(3), Pause(5)
Implémentez un ensemble (set) en Python avec des opérations de base.
1. Créez un ensemble vide
2. Ajoutez les éléments 5, 10, 15 à l'ensemble
3. Supprimez l'élément 10
4. Vérifiez si 15 est présent dans l'ensemble
# Solution :
# 1. Création d'un ensemble vide
mon_ensemble = set()
# 2. Ajout d'éléments
mon_ensemble.add(5)
mon_ensemble.add(10)
mon_ensemble.add(15)
# 3. Suppression d'un élément
mon_ensemble.remove(10)
# 4. Vérification de présence
print(f"15 est présent : {15 in mon_ensemble}") # True
# Affichage final
print(f"Ensemble final : {mon_ensemble}") # {5, 15}
Implémentez un dictionnaire pour stocker des informations sur des étudiants.
1. Créez un dictionnaire vide
2. Ajoutez trois étudiants avec leur note (clé=nom, valeur=note)
3. Modifiez la note d'un étudiant
4. Affichez tous les noms d'étudiants et leurs notes
# Solution :
# 1. Création d'un dictionnaire vide
etudiants = {}
# 2. Ajout d'étudiants
etudiants["Alice"] = 15
etudiants["Bob"] = 12
etudiants["Claire"] = 18
# 3. Modification d'une note
etudiants["Bob"] = 14
# 4. Affichage des données
for nom, note in etudiants.items():
print(f"{nom} : {note}/20")
# Résultat :
# Alice : 15/20
# Bob : 14/20
# Claire : 18/20
Implémentez une liste chaînée simple en Python.
1. Créez une classe Node avec valeur et suivant
2. Créez une classe LinkedList avec tête
3. Implémentez une méthode pour ajouter en tête
4. Implémentez une méthode pour afficher la liste
# Solution :
class Node:
def __init__(self, valeur):
self.valeur = valeur
self.suivant = None
class LinkedList:
def __init__(self):
self.tete = None
def ajouter_tete(self, valeur):
nouveau_noeud = Node(valeur)
nouveau_noeud.suivant = self.tete
self.tete = nouveau_noeud
def afficher(self):
noeud_actuel = self.tete
while noeud_actuel:
print(noeud_actuel.valeur, end=" -> ")
noeud_actuel = noeud_actuel.suivant
print("None")
# Test
liste = LinkedList()
liste.ajouter_tete(3)
liste.ajouter_tete(2)
liste.ajouter_tete(1)
liste.afficher() # 1 -> 2 -> 3 -> None
Implémentez un arbre binaire et un parcours en profondeur (DFS).
1. Créez une classe Node avec valeur, gauche et droit
2. Construisez l'arbre suivant :
1
/ \
2 3
/ \ /
4 5 6
3. Implémentez le parcours pré-ordre (racine, gauche, droit)
# Solution :
class Node:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droit = None
def dfs_preordre(noeud):
if noeud:
print(noeud.valeur, end=" ")
dfs_preordre(noeud.gauche)
dfs_preordre(noeud.droit)
# Construction de l'arbre
racine = Node(1)
racine.gauche = Node(2)
racine.droit = Node(3)
racine.gauche.gauche = Node(4)
racine.gauche.droit = Node(5)
racine.droit.gauche = Node(6)
# Parcours pré-ordre
print("Parcours pré-ordre : ", end="")
dfs_preordre(racine) # 1 2 4 5 3 6
Implémentez une table de hachage (hashmap) en Python.
1. Créez une classe HashMap avec taille fixe
2. Implémentez une fonction de hachage simple (par exemple, modulo)
3. Implémentez les méthodes put(clé, valeur) et get(clé)
4. Testez avec quelques insertions et récupérations
# Solution :
class HashMap:
def __init__(self, taille=10):
self.taille = taille
self.table = [[] for _ in range(taille)]
def _hachage(self, cle):
return hash(cle) % self.taille
def put(self, cle, valeur):
index = self._hachage(cle)
for i, (k, v) in enumerate(self.table[index]):
if k == cle:
self.table[index][i] = (cle, valeur)
return
self.table[index].append((cle, valeur))
def get(self, cle):
index = self._hachage(cle)
for (k, v) in self.table[index]:
if k == cle:
return v
return None
# Test
hm = HashMap()
hm.put("a", 1)
hm.put("b", 2)
hm.put("c", 3)
print(hm.get("a")) # 1
print(hm.get("b")) # 2
print(hm.get("x")) # None
Explorez comment l'art et la philosophie s'entrelacent pour questionner notre perception de la réalité et de l'esthétique.
Read more.Plongez dans les débats philosophiques sur la liberté, ses implications éthiques et les défis contemporains qui l'entourent.
Read more.Découvrez les différentes approches philosophiques de la vérité et comment elles influencent notre compréhension du monde.
Read more.
