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