CKTIS / C
Самореферираща структура в C
Структурата `Group` сочи към подгрупи от същия тип. Търсенето в дълбочина проверява първо локалните стойности и може да запише указател към групата с първото съвпадение.
Версия: ISO C23; implementation support may vary
Синтаксис
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);Саморефериращата структура използва указател, за да сочи към обект от собствения си тип. В typedef struct Group { ... } Group; тагът Group вече е видим след struct, но типът остава непълен до затварящата }. Затова член struct Group child; е недопустим, а struct Group **subs; е допустим. Тагът и името от typedef са в различни пространства от имена; въведеният тук псевдоним още не е достъпен между фигурните скоби.
subs е указател към указател, а не масив, вграден в структурата. В примера той сочи към първия елемент на отделен масив от указатели Group *. Макросът NULL е достъпен чрез <stddef.h>: subs == NULL означава, че няма масив от подгрупи, а първият елемент NULL в съществуващ масив отбелязва края му. Без този маркер може да се стигне до четене извън границите на масива. За обхождането на локалните стойности вместо това се използва value_count. Ако value_count е различно от нула, values трябва да сочи към началото на последователност от поне value_count елемента, които могат да се четат.
find_value извършва търсене в дълбочина (DFS): първо проверява стойностите на текущата група, а после търси рекурсивно в подгрупите по реда им в масива. Спира при първото съвпадение и връща 1; нулев указател към група или липса на съвпадение води до резултат 0. Подай &found, където found е от тип Group *, за да се запише при успех указател към групата чрез *out_group. Подай NULL, ако ти трябва само резултатът от проверката. При липса на съвпадение изходната променлива остава непроменена.
Групите и масивите не се копират и трябва да съществуват, докато се използват чрез указателите. Функцията предполага, че няма цикли; ако са възможни, отбелязвай посетените групи. При много дълбоки йерархии обмисли използването на явен стек вместо рекурсия. Този модел не изисква нововъведения от C23; поддръжката на режим C23 зависи от реализацията.
Примери
#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;
}
Резултат
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` се намира в `root`, преди да се претърсят подгрупите. При търсенето на `42` функцията слиза през `left` до `deep` и спира там при съвпадението. Затова `right`, следващата подгрупа на `root`, не се проверява. За `9` не се изисква запис на указател, а тъй като `99` не се намира, `found` продължава да сочи към `deep`.
Свързани уроци
- C · Урок 79 · Напреднало · Версия: 3