Fiche de révision - Structures de données
1. Interface vs implémentation
- Interface : ensemble des opérations offertes (le « quoi »)
- Implémentation : réalisation concrète en mémoire (le « comment »)
- Plusieurs implémentations peuvent offrir la même interface avec des performances différentes
2. Programmation objet
| Terme |
Définition |
| Classe |
Modèle définissant attributs et méthodes |
| Objet |
Instance concrète d'une classe |
| Attribut |
Variable attachée à un objet (self.x) |
| Méthode |
Fonction attachée à un objet (def methode(self)) |
| Constructeur |
__init__ : initialise l'objet à la création |
| Encapsulation |
Regroupement données + traitements |
3. Structures linéaires
| Structure |
Principe |
Ajout |
Retrait |
Accès |
| Liste chaînée |
Maillons chaînés par des références |
O(1) en tête |
O(1) en tête |
O(n) par index |
| Pile (LIFO) |
Dernier entré, premier sorti |
O(1) empiler |
O(1) dépiler |
O(1) sommet |
| File (FIFO) |
Premier entré, premier sorti |
O(1) enfiler |
O(1) défiler (amorti) |
- |
| Dictionnaire |
Clé → valeur |
O(1) |
O(1) |
O(1) par clé |
Pile : historique, Ctrl+Z, appels de fonctions, parenthèses.
File : impression, ordonnancement, parcours en largeur.
4. Arbres binaires
- Arbre binaire : vide ou nœud + sous-arbre gauche + sous-arbre droit
- Racine : nœud au sommet | Feuille : nœud sans enfant
- Taille :
1 + taille(g) + taille(d) | arbre vide → 0
- Hauteur :
1 + max(hauteur(g), hauteur(d)) | arbre vide → -1
- Encadrement : \(\lfloor \log_2 n \rfloor \leq h \leq n - 1\)
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
5. Graphes
- Graphe non orienté : arêtes symétriques
- Graphe orienté : arcs avec un sens
| Représentation |
Principe |
Mémoire |
Tester voisinage |
| Matrice d'adjacence |
Tableau 2D de 0 et 1 |
O(n²) |
O(1) |
| Liste d'adjacence |
Dictionnaire sommet → voisins |
O(n + m) |
O(degré) |
Degré : nombre de voisins d'un sommet.
6. Résumé : quelle structure choisir ?
| Besoin |
Structure |
| Retour en arrière, annulation |
Pile |
| Traitement dans l'ordre d'arrivée |
File |
| Accès rapide par identifiant |
Dictionnaire |
| Insertions/suppressions en tête |
Liste chaînée |
| Organisation hiérarchique |
Arbre |
| Relations entre éléments |
Graphe |