База знанияИзпитен център
BGБългарски
Избери език13

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

Източници