Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

Samoreferencijalna struktura u C-u

Struktura `Group` pokazuje na podgrupe istog tipa. Pretraživanje u dubinu prvo provjerava lokalne vrijednosti i može predati pokazivač na grupu s prvim pogotkom.

Verzija: ISO C23; implementation support may vary

Sintaksa

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);

Samoreferencijalna struktura pokazivačem upućuje na objekt vlastitog tipa. U typedef struct Group { ... } Group; oznaka Group već je vidljiva nakon struct, ali tip ostaje nepotpun do zatvarajuće }. Član struct Group child; stoga nije dopušten, a struct Group **subs; jest. Oznaka i ime uvedeno pomoću typedef pripadaju različitim imenskim prostorima; taj alias još nije dostupan unutar vitičastih zagrada.

subs je pokazivač na pokazivač, a ne polje ugrađeno u strukturu. U primjeru pokazuje na prvi element zasebnog polja pokazivača Group *. Makro NULL dostupan je iz <stddef.h>: subs == NULL znači da polja podgrupa nema, dok prvi element NULL u postojećem polju označava kraj. Bez te oznake može doći do čitanja izvan granica polja. Lokalne se vrijednosti, nasuprot tome, obilaze prema value_count. Ako value_count nije nula, values mora pokazivati na početak niza od najmanje value_count elemenata koji se mogu čitati.

find_value pretražuje u dubinu (DFS): najprije provjerava vrijednosti trenutačne grupe, a zatim rekurzivno pretražuje podgrupe redom iz polja. Zaustavlja se na prvom pogotku i vraća 1; ako je pokazivač na grupu nul-pokazivač ili nema pogotka, vraća 0. Proslijedi &found, pri čemu je found tipa Group *, da se pri uspjehu preko *out_group spremi pokazivač na grupu. Proslijedi NULL ako želiš samo status. Ako nema pogotka, izlazna varijabla ostaje nepromijenjena.

Grupe i polja ne kopiraju se i moraju postojati dok se rabe preko pokazivača. Funkcija pretpostavlja da nema ciklusa; ako su mogući, bilježi posjećene grupe. Za vrlo duboke hijerarhije razmotri eksplicitan stog umjesto rekurzije. Ovaj obrazac ne zahtijeva novosti uvedene u C23; podrška za način rada C23 ovisi o implementaciji.

Primjeri

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

Rezultat

7: root
42: deep
9: found without output parameter
99: not found; previous result: deep

`7` se nalazi u `root` prije pretraživanja podgrupa. Pri traženju `42` funkcija se spušta preko `left` do `deep` i ondje se zaustavlja kad pronađe vrijednost. Zato ne provjerava `right`, sljedeću podgrupu grupe `root`. Za `9` izlazni se pokazivač ne traži; budući da `99` nije pronađen, `found` i dalje pokazuje na `deep`.

Povezane lekcije

  • C · Lekcija 79 · Napredno · Verzija: 3

Izvori