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.

TypeRelation entre élémentsExemple typiqueScénario applicable
Structure linéaireRelation séquentielle un-à-unTableaux, listes chaînées, piles, filesLes données ont un ordre évident, comme les listes de tâches et l'historique de navigation
Structure arborescenteRelation hiérarchique un-à-plusieursArbres binaires, BST, tasLes données ont une propriété hiérarchique, comme les répertoires de système de fichiers et les structures organisationnelles
Structure de grapheRelation réseau plusieurs-à-plusieursGraphes orientés, graphes non orientés, graphes pondérésLes 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.

TypeCaractéristiquesExemple typiqueCompromis
Stockage séquentielLes éléments sont stockés un par un dans un espace mémoire contiguTableaux, piles/files implémentées avec des tableauxAccè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 pointeursListes 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éesTables 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, peekImplé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

#include <stdio.h>

int main() {
    int num = 42;        /* variable entière ordinaire */
    int *ptr = &num;   /* 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 :

UtiliserExemple
Établir des connexions entre des nœuds dynamiquesDans les nœuds de liste chaînée,nextpointeurs ; dans les nœuds d'arbre,left/rightpointeurs
Accéder et modifier les données indirectementUtiliser des paramètres pointeurs pour permettre aux fonctions de modifier les valeurs de variables externes
Gestion dynamique de la mémoiremallocRenvoie 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éesLorsqu'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 <stdio.h>
#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 :

FonctionFonctionnalitéExemple
mallocAllouer de la mémoire de la taille en octets spécifiée, contenu non initialiséint* p = malloc(10 * sizeof(int));
callocAllouer de la mémoire et l'initialiser à zéroint* p = calloc(10, sizeof(int));
reallocRedimensionner une mémoire déjà allouéep = realloc(p, 20 * sizeof(int));
freeLibérer la mémoire allouée et la rendre au systèmefree(p);

Exemple

#include <stdio.h>
#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;
}

Le langage C ne récupère pas automatiquement la mémoire allouée dynamiquement. Chaque foismalloc(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.

Autres extensions