Concepts de base des structures de données
Avant d'apprendre formellement diverses structures de données, vous devez maîtriser les méthodes de classification des structures de données, le concept de types de données abstraits, et revoir les points de connaissance essentiels du langage C étroitement liés aux structures de données.
Classification des structures de données
Les structures de données peuvent être classées selon deux dimensions : la structure logique et le mode de stockage. Comprendre ces deux méthodes de classification vous aide à déterminer rapidement quel type de structure de données choisir face à des problèmes spécifiques.
La figure ci-dessus montre le système de classification complet des structures de données, expliqué un par un ci-dessous.
Classification selon la structure logique
La structure logique décrit les relations abstraites entre les éléments de données, sans impliquer le mode de stockage réel des données en mémoire.
| Type | Relation entre éléments | Exemple typique | Scénario applicable |
|---|---|---|---|
| Structure linéaire | Relation séquentielle un-à-un | Tableaux, listes chaînées, piles, files | Les données ont un ordre évident, comme les listes de tâches et l'historique de navigation |
| Structure arborescente | Relation hiérarchique un-à-plusieurs | Arbres binaires, BST, tas | Les données ont une propriété hiérarchique, comme les répertoires de système de fichiers et les structures organisationnelles |
| Structure de graphe | Relation réseau plusieurs-à-plusieurs | Graphes orientés, graphes non orientés, graphes pondérés | Les relations entre les données sont complexes, comme les réseaux sociaux et la navigation cartographique |
Classification par méthode de stockage
La méthode de stockage décrit l'organisation réelle des données en mémoire.
| Type | Caractéristiques | Exemple typique | Compromis |
|---|---|---|---|
| Stockage séquentiel | Les éléments sont stockés un par un dans un espace mémoire contigu | Tableaux, piles/files implémentées avec des tableaux | Accès rapide (O(1)), mais insertion et suppression lentes, taille fixe |
| Stockage chaîné | Les éléments peuvent être stockés de manière dispersée, reliés par des pointeurs | Listes chaînées, arbres, graphes (liste d'adjacence) | Insertion et suppression rapides, mais ne permet pas l'accès aléatoire, surcoût dû aux pointeurs |
| Stockage indexé | Établir une table d’index supplémentaire pour localiser les données | Tables de hachage (indexées via des fonctions de hachage) | Recherche extrêmement rapide, mais nécessite de l’espace supplémentaire pour stocker la structure d’index |
La même structure logique peut être implémentée avec différentes méthodes de stockage. Par exemple, une pile (logiquement une structure linéaire) peut être implémentée soit avec un tableau (stockage séquentiel), soit avec une liste chaînée (stockage chaîné). L’implémentation choisie dépend des exigences de l’application spécifique en matière de vitesse d’accès, d’efficacité d’insertion/suppression et d’utilisation de la mémoire.
Type abstrait de données (TAD)
Type abstrait de données (TAD)est un concept central dans l’étude des structures de données.
Il désigne une description abstraite d’un ensemble de données et d’un ensemble d’opérations définies sur ces données, en se préoccupant uniquement de « quoi faire », et non de « comment le faire ».
Prenons l’exemple de la « pile » pour comprendre le TAD :
| Niveau TAD (quoi faire) | Niveau d’implémentation (comment le faire) |
|---|---|
| Définir les opérations : push, pop, peek | Implémenter avec un tableau : maintenir un tableau + un pointeur de sommet |
| Définir le comportement : dernier entré, premier sorti (LIFO) | Implémenter avec une liste chaînée : utiliser la tête de la liste chaînée comme sommet de la pile |
| Spécifier des contraintes : les opérations ne peuvent être effectuées qu'à une extrémité | Les deux implémentations satisfont la définition du TAD, mais ont des caractéristiques de performance différentes |
Cette idée de « séparation de l'interface et de l'implémentation » est la pierre angulaire de la conception modulaire en ingénierie logicielle moderne.
Lorsque vous utilisez une pile, vous avez seulement besoin de savoir utiliser des opérations telles que push et pop, sans avoir à vous soucier de savoir si l'implémentation sous-jacente est un tableau ou une liste chaînée — c'est exactement la valeur du TAD.
Révision des bases du langage C
Avant d'apprendre les structures de données, vous devez maîtriser les trois points de connaissance fondamentaux suivants du langage C, qui apparaissent dans presque tous les chapitres de ce tutoriel.
Pointeur
Un pointeur est l'une des fonctionnalités les plus importantes et les plus flexibles du C. Il stocke l'adresse mémoire d'une autre variable, permettant un accès indirect et la manipulation de la variable cible.
Exemple
int main() {
int num = 42; /* variable entière ordinaire */
int *ptr = # /* ptr est un pointeur vers int, stockant l'adresse de num */
printf("valeur de num : %d\n", num); /* Sortie : 42 */
printf("adresse de num : %p\n", &num); /* Sortie : 0x16d2f2f38 (adresse d'exemple) */
printf("adresse stockée dans ptr : %p\n", ptr); /* Sortie : identique à ci-dessus */
printf("valeur déréférencée par *ptr : %d\n", *ptr); /* Sortie : 42, * est l'opérateur de déréférencement */
*ptr = 100; /* Modifier la valeur de num via le pointeur */
printf("après modification, num = %d\n", num); /* Sortie : 100 */
return 0;
}
Utilisations principales des pointeurs dans les structures de données :
| Utiliser | Exemple |
|---|---|
| Établir des connexions entre des nœuds dynamiques | Dans les nœuds de liste chaînée,nextpointeurs ; dans les nœuds d'arbre,left/rightpointeurs |
| Accéder et modifier les données indirectement | Utiliser des paramètres pointeurs pour permettre aux fonctions de modifier les valeurs de variables externes |
| Gestion dynamique de la mémoire | mallocRenvoie l'adresse de début de la mémoire allouée, qui doit être reçue avec un pointeur |
| Éviter de copier de grandes quantités de données | Lorsqu'on passe de grandes structures à des fonctions, passer des pointeurs est plus efficace que de passer par valeur |
Ce que les débutants confondent le plus facilement, c'est
*et&l'utilisation de * et &: dans les déclarations,int *p* indique que p est de type pointeur ; lors de l'utilisation,*p* indique un déréférencement (obtenir la valeur) ;&x& indique la prise d'adresse. Ce sont deux opérateurs complètement différents, et comprendre cette différence est le prérequis pour bien utiliser les pointeurs.
Structure (struct)
Une struct permet de combiner plusieurs données de types différents en un type personnalisé, et constitue l'unité de base pour construire des structures de données composites telles que les nœuds de listes chaînées et les nœuds d'arbres.
Exemple
#include <string.h> /* fichier d'en-tête pour strcpy */
/* Définir la structure de nœud de liste chaînée */
struct Node {
int data; /* Champ de données : stocke les données réelles */
struct Node* next; /* Champ pointeur : pointe vers le nœud suivant */
};
/* Définir la structure d'informations sur l'étudiant */
struct Student {
int id; /* Identifiant de l'étudiant */
char name[50]; /* Nom, tableau de caractères */
float score; /* Note */
};
int main() {
/* Créer un nœud */
struct Node node1;
node1.data = 10;
node1.next = NULL; /* NULL signifie qu'il n'y a actuellement aucun nœud suivant */
printf("node1.data = %d\n", node1.data); /* Sortie : 10 */
/* Créer un enregistrement d'étudiant */
struct Student stu;
stu.id = 1001;
strcpy(stu.name, "EXAMPLE"); /* strcpy : copie une chaîne dans un tableau de caractères */
stu.score = 95.5;
printf("ID: %d, Nom: %s, Score: %.1f\n",
stu.id, stu.name, stu.score);
/* Sortie : ID: 1001, Nom: EXAMPLE, Score: 95.5 */
return 0;
}
Les structures combinées aux pointeurs permettent des structures de données dynamiques flexibles. Par exemple, la structure auto-référentielle d'un nœud de liste chaînée (struct Node* nextpointe vers le nœud suivant du même type) est exactement la base d'implémentation des listes chaînées.
Allocation dynamique de mémoire
L'allocation dynamique de mémoire permet à un programme de demander et de libérer de la mémoire du tas à l'exécution selon les besoins, et elle est essentielle pour construire des structures de données de taille variable (comme les listes chaînées et les arbres).
Le C fournit quatre fonctions essentielles :
| Fonction | Fonctionnalité | Exemple |
|---|---|---|
| malloc | Allouer de la mémoire de la taille en octets spécifiée, contenu non initialisé | int* p = malloc(10 * sizeof(int)); |
| calloc | Allouer de la mémoire et l'initialiser à zéro | int* p = calloc(10, sizeof(int)); |
| realloc | Redimensionner une mémoire déjà allouée | p = realloc(p, 20 * sizeof(int)); |
| free | Libérer la mémoire allouée et la rendre au système | free(p); |
Exemple
#include <stdlib.h> /* fichier d'en-tête pour malloc, free */
int main() {
int n = 5;
/* malloc: allouer un espace contigu pour n entiers sur le tas */
int* arr = (int*)malloc(n * sizeof(int));
/* Vérifier si l'allocation a réussi ; malloc renvoie NULL en cas d'échec */
if (arr == NULL) {
printf("Échec de l'allocation de mémoire !\n");
return 1; /* Sortie anormale */
}
/* Utiliser la mémoire allouée dynamiquement comme un tableau normal */
for (int i = 0; i < n; i++) {
arr[i] = (i + 1) * 10; /* Affecter : 10, 20, 30, 40, 50 */
}
printf("Contenu du tableau dynamique : ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Sortie : Contenu du tableau dynamique : 10 20 30 40 50 */
free(arr); /* Libérer la mémoire pour éviter les fuites de mémoire */
arr = NULL; /* Bonne pratique : définir le pointeur sur NULL pour éviter les pointeurs fous */
return 0;
}
Autres extensionsLe langage C ne récupère pas automatiquement la mémoire allouée dynamiquement. Chaque fois
malloc(oucalloc) doit avoir un correspondantfree, sinon cela provoquera des fuites de mémoire. Dans les projets réels, les fuites de mémoire épuiseront progressivement les ressources système et finiront par faire planter le programme. C'est l'une des erreurs les plus courantes commises par les débutants en langage C.