CKTIS / C
Recherche en profondeur (DFS) en C
Parcourez récursivement un arbre de groupes en examinant d’abord les éléments du groupe courant, puis ses sous-groupes, et en conservant au besoin un pointeur vers le groupe du premier résultat.
Version : ISO C23; implementation support may vary
Syntaxe
#include <stddef.h>
typedef struct Group {
const char *name;
const int *items;
size_t item_count;
struct Group **subs;
} Group;
static bool find_item(Group *group, int target, Group **out);find_item effectue une recherche en profondeur (DFS) dans un arbre de groupes. Chaque appel examine d’abord les éléments du groupe courant, puis visite ses sous-groupes dans l’ordre du tableau. La récursion explore un sous-arbre entier avant de passer au suivant, sauf si elle trouve la cible plus tôt. true remonte immédiatement ; false indique l’absence de résultat dans ce sous-arbre.
Dans cette structure autoréférentielle, struct Group **subs pointe vers le premier élément d’un tableau de pointeurs vers des groupes, et non vers un tableau d’objets Group. Dans la définition, l’étiquette struct Group est déjà utilisable, mais le type est encore incomplet et l’alias Group introduit par ce typedef n’est pas encore visible. La structure peut contenir un pointeur, mais pas directement un objet de son propre type.
La macro NULL, définie dans <stddef.h>, se développe en une constante de pointeur nul. subs == NULL signifie qu’il n’y a pas de tableau de sous-groupes. Dans un tableau existant, la première entrée NULL est une sentinelle de fin, pas une case vide à ignorer. Les groupes et les tableaux doivent rester en vie pendant la recherche, et le groupe trouvé tant que son pointeur est utilisé. L’absence de sentinelle peut entraîner une lecture hors limites. Pour chaque groupe dont item_count est non nul, items doit pointer vers le début d’une plage d’au moins item_count éléments de type int accessibles en lecture.
C’est l’écriture qui est facultative, pas l’argument : passez &found pour une variable de type Group *, ou NULL pour tester seulement l’existence. La fonction écrit le groupe trouvé via *out uniquement en cas de résultat et si out != NULL. Si elle renvoie false, la variable de l’appelant reste inchangée et peut encore contenir un résultat antérieur.
Dans le pire cas, le temps est en O(G + I) pour G groupes et I éléments locaux, et O(h) appels sont actifs simultanément pour un arbre de hauteur h. Pour des entrées très profondes, envisagez une pile explicite ; dans un graphe cyclique, mémorisez les nœuds visités. L’exemple utilise la syntaxe d’ISO C23 ; sa prise en charge dépend de l’implémentation.
Exemples
#include <stddef.h>
#include <stdio.h>
typedef struct Group {
const char *name;
const int *items;
size_t item_count;
struct Group **subs;
} Group;
static bool find_item(Group *group, int target, Group **out)
{
for (size_t i = 0; i < group->item_count; ++i) {
if (group->items[i] == target) {
if (out != NULL) {
*out = group;
}
return true;
}
}
if (group->subs != NULL) {
for (size_t i = 0; group->subs[i] != NULL; ++i) {
if (find_item(group->subs[i], target, out)) {
return true;
}
}
}
return false;
}
int main(void)
{
const int sevens[] = {7};
const int answers[] = {42};
Group deep = {"deep", answers, 1, NULL};
Group right = {"right", answers, 1, NULL};
Group *left_subs[] = {&deep, NULL};
Group left = {"left", sevens, 1, left_subs};
Group *root_subs[] = {&left, &right, NULL};
Group root = {"root", sevens, 1, root_subs};
Group *found = NULL;
if (find_item(&root, 7, &found)) {
printf("7 -> %s\n", found->name);
}
if (find_item(&root, 42, &found)) {
printf("42 -> %s\n", found->name);
}
printf("42 exists: %s\n", find_item(&root, 42, NULL) ? "yes" : "no");
if (!find_item(&root, 99, &found)) {
printf("99 missing; saved group: %s\n", found->name);
}
return 0;
}
Résultat
7 -> root 42 -> deep 42 exists: yes 99 missing; saved group: deep
`7` est trouvé dans `root` avant tout sous-groupe. Pour `42`, le sous-arbre `left` mène à `deep` avant toute visite de `right`. L’appel avec `NULL` teste seulement l’existence ; l’échec pour `99` laisse `found` pointer vers `deep`.
Leçons associées
- C · Leçon 79 · Avancé · Version : 3