C Academy · Leçon

Insérer, rechercher, supprimer

Opérations essentielles

Leçon 3 sur 413 étapes

Insérer, rechercher, supprimer est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.

Les trois opérations essentielles

Toute table de hachage prend en charge trois opérations : insertion, recherche et suppression. Avec un bon hachage et un facteur de charge raisonnable, ces trois opérations s’exécutent en O(1) en moyenne.

Nous allons construire progressivement une table fondée sur le chaînage.

Les types Table et Node

Nous définissons un nœud contenant une chaîne de clé copiée et une valeur entière, ainsi qu’une structure de table contenant le tableau de compartiments et sa capacité.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node **buckets;
    unsigned capacity;
    unsigned size;
} HashTable;

int main(void) {
    printf("types defined\n");
    return 0;
}

Créer la table

Allouez la table et un tableau de compartiments initialisés à zéro avec calloc, afin que chaque compartiment commence par NULL.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;

HashTable *ht_create(unsigned cap) {
    HashTable *t = malloc(sizeof *t);
    t->buckets = calloc(cap, sizeof(Node *));
    t->capacity = cap; t->size = 0;
    return t;
}

int main(void) {
    HashTable *t = ht_create(16);
    printf("capacity=%u size=%u\n", t->capacity, t->size);
    return 0;
}

La fonction auxiliaire de hachage

Nous réutilisons DJB2 et réduisons sa valeur à un indice de compartiment. Cette fonction auxiliaire est utilisée par les trois opérations.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381; int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

unsigned bucket_of(const char *key, unsigned cap) {
    return (unsigned)(djb2(key) % cap);
}

int main(void) {
    printf("%u\n", bucket_of("name", 16));
    return 0;
}

Insérer : mettre à jour ou ajouter au début

Lors d’une insertion, recherchez d’abord dans le compartiment. Si la clé existe, mettez sa valeur à jour. Sinon, allouez un nouveau nœud (avec une clé copiée grâce à strdup) et ajoutez-le au début.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

Node *insert(Node *head, const char *key, int val) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) { p->value = val; return head; }
    Node *n = malloc(sizeof *n);
    n->key = strdup(key); n->value = val; n->next = head;
    return n;
}

int main(void) {
    Node *b = NULL;
    b = insert(b, "a", 1);
    b = insert(b, "a", 99); /* update */
    printf("%s=%d\n", b->key, b->value);
    return 0;
}

Rechercher

La recherche hache la clé, puis parcourt la liste du compartiment en comparant les clés avec strcmp. Elle renvoie un pointeur vers la valeur (ou NULL si elle est absente).

#include <stdio.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

int *lookup(Node *head, const char *key) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) return &p->value;
    return NULL;
}

int main(void) {
    Node n2 = {"y", 20, NULL};
    Node n1 = {"x", 10, &n2};
    int *v = lookup(&n1, "y");
    printf("%d\n", v ? *v : -1);
    return 0;
}

Supprimer : relier la liste

La suppression parcourt le compartiment en conservant un pointeur vers le nœud précédent, puis relie la liste autour de la cible et libère celle-ci (la clé copiée ainsi que le nœud).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

Node *delete_key(Node *head, const char *key) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else head = cur->next;
            free(cur->key); free(cur);
            return head;
        }
        prev = cur; cur = cur->next;
    }
    return head;
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("a"); b->value = 1; b->next = NULL;
    b = delete_key(b, "a");
    printf("%s\n", b ? "left" : "empty");
    return 0;
}

Assembler le tout

Une table complète regroupe ces opérations en calculant le compartiment, puis en déléguant le traitement aux fonctions auxiliaires de la liste. Voici une petite table complète en action.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

#define CAP 16
Node *table[CAP];

void put(const char *k, int v) {
    unsigned i = djb2(k) % CAP;
    Node *n = malloc(sizeof *n);
    n->key = strdup(k); n->value = v; n->next = table[i];
    table[i] = n;
}
int get(const char *k) {
    for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
        if (!strcmp(p->key, k)) return p->value;
    return -1;
}

int main(void) {
    put("age", 30); put("score", 95);
    printf("age=%d score=%d\n", get("age"), get("score"));
    return 0;
}

Pourquoi copier la clé

Nous stockons les clés avec strdup afin que la table possède sa propre copie. Si nous stockions le pointeur fourni par l’appelant, la clé pourrait être modifiée ou libérée indépendamment de la table, ce qui fausserait les recherches.

Cela signifie également que la suppression doit appeler free sur la clé copiée.

Complexité temporelle

Avec un hachage uniforme et un facteur de charge maintenu autour de 0,75 :

Insertion : O(1) en moyenne
Recherche : O(1) en moyenne
Suppression : O(1) en moyenne

Dans le pire des cas, la complexité est O(n), lorsque toutes les clés entrent en collision dans un seul compartiment.

Libérer toute la table

Pour éviter les fuites, libérez chaque nœud de chaque compartiment, puis le tableau de compartiments et enfin la structure de table.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node { char *key; int value; struct Node *next; } Node;

void free_bucket(Node *head) {
    while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("k"); b->value = 1; b->next = NULL;
    free_bucket(b);
    printf("freed\n");
    return 0;
}

Vérification rapide

Testez votre compréhension des opérations essentielles.

Réponds-y dans la leçon interactive

Récapitulatif

Vous avez implémenté les trois opérations essentielles d’une table de hachage avec le chaînage.

L’insertion met à jour un nœud ou l’ajoute au début
La recherche parcourt la liste du compartiment avec strcmp
La suppression relie la liste et libère la clé ainsi que le nœud
Conservez vos propres clés avec strdup et libérez tout lors de la destruction

Gratuit pour commencer

Apprends C avec un tuteur IA — gratuit

Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.

Cours: 39
Leçons: 144

Commencer gratuitement Voir le cours complet

Questions Fréquemment Posées

La leçon « Insérer, rechercher, supprimer » est-elle gratuite ?

Oui — le texte complet de « Insérer, rechercher, supprimer » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Insérer, rechercher, supprimer » ?

Opérations essentielles Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C Academy ?

Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.

Combien de temps prend la leçon « Insérer, rechercher, supprimer » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C Academy ?

Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

← Retour à C Academy