Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C

Estrutura autorreferencial em C

Uma estrutura `Group` aponta para subgrupos do mesmo tipo. A pesquisa em profundidade verifica primeiro os valores locais e pode indicar em que grupo ocorre a primeira correspondência.

Versão: ISO C23; implementation support may vary

Sintaxe

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);

Uma estrutura autorreferencial usa um ponteiro para referenciar um objeto do seu próprio tipo. Em typedef struct Group { ... } Group;, a etiqueta Group já está visível após struct, mas o tipo continua incompleto até à chaveta de fecho }. O membro struct Group child; é, por isso, inválido, ao passo que struct Group **subs; é válido. A etiqueta e o nome de typedef pertencem a espaços de nomes distintos; o alias aqui introduzido ainda não está disponível dentro das chavetas.

subs é um ponteiro para um ponteiro, não um vetor incorporado na estrutura. No exemplo, aponta para o primeiro elemento de um vetor separado de ponteiros Group *. A macro NULL está disponível em <stddef.h>: subs == NULL significa que não há vetor de subgrupos, enquanto o primeiro elemento NULL de um vetor existente marca o seu fim. A falta desta sentinela pode levar a uma leitura fora dos limites do vetor. Já os valores locais são percorridos de acordo com value_count. Se value_count for diferente de zero, values tem de apontar para o início de uma sequência de pelo menos value_count elementos que possam ser lidos.

find_value faz uma pesquisa em profundidade (DFS): verifica primeiro os valores do grupo atual e depois pesquisa recursivamente os subgrupos pela ordem do vetor. Para na primeira correspondência e devolve 1; um ponteiro nulo para o grupo ou a ausência de correspondência dá 0. Passa &found, sendo found do tipo Group *, para receber o ponteiro para o grupo através de *out_group em caso de sucesso. Passa NULL se só quiseres saber o resultado. Se não houver correspondência, a variável de saída mantém-se inalterada.

Os grupos e os vetores não são copiados e devem manter-se vivos enquanto forem usados através dos ponteiros. A função pressupõe que não há ciclos; se forem possíveis, regista os grupos visitados. Em hierarquias muito profundas, pondera usar uma pilha explícita em vez de recursão. Este padrão não requer funcionalidades introduzidas no C23; o suporte do modo C23 depende da implementação.

Exemplos

#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;
}

Resultado

7: root
42: deep
9: found without output parameter
99: not found; previous result: deep

`7` é encontrado em `root` antes de se pesquisar qualquer subgrupo. Para `42`, a pesquisa desce por `left` até `deep` e termina ao encontrar aí o valor. Por isso, `right`, o subgrupo seguinte de `root`, não é verificado. Para `9`, não se pede um ponteiro de saída; como não se encontra `99`, `found` continua a apontar para `deep`.

Lições relacionadas

  • C · Lição 79 · Avançado · Versão: 3

Fontes