CKTIS / C
Diepte-eerst zoeken (DFS) in C
Doorzoek een boom van groepen recursief: controleer eerst de eigen elementen van de huidige groep, daarna de subgroepen, en bewaar zo nodig een pointer naar de groep met de eerste treffer.
Versie: ISO C23; implementation support may vary
Syntax
#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 gebruikt diepte-eerst zoeken (DFS) in een boom van groepen. Elke aanroep controleert eerst de eigen elementen van de huidige groep en bezoekt daarna de subgroepen in arrayvolgorde. De recursie doorzoekt een deelboom volledig voordat ze naar de volgende gaat, tenzij het gezochte element eerder wordt gevonden. true wordt direct doorgegeven; false betekent dat er in die deelboom geen treffer is.
In de zelfverwijzende structuur wijst struct Group **subs naar het eerste element van een array met pointers naar groepen, niet naar een array met Group-objecten. Binnen de definitie is de tag struct Group al bruikbaar, maar het type is nog onvolledig en de naam Group uit deze typedef is nog niet zichtbaar. De structuur mag een pointer als lid hebben, maar niet rechtstreeks een object van haar eigen type bevatten.
De macro NULL uit <stddef.h> expandeert tot een nulpointerconstante. subs == NULL betekent dat er geen subgroeparray is; in een bestaande array markeert het eerste NULL-element het einde en is het geen gat om over te slaan. Groepen en arrays moeten tijdens de zoekactie blijven bestaan; de gevonden groep moet blijven bestaan zolang je de opgeslagen pointer gebruikt. Zonder eindmarkering kan er buiten de array worden gelezen. Voor elke groep waarin item_count niet nul is, moet items naar het begin van een reeks van minstens item_count leesbare elementen van het type int wijzen.
Het schrijven is optioneel, niet het argument: geef &found mee voor een variabele van het type Group *, of geef NULL mee om alleen te testen of het element bestaat. Alleen bij een treffer én als out != NULL schrijft de functie de groep via *out weg. Bij false blijft de variabele van de aanroeper ongewijzigd en kan die nog een eerder resultaat bevatten.
In het slechtste geval is de looptijd O(G + I) voor G groepen en I lokale elementen, met O(h) gelijktijdig actieve aanroepen bij boomhoogte h. Overweeg bij zeer diepe invoer een expliciete stack; houd bij een graaf met cycli bij welke knopen bezocht zijn. Het voorbeeld gebruikt ISO C23-syntaxis; ondersteuning kan per implementatie verschillen.
Voorbeelden
#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;
}
Resultaat
7 -> root 42 -> deep 42 exists: yes 99 missing; saved group: deep
`7` wordt in `root` gevonden voordat een subgroep aan de beurt komt. Voor `42` leidt de deelboom `left` naar `deep` voordat `right` wordt bezocht. De aanroep met `NULL` test alleen of het element bestaat; na de mislukte zoekactie naar `99` wijst `found` nog naar `deep`.
Gerelateerde lessen
- C · Les 79 · Gevorderd · Versie: 3