CKTIS / C
Structure autoréférentielle en C
Une structure `Group` pointe vers des sous-groupes du même type. La recherche en profondeur examine d’abord les valeurs locales et peut indiquer le groupe de la première correspondance.
Version : ISO C23; implementation support may vary
Syntaxe
typedef struct Group {
const char *name;
const int *values;
size_t value_count;
struct Group **subs;
} Group;
static int find_value(Group *group, int wanted, Group **out_group);Une structure autoréférentielle utilise un pointeur pour désigner un objet de son propre type. Dans typedef struct Group { ... } Group;, l’étiquette Group est déjà visible après struct, mais le type reste incomplet jusqu’à l’accolade fermante }. Le membre struct Group child; est donc interdit, alors que struct Group **subs; est valide. L’étiquette et le nom de typedef sont dans des espaces de noms distincts ; l’alias introduit ici n’est pas encore disponible à l’intérieur des accolades.
subs est un pointeur vers un pointeur, et non un tableau intégré à la structure. Dans l’exemple, il pointe vers le premier élément d’un tableau distinct de pointeurs Group *. La macro NULL est disponible dans <stddef.h> : subs == NULL signifie qu’il n’y a pas de tableau de sous-groupes, tandis que le premier élément NULL d’un tableau existant en marque la fin. Sans cette sentinelle, une lecture hors limites est possible. Les valeurs locales sont, elles, parcourues selon value_count. Si value_count est non nul, values doit pointer vers le début d’une suite d’au moins value_count éléments accessibles en lecture.
find_value effectue une recherche en profondeur (DFS) : elle examine d’abord les valeurs du groupe courant, puis parcourt récursivement les sous-groupes dans l’ordre du tableau. Elle s’arrête à la première correspondance et renvoie 1 ; un pointeur de groupe nul ou l’absence de correspondance donne 0. Passez &found, où found est de type Group *, pour recevoir le pointeur du groupe via *out_group en cas de succès. Passez NULL pour obtenir uniquement le statut. En cas d’échec, la variable de sortie reste inchangée.
Les groupes et les tableaux ne sont pas copiés et doivent rester en vie tant qu’ils sont utilisés via des pointeurs. La fonction suppose l’absence de cycles ; si des cycles sont possibles, mémorisez les groupes déjà visités. Pour une hiérarchie très profonde, envisagez une pile explicite plutôt que la récursion. Ce modèle ne requiert aucune nouveauté de C23 ; la prise en charge du mode C23 dépend de l’implémentation.
Exemples
#include <stddef.h>
#include <stdio.h>
typedef struct Group {
const char *name;
const int *values;
size_t value_count;
struct Group **subs;
} Group;
static int find_value(Group *group, int wanted, Group **out_group)
{
if (group == NULL)
return 0;
for (size_t i = 0; i < group->value_count; ++i) {
if (group->values[i] == wanted) {
if (out_group != NULL)
*out_group = group;
return 1;
}
}
if (group->subs != NULL) {
for (size_t i = 0; group->subs[i] != NULL; ++i) {
if (find_value(group->subs[i], wanted, out_group))
return 1;
}
}
return 0;
}
int main(void)
{
const int root_values[] = {7, 9};
const int deep_values[] = {7, 42};
const int right_values[] = {42};
Group deep = {"deep", deep_values, 2, NULL};
Group right = {"right", right_values, 1, NULL};
Group *left_subs[] = {&deep, NULL};
Group left = {"left", NULL, 0, left_subs};
Group *root_subs[] = {&left, &right, NULL};
Group root = {"root", root_values, 2, root_subs};
Group *found = NULL;
if (find_value(&root, 7, &found))
printf("7: %s\n", found->name);
if (find_value(&root, 42, &found))
printf("42: %s\n", found->name);
if (find_value(&root, 9, NULL))
puts("9: found without output parameter");
if (!find_value(&root, 99, &found))
printf("99: not found; previous result: %s\n", found->name);
return 0;
}
Résultat
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` est trouvé dans `root` avant tout parcours des sous-groupes. Pour `42`, la recherche descend par `left` jusqu’à `deep` et s’y arrête dès qu’elle trouve la valeur. Le sous-groupe suivant de `root`, `right`, n’est donc pas examiné. Pour `9`, aucun pointeur de sortie n’est demandé ; l’absence de `99` laisse `found` pointer vers `deep`.
Leçons associées
- C · Leçon 79 · Avancé · Version : 3