KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C

Zelfverwijzende structuur in C

Een `Group`-structuur verwijst naar subgroepen van hetzelfde type. Diepte-eerst zoeken controleert eerst de lokale waarden en kan de groep van de eerste treffer terugmelden.

Versie: ISO C23; implementation support may vary

Syntax

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

Een zelfverwijzende structuur gebruikt een pointer om naar een object van het eigen type te verwijzen. In typedef struct Group { ... } Group; is de tag Group na struct al zichtbaar, maar het type is pas compleet bij de afsluitende }. Een lid struct Group child; is daarom ongeldig, terwijl struct Group **subs; geldig is. De tag en de typedef-naam staan in verschillende naamruimten; de hier ingevoerde alias is binnen de accolades nog niet beschikbaar.

subs is een pointer naar een pointer, geen ingebedde array. In het voorbeeld wijst deze naar het eerste element van een aparte array met Group *-pointers. De macro NULL is beschikbaar via <stddef.h>: subs == NULL betekent dat er geen subgroeparray is, terwijl het eerste NULL-element in een bestaande array het einde markeert. Zonder die eindmarkering kan de functie buiten de arraygrenzen lezen. De lokale waarden worden daarentegen doorlopen op basis van value_count. Als value_count niet nul is, moet values naar het begin van een reeks van ten minste value_count leesbare elementen wijzen.

find_value zoekt diepte-eerst (DFS): de functie controleert eerst de waarden van de huidige groep en doorzoekt daarna recursief de subgroepen in arrayvolgorde. Ze stopt bij de eerste treffer en geeft 1 terug; een nulpointer als groepsargument of geen treffer levert 0 op. Geef &found mee, waarbij found het type Group * heeft, om bij succes de groepspointer via *out_group op te slaan. Geef NULL mee als je alleen de status wilt. Zonder treffer blijft de uitvoervariabele ongewijzigd.

De groepen en arrays worden niet gekopieerd en moeten blijven bestaan zolang ze via pointers worden gebruikt. De functie gaat ervan uit dat er geen cycli zijn; houd bezochte groepen bij als cycli mogelijk zijn. Overweeg bij zeer diepe hiërarchieën een expliciete stack in plaats van recursie. Dit patroon vereist geen nieuwe C23-functionaliteit; ondersteuning voor de C23-modus hangt af van de implementatie.

Voorbeelden

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

Resultaat

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

`7` wordt in `root` gevonden voordat een subgroep wordt doorzocht. Voor `42` daalt de zoekactie via `left` af naar `deep` en stopt daar bij de treffer. Daardoor wordt `right`, de volgende subgroep van `root`, niet gecontroleerd. Voor `9` wordt geen uitvoerpointer gevraagd; doordat `99` niet wordt gevonden, blijft `found` naar `deep` wijzen.

Gerelateerde lessen

  • C · Les 79 · Gevorderd · Versie: 3

Bronnen