CKTIS / C
Търсене в дълбочина (DFS) в C
Претърсвай рекурсивно дърво от групи: първо провери елементите на текущата група, после подгрупите ѝ, и при нужда запази указател към групата с първото съвпадение.
Версия: ISO C23; implementation support may vary
Синтаксис
#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 извършва търсене в дълбочина (DFS) в дърво от групи. Всяко извикване първо проверява елементите на текущата група, а после посещава подгрупите по реда им в масива. Рекурсията претърсва цялото поддърво, преди да премине към следващото, освен ако не намери целта по-рано. true се предава веднага обратно по веригата от извиквания; false означава, че в това поддърво няма съвпадение.
В структурата, която се позовава на собствения си тип, struct Group **subs сочи към първия елемент на масив от указатели към групи, а не към масив от обекти Group. В дефиницията името на тага struct Group вече може да се използва, но типът е още непълен, а псевдонимът Group от тази декларация с typedef още не е видим. Структурата може да има поле от тип указател, но не може пряко да съдържа обект от собствения си тип.
NULL е макрос от <stddef.h>, който се разгъва до константа за нулев указател. subs == NULL означава, че няма масив от подгрупи; в съществуващ масив първият елемент NULL е маркер за край, а не празно място за прескачане. Групите и масивите трябва да съществуват по време на търсенето, а намерената група — докато се използва запазеният указател. Липсващ маркер може да доведе до четене извън границите на масива. Във всяка група с ненулево item_count указателят items трябва да сочи към началото на последователност от поне item_count елемента от тип int, които могат да бъдат прочетени.
Незадължителен е записът, не аргументът: подай &found за променлива от тип Group * или NULL, ако проверяваш само за наличие. Функцията записва намерената група чрез *out само при съвпадение и ако out != NULL. При false променливата на извикващия код остава непроменена и може още да съдържа предишен резултат.
В най-лошия случай времето е O(G + I) за G групи и I локални елемента, а при височина на дървото h едновременно са активни O(h) извиквания. При много дълбоки входни данни обмисли явен стек; при граф с цикли отбелязвай посетените върхове. Примерът използва синтаксис на ISO C23; поддръжката може да се различава между реализациите.
Примери
#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;
}
Резултат
7 -> root 42 -> deep 42 exists: yes 99 missing; saved group: deep
`7` се намира в `root`, преди да се проверят подгрупите. При търсене на `42` поддървото `left` води до `deep`, преди да бъде посетено `right`. Извикването с `NULL` проверява само за наличие; след неуспешното търсене на `99` указателят `found` продължава да сочи към `deep`.
Свързани уроци
- C · Урок 79 · Напреднало · Версия: 3