Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C

Prehľadávanie do hĺbky (DFS) v C

Prehľadávajte strom skupín rekurzívne: najprv skontrolujte položky aktuálnej skupiny, potom jej podskupiny, a podľa potreby uložte ukazovateľ na skupinu s prvým výskytom.

Verzia: 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 prehľadáva strom skupín do hĺbky (DFS). Každé volanie najprv skontroluje vlastné položky aktuálnej skupiny a potom navštívi podskupiny v poradí v poli. Rekurzia prehľadá celý podstrom, kým prejde k ďalšiemu, pokiaľ skôr nenájde hľadanú hodnotu. true sa ihneď odovzdáva späť; false znamená, že v danom podstrome sa zhoda nenašla.

V štruktúre odkazujúcej na vlastný typ ukazuje struct Group **subs na prvý prvok poľa ukazovateľov na skupiny, nie na pole objektov Group. Vnútri definície už možno použiť značku struct Group, ale typ je ešte neúplný a alias Group z tohto typedef ešte nie je v rozsahu platnosti. Štruktúra môže mať členský ukazovateľ, ale nesmie priamo obsahovať objekt svojho vlastného typu.

NULL je makro z <stddef.h>, ktoré sa rozvinie na konštantu nulového ukazovateľa. subs == NULL znamená, že pole podskupín neexistuje; v existujúcom poli je prvý prvok NULL koncovou značkou, nie medzerou na preskočenie. Skupiny a polia musia existovať počas vyhľadávania a nájdená skupina musí existovať po celý čas používania uloženého ukazovateľa. Chýbajúca koncová značka môže viesť k čítaniu mimo hraníc poľa. V každej skupine s nenulovým item_count musí items ukazovať na začiatok úseku s aspoň item_count prvkami typu int, ktoré možno čítať.

Voliteľný je zápis, nie argument: odovzdajte &found pre premennú typu Group * alebo NULL, ak chcete overiť iba existenciu. Funkcia uloží nájdenú skupinu cez *out, iba ak nájde zhodu a out != NULL. Pri výsledku false sa premenná volajúceho nezmení a môže stále obsahovať skorší výsledok.

V najhoršom prípade je čas O(G + I) pre G skupín a I lokálnych položiek; pri výške stromu h je súčasne aktívnych O(h) volaní. Pri veľmi hlbokých vstupoch zvážte explicitný zásobník; v grafe s cyklami evidujte navštívené uzly. Príklad používa syntax ISO C23; podpora sa môže líšiť podľa implementácie.

Prí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ýsledok

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

`7` sa nájde v `root` pred kontrolou podskupín. Pri hľadaní `42` vedie podstrom `left` do `deep` pred návštevou `right`. Volanie s `NULL` overuje iba existenciu; po neúspešnom hľadaní `99` ukazuje `found` stále na `deep`.

Súvisiace lekcie

  • C · Lekcia 79 · Pokročilá · Verzia: 3

Zdroje