CKTIS / C
Sebareferenčná štruktúra v C
Štruktúra `Group` odkazuje na podskupiny rovnakého typu. Prehľadávanie do hĺbky najprv kontroluje lokálne hodnoty a môže odovzdať ukazovateľ na skupinu s prvým nálezom.
Verzia: ISO C23; implementation support may vary
Syntax
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);Sebareferenčná štruktúra odkazuje pomocou ukazovateľa na objekt vlastného typu. V typedef struct Group { ... } Group; je značka Group za struct už viditeľná, ale typ zostáva neúplný až po uzatváraciu }. Člen struct Group child; preto nie je prípustný, no struct Group **subs; je platný. Značka a názov zavedený pomocou typedef patria do rôznych menných priestorov; tento alias ešte nie je dostupný vnútri zložených zátvoriek.
subs je ukazovateľ na ukazovateľ, nie pole vložené do štruktúry. V príklade ukazuje na prvý prvok samostatného poľa ukazovateľov Group *. Makro NULL je dostupné z <stddef.h>: subs == NULL znamená, že pole podskupín neexistuje, kým prvý prvok NULL v existujúcom poli označuje jeho koniec. Chýbajúca koncová značka môže viesť k čítaniu mimo hraníc poľa. Lokálne hodnoty sa naopak prechádzajú podľa value_count. Ak je value_count nenulové, values musí ukazovať na začiatok postupnosti aspoň value_count prvkov, ktoré možno čítať.
find_value prehľadáva do hĺbky (DFS): najprv skontroluje hodnoty aktuálnej skupiny, potom rekurzívne prehľadá podskupiny v poradí podľa poľa. Pri prvom náleze skončí a vráti 1; nulový ukazovateľ na skupinu alebo žiadny nález znamená 0. Odovzdaj &found, kde má found typ Group *, aby sa pri úspechu ukazovateľ na skupinu uložil cez *out_group. Ak chceš len stav, odovzdaj NULL. Pri neúspešnom hľadaní sa výstupná premenná nezmení.
Skupiny ani polia sa nekopírujú a musia existovať, kým sa používajú cez ukazovatele. Funkcia predpokladá, že neexistujú cykly; ak sú možné, eviduj navštívené skupiny. Pri veľmi hlbokých hierarchiách zváž explicitný zásobník namiesto rekurzie. Tento vzor nevyžaduje prvky zavedené v C23; podpora režimu C23 závisí od implementácie.
Príklady
#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;
}
Výsledok
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` sa nájde v `root` ešte pred prehľadávaním podskupín. Pri hľadaní `42` funkcia zostúpi cez `left` do `deep` a tam po nájdení hodnoty skončí. Ďalšia podskupina `root`, `right`, sa preto neprehľadá. Pre `9` sa výstupný ukazovateľ nežiada, a keďže sa `99` nenájde, `found` ďalej ukazuje na `deep`.
Súvisiace lekcie
- C · Lekcia 79 · Pokročilá · Verzia: 3