Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / C

Estructura autorreferencial en C

Una estructura `Group` apunta a subgrupos de su mismo tipo. La búsqueda en profundidad revisa primero los valores locales y puede indicar el grupo de la primera coincidencia.

Versión: ISO C23; implementation support may vary

Sintaxis

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

Una estructura autorreferencial usa un puntero para referirse a un objeto de su propio tipo. En typedef struct Group { ... } Group;, la etiqueta Group ya es visible tras struct, pero el tipo sigue incompleto hasta la llave de cierre }. Por eso, el miembro struct Group child; no es válido, mientras que struct Group **subs; sí lo es. La etiqueta y el nombre de typedef pertenecen a espacios de nombres distintos; el alias declarado aquí aún no está disponible dentro de las llaves.

subs es un puntero a un puntero, no un array incluido en la estructura. En el ejemplo, apunta al primer elemento de un array separado de punteros Group *. La macro NULL está disponible en <stddef.h>: subs == NULL indica que no hay array de subgrupos, mientras que el primer elemento NULL de un array existente marca su final. Si falta este centinela, se puede leer fuera de los límites del array. En cambio, los valores locales se recorren según value_count. Si value_count no es cero, values debe apuntar al inicio de una secuencia de al menos value_count elementos accesibles para lectura.

find_value realiza una búsqueda en profundidad (DFS): primero revisa los valores del grupo actual y luego busca de forma recursiva en los subgrupos, en el orden del array. Se detiene en la primera coincidencia y devuelve 1; si el puntero al grupo es nulo o no hay coincidencia, devuelve 0. Pasa &found, donde found es de tipo Group *, para recibir el puntero al grupo mediante *out_group si hay éxito. Pasa NULL si solo quieres el estado. Si no hay coincidencia, la variable de salida no cambia.

Los grupos y los arrays no se copian y deben seguir vivos mientras se usen a través de punteros. La función presupone que no hay ciclos; si puede haberlos, registra los grupos visitados. Para jerarquías muy profundas, considera usar una pila explícita en lugar de recursión. Este patrón no requiere ninguna característica introducida en C23; la compatibilidad con el modo C23 depende de la implementación.

Ejemplos

#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` se encuentra en `root` antes de buscar en los subgrupos. Para `42`, la búsqueda baja por `left` hasta `deep` y se detiene al encontrar el valor allí. Por tanto, no se revisa `right`, el siguiente subgrupo de `root`. Para `9` no se solicita un puntero de salida; al no encontrar `99`, `found` sigue apuntando a `deep`.

Lecciones relacionadas

  • C · Lección 79 · Avanzado · Versión: 3

Fuentes