Structures et listes chaînées en C : piles, files et arbres

Une structure regroupe des valeurs liées dans un seul enregistrement. Ses membres ont des noms et peuvent être de types différents. Une mesure de capteur, par exemple, comporte à la fois un identifiant et une température.

Définir et initialiser un enregistrement

struct reading {
    int id;
    double temp_c;
};
struct reading r = {.temp_c = 21.5, .id = 7};
r.temp_c += 0.5;

La définition introduit le type struct reading ; reading est son étiquette. Le point-virgule final se place après l’accolade fermante. Définir le type n’alloue aucun objet. La déclaration de r crée un objet, et . sélectionne ses membres. Ici, la température devient 22,0 °C. Lorsqu’une seule étiquette est déclarée, le nom du type inclut struct : reading r; nécessite un typedef distinct.

Un initialiseur tel que {7, 21.5} suit l’ordre de déclaration. Des désignateurs tels que .id = 7 permettent de nommer les membres dans un autre ordre. Les membres omis dans un initialiseur reçoivent des valeurs nulles : {0} initialise donc tout l’enregistrement. Une déclaration locale struct reading r; sans initialiseur laisse ses membres indéterminés jusqu’à ce qu’une valeur leur soit affectée.

Un membre a son propre type et sa propre adresse. Pour lire une température avec scanf, utilise scanf("%lf", &r.temp_c) et vérifie que la valeur de retour est 1. Le point est prioritaire sur & : l’adresse du membre de type double est donc transmise.

Copier et comparer les valeurs

struct reading s = r;
s.temp_c = -4.0;
int same = r.id == s.id && r.temp_c == s.temp_c;

L’affectation copie tous les membres. Modifier s.temp_c laisse r.temp_c à 22,0. Les tableaux de taille fixe contenus dans les structures sont aussi copiés : un membre char name[32] appartient à l’enregistrement. Cela fonctionne même si les tableaux C indépendants ne peuvent pas être affectés avec =. Les membres pointeurs demandent plus d’attention, car le pointeur copié pointe toujours vers le même objet.

Le C ne définit pas == pour les structures entières. Compare les membres qui définissent l’égalité pour ta tâche. memcmp compare les octets bruts, y compris le bourrage, et peut signaler une différence entre des enregistrements dont les valeurs des membres sont égales.

Suivre la disposition en mémoire

Les membres apparaissent dans l’ordre de déclaration, sans bourrage avant le premier membre. Le compilateur peut ajouter des octets inutilisés entre les membres et à la fin pour respecter les exigences d’alignement. Sur une plateforme 64 bits courante avec un int de 4 octets aligné sur 4 octets, struct { char c; int i; char d; } occupe 12 octets. Ses membres commencent aux décalages 0, 4 et 8. Les réordonner sous la forme int i; char c; char d; réduit généralement la taille à 8 octets. Utilise sizeof pour obtenir la taille réelle et offsetof de <stddef.h> pour obtenir un décalage.

Les structures peuvent être imbriquées. Avec struct point { double x_m, y_m; }; et struct rect { struct point corner; double width_m, height_m; };, box.corner.x_m donne accès à l’abscisse du coin en mètres. Une structure ne peut pas contenir un membre complet de son propre type : cela exigerait un objet de taille infinie. Un pointeur vers son propre type a une taille fixe et rend possibles les nœuds chaînés.

Un typedef donne un autre nom à un type existant. Il change la façon d’écrire le type, pas le comportement de ses objets. typedef double meters; fait de meters un autre nom pour double.

Nommer une structure et la passer par valeur

typedef struct {
    int id;
    double temp_c;
} reading;

reading make_reading(int id, double t) {
    reading r = {id, t};
    return r;
}
void warm_copy(reading r) {
    r.temp_c += 1.0;
}

Tu peux maintenant déclarer reading r = make_reading(7, 21.5);. Renvoyer une structure renvoie sa valeur. L’appel warm_copy(r) donne une copie à la fonction : la température de la fonction appelante reste donc à 21,5 °C. Une copie d’un petit enregistrement est souvent l’interface la plus claire lorsque l’objet de la fonction appelante doit rester inchangé.

Un type autoréférentiel a besoin de son étiquette à l’intérieur de la définition :

typedef struct node {
    int number;
    struct node *next;
} node;

L’alias node devient disponible après la déclaration. À l’intérieur de ces accolades, struct node désigne déjà le type incomplet et peut être utilisé pour un pointeur. L’étiquette et l’alias peuvent avoir la même orthographe, car les étiquettes utilisent leur propre espace de noms.

Accéder à l’objet de la fonction appelante par un pointeur

void warm(reading *p) {
    p->temp_c += 1.0;
}
reading r = {7, 21.5};
reading *p = &r;
p->temp_c -= 1.5;
warm(&r);

La soustraction modifie r.temp_c pour lui donner la valeur 20,0 ; warm lui donne ensuite la valeur 21,0. La fonction reçoit une copie de l’adresse, et les deux pointeurs donnent toujours accès au même enregistrement. Utilise -> avec un pointeur et . avec un objet de type structure. p->temp_c signifie (*p).temp_c. Les parenthèses sont nécessaires, car l’accès au membre est prioritaire sur le déréférencement : *p.temp_c tente de sélectionner un membre de p avant d’appliquer *.

Pour lire sans copier la structure, accepte un paramètre const reading *p. Une affectation à p->temp_c à travers ce pointeur est rejetée. La variable pointeur peut encore changer, par exemple lorsqu’elle parcourt un tableau. En revanche, reading *const p rend le pointeur lui-même constant. Pour les structures ayant des membres pointeurs, un pointeur vers un objet constant ne rend pas accessibles en lecture seule les données allouées séparément vers lesquelles ces membres pointent.

Donner un propriétaire à un enregistrement dans le tas

Inclus <stdlib.h> pour l’allocation et <stdbool.h> pour ce résultat indiquant la réussite :

bool make_heap_reading(reading **out, int id, double t) {
    reading *p = malloc(sizeof *p);
    if (p == NULL) return false;
    *p = (reading){.id = id, .temp_c = t};
    *out = p;
    return true;
}

La fonction écrit dans *out seulement après la réussite de l’allocation. La fonction appelante peut déclarer reading *item = NULL;, appeler make_heap_reading(&item, 8, -2.0), traiter un résultat faux, puis appeler free(item) plus tard. sizeof *p mesure le type pointé même avant que p pointe vers un enregistrement initialisé ; cette expression ne lit pas cet enregistrement.

Un pointeur vers une structure locale automatique devient pendant au retour de la fonction. Renvoie la valeur de la structure ou une allocation dans le tas ayant un propriétaire clairement défini. Renvoyer &r depuis une fonction dont la variable locale est r ne peut pas prolonger sa durée de vie.

Un tableau de structures conserve des enregistrements côte à côte. Utilise un indice pour sélectionner un enregistrement, puis un point pour sélectionner un membre. Les parcours, les recherches et les tris fonctionnent ainsi à peu près comme avec un tableau de nombres.

Parcourir les enregistrements avec un nombre explicite

reading readings[4] = {
    {1, 21.5}, {2, -3.0}, {3, 18.25}, {4, 30.0}
};
size_t n = sizeof readings / sizeof readings[0];
size_t best = 0;
for (size_t i = 1; i < n; ++i) {
    if (readings[i].temp_c > readings[best].temp_c)
        best = i;
}

Ici, reading est l’alias de la structure contenant un identifiant et une température. L’indice du meilleur élément passe de 0 à 3 : l’enregistrement de température la plus élevée a donc l’identifiant 4 et la température 30,0 °C. Commencer avec un élément réel fonctionne aussi lorsque toutes les températures sont négatives ; commencer avec un maximum supposé de zéro peut échouer. Ce parcours exige au moins un élément. Une recherche réutilisable doit signaler un tableau vide avant de lire l’élément 0.

Le calcul du nombre d’éléments avec sizeof fonctionne là où readings est un tableau. Dans un paramètre de fonction, une déclaration de tableau devient un pointeur : passe donc n séparément. (items + i)->temp_c et items[i].temp_c donnent accès au même membre.

Fournir une fonction de comparaison à qsort

Inclus <stdlib.h>. Pour des températures finies, cette fonction de comparaison renvoie un signe sans convertir une petite différence de température en entier :

int cmp_temp(const void *a, const void *b) {
    const reading *x = a;
    const reading *y = b;
    return (x->temp_c > y->temp_c)
         - (x->temp_c < y->temp_c);
}
/* With the array above: */
qsort(readings, n, sizeof readings[0], cmp_temp);

La fonction de comparaison reçoit les adresses des éléments. Un résultat négatif signifie que le premier vient avant, zéro signifie qu’ils sont égaux, et un résultat positif qu’il vient après. L’ordre des identifiants après tri est 2, 3, 1, 4. Renvoyer directement la différence de type double tronque une différence telle que −0,25 à zéro. Soustraire des clés entières peut provoquer un débordement. Les comparer d’abord évite ces erreurs. qsort ne conserve pas l’ordre initial des éléments égaux.

Agrandir un tableau sans perdre son stockage

Conserve séparément son nombre d’éléments utilisés et sa capacité. Pour un tableau alloué dont cap est positif, utilise un pointeur temporaire lorsque tu doubles la capacité. Inclus <stdint.h> pour SIZE_MAX :

if (cap > SIZE_MAX / 2 / sizeof *items) return false;
size_t new_cap = 2 * cap;
reading *tmp = realloc(items, new_cap * sizeof *items);
if (tmp == NULL) return false;
items = tmp;
cap = new_cap;

Ces instructions se placent dans une fonction qui renvoie un bool ; items est son pointeur vers le tableau et cap sa capacité positive. En cas d’échec, l’ancienne allocation reste disponible. En cas de réussite, l’allocation peut être déplacée : les anciens pointeurs vers ses éléments doivent donc être remplacés. Une capacité initiale nulle nécessite sa propre allocation initiale.

Déterminer ce dont une copie est propriétaire

Avec typedef struct { char *name; int age; } person;, person b = a; copie l’adresse contenue dans name. Les deux enregistrements donnent accès à la même chaîne. Libérer les deux copies en tant que propriétaires libérerait deux fois la même allocation. Pour obtenir une copie indépendante, alloue strlen(a.name) + 1 octets, vérifie la réussite et utilise strcpy de <string.h>. Un membre de taille fixe char name[32] est copié avec la structure. strdup effectue l’allocation et la copie, mais appartient à POSIX et à C23, pas à la bibliothèque standard C17.

Une énumération donne des noms lisibles à des choix représentés par des entiers. Des noms tels que HIGH rendent visible le rôle d’une condition sans obliger le lecteur à se souvenir de ce que représente le nombre 10.

Suivre la numérotation

enum weekday { MON, TUE, WED, THU, FRI, SAT, SUN };
enum level { LOW = 1, MEDIUM, HIGH = 10, CRITICAL };
enum level alert = HIGH;

Une première valeur omise vaut zéro. Les valeurs omises suivantes augmentent la valeur précédente de un. Ainsi, MON vaut 0 et SUN vaut 6 ; les niveaux valent 1, 2, 10 et 11. Une valeur explicite relance le comptage à partir de cette valeur. Des constantes différentes peuvent partager une valeur, mais des valeurs identiques ne peuvent pas apparaître comme étiquettes case distinctes dans un même switch.

Un alias peut raccourcir une déclaration : typedef enum { RED, YELLOW, GREEN } light; permet d’écrire light signal = RED;. Les constantes d’énumération partagent l’espace de noms des identificateurs ordinaires dans leur portée. Deux énumérations différentes ne peuvent pas toutes deux déclarer RED dans la même portée. Des préfixes tels que LIGHT_RED et PAINT_RED permettent de distinguer les noms.

Traiter chaque choix

const char *level_name(enum level value) {
    switch (value) {
        case LOW: return "low";
        case MEDIUM: return "medium";
        case HIGH: return "high";
        case CRITICAL: return "critical";
    }
    return "unknown";
}

Chaque return termine son cas. Si un cas effectue plutôt une action et doit ensuite s’arrêter, ajoute-lui un break ; atteindre l’étiquette suivante y poursuit l’exécution. Avec GCC, -Wall active les avertissements pour les cas d’énumération manquants lorsqu’il n’y a pas de default ; Clang signale aussi ces omissions par défaut. Un avertissement peut révéler un cas manquant lorsque tu ajoutes une constante par la suite.

Valider une entrée parmi un ensemble de choix

Le type énumération ne garantit pas l’appartenance à l’ensemble nommé. C17 autorise l’affectation d’un entier : enum level x = 42; peut donc compiler. Vérifier que le nombre est compris entre 1 et 11 accepte encore des valeurs sans nom comme 6. Teste les valeurs effectivement autorisées :

#include <stdbool.h>
bool valid_level(int value) {
    return value == LOW || value == MEDIUM
        || value == HIGH || value == CRITICAL;
}

Ce n’est qu’après cette vérification que l’entrée doit devenir un niveau. Pour les jours de la semaine consécutifs, une vérification des bornes de MON à SUN suffit. Dans une énumération ordinaire C17, les constantes d’énumération sont de type int. C23 permet en outre de spécifier un type sous-jacent, comme dans enum color : unsigned char ; cette syntaxe n’appartient pas à C17.

Afficher les noms et utiliser les nombres d’éléments

printf("%d\n", SUN) affiche « 6 », pas « SUN ». Pour des valeurs consécutives commençant à zéro, un tableau de noms fournit le texte : const char *day_names[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};. Après validation d’un indice, day_names[SUN] vaut « Sun ». Utiliser une valeur de niveau telle que HIGH comme indice d’un tel tableau exigerait une autre correspondance, car les valeurs des niveaux ne sont pas consécutives.

Ajouter DAY_COUNT immédiatement après SUN lui donne la valeur 7, utile comme borne de boucle ou taille de tableau. Cette constante compte les jours, mais n’est pas elle-même un jour valide. Les noms d’énumération suivent les règles de portée du C et peuvent être affichés par les débogueurs ; un #define effectue quant à lui une substitution de texte par le préprocesseur.

Une union donne à plusieurs membres la même zone de stockage. Elle convient à une valeur qui peut être de plusieurs types. Une structure donne à chaque membre sa propre zone de stockage et convient à un enregistrement qui a besoin de toutes ces valeurs ensemble.

Stocker une des valeurs possibles

union value {
    int i;
    double d;
    char c;
};
union value v = {.d = 2.5};

Tous les membres commencent à la même adresse. L’union doit contenir son plus grand membre et respecter les exigences d’alignement ; avec un double de 8 octets sur les plateformes courantes, cette union occupe 8 octets. Un initialiseur simple {42} initialise son premier membre, i ; .d = 2.5 choisit explicitement d.

Écrire v.i = 42 après l’initialisation remplace la valeur stockée. Lire ensuite v.d ne convertit pas 42 en double : cela interprète les octets stockés selon une autre représentation. Cette représentation peut être invalide. Lis le membre correspondant à la valeur que tu as stockée.

Indiquer quel membre est valide

Associe l’union à une énumération. L’énumération est l’étiquette, et l’union est la charge utile :

enum kind { K_INT, K_DOUBLE, K_CHAR };
struct tagged {
    enum kind kind;
    union value as;
};
struct tagged make_double(double d) {
    return (struct tagged){.kind = K_DOUBLE, .as = {.d = d}};
}

Une fonction auxiliaire définit les deux éléments ensemble. Le code qui écrit maintient les deux champs synchronisés. Si le code écrit dans t.as.i mais laisse t.kind à K_DOUBLE, une lecture ultérieure choisit la mauvaise représentation.

#include <stdio.h>
void print_cell(struct tagged t) {
    switch (t.kind) {
        case K_INT: printf("%d", t.as.i); break;
        case K_DOUBLE: printf("%.1f", t.as.d); break;
        case K_CHAR: printf("%c", t.as.c); break;
    }
}

Appeler cette fonction pour des cellules contenant 42, 2,5 et 'x', en affichant des espaces entre les appels, produit « 42 2.5 x ». Chaque cas choisit à la fois le membre et le format correspondants. Un jeton de calculatrice peut de même contenir soit un nombre, soit un opérateur.

Sur les plateformes 64 bits courantes, une énumération de 4 octets, du bourrage et cette union de 8 octets font que struct tagged occupe 16 octets. Une structure stockant séparément l’énumération et les trois valeurs possibles occupe généralement 24 octets. Ce sont des exemples de disposition ; interroge les types réels avec sizeof.

Regrouper de petits indicateurs dans des champs de bits

struct flags {
    unsigned int ready : 1;
    unsigned int mode : 3;
};

La largeur suit les deux-points. Un champ non signé de 1 bit contient 0 ou 1 ; un champ de 3 bits contient une valeur de 0 à 7. Stocker 9 dans mode conserve les trois bits de poids faible et stocke 1. Cela perd de l’information : valide donc un mode avant de le stocker lorsque des valeurs plus grandes indiquent une erreur.

Un champ de bits ne possède pas d’emplacement adressable séparément : &flags.mode n’est donc pas valide pour une variable nommée flags. Son ordre d’allocation et son regroupement dépendent de l’implémentation. N’utilise pas une déclaration de champ de bits comme garantie portable d’une disposition précise de fichier ou de matériel. Une largeur indiquée précise la plage de valeurs du champ, pas la disposition de chaque octet autour de lui.

Une liste simplement chaînée stocke chaque élément dans un nœud alloué séparément. Chaque nœud contient sa valeur et l’adresse du nœud suivant. Le pointeur de tête pointe vers le premier nœud ; NULL marque à la fois une liste vide et la fin d’une chaîne.

Définir le lien et insérer en tête

#include <stdbool.h>
#include <stdlib.h>
typedef struct node {
    int number;
    struct node *next;
} node;

bool prepend(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *head;
    *head = n;
    return true;
}

Commence par node *list = NULL;. Appelle prepend(&list, value) et traite un résultat faux. La fonction prend l’adresse du pointeur de tête de la fonction appelante. *head désigne donc le pointeur qui doit changer. Prendre seulement node *head et affecter une valeur à ce pointeur local laisserait le pointeur de tête de la fonction appelante inchangé.

L’ordre des dernières affectations préserve l’ancienne liste. Relie d’abord le nouveau nœud à l’ancienne tête, puis remplace le pointeur de tête. Inverser ces instructions fait pointer n->next vers n lui-même et fait perdre l’ancienne chaîne. Pour les valeurs arrivant dans l’ordre 1, 2 et 3, les insertions successives en tête produisent 1, puis 2 → 1, puis 3 → 2 → 1 → NULL. L’insertion en tête inverse l’ordre d’arrivée.

Parcourir sans déplacer le pointeur qui donne accès à la liste

#include <stdio.h>
void print_list(const node *head) {
    for (const node *p = head; p != NULL; p = p->next)
        printf("%d ", p->number);
}

Le pointeur de parcours p se déplace tandis que head reste disponible. L’exemple affiche « 3 2 1 », avec un espace final. Pour une liste vide, le corps de la boucle s’exécute zéro fois. Il n’y a pas d’indice de tableau : chaque étape lit un lien pour trouver le nœud suivant. Les allocations peuvent être dispersées en mémoire, et insérer un nœud ne déplace pas les nœuds existants.

Ajouter en fin de liste

bool append(node **head, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    node **link = head;
    while (*link != NULL) link = &(*link)->next;
    *link = n;
    return true;
}

link commence à l’adresse du pointeur de tête de la fonction appelante. Il passe ensuite à l’adresse de chaque membre next jusqu’à désigner le lien nul final. Affecter une valeur à cet emplacement fonctionne aussi pour une liste vide. Sans pointeur de queue conservé, chaque ajout en fin doit d’abord suivre la chaîne existante jusqu’à son extrémité. Une fonction peut aussi renvoyer un nouveau pointeur de tête, à condition que la fonction appelante le conserve et traite un échec d’allocation sans perdre l’ancienne liste.

Libérer les nœuds dans un ordre sûr

void clear_list(node **head) {
    while (*head != NULL) {
        node *old = *head;
        *head = old->next;
        free(old);
    }
}

Lis le successeur tant que old existe encore, déplace le pointeur de tête, puis libère l’ancien nœud. Après la boucle, le pointeur de tête de la fonction appelante vaut NULL. Lire old->next après avoir libéré old est une utilisation après libération, même si la mémoire semble inchangée. Un outil de vérification de la mémoire peut aider à révéler les lectures invalides et les allocations oubliées ; le nettoyage doit aussi être exécuté après l’échec d’une opération ultérieure.

La recherche dans une liste suit les liens un par un. L’insertion et la suppression demandent une information supplémentaire : l’adresse du lien qui doit changer. Ce lien peut être le pointeur de tête ou un membre next situé dans un nœud précédent.

Rechercher une valeur

Avec le type node et ses membres number et next :

node *find(node *head, int value) {
    for (node *p = head; p != NULL; p = p->next)
        if (p->number == value) return p;
    return NULL;
}

Une correspondance renvoie l’adresse du nœud lui-même. Une valeur absente donne NULL. Atteindre le 1 000e nœud exige de suivre 999 liens depuis la tête, même lorsque tu connais sa position à l’avance.

Conserver un pointeur vers le lien à modifier

Un node ** peut pointer soit vers le pointeur de tête, soit vers le champ next d’un nœud. Appelons-le link : *link est le nœud actuellement atteint par ce lien. Avancer avec link = &(*link)->next change le lien que tu examines ; cela ne modifie pas la liste.

bool insert_sorted(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number < value)
        link = &(*link)->next;
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->number = value;
    n->next = *link;
    *link = n;
    return true;
}

Inclus <stdbool.h> et <stdlib.h>. La liste reçue doit déjà être triée par ordre croissant. Arrête-toi avant la première valeur qui n’est pas inférieure à la nouvelle : les doublons sont ainsi placés avant les valeurs égales. La partie gauche de && vérifie si le pointeur vaut NULL avant que la partie droite ne déréférence le nœud. Inverser ces tests déréférencerait un pointeur nul à la fin.

Pour les insertions 5, 2, 8 et 4, la liste finale est 2 → 4 → 5 → 8. Lors de l’insertion de 4 dans 2 → 5 → 8, link passe du pointeur de tête à 2.next. Le nouveau nœud pointe vers 5, et 2.next est redirigé vers le nouveau nœud. Si le nouvel élément est le plus petit, link désigne encore le pointeur de tête. À la fin, il désigne le lien nul final.

Déchaîner avant de libérer

bool remove_first(node **head, int value) {
    node **link = head;
    while (*link != NULL && (*link)->number != value)
        link = &(*link)->next;
    if (*link == NULL) return false;
    node *old = *link;
    *link = old->next;
    free(old);
    return true;
}

La boucle trouve le lien entrant. Sauvegarder sa cible dans old garde le nœud accessible pendant que *link est modifié pour pointer vers son successeur. Ce n’est qu’ensuite que le nœud retiré est libéré. Supprimer 5 de 2 → 4 → 5 → 8 donne 2 → 4 → 8. Supprimer ensuite 2 modifie le pointeur de tête et laisse 4 → 8. Si la valeur est absente, la fonction renvoie une valeur fausse sans modifier la liste.

Une version à deux pointeurs conserve prev et cur. Lorsque prev est nul, le nœud trouvé est la tête et le pointeur de tête doit changer ; sinon, mets à jour prev->next. Oublier le cas de la tête laisse un pointeur vers une zone de mémoire libérée. La version utilisant l’adresse du lien traite les deux cas par la même affectation.

Teste une liste vide, une liste à un nœud, une correspondance en premier ou en dernier, ainsi qu’une valeur absente. Pour chaque modification, repère le lien entrant, le nœud concerné et son successeur avant d’écrire une affectation. Aucun nœud conservé ne doit devenir inaccessible, et aucun lien ne doit pointer vers un nœud libéré.

La question utile est de savoir quelles opérations ton programme effectue. Les tableaux et les listes peuvent contenir les mêmes valeurs, mais ils y accèdent et les déplacent différemment.

Comparer les opérations

Une liste ne permet pas de trouver une position sans parcours. L’insertion après un nœud dont tu disposes déjà est directe, mais la suppression nécessite aussi le prédécesseur ou le lien qui pointe vers le nœud. Avec seulement l’adresse du nœud, une liste simplement chaînée exige généralement un parcours depuis la tête pour trouver ce lien entrant.

Le stockage compte aussi. Sur une plateforme 64 bits typique, un nœud comportant un int de 4 octets et un pointeur de 8 octets occupe 16 octets après ajout du bourrage. Pour 1 000 entiers, les nœuds utilisent 16 000 octets plus les informations de gestion des allocations ; un tableau contigu d’entiers utilise 4 000 octets. Parcourir le tableau est généralement plus rapide, car les valeurs voisines sont stockées ensemble.

Regrouper les métadonnées de la liste

typedef struct {
    node *head;
    node *tail;
    size_t count;
} list_t;

Initialise une structure englobante avec list_t list = {0};. Les règles pour l’état vide sont head == NULL, tail == NULL et count == 0. Chaque insertion ou suppression réussie doit mettre à jour le compteur ainsi que les liens. Un échec d’allocation ne modifie aucun de ces éléments.

Avec un pointeur de queue, l’ajout en fin après vérification de l’allocation utilise ces affectations :

n->next = NULL;
if (list.tail == NULL) list.head = n;
else list.tail->next = n;
list.tail = n;
++list.count;

Ici, n est un nœud initialisé. Pour le premier nœud, les pointeurs de tête et de queue deviennent égaux. La suppression du dernier nœud doit faire reculer le pointeur de queue ; pour une liste simplement chaînée, cela exige le prédécesseur. La suppression de l’unique nœud met les deux pointeurs à NULL et le compteur à zéro.

Relier dans les deux sens

typedef struct dnode {
    int value;
    struct dnode *prev, *next;
} dnode;
typedef struct {
    dnode *head, *tail;
} dlist;

void unlink_node(dlist *list, dnode *d) {
    if (d->prev != NULL) d->prev->next = d->next;
    else list->head = d->next;
    if (d->next != NULL) d->next->prev = d->prev;
    else list->tail = d->prev;
    free(d);
}

Cette fonction reçoit un nœud encore valide appartenant à la liste. Les liens des deux voisins sont rétablis avant sa libération. Aux extrémités, le pointeur de tête ou de queue est modifié à la place d’un voisin absent. Une liste doublement chaînée peut être parcourue à rebours et permet de supprimer un nœud dont on dispose sans chercher son prédécesseur, au prix d’un pointeur supplémentaire par nœud et d’un plus grand nombre de liens à maintenir.

Libérer les données possédées avant leur nœud

Un word_node peut être propriétaire à la fois d’une allocation pour le nœud et d’une allocation pour une chaîne accessible par word. Sauvegarde next, appelle free(n->word), puis free(n), et passe au successeur sauvegardé. Libérer uniquement le nœud provoque une fuite de mémoire pour la chaîne. Lire n->word après avoir libéré le nœud est invalide. La propriété indique quel code doit libérer chaque allocation, même lorsque plusieurs pointeurs permettent d’y accéder.

Une pile retire d’abord l’élément ajouté le plus récemment : dernier entré, premier sorti (LIFO). Ses opérations définissent un type abstrait de données indépendamment du fait qu’un tableau ou des nœuds chaînés contiennent les valeurs. push ajoute au sommet, pop retire l’élément au sommet et peek le lit sans le retirer.

Utiliser un tableau et un compteur

#include <stdbool.h>
#define STACK_CAP 100
typedef struct {
    int items[STACK_CAP];
    int top;
} stack;

bool push(stack *s, int value) {
    if (s->top == STACK_CAP) return false;
    s->items[s->top++] = value;
    return true;
}
bool pop(stack *s, int *out) {
    if (s->top == 0) return false;
    *out = s->items[--s->top];
    return true;
}

Initialise avec stack s = {0};. Ici, top est le nombre d’éléments stockés : l’indice occupé au sommet est donc top - 1. Un empilement réussi écrit dans la prochaine case libre et augmente le compteur. Un dépilement réussi diminue d’abord le compteur, puis lit l’élément à cet indice. La fonction appelante fournit un pointeur out valide et vérifie le résultat avant d’utiliser sa valeur.

Empiler 4, 7 et 1, puis dépiler deux fois renvoie 1 et 7, et laisse 4. Sans vérification de capacité, empiler dans une pile pleine écrit dans items[STACK_CAP], après la fin du tableau. Sans vérification de l’état vide, le top signé passe de 0 à −1 et le dépilement lit items[-1]. Les deux accès ont un comportement indéfini.

Utiliser la tête d’une liste comme sommet

Une pile chaînée empile en insérant en tête un nœud dont l’allocation a été vérifiée. Le dépilement retire la tête :

bool pop_linked(node **top, int *out) {
    if (*top == NULL) return false;
    node *old = *top;
    *out = old->number;
    *top = old->next;
    free(old);
    return true;
}

node possède un entier number et un pointeur next. Une pile chaînée n’a pas de capacité fixe de tableau, mais un empilement peut échouer si l’allocation échoue. Elle exige toujours de vérifier si elle est vide et de libérer les nœuds restants à la fin.

Apparier les délimiteurs imbriqués

Parcours l’entrée de gauche à droite. Empile chaque parenthèse, crochet ou accolade ouvrant. Pour chaque délimiteur fermant, dépile et vérifie que les types correspondent. Un délimiteur fermant sans délimiteur ouvrant provoque immédiatement un échec. Termine en vérifiant que la pile est vide : des délimiteurs ouvrants restants indiquent aussi une discordance.

Le texte « ( [ ] { } ) » est équilibré. Pour « ( ] », le délimiteur fermant ne correspond pas au délimiteur ouvrant dépilé. Pour « ( ( ) », un délimiteur ouvrant reste après le parcours. Un simple comptage des délimiteurs ouvrants et fermants manquerait une imbrication incorrecte comme « ( [ ) ] ».

Évaluer des expressions postfixées

Empile les nombres à mesure qu’ils arrivent. Pour un opérateur binaire, dépile d’abord l’opérande de droite, puis celui de gauche, calcule left operator right et empile le résultat. Pour « 3 4 + 2 * », + combine 3 et 4 pour donner 7, puis * combine 7 et 2 pour donner 14. Pour « 9 4 - », dépile 4 comme opérande de droite et 9 comme opérande de gauche, ce qui donne 5. Les inverser donne −5. Rejette les expressions qui n’ont pas assez d’opérandes et exige un seul résultat final ; la division exige aussi un opérande de droite non nul.

Les appels de fonctions ont des durées de vie organisées en pile : une fonction appelée se termine avant que la fonction appelante ne poursuive son exécution. Chaque appel actif a besoin d’un cadre de pile, si bien qu’une récursivité très profonde peut épuiser la pile d’appels même lorsque les allocations dans le tas réussissent.

Une file retire d’abord l’élément le plus ancien : premier entré, premier sorti (FIFO). Enfiler ajoute en queue ; défiler retire en tête. Après avoir enfilé A, B et C, les deux retraits suivants renvoient A et B. Cela convient aux tâches qui doivent être traitées dans leur ordre d’arrivée.

Conserver les deux extrémités d’une file chaînée

Avec des nœuds comportant les membres number et next, et en incluant <stdbool.h> et <stdlib.h> :

typedef struct { node *head, *tail; } queue;

bool enqueue(queue *q, int value) {
    node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    *n = (node){.number = value, .next = NULL};
    if (q->tail == NULL) q->head = n;
    else q->tail->next = n;
    q->tail = n;
    return true;
}
bool dequeue(queue *q, int *out) {
    if (q->head == NULL) return false;
    node *old = q->head;
    *out = old->number;
    q->head = old->next;
    if (q->head == NULL) q->tail = NULL;
    free(old);
    return true;
}

Initialise avec queue q = {0};. L’enfilement définit le lien de l’ancienne queue avant de déplacer le pointeur de queue. Pour le premier nœud, il définit aussi le pointeur de tête. Le défilement fait avancer le pointeur de tête. Lorsque cela retire l’unique nœud, le pointeur de queue doit lui aussi devenir NULL. Sinon, le prochain enfilement écrit à travers un pointeur de queue pendant. Aucune des deux opérations n’exige de parcourir la liste.

Réutiliser un tableau fixe comme anneau

Une file dans un tableau ordinaire qui retire toujours l’élément d’indice 0 doit décaler les valeurs restantes. Un tampon circulaire suit plutôt un indice de tête et un nombre d’éléments :

#define CAP 4
typedef struct {
    char items[CAP];
    unsigned head, count;
} ring;

bool ring_put(ring *q, char value) {
    if (q->count == CAP) return false;
    q->items[(q->head + q->count) % CAP] = value;
    ++q->count;
    return true;
}
bool ring_get(ring *q, char *out) {
    if (q->count == 0) return false;
    *out = q->items[q->head];
    q->head = (q->head + 1) % CAP;
    --q->count;
    return true;
}

Initialise un tampon circulaire avec {0}. head indique toujours l’élément en tête lorsque la file n’est pas vide. Le prochain indice d’insertion est l’indice de tête augmenté du nombre d’éléments, avec retour au début grâce à % CAP. Lis l’élément en tête avant de déplacer head. Le compteur permet de distinguer une file vide d’une file pleine sans renoncer à une case.

Suivre le retour au début

Enfile A, B et C dans les cases 0, 1 et 2. Défile A : l’indice de tête devient 1 et le compteur devient 2. D entre dans la case 3 ; E entre dans la case 0. Le tableau physique contient maintenant E, B, C, D, mais l’ordre logique de retrait est B, C, D, E. Le tampon circulaire est plein parce que le compteur vaut 4, même si la tête est à l’indice 1.

Une autre conception suit l’indice de tête et l’indice de queue correspondant à la prochaine case libre, sans compteur. Dans cette conception, des indices égaux pourraient signifier que la file est vide ou pleine : une convention courante laisse donc une case inutilisée. La file est vide lorsque head == tail et pleine lorsque (tail + 1) % CAP == head. Ne mélange pas cette convention avec les règles de capacité de la version utilisant un compteur. Les files permettent aussi de visiter un arbre niveau par niveau en conservant les nœuds qui attendent leur tour.

Un arbre binaire donne à chaque nœud au plus deux enfants, appelés gauche et droit. La racine est le nœud au sommet. Une feuille n’a pas d’enfant, et un nœud accompagné de tous ses descendants forme un sous-arbre. Un enfant absent et un arbre vide sont représentés par NULL.

Représenter les branches

typedef struct tnode {
    int key;
    struct tnode *left;
    struct tnode *right;
} tnode;

Chaque pointeur vers un enfant mène à la racine d’un autre arbre. La même définition décrit donc une feuille, un grand arbre ramifié ou une longue chaîne. La hauteur compte les arêtes du plus long chemin de la racine à une feuille : une racine seule a une hauteur de 0. Utilise −1 pour un arbre vide, de sorte que les deux sous-arbres vides d’une feuille conduisent naturellement à la hauteur 0. Compter les niveaux donnerait un de plus.

Appliquer la règle aux sous-arbres entiers

Un arbre binaire de recherche ordonne les clés. Pour chaque nœud, toutes les clés de son sous-arbre gauche sont plus petites et toutes celles de son sous-arbre droit sont plus grandes. Stocke chaque clé une seule fois. Cette condition inclut les descendants éloignés. Une racine 50 avec un enfant gauche 30 et un enfant droit 60 sous ce 30 est invalide : 60 se trouve toujours dans le sous-arbre gauche de 50.

Insère 50, 30, 70, 20, 40, 60 et 80 dans un arbre binaire de recherche vide. La racine est 50 ; 30 et 70 sont ses enfants. Les enfants de 30 sont 20 et 40, et ceux de 70 sont 60 et 80. Chaque choix de branche préserve les bornes héritées des ancêtres.

Choisir une branche à chaque étape

#include <stddef.h>
tnode *search(tnode *t, int key) {
    while (t != NULL) {
        if (key == t->key) return t;
        if (key < t->key) t = t->left;
        else t = t->right;
    }
    return NULL;
}

La recherche de 60 dans l’exemple visite 50, va à droite vers 70, puis à gauche vers 60 : trois nœuds. La recherche de 65 suit le même chemin, puis essaie l’enfant droit de 60. Cet enfant vaut NULL : 65 est donc absent. Tu n’as pas besoin d’examiner le sous-arbre gauche de 50, car toutes ses clés sont inférieures à 50.

La version récursive traite d’abord t == NULL et une clé correspondante, puis effectue la recherche dans l’enfant choisi. Le test du sous-arbre vide est le cas de base. Sans lui, une recherche infructueuse finit par déréférencer un pointeur nul. La version avec boucle s’arrête à la même limite sans ajouter d’appels récursifs.

Expliquer le travail par la forme de l’arbre

Un arbre parfaitement équilibré à 20 niveaux contient 1 048 575 clés, et une recherche visite au plus 20 nœuds. Insérer à la place les clés déjà triées 10, 20, 30, 40, 50 crée une chaîne dirigée vers la droite. Sa hauteur est de 4, et trouver 50 visite les cinq nœuds. La seule règle d’ordre d’un arbre binaire de recherche ne garantit pas une faible hauteur. Les arbres autoéquilibrés comme les arbres AVL réorganisent les branches pour contrôler la hauteur.

Pour trouver un minimum, suis les enfants gauches jusqu’à ce que le lien gauche suivant vaille NULL. Pour trouver un maximum, suis les enfants droits. Dans l’exemple à sept nœuds, ces clés sont 20 et 80. Les mêmes choix de direction fonctionnent à la racine de n’importe quel sous-arbre, car la règle d’ordre s’y applique aussi.

Les fonctions sur les arbres travaillent sur un sous-arbre et relient leur résultat à son parent. Garde explicite le cas du sous-arbre vide et distingue les opérations qui modifient les liens de celles qui ne font que visiter les nœuds.

Insérer par le lien du sous-arbre

Avec tnode contenant key, left et right, inclus <stdbool.h> et <stdlib.h> :

bool insert(tnode **link, int key) {
    if (*link == NULL) {
        tnode *n = malloc(sizeof *n);
        if (n == NULL) return false;
        *n = (tnode){.key = key, .left = NULL, .right = NULL};
        *link = n;
        return true;
    }
    if (key < (*link)->key) return insert(&(*link)->left, key);
    if (key > (*link)->key) return insert(&(*link)->right, key);
    return true;
}

Appelle la fonction avec insert(&root, key) et vérifie son résultat. Une clé existante laisse l’arbre inchangé et compte comme une réussite. L’adresse du lien permet à l’insertion de mettre à jour soit la racine de la fonction appelante, soit un pointeur vers un enfant. Avec une interface qui renvoie la racine, conserve chaque résultat : t->left = insert(t->left, key) et root = insert(root, key). Ignorer une allocation renvoyée alors que le sous-arbre initial était vide laisse ce nœud sans lien et provoque une fuite de mémoire.

Choisir quand visiter la racine

Pour les insertions 50, 30, 70, 20, 40, 60, 80, le parcours infixe produit « 20 30 40 50 60 70 80 ». Le parcours préfixe donne « 50 30 20 40 70 60 80 » ; le parcours postfixe donne « 20 40 30 60 80 70 50 ».

void free_tree(tnode *t) {
    if (t == NULL) return;
    free_tree(t->left);
    free_tree(t->right);
    free(t);
}

Après free_tree(root), définis root = NULL chez le propriétaire. La fonction libère d’abord les enfants afin de pouvoir lire leurs adresses dans le parent encore valide. La taille est zéro pour un sous-arbre vide, sinon un plus la taille des deux enfants. La hauteur est −1 pour un sous-arbre vide, sinon un plus la plus grande hauteur des enfants. L’exemple a une taille de 7 et une hauteur de 2.

Supprimer sans rompre l’ordre

Une feuille devient NULL. Un nœud ayant un enfant est remplacé par cet enfant. Pour deux enfants, copie dans le nœud la plus petite clé du sous-arbre droit, puis supprime ce successeur de sa position d’origine :

tnode *erase(tnode *t, int key) {
    if (t == NULL) return NULL;
    if (key < t->key) t->left = erase(t->left, key);
    else if (key > t->key) t->right = erase(t->right, key);
    else {
        if (t->left == NULL || t->right == NULL) {
            tnode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        tnode *s = t->right;
        while (s->left != NULL) s = s->left;
        t->key = s->key;
        t->right = erase(t->right, s->key);
    }
    return t;
}

Appelle la fonction avec root = erase(root, key). Supprimer 50 de l’exemple place 60 dans la racine et retire l’ancien nœud 60. Le parcours infixe devient « 20 30 40 60 70 80 » ; le parcours préfixe devient « 60 30 20 40 70 80 ». Un successeur peut avoir un enfant droit : sa suppression doit donc reconnecter cet enfant.

Pour des clés de type mot, utilise le signe de strcmp, pas l’égalité des pointeurs, et donne à chaque mot possédé sa propre allocation. Libère le mot avant son nœud. La suppression d’enregistrements de ce type dont le nœud a deux enfants exige aussi de prévoir la propriété du mot déplacé et de toute valeur associée ; copier un pointeur propriétaire puis libérer le mot dans son nœud d’origine laisserait une clé pendante.

Une table de hachage choisit un emplacement de départ à partir d’une clé. Une fonction de hachage produit un nombre ; réduire ce nombre modulo un nombre positif d’alvéoles donne un indice. Le chaînage séparé conserve une liste chaînée dans chaque alvéole : la recherche parcourt donc la chaîne sélectionnée.

Distinguer hachage et égalité

Une fonction de hachage utile est déterministe, rapide à calculer et répartit les clés attendues entre les alvéoles. Des clés égales doivent produire des résultats de hachage égaux. Des clés différentes peuvent néanmoins partager un indice : c’est une collision, et toute table doit la gérer. Lorsqu’il existe plus de clés possibles que d’alvéoles, certaines collisions sont inévitables.

Pour des mots commençant par une lettre sur un système compatible avec ASCII, toupper((unsigned char)word[0]) - 'A' attribue 26 alvéoles aux lettres ; « Luigi » commence dans l’alvéole 11. Beaucoup de mots anglais commencent par « s » et peu par « x » : cette règle peut donc produire des chaînes très inégales. La conversion explicite est nécessaire, car les fonctions de <ctype.h> exigent une valeur de caractère non signé ou EOF. Vérifie la première lettre et l’hypothèse sur le jeu de caractères avant d’utiliser cette règle d’indexation.

Un hachage par somme des caractères présente aussi des faiblesses. Avec les codes ASCII et dix alvéoles, « cat » donne la somme 99 + 97 + 116 = 312 et atteint l’alvéole 2 ; « dog » donne la somme 314 et atteint l’alvéole 4. « act » donne aussi la somme 312. L’addition perd l’ordre des lettres : toute permutation produit donc une collision.

Intégrer l’ordre des caractères au hachage

unsigned long hash_word(const char *word) {
    unsigned long h = 5381;
    const unsigned char *p = (const unsigned char *)word;
    while (*p != '\0') {
        h = h * 33 + *p;
        ++p;
    }
    return h;
}

Cette construction djb2 utilise des opérations non signées, dont le débordement provoque un rebouclage défini. Un débordement signé aurait un comportement indéfini. Pour les chaînes ASCII « cat » et « act », les valeurs sont 193488125 et 193486013. Réduis-les avec hash_word(word) % N, où N est le nombre positif d’alvéoles. L’ordre des lettres change ces résultats de hachage, même si leur réduction peut encore produire une collision.

Si une table considère « Cat » et « cat » comme égaux, le hachage et la comparaison doivent tous deux appliquer la même règle de casse. Ignorer la casse uniquement lors de la comparaison peut envoyer des clés égales dans des alvéoles différentes, où la recherche ne les comparera pas. Un reste négatif obtenu à partir d’un résultat de hachage signé ne convient pas non plus comme indice de tableau.

Choisir une stratégie de gestion des collisions

Le chaînage séparé stocke toutes les entrées en collision dans la liste chaînée d’une alvéole. La recherche compare les clés jusqu’à trouver une correspondance ou à atteindre la fin. L’adressage ouvert stocke les entrées dans le tableau lui-même. Avec le sondage linéaire, une collision conduit à essayer la case suivante, puis à revenir au début après la fin. La recherche suit la même séquence de sondage et peut donc examiner plusieurs cases du tableau.

Recalculer les indices lorsque la table grandit

Le facteur de charge est le nombre de clés stockées divisé par le nombre d’alvéoles. Douze clés dans huit alvéoles donnent en moyenne 1,5 entrée par alvéole. Seize alvéoles réduisent cette moyenne à 0,75. Cette moyenne ne garantit pas que chaque chaîne est courte ; une mauvaise fonction de hachage peut placer toutes les clés ensemble.

Un indice d’alvéole dépend du nombre d’alvéoles. Après avoir alloué et initialisé un tableau d’alvéoles plus grand, recalcule l’indice de chaque clé stockée pour le nouveau nombre et relie-la à son nouvel emplacement. Copier les anciens pointeurs de tête dans les nouvelles alvéoles de même numéro laisse les clés à des endroits où la nouvelle recherche ne les cherchera pas. Une table à chaînage séparé peut contenir plus d’entrées que d’alvéoles ; l’adressage ouvert exige des cases inutilisées pour les nouvelles entrées et un sondage fiable.

Une table à chaînage séparé combine un tableau, des liens de liste, la comparaison de chaînes et la propriété des allocations. Chaque entrée est propriétaire de sa clé copiée. Le tableau d’alvéoles est propriétaire des chaînes, et chaque chaîne se termine par NULL.

Initialiser les alvéoles et rechercher du texte

#include <stdbool.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>
#define N 26
typedef struct entry {
    char *key;
    int count;
    struct entry *next;
} entry;
static entry *table[N];

Avec une durée de stockage statique, chaque alvéole contient initialement un pointeur nul. Un tableau local a en revanche besoin d’un initialiseur tel que entry *table[N] = {NULL};. Utilise la fonction hash_word non signée qui commence à 5381 et intègre chaque octet avec le multiplicateur 33.

entry *find_word(const char *key) {
    size_t i = hash_word(key) % N;
    for (entry *e = table[i]; e != NULL; e = e->next)
        if (strcmp(e->key, key) == 0) return e;
    return NULL;
}

strcmp compare le texte. e->key == key vérifierait si les pointeurs désignent le même emplacement. Deux tampons distincts peuvent contenir des mots égaux : l’égalité des pointeurs ne permet donc pas de rechercher un mot.

Compter une clé existante ou en installer une nouvelle

bool add_word(const char *key) {
    entry *e = find_word(key);
    if (e != NULL) {
        if (e->count == INT_MAX) return false;
        ++e->count;
        return true;
    }
    e = malloc(sizeof *e);
    if (e == NULL) return false;
    e->key = malloc(strlen(key) + 1);
    if (e->key == NULL) {
        free(e);
        return false;
    }
    strcpy(e->key, key);
    e->count = 1;
    size_t i = hash_word(key) % N;
    e->next = table[i];
    table[i] = e;
    return true;
}

La fonction appelante fournit une chaîne terminée par un caractère nul. La vérification de INT_MAX signale un échec avant que le compteur ne dépasse la plage de son type int. L’octet supplémentaire alloué pour la chaîne contient '\0'. Si la seconde allocation échoue, libère l’entrée qui n’est pas encore reliée. Le pointeur de tête de l’alvéole ne change qu’après la réussite des deux allocations et de l’initialisation.

Enregistrer e->key = key conserverait à la place l’adresse de la zone de stockage de la fonction appelante. Si l’entrée réutilise sans cesse un même tampon, chaque pointeur enregistré pourrait montrer le mot le plus récent. Copier le texte donne à chaque entrée une durée de vie indépendante de ce tampon. strdup fournit cette opération dans POSIX et C23 ; l’allocation explicite et strcpy fonctionnent en C17.

Dans un exemple à dix alvéoles utilisant la somme des codes de caractères, insérer « cat », « dog », « act » laisse « act » → « cat » dans l’alvéole 2 et « dog » dans l’alvéole 4. La recherche de « tac » parcourt l’alvéole 2, compare les deux mots et atteint NULL. Une alvéole correspondante n’est qu’un emplacement possible, pas une preuve d’égalité des clés.

Libérer les charges utiles, les nœuds et les pointeurs de tête des alvéoles

void clear_table(void) {
    for (size_t i = 0; i < N; ++i) {
        entry *e = table[i];
        while (e != NULL) {
            entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[i] = NULL;
    }
}

La sauvegarde de next et la libération de la clé ont lieu tant que l’entrée est encore valide. Réinitialiser chaque alvéole permet de la réutiliser. Les outils de vérification de la mémoire aident à vérifier les chemins exécutés ; les chemins d’échec d’allocation nécessitent aussi un nettoyage. L’ordre de hachage n’est pas un ordre trié. Pour afficher les clés par ordre alphabétique, rassemble-les pour les trier ou stocke-les dans un arbre binaire de recherche.

En adressage ouvert, la suppression nécessite un marqueur de suppression afin que la recherche traverse la case supprimée pour atteindre les clés en collision situées plus loin. Une case réellement inutilisée peut mettre fin à une recherche infructueuse. Les séquences de sondage doivent être bornées, et la table doit grandir avant que toutes les cases soient occupées.