База знанияИзпитен център
BGБългарски
Избери език13

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

Източници