CKTIS / C
Ricerca in profondità (DFS) in C
Visita ricorsivamente un albero di gruppi controllando prima gli elementi del gruppo corrente e poi i suoi sottogruppi; se serve, salva un puntatore al gruppo del primo risultato.
Versione: ISO C23; implementation support may vary
Sintassi
#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 esegue una ricerca in profondità (DFS) in un albero di gruppi. Ogni chiamata controlla prima gli elementi del gruppo corrente, poi visita i sottogruppi nell’ordine dell’array. La ricorsione esamina un intero sottoalbero prima di passare al successivo, a meno che non trovi prima il valore cercato. true viene propagato subito; false indica che quel sottoalbero non contiene corrispondenze.
Nella struttura autoreferenziale, struct Group **subs punta al primo elemento di un array di puntatori a gruppi, non a un array di oggetti Group. All’interno della definizione il tag struct Group è già utilizzabile, ma il tipo è ancora incompleto e l’alias Group di questo typedef non è ancora visibile. La struttura può avere un membro puntatore, ma non può contenere direttamente un oggetto del proprio tipo.
La macro NULL, definita in <stddef.h>, si espande in una costante di puntatore nullo. subs == NULL indica che non esiste un array di sottogruppi; se l’array esiste, il primo elemento NULL è una sentinella di fine, non un posto vuoto da saltare. Gruppi e array devono rimanere in vita durante la ricerca, e il gruppo trovato finché si usa il puntatore salvato. Se manca la sentinella, si può leggere oltre i limiti dell’array. Per ogni gruppo con item_count diverso da zero, items deve puntare all’inizio di una sequenza di almeno item_count elementi di tipo int accessibili in lettura.
È opzionale la scrittura, non l’argomento: passa &found per una variabile di tipo Group *, oppure NULL per controllare solo l’esistenza. La funzione salva il gruppo tramite *out solo se trova una corrispondenza e out != NULL. Quando restituisce false, lascia invariata la variabile del chiamante, che può ancora contenere un risultato precedente.
Nel caso peggiore il tempo è O(G + I) per G gruppi e I elementi locali; con un albero di altezza h ci sono O(h) chiamate attive contemporaneamente. Per input molto profondi, valuta una pila esplicita; in un grafo con cicli, tieni traccia dei nodi visitati. L’esempio usa la sintassi ISO C23; il supporto può variare a seconda dell’implementazione.
Esempi
#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;
}
Risultato
7 -> root 42 -> deep 42 exists: yes 99 missing; saved group: deep
`7` viene trovato in `root` prima di controllare i sottogruppi. Per `42`, il sottoalbero `left` porta a `deep` prima che venga visitato `right`. La chiamata con `NULL` controlla solo l’esistenza; la ricerca fallita di `99` lascia `found` puntare a `deep`.
Lezioni correlate
- C · Lezione 79 · Avanzato · Versione: 3