CKTIS / C
Selbstreferenzielle Struktur in C
Eine `Group`-Struktur verweist auf Untergruppen desselben Typs. Die Tiefensuche prüft zuerst lokale Werte und kann die Gruppe mit dem ersten Treffer melden.
Version: 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);Eine selbstreferenzielle Struktur verweist über einen Zeiger auf ein Objekt ihres eigenen Typs. In typedef struct Group { ... } Group; ist der Tag Group nach struct bereits sichtbar, doch der Typ bleibt bis zur schließenden } unvollständig. Das Mitglied struct Group child; ist daher unzulässig, struct Group **subs; dagegen zulässig. Tag und Typedef-Name gehören zu unterschiedlichen Namensräumen; der hier eingeführte Alias ist innerhalb der geschweiften Klammern noch nicht verfügbar.
subs ist ein Zeiger auf einen Zeiger, kein eingebettetes Array. Im Beispiel zeigt er auf das erste Element eines separaten Arrays aus Group *-Zeigern. Das Makro NULL steht in <stddef.h> zur Verfügung: subs == NULL bedeutet, dass es kein Untergruppenarray gibt. In einem vorhandenen Array markiert das erste NULL-Element das Ende. Fehlt diese Endmarkierung, kann über die Arraygrenze hinaus gelesen werden. Die lokalen Werte werden dagegen anhand von value_count durchsucht. Ist value_count größer als null, muss values auf den Anfang einer Folge von mindestens value_count lesbaren Elementen zeigen.
find_value führt eine Tiefensuche (DFS) aus: Zuerst prüft die Funktion die Werte der aktuellen Gruppe, dann durchsucht sie die Untergruppen rekursiv in Arrayreihenfolge. Beim ersten Treffer bricht sie ab und liefert 1; ein Nullzeiger als Gruppe oder kein Treffer ergibt 0. Übergib &found, wobei found den Typ Group * hat, damit bei Erfolg der Gruppenzeiger über *out_group gespeichert wird. Übergib NULL, wenn nur der Status gebraucht wird. Ohne Treffer bleibt die Ausgabevariable unverändert.
Gruppen und Arrays werden nicht kopiert und müssen während ihrer Nutzung über Zeiger gültig bleiben. Die Funktion setzt Zyklenfreiheit voraus; wenn Zyklen möglich sind, merke dir bereits besuchte Gruppen. Für sehr tiefe Hierarchien kommt ein expliziter Stack statt Rekursion infrage. Das Muster benötigt keine in C23 eingeführten Sprachmerkmale; die Unterstützung des C23-Modus hängt von der Implementierung ab.
Beispiele
#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;
}
Ergebnis
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` wird in `root` gefunden, noch bevor eine Untergruppe durchsucht wird. Bei der Suche nach `42` gelangt die Funktion über `left` zu `deep` und bricht dort beim Treffer ab. Die nächste Untergruppe von `root`, `right`, wird daher nicht geprüft. Für `9` wird kein Ausgabezeiger angefordert; bei der erfolglosen Suche nach `99` zeigt `found` weiterhin auf `deep`.
Zugehörige Lektionen
- C · Lektion 79 · Fortgeschritten · Version: 3