Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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

Źródła