Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C

Prohledávání do hloubky (DFS) v C

Prohledávejte strom skupin rekurzivně: nejdřív zkontrolujte položky aktuální skupiny, pak její podskupiny, a podle potřeby uložte ukazatel na skupinu s prvním výskytem.

Verze: ISO C23; implementation support may vary

Syntaxe

#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 prohledává strom skupin do hloubky (DFS). Každé volání nejprve zkontroluje vlastní položky aktuální skupiny a potom navštíví podskupiny v pořadí v poli. Rekurze prohledá celý podstrom, než přejde k dalšímu, pokud nenajde hledanou hodnotu dříve. true se předává ihned zpět; false znamená, že v daném podstromu nebyla nalezena shoda.

V sebeodkazující struktuře ukazuje struct Group **subs na první prvek pole ukazatelů na skupiny, nikoli na pole objektů Group. Uvnitř definice už lze použít značku struct Group, ale typ je stále neúplný a alias Group z tohoto typedef ještě není v oboru platnosti. Struktura může mít členský ukazatel, ale nesmí přímo obsahovat objekt vlastního typu.

NULL je makro z <stddef.h>, které se rozvine na konstantu nulového ukazatele. subs == NULL znamená, že pole podskupin neexistuje; v existujícím poli je první prvek NULL koncovou zarážkou, nikoli mezerou k přeskočení. Skupiny a pole musí existovat během hledání a nalezená skupina musí existovat po celou dobu používání uloženého ukazatele. Chybějící zarážka může vést ke čtení mimo meze pole. V každé skupině s nenulovým item_count musí items ukazovat na začátek úseku s alespoň item_count prvky typu int, které lze číst.

Volitelný je zápis, ne argument: předejte &found pro proměnnou typu Group *, nebo NULL, pokud chcete ověřit jen existenci. Funkce uloží nalezenou skupinu přes *out, pouze pokud najde shodu a out != NULL. Při výsledku false zůstane proměnná volajícího beze změny a může stále obsahovat předchozí výsledek.

V nejhorším případě je čas O(G + I) pro G skupin a I lokálních položek; při výšce stromu h je současně aktivních O(h) volání. Pro velmi hluboké vstupy zvažte explicitní zásobník; v grafu s cykly evidujte navštívené uzly. Příklad používá syntaxi ISO C23; podpora se může lišit podle implementace.

Příklady

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

Výsledek

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

`7` se najde v `root` dříve, než se zkontrolují podskupiny. Při hledání `42` vede podstrom `left` do `deep` ještě před návštěvou `right`. Volání s `NULL` ověřuje jen existenci; po neúspěšném hledání `99` ukazuje `found` stále na `deep`.

Související lekce

  • C · Lekce 79 · Pokročilá · Verze: 3

Zdroje