Structures de données
Les structures de données servent à organiser l’information pour la stocker, la retrouver et la manipuler efficacement.
1
Notion et rôle
Définition
Une structure de données organise des informations selon un usage précis.
- Le choix de la structure change le coût des opérations.
- Elle facilite l’accès, l’ajout, la suppression ou la recherche.
- Ne pas confondre structure de données et algorithme
2
Structures linéaires
Pile
- LIFO.
- Dernier entré, premier sorti.
- On agit au sommet.
File
- FIFO.
- Premier entré, premier sorti.
- On retire au début de la file.
| Structure | Idée | Usage |
|---|---|---|
| Liste | Suite ordonnée | Accès par position |
| Dictionnaire | Clé-valeur | Recherche rapide par clé |
| Pile | Empilement | Historique, appels |
| File | Attente | Tâches, files d’attente |
3
Listes et dictionnaires
==Pile = LIFO ; File = FIFO==. La lettre O rappelle l’ordre d’arrivée.
4
Arbres et graphes
Arbre
- Structure hiérarchique.
- Racine, nœuds, feuilles.
- Un seul chemin entre deux nœuds.
Graphe
- Sommets reliés par des arêtes.
- Réseau de relations.
- Peut contenir des cycles.
5
Opérations et choix
- 1
Identifier l’opération dominante.
- 2
Comparer accès, ajout et suppression.
On veut gérer des tâches dans l’ordre d’arrivée.
- Une pile traiterait la dernière tâche arrivée en premier.
- Une file respecte l’ordre d’arrivée des tâches.
- Le dictionnaire convient plutôt à une recherche par clé.
Pour des tâches ordonnées, on choisit une file.
- Quelle structure suit LIFO ?
- Quelle structure associe une clé à une valeur ?
À retenir
- Une structure organise les données pour un usage précis.
- Liste, pile, file et dictionnaire sont des structures linéaires.
- Arbres et graphes représentent des relations plus complexes.
- Le bon choix dépend surtout de l’opération fréquente.