Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C

Pretraživanje u dubinu (DFS) u C-u

Rekurzivno pretraži stablo grupa: prvo provjeri elemente trenutačne grupe, zatim njezine podgrupe, i po potrebi spremi pokazivač na grupu u kojoj je pronađeno prvo podudaranje.

Verzija: ISO C23; implementation support may vary

Sintaksa

#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 pretražuje stablo grupa u dubinu (DFS). Svaki poziv prvo provjerava vlastite elemente trenutačne grupe, a zatim posjećuje podgrupe redoslijedom u polju. Rekurzija pretražuje cijelo podstablo prije prelaska na sljedeće, osim ako prije pronađe traženu vrijednost. true se odmah prenosi natrag kroz pozive; false znači da u tom podstablu nema podudaranja.

U strukturi koja upućuje na vlastiti tip, struct Group **subs pokazuje na prvi element polja pokazivača na grupe, a ne na polje objekata Group. Unutar definicije oznaka struct Group već se može upotrijebiti, no tip je još nepotpun, a ime Group iz te deklaracije typedef još nije vidljivo. Struktura može sadržavati pokazivač kao član, ali ne može izravno sadržavati objekt vlastitog tipa.

NULL je makronaredba iz <stddef.h> koja se proširuje u konstantu nul-pokazivača. subs == NULL znači da nema polja podgrupa; u postojećem polju prvi element NULL označava kraj, a ne prazno mjesto koje treba preskočiti. Grupe i polja moraju postojati tijekom pretraživanja, a pronađena grupa dok god se rabi spremljeni pokazivač. Ako nedostaje oznaka kraja, moguće je čitanje izvan granica polja. U svakoj grupi u kojoj item_count nije nula, items mora pokazivati na početak niza od najmanje item_count elemenata tipa int koji se mogu čitati.

Neobavezan je upis, a ne argument: proslijedi &found za varijablu tipa Group * ili NULL za provjeru samog postojanja. Funkcija sprema pronađenu grupu preko *out samo ako nađe podudaranje i ako je out != NULL. Ako vrati false, varijabla pozivatelja ostaje nepromijenjena i može još sadržavati prethodni rezultat.

U najgorem slučaju vrijeme je O(G + I) za G grupa i I lokalnih elemenata, uz O(h) istodobno aktivnih poziva za visinu stabla h. Za vrlo duboke ulaze razmotri eksplicitni stog; u grafu s ciklusima bilježi posjećene čvorove. Primjer koristi sintaksu ISO C23; podrška ovisi o implementaciji.

Primjeri

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

Rezultat

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

`7` se pronalazi u `root` prije pregleda podgrupa. Pri traženju `42`, podstablo `left` vodi do `deep` prije posjeta grupi `right`. Poziv s `NULL` provjerava samo postojanje; nakon neuspješne potrage za `99`, `found` i dalje pokazuje na `deep`.

Povezane lekcije

  • C · Lekcija 79 · Napredno · Verzija: 3

Izvori