CKTIS / C
Samoreferenčna struktura v C-ju
Struktura `Group` kaže na podskupine istega tipa. Iskanje v globino najprej preveri lokalne vrednosti in lahko vrne kazalec na skupino s prvim zadetkom.
Različica: 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);Samoreferenčna struktura se prek kazalca sklicuje na objekt svojega tipa. V typedef struct Group { ... } Group; je oznaka Group za struct že vidna, tip pa je do zaključnega } nepopoln. Član struct Group child; zato ni dovoljen, struct Group **subs; pa je veljaven. Oznaka in ime, uvedeno s typedef, sta v različnih imenskih prostorih; ta vzdevek znotraj zavitih oklepajev še ni na voljo.
subs je kazalec na kazalec, ne polje, vgrajeno v strukturo. V primeru kaže na prvi element ločenega polja kazalcev Group *. Makro NULL je na voljo v <stddef.h>: subs == NULL pomeni, da polja podskupin ni, prvi element NULL v obstoječem polju pa označuje njegov konec. Če ta oznaka manjka, lahko pride do branja zunaj meja polja. Lokalne vrednosti se nasprotno pregledujejo glede na value_count. Če value_count ni nič, mora values kazati na začetek zaporedja vsaj value_count elementov, ki jih je mogoče prebrati.
find_value išče v globino (DFS): najprej preveri vrednosti trenutne skupine, nato rekurzivno preišče podskupine po vrstnem redu v polju. Ustavi se pri prvem zadetku in vrne 1; če je kazalec na skupino ničeln ali zadetka ni, vrne 0. Podaj &found, kjer ima found tip Group *, da se ob uspehu prek *out_group shrani kazalec na skupino. Če želiš le status, podaj NULL. Če zadetka ni, izhodna spremenljivka ostane nespremenjena.
Skupine in polja se ne kopirajo in morajo obstajati, dokler se uporabljajo prek kazalcev. Funkcija predpostavlja, da ni ciklov; če so mogoči, beleži že obiskane skupine. Pri zelo globokih hierarhijah razmisli o eksplicitnem skladu namesto rekurzije. Ta vzorec ne zahteva novosti iz C23; podpora za način C23 je odvisna od implementacije.
Primeri
#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` je najden v `root`, še preden se preišče katera koli podskupina. Pri iskanju `42` se funkcija spusti prek `left` do `deep` in se ob zadetku ustavi. Naslednje podskupine `root`, `right`, zato ne preveri. Za `9` izhodni kazalec ni zahtevan; ker `99` ni najden, `found` še vedno kaže na `deep`.
Povezane lekcije
- C · Lekcija 79 · Napredna · Različica: 3