CKTIS / C
Iskanje v globino (DFS) v C-ju
Rekurzivno preišči drevo skupin: najprej preveri elemente trenutne skupine, nato njene podskupine, in po potrebi shrani kazalec na skupino s prvim zadetkom.
Različica: 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 izvaja iskanje v globino (DFS) v drevesu skupin. Vsak klic najprej preveri elemente trenutne skupine, nato obišče podskupine po vrstnem redu v tabeli. Rekurzija preišče celotno poddrevo, preden preide na naslednje, razen če prej najde iskano vrednost. true se takoj prenese nazaj po verigi klicev; false pomeni, da v tem poddrevesu ni zadetka.
V samonanašalni strukturi struct Group **subs kaže na prvi element tabele kazalcev na skupine, ne na tabelo objektov Group. Znotraj definicije je oznaka struct Group že uporabna, vendar je tip še nepopoln, ime Group iz te deklaracije typedef pa še ni vidno. Struktura lahko vsebuje kazalec, ne more pa neposredno vsebovati objekta lastnega tipa.
NULL je makro iz <stddef.h>, ki se razširi v konstanto ničelnega kazalca. subs == NULL pomeni, da tabele podskupin ni; v obstoječi tabeli prvi element NULL označuje konec, ne praznega mesta, ki bi ga lahko preskočili. Skupine in tabele morajo obstajati med iskanjem, najdena skupina pa ves čas uporabe shranjenega kazalca. Manjkajoča končna oznaka lahko povzroči branje zunaj meja tabele. V vsaki skupini z neničelnim item_count mora items kazati na začetek zaporedja vsaj item_count elementov tipa int, ki jih je mogoče prebrati.
Neobvezen je zapis, ne argument: podaj &found za spremenljivko tipa Group * ali NULL, če želiš le preveriti obstoj. Funkcija prek *out shrani najdeno skupino le ob zadetku in če out != NULL. Ob rezultatu false spremenljivke klicatelja ne spremeni, zato lahko v njej ostane prejšnji rezultat.
V najslabšem primeru je čas O(G + I) za G skupin in I lokalnih elementov, pri višini drevesa h pa je hkrati aktivnih O(h) klicev. Pri zelo globokih vhodnih podatkih razmisli o eksplicitnem skladu; pri grafu s cikli beleži obiskana vozlišča. Primer uporablja skladnjo ISO C23; podpora se lahko razlikuje med implementacijami.
Primeri
#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` je najden v `root` pred pregledom podskupin. Pri iskanju `42` poddrevo `left` pripelje do `deep` pred obiskom `right`. Klic z `NULL` preveri le obstoj; po neuspešnem iskanju `99` kazalec `found` še vedno kaže na `deep`.
Povezane lekcije
- C · Lekcija 79 · Napredna · Različica: 3