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