Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C

Przeszukiwanie w głąb (DFS) w C

Przeszukuj drzewo grup rekurencyjnie: najpierw sprawdzaj elementy bieżącej grupy, potem jej podgrupy, i opcjonalnie zapisz wskaźnik do grupy z pierwszym trafieniem.

Wersja: ISO C23; implementation support may vary

Składnia

#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 realizuje przeszukiwanie w głąb (DFS) drzewa grup. Każde wywołanie najpierw sprawdza elementy własnej grupy, a potem odwiedza podgrupy w kolejności tablicy. Rekurencja przeszukuje całe poddrzewo przed przejściem do następnej podgrupy, chyba że wcześniej znajdzie cel. Pierwsze true jest przekazywane w górę bez dalszego szukania; false oznacza brak trafienia w danym poddrzewie.

W samoodwołującej się strukturze struct Group **subs wskazuje na pierwszy element tablicy wskaźników do grup, a nie na tablicę obiektów Group. Wewnątrz definicji znacznik struct Group jest już dostępny, lecz typ jest jeszcze niekompletny, a alias Group z tej deklaracji typedef nie jest jeszcze dostępny. Składowa może być wskaźnikiem, ale nie może zawierać obiektu własnego typu bezpośrednio.

NULL to makro z <stddef.h> oznaczające stałą wskaźnika pustego. subs == NULL oznacza brak tablicy podgrup; w istniejącej tablicy pierwszy element NULL jest wartownikiem końca, nie pustym miejscem do pominięcia. Grupy i tablice muszą istnieć podczas szukania, a użycie zwróconego wskaźnika wymaga, by wskazywana grupa nadal istniała. Brak wartownika może doprowadzić do odczytu poza tablicą. W każdej grupie z niezerowym item_count wskaźnik items musi wskazywać na początek zakresu co najmniej item_count elementów typu int dostępnych do odczytu.

Opcjonalny jest zapis, nie argument: przekaż &found, gdzie found ma typ Group *, albo przekaż NULL, by sprawdzić tylko istnienie celu. Tylko przy trafieniu i out != NULL funkcja zapisuje grupę przez *out. Przy false nie zmienia zmiennej wywołującego, która może nadal zawierać wcześniejszy wynik.

W najgorszym przypadku czas to O(G + I) dla G grup i I elementów lokalnych, a liczba jednoczesnych wywołań to O(h) dla wysokości drzewa h. Dla bardzo głębokich danych rozważ jawny stos; w grafie z cyklami rejestruj odwiedzone węzły. Przykład używa składni ISO C23; obsługa zależy od implementacji.

Przykłady

#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;
}

Wynik

7 -> root
42 -> deep
42 exists: yes
99 missing; saved group: deep

`7` zostaje znalezione w `root` przed sprawdzeniem podgrup. Dla `42` poddrzewo `left` prowadzi do `deep` przed odwiedzeniem `right`. Wywołanie z `NULL` sprawdza tylko istnienie, a brak `99` pozostawia w `found` wskaźnik do `deep`.

Powiązane lekcje

  • C · Lekcja 79 · Zaawansowany · Wersja: 3

Źródła