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