CKTIS / C
Sebereferenční struktura v C
Struktura `Group` odkazuje na podskupiny stejného typu. Prohledávání do hloubky nejprve kontroluje místní hodnoty a může předat ukazatel na skupinu s prvním nálezem.
Verze: ISO C23; implementation support may vary
Syntaxe
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);Sebereferenční struktura odkazuje pomocí ukazatele na objekt vlastního typu. V typedef struct Group { ... } Group; je značka Group za struct už viditelná, ale typ je až do uzavírací } neúplný. Člen struct Group child; je proto nepřípustný, zatímco struct Group **subs; je platný. Značka a jméno zavedené pomocí typedef patří do různých jmenných prostorů; tento alias uvnitř složených závorek ještě není dostupný.
subs je ukazatel na ukazatel, nikoli pole vložené do struktury. V příkladu ukazuje na první prvek samostatného pole ukazatelů Group *. Makro NULL je dostupné z <stddef.h>: subs == NULL znamená, že pole podskupin neexistuje, zatímco první prvek NULL v existujícím poli označuje jeho konec. Chybějící koncová značka může vést ke čtení mimo meze pole. Místní hodnoty se naopak procházejí podle value_count. Pokud je value_count nenulové, musí values ukazovat na začátek posloupnosti nejméně value_count prvků, které lze číst.
find_value prohledává do hloubky (DFS): nejprve zkontroluje hodnoty aktuální skupiny, pak rekurzivně prohledá podskupiny v pořadí podle pole. Při prvním nálezu skončí a vrátí 1; nulový ukazatel na skupinu nebo žádný nález znamená 0. Předej &found, kde má found typ Group *, aby se při úspěchu ukazatel na skupinu uložil přes *out_group. Pokud chceš jen stav, předej NULL. Při neúspěšném hledání se výstupní proměnná nezmění.
Skupiny ani pole se nekopírují a musí existovat po celou dobu, kdy se používají přes ukazatele. Funkce předpokládá, že neexistují cykly; pokud jsou možné, eviduj navštívené skupiny. U velmi hlubokých hierarchií zvaž explicitní zásobník namísto rekurze. Tento vzor nevyžaduje novinky zavedené v C23; podpora režimu C23 závisí na implementaci.
Pří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ýsledek
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` se najde v `root` ještě před prohledáním podskupin. Při hledání `42` funkce sestoupí přes `left` do `deep` a tam po nalezení hodnoty skončí. Další podskupina `root`, `right`, se proto neprohledá. Pro `9` se výstupní ukazatel nepožaduje, a protože se `99` nenajde, `found` dál ukazuje na `deep`.
Související lekce
- C · Lekce 79 · Pokročilá · Verze: 3