Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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

Fonti