Exercices - Structures de données¶
Interface et POO¶
Exercice 1 - Classe Fraction¶
Écrire une classe Fraction avec :
- un constructeur prenant un numérateur et un dénominateur ;
- une méthode
simplifier()qui simplifie la fraction (utiliser le PGCD) ; - les méthodes
__str__,__add__et__eq__.
Solution
from math import gcd
class Fraction:
def __init__(self, num, den):
assert den != 0, "Dénominateur nul"
d = gcd(abs(num), abs(den))
self.num = num // d
self.den = den // d
def __str__(self):
if self.den == 1:
return str(self.num)
return f"{self.num}/{self.den}"
def __add__(self, autre):
num = self.num * autre.den + autre.num * self.den
den = self.den * autre.den
return Fraction(num, den)
def __eq__(self, autre):
return self.num == autre.num and self.den == autre.den
f1 = Fraction(2, 4)
print(f1) # 1/2
f2 = Fraction(1, 3)
print(f1 + f2) # 5/6
print(Fraction(3, 6) == Fraction(1, 2)) # True
Structures linéaires¶
Exercice 2 - Pile : vérification de parenthèses¶
Écrire une fonction parentheses_valides(expression) qui vérifie si les parenthèses, crochets et accolades d'une expression sont correctement équilibrés, en utilisant une pile.
Exemples :
"(3 + [5 - 2]) * {1 + 1}"→True"(3 + [5)"→False(crochet fermé par une parenthèse)"3 + 5) * 2"→False
Solution
def parentheses_valides(expression):
pile = []
correspondance = {')': '(', ']': '[', '}': '{'}
for c in expression:
if c in "([{":
pile.append(c)
elif c in ")]}":
if len(pile) == 0 or pile[-1] != correspondance[c]:
return False
pile.pop()
return len(pile) == 0
print(parentheses_valides("(3 + [5 - 2]) * {1 + 1}")) # True
print(parentheses_valides("(3 + [5)")) # False
print(parentheses_valides("3 + 5) * 2")) # False
Exercice 3 - Pile : notation polonaise inversée¶
En notation polonaise inversée (NPI), les opérateurs sont placés après leurs opérandes :
3 4 +signifie3 + 4 = 73 4 + 2 *signifie(3 + 4) * 2 = 14
Écrire une fonction evaluer_npi(expression) qui évalue une expression en NPI en utilisant une pile.
Solution
def evaluer_npi(expression):
pile = []
for token in expression.split():
if token in "+-*/":
b = pile.pop()
a = pile.pop()
if token == '+': pile.append(a + b)
elif token == '-': pile.append(a - b)
elif token == '*': pile.append(a * b)
elif token == '/': pile.append(a / b)
else:
pile.append(float(token))
return pile[0]
print(evaluer_npi("3 4 +")) # 7.0
print(evaluer_npi("3 4 + 2 *")) # 14.0
print(evaluer_npi("5 1 2 + 4 * + 3 -")) # 14.0
Exercice 4 - File : simulation d'une file d'attente¶
Écrire une classe FileAttente avec les méthodes arrivee(nom), service(), attente() et afficher(). Simuler : Alice arrive, Bob arrive, Alice est servie, Clara arrive, Bob est servi.
Solution
class FileAttente:
def __init__(self):
self.personnes = []
def arrivee(self, nom):
self.personnes.append(nom)
def service(self):
if len(self.personnes) == 0:
return None
return self.personnes.pop(0)
def attente(self):
return len(self.personnes)
def afficher(self):
if len(self.personnes) == 0:
print("File vide")
else:
print(" ← ".join(self.personnes))
f = FileAttente()
f.arrivee("Alice")
f.arrivee("Bob")
f.afficher() # Alice ← Bob
print(f.service()) # Alice
f.arrivee("Clara")
f.afficher() # Bob ← Clara
print(f.service()) # Bob
Exercice 5 - Liste chaînée : opérations¶
Compléter la classe ListeChainee avec :
a. element(i) : renvoie la valeur à l'indice i.
b. supprimer_en_tete() : supprime le premier maillon.
c. inserer_apres(valeur, nouvelle_valeur) : insère un maillon après le premier maillon contenant valeur.
Solution
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeChainee:
def __init__(self):
self.tete = None
def ajouter_en_tete(self, valeur):
self.tete = Maillon(valeur, self.tete)
def element(self, i):
courant = self.tete
for _ in range(i):
courant = courant.suivant
return courant.valeur
def supprimer_en_tete(self):
assert self.tete is not None, "Liste vide"
valeur = self.tete.valeur
self.tete = self.tete.suivant
return valeur
def inserer_apres(self, valeur, nouvelle_valeur):
courant = self.tete
while courant is not None:
if courant.valeur == valeur:
nouveau = Maillon(nouvelle_valeur, courant.suivant)
courant.suivant = nouveau
return
courant = courant.suivant
lst = ListeChainee()
for v in [30, 20, 10]:
lst.ajouter_en_tete(v)
print(lst.element(0)) # 10
print(lst.element(2)) # 30
lst.inserer_apres(20, 25)
print(lst.element(2)) # 25
Arbres¶
Exercice 6 - Mesures d'un arbre binaire¶
On considère l'arbre binaire suivant :
a. Donner la racine, les feuilles et les nœuds internes.
b. Quelle est la taille ? La hauteur ?
c. Quelle est la profondeur du nœud 7 ? Du nœud 18 ?
d. Construire cet arbre en Python et vérifier avec les fonctions taille() et hauteur().
Solution
a. Racine : 12. Feuilles : 3, 7, 25. Nœuds internes : 12, 6, 18, 8.
b. Taille = 7. Hauteur = 3 (chemin 12 → 6 → 8 → 7).
c. Profondeur de 7 : 3 (3 arêtes). Profondeur de 18 : 1.
d.
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def taille(a):
if a is None: return 0
return 1 + taille(a.gauche) + taille(a.droit)
def hauteur(a):
if a is None: return -1
return 1 + max(hauteur(a.gauche), hauteur(a.droit))
arbre = Noeud(12,
Noeud(6, Noeud(3), Noeud(8, Noeud(7))),
Noeud(18, None, Noeud(25))
)
print(taille(arbre)) # 7
print(hauteur(arbre)) # 3
Graphes¶
Exercice 7 - Modélisation¶
Modéliser les situations suivantes sous forme de graphes (orienté ou non, sommets, arêtes/arcs, liste d'adjacence Python).
a. Un groupe de 5 amis : Alice, Bob, Clara, David, Emma. Alice est amie avec Bob et Clara. Bob est ami avec David. Clara est amie avec Emma et David.
b. Un réseau de pages web : la page A contient un lien vers B et C. La page B contient un lien vers A. La page C contient un lien vers B.
Solution
a. Graphe non orienté :
amis = {
"Alice": ["Bob", "Clara"],
"Bob": ["Alice", "David"],
"Clara": ["Alice", "Emma", "David"],
"David": ["Bob", "Clara"],
"Emma": ["Clara"]
}
b. Graphe orienté :
Exercice 8 - Matrice d'adjacence¶
On considère le graphe : A-B, A-C, B-C, B-D, C-D.
a. Écrire la matrice d'adjacence.
b. Écrire une fonction nb_aretes(matrice) qui calcule le nombre d'arêtes.
c. Écrire une fonction degre(matrice, sommet) qui renvoie le degré d'un sommet.
Solution
a.
b. et c.
matrice = [[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]]
def nb_aretes(matrice):
total = 0
for i in range(len(matrice)):
for j in range(len(matrice)):
total += matrice[i][j]
return total // 2
def degre(matrice, sommet):
return sum(matrice[sommet])
print(nb_aretes(matrice)) # 5
print(degre(matrice, 1)) # 3 (B)
Exercice 9 - Choix de structure¶
Pour chaque situation, indiquer la structure la plus adaptée et justifier.
a. Historique des pages visitées (bouton « retour »).
b. File d'impression.
c. Arbre généalogique.
d. Plan de métro.
e. Annuaire téléphonique.
Solution
a. Pile (LIFO) : le retour va à la dernière page, au sommet de la pile.
b. File (FIFO) : les documents sont traités dans l'ordre d'envoi.
c. Arbre : structure hiérarchique (parents → enfants).
d. Graphe non orienté : les stations sont les sommets, les liaisons les arêtes. Il y a des cycles.
e. Dictionnaire : clé = nom, valeur = numéro. Accès rapide.
Activités¶
🧪 Activité 1 - Deux implémentations d'une pile¶
Implémenter la même interface de pile de deux manières différentes : avec un tableau Python (list) et avec une liste chaînée. Vérifier qu'elles se comportent de manière identique sur un même scénario de test.
Solution
class Maillon:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class PileTableau:
def __init__(self):
self.elements = []
def empiler(self, x):
self.elements.append(x)
def depiler(self):
return self.elements.pop()
def est_vide(self):
return len(self.elements) == 0
def sommet(self):
return self.elements[-1]
class PileChainee:
def __init__(self):
self.tete = None
def empiler(self, x):
self.tete = Maillon(x, self.tete)
def depiler(self):
val = self.tete.valeur
self.tete = self.tete.suivant
return val
def est_vide(self):
return self.tete is None
def sommet(self):
return self.tete.valeur
def tester_pile(pile, nom):
print(f"--- Test {nom} ---")
pile.empiler(10)
pile.empiler(20)
pile.empiler(30)
print(f"Sommet : {pile.sommet()}")
print(f"Dépiler : {pile.depiler()}")
print(f"Dépiler : {pile.depiler()}")
print(f"Vide ? {pile.est_vide()}")
print(f"Dépiler : {pile.depiler()}")
print(f"Vide ? {pile.est_vide()}")
tester_pile(PileTableau(), "PileTableau")
tester_pile(PileChainee(), "PileChainee")
🧪 Activité 2 - Convertir un graphe¶
Écrire un programme qui :
- Construit un graphe non orienté (au choix : réseau d'amis, plan simplifié) en liste d'adjacence ;
- Le convertit en matrice d'adjacence ;
- Affiche la matrice formatée ;
- Reconvertit la matrice en liste d'adjacence ;
- Vérifie que le résultat est identique au graphe original.
Solution
def liste_vers_matrice(graphe, sommets):
n = len(sommets)
index = {s: i for i, s in enumerate(sommets)}
matrice = [[0] * n for _ in range(n)]
for s in graphe:
for v in graphe[s]:
matrice[index[s]][index[v]] = 1
return matrice
def matrice_vers_liste(matrice, sommets):
graphe = {}
for i in range(len(sommets)):
graphe[sommets[i]] = [sommets[j]
for j in range(len(sommets)) if matrice[i][j] == 1]
return graphe
def afficher_matrice(matrice, sommets):
print(" " + " ".join(sommets))
for i, s in enumerate(sommets):
print(f"{s} {matrice[i]}")
graphe = {
"Paris": ["Lyon", "Lille"],
"Lyon": ["Paris", "Marseille"],
"Lille": ["Paris", "Bruxelles"],
"Marseille": ["Lyon"],
"Bruxelles": ["Lille"]
}
sommets = list(graphe.keys())
mat = liste_vers_matrice(graphe, sommets)
afficher_matrice(mat, sommets)
graphe2 = matrice_vers_liste(mat, sommets)
print("\nVérification :", graphe == graphe2)
🧪 Activité 3 - Arbre d'expressions arithmétiques¶
Modéliser une expression arithmétique sous forme d'arbre binaire (les feuilles sont les nombres, les nœuds internes les opérateurs). Écrire une fonction récursive evaluer(arbre) qui calcule le résultat.
Tester avec l'expression (3 + 5) × (7 - 2).
Solution
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
def evaluer(arbre):
if arbre.gauche is None and arbre.droit is None:
return float(arbre.valeur)
g = evaluer(arbre.gauche)
d = evaluer(arbre.droit)
if arbre.valeur == '+': return g + d
if arbre.valeur == '-': return g - d
if arbre.valeur == '*': return g * d
if arbre.valeur == '/': return g / d
def infixe(arbre):
if arbre.gauche is None:
return str(arbre.valeur)
return f"({infixe(arbre.gauche)} {arbre.valeur} {infixe(arbre.droit)})"
# (3 + 5) * (7 - 2)
expr = Noeud('*',
Noeud('+', Noeud(3), Noeud(5)),
Noeud('-', Noeud(7), Noeud(2))
)
print(infixe(expr)) # ((3 + 5) * (7 - 2))
print(evaluer(expr)) # 40.0
Projet¶
🎯 Projet - Gestionnaire de tâches avec priorités¶
Créer un gestionnaire de tâches utilisant :
- une file de priorité (les tâches les plus urgentes sont traitées en premier) ;
- une pile pour l'historique des tâches terminées (annulation possible) ;
- un dictionnaire pour stocker les détails de chaque tâche.
Fonctionnalités : ajouter une tâche (nom, priorité, description), traiter la tâche la plus urgente, annuler le dernier traitement, afficher les tâches en attente et l'historique.
Solution
class Tache:
def __init__(self, nom, priorite, description):
self.nom = nom
self.priorite = priorite
self.description = description
def __str__(self):
return f"[P{self.priorite}] {self.nom} : {self.description}"
class GestionnaireTaches:
def __init__(self):
self.en_attente = []
self.historique = []
def ajouter(self, nom, priorite, description):
tache = Tache(nom, priorite, description)
self.en_attente.append(tache)
self.en_attente.sort(key=lambda t: t.priorite)
print(f"Tâche ajoutée : {tache}")
def traiter(self):
if len(self.en_attente) == 0:
print("Aucune tâche en attente.")
return
tache = self.en_attente.pop(0)
self.historique.append(tache)
print(f"Tâche traitée : {tache}")
def annuler(self):
if len(self.historique) == 0:
print("Aucune tâche à annuler.")
return
tache = self.historique.pop()
self.en_attente.append(tache)
self.en_attente.sort(key=lambda t: t.priorite)
print(f"Annulation : {tache} remise en attente")
def afficher_attente(self):
print("--- Tâches en attente ---")
if len(self.en_attente) == 0:
print(" (aucune)")
for t in self.en_attente:
print(f" {t}")
def afficher_historique(self):
print("--- Historique (plus récent en haut) ---")
if len(self.historique) == 0:
print(" (vide)")
for t in reversed(self.historique):
print(f" {t}")
g = GestionnaireTaches()
g.ajouter("Bug critique", 1, "Corriger le crash au démarrage")
g.ajouter("Documentation", 3, "Écrire le README")
g.ajouter("Nouvelle fonctionnalité", 2, "Ajouter le mode sombre")
g.afficher_attente()
g.traiter()
g.traiter()
g.afficher_historique()
g.annuler()
g.afficher_attente()