CKTIS / C
Pesquisa em profundidade (DFS) em C
Pesquisa recursivamente numa árvore de grupos: verifica primeiro os elementos do grupo atual, depois os seus subgrupos, e guarda, se necessário, um apontador para o grupo da primeira ocorrência.
Versão: ISO C23; implementation support may vary
Sintaxe
#include <stddef.h>
typedef struct Group {
const char *name;
const int *items;
size_t item_count;
struct Group **subs;
} Group;
static bool find_item(Group *group, int target, Group **out);find_item faz uma pesquisa em profundidade (DFS) numa árvore de grupos. Cada chamada verifica primeiro os elementos do grupo atual e depois visita os subgrupos pela ordem do vetor. A recursão percorre toda uma subárvore antes de passar à seguinte, a menos que encontre primeiro o valor procurado. true propaga-se de imediato; false indica que não houve correspondência nessa subárvore.
Na estrutura autorreferencial, struct Group **subs aponta para o primeiro elemento de um vetor de apontadores para grupos, não para um vetor de objetos Group. Dentro da definição, a etiqueta struct Group já pode ser usada, mas o tipo ainda está incompleto e o nome alternativo Group deste typedef ainda não está visível. A estrutura pode ter um membro do tipo apontador, mas não pode conter diretamente um objeto do seu próprio tipo.
NULL é uma macro definida em <stddef.h> que é expandida para uma constante de apontador nulo. subs == NULL indica a ausência de um vetor de subgrupos; num vetor existente, a primeira entrada NULL é uma sentinela de fim, não uma posição vazia que possa ser ignorada. Os grupos e os vetores têm de existir durante a pesquisa, e o grupo encontrado tem de continuar a existir enquanto usares o apontador guardado. Sem a sentinela, pode ocorrer uma leitura fora dos limites. Em cada grupo cujo item_count seja diferente de zero, items tem de apontar para o início de uma sequência de pelo menos item_count elementos do tipo int que possam ser lidos.
O que é opcional é a escrita, não o argumento: passa &found para uma variável do tipo Group *, ou NULL para verificar apenas se o valor existe. A função guarda o grupo através de *out apenas se encontrar o valor e out != NULL. Se devolver false, deixa inalterada a variável de quem chamou, que pode ainda ter um resultado anterior.
No pior caso, o tempo é O(G + I) para G grupos e I elementos locais, com O(h) chamadas simultâneas para uma árvore de altura h. Para estruturas muito profundas, considera uma pilha explícita; num grafo com ciclos, regista os nós visitados. O exemplo usa sintaxe ISO C23; o suporte pode variar consoante a implementação.
Exemplos
#include <stddef.h>
#include <stdio.h>
typedef struct Group {
const char *name;
const int *items;
size_t item_count;
struct Group **subs;
} Group;
static bool find_item(Group *group, int target, Group **out)
{
for (size_t i = 0; i < group->item_count; ++i) {
if (group->items[i] == target) {
if (out != NULL) {
*out = group;
}
return true;
}
}
if (group->subs != NULL) {
for (size_t i = 0; group->subs[i] != NULL; ++i) {
if (find_item(group->subs[i], target, out)) {
return true;
}
}
}
return false;
}
int main(void)
{
const int sevens[] = {7};
const int answers[] = {42};
Group deep = {"deep", answers, 1, NULL};
Group right = {"right", answers, 1, NULL};
Group *left_subs[] = {&deep, NULL};
Group left = {"left", sevens, 1, left_subs};
Group *root_subs[] = {&left, &right, NULL};
Group root = {"root", sevens, 1, root_subs};
Group *found = NULL;
if (find_item(&root, 7, &found)) {
printf("7 -> %s\n", found->name);
}
if (find_item(&root, 42, &found)) {
printf("42 -> %s\n", found->name);
}
printf("42 exists: %s\n", find_item(&root, 42, NULL) ? "yes" : "no");
if (!find_item(&root, 99, &found)) {
printf("99 missing; saved group: %s\n", found->name);
}
return 0;
}
Resultado
7 -> root 42 -> deep 42 exists: yes 99 missing; saved group: deep
`7` é encontrado em `root` antes de serem consultados os subgrupos. Para `42`, a subárvore `left` leva a `deep` antes de `right` ser visitado. A chamada com `NULL` verifica apenas a existência; a pesquisa sem sucesso por `99` deixa `found` a apontar para `deep`.
Lições relacionadas
- C · Lição 79 · Avançado · Versão: 3