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