CKTIS / C
Struktura samoodwołująca się w C
Struktura `Group` przechowuje wskaźniki do podgrup tego samego typu. Wyszukiwanie w głąb sprawdza najpierw wartości lokalne i może zapisać wskaźnik do grupy z pierwszym trafieniem.
Wersja: ISO C23; implementation support may vary
Składnia
typedef struct Group {
const char *name;
const int *values;
size_t value_count;
struct Group **subs;
} Group;
static int find_value(Group *group, int wanted, Group **out_group);Struktura samoodwołująca się odwołuje się przez wskaźnik do obiektu własnego typu. W typedef struct Group { ... } Group; znacznik Group jest już widoczny po struct, ale typ pozostaje niekompletny aż do zamykającego }. Składowa struct Group child; jest więc niedozwolona, natomiast struct Group **subs; jest poprawna. Znacznik i nazwa typedef należą do różnych przestrzeni nazw; alias z tej deklaracji nie jest jeszcze dostępny w jej wnętrzu.
subs to wskaźnik do wskaźnika, a nie tablica osadzona w strukturze. W przykładzie wskazuje pierwszy element osobnej tablicy wskaźników Group *. Makro NULL jest dostępne w <stddef.h>: subs == NULL oznacza brak tablicy podgrup, a pierwszy element równy NULL kończy przeglądanie istniejącej tablicy. Brak znacznika końca może doprowadzić do odczytu poza granicami tablicy. Wartości lokalne są natomiast przeglądane według value_count. Jeśli value_count jest większe od zera, values musi wskazywać na początek obszaru zawierającego co najmniej value_count elementów dostępnych do odczytu.
find_value wykonuje wyszukiwanie w głąb (DFS): najpierw sprawdza wartości bieżącej grupy, potem rekurencyjnie przeszukuje podgrupy w kolejności tablicy. Kończy się przy pierwszym trafieniu i zwraca 1; dla pustego wskaźnika do grupy lub braku trafienia zwraca 0. Podaj &found, gdzie found ma typ Group *, aby przy sukcesie zapisać wskaźnik przez *out_group, albo NULL, aby otrzymać tylko wynik wyszukiwania. Przy braku trafienia zmienna wyjściowa pozostaje bez zmian.
Grupy i tablice nie są kopiowane i muszą pozostawać przy życiu, dopóki są używane przez wskaźniki. Funkcja zakłada brak cykli; jeśli są możliwe, zapamiętuj odwiedzone grupy. Dla bardzo głębokich hierarchii rozważ jawny stos zamiast rekurencji. Ten wzorzec nie wymaga funkcji wprowadzonych w C23; obsługa trybu C23 zależy od implementacji.
Przykłady
#include <stddef.h>
#include <stdio.h>
typedef struct Group {
const char *name;
const int *values;
size_t value_count;
struct Group **subs;
} Group;
static int find_value(Group *group, int wanted, Group **out_group)
{
if (group == NULL)
return 0;
for (size_t i = 0; i < group->value_count; ++i) {
if (group->values[i] == wanted) {
if (out_group != NULL)
*out_group = group;
return 1;
}
}
if (group->subs != NULL) {
for (size_t i = 0; group->subs[i] != NULL; ++i) {
if (find_value(group->subs[i], wanted, out_group))
return 1;
}
}
return 0;
}
int main(void)
{
const int root_values[] = {7, 9};
const int deep_values[] = {7, 42};
const int right_values[] = {42};
Group deep = {"deep", deep_values, 2, NULL};
Group right = {"right", right_values, 1, NULL};
Group *left_subs[] = {&deep, NULL};
Group left = {"left", NULL, 0, left_subs};
Group *root_subs[] = {&left, &right, NULL};
Group root = {"root", root_values, 2, root_subs};
Group *found = NULL;
if (find_value(&root, 7, &found))
printf("7: %s\n", found->name);
if (find_value(&root, 42, &found))
printf("42: %s\n", found->name);
if (find_value(&root, 9, NULL))
puts("9: found without output parameter");
if (!find_value(&root, 99, &found))
printf("99: not found; previous result: %s\n", found->name);
return 0;
}
Wynik
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` zostaje znalezione w `root` przed przeszukaniem podgrup. Przy szukaniu `42` funkcja najpierw przeszukuje podgrupę `left` i schodzi do `deep`. Trafienie w `deep` kończy wyszukiwanie, więc następna w kolejności podgrupa `right` nie jest sprawdzana. Dla `9` nie żądamy zapisu wskaźnika, a brak `99` pozostawia `found` wskazujący na `deep`.
Powiązane lekcje
- C · Lekcja 79 · Zaawansowany · Wersja: 3