WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C

Tiefensuche (DFS) in C

Durchsuche einen Gruppenbaum rekursiv: Prüfe zuerst die Elemente der aktuellen Gruppe, dann ihre Untergruppen, und speichere bei Bedarf einen Zeiger auf die Gruppe des ersten Treffers.

Version: ISO C23; implementation support may vary

Syntax

#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 führt eine Tiefensuche (DFS) in einem Gruppenbaum aus. Jeder Aufruf prüft zuerst die eigenen Elemente der aktuellen Gruppe und besucht dann die Untergruppen in Array-Reihenfolge. Die Rekursion durchsucht einen Teilbaum vollständig, bevor sie zum nächsten wechselt, sofern sie nicht vorher fündig wird. true wird sofort nach oben weitergegeben; false bedeutet, dass der Teilbaum keinen Treffer enthält.

In der selbstreferenziellen Struktur zeigt struct Group **subs auf das erste Element eines Arrays von Gruppenzeigern, nicht auf ein Array von Group-Objekten. Innerhalb der Definition ist der Tag struct Group bereits verwendbar, der Typ aber noch unvollständig und der durch dieses typedef eingeführte Alias Group noch nicht sichtbar. Die Struktur darf einen Zeiger als Mitglied haben, aber kein Objekt ihres eigenen Typs direkt enthalten.

Das Makro NULL aus <stddef.h> expandiert zu einer Nullzeigerkonstanten. subs == NULL bedeutet, dass kein Untergruppenarray vorliegt. In einem vorhandenen Array markiert der erste NULL-Eintrag das Ende; er ist keine Lücke zum Überspringen. Gruppen und Arrays müssen während der Suche gültig bleiben, und die gefundene Gruppe muss so lange existieren, wie der gespeicherte Zeiger verwendet wird. Fehlt die Endmarke, kann außerhalb des Arrays gelesen werden. In jeder Gruppe mit item_count ungleich null muss items auf den Anfang eines Bereichs mit mindestens item_count lesbaren Elementen vom Typ int zeigen.

Optional ist das Schreiben, nicht das Argument: Übergib &found für eine Variable vom Typ Group * oder NULL, um nur die Existenz zu prüfen. Die Funktion schreibt die gefundene Gruppe nur bei einem Treffer und bei out != NULL über *out. Bei false bleibt die Variable des Aufrufers unverändert und kann noch ein früheres Ergebnis enthalten.

Im schlechtesten Fall beträgt die Laufzeit O(G + I) für G Gruppen und I lokale Elemente; bei Baumhöhe h sind O(h) Aufrufe gleichzeitig aktiv. Für sehr tiefe Eingaben bietet sich ein expliziter Stack an. Erfasse bei Graphen mit Zyklen die besuchten Knoten. Das Beispiel nutzt ISO-C23-Syntax; die Unterstützung hängt von der Implementierung ab.

Beispiele

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

Ergebnis

7 -> root
42 -> deep
42 exists: yes
99 missing; saved group: deep

`7` wird in `root` gefunden, bevor Untergruppen geprüft werden. Für `42` erreicht die Suche im Teilbaum `left` zuerst `deep` und besucht `right` nicht mehr. Der Aufruf mit `NULL` prüft nur die Existenz. Die erfolglose Suche nach `99` lässt `found` weiterhin auf `deep` zeigen.

Zugehörige Lektionen

  • C · Lektion 79 · Fortgeschritten · Version: 3

Quellen