CKTIS / C
Struttura autoreferenziale in C
Una struttura `Group` punta a sottogruppi dello stesso tipo. La ricerca in profondità controlla prima i valori locali e può indicare il gruppo della prima corrispondenza.
Versione: ISO C23; implementation support may vary
Sintassi
typedef struct Group {
const char *name;
const int *values;
size_t value_count;
struct Group **subs;
} Group;
static int find_value(Group *group, int wanted, Group **out_group);Una struttura autoreferenziale usa un puntatore per riferirsi a un oggetto del proprio tipo. In typedef struct Group { ... } Group;, il tag Group è già visibile dopo struct, ma il tipo rimane incompleto fino alla parentesi graffa di chiusura }. Il membro struct Group child; non è quindi valido, mentre struct Group **subs; lo è. Il tag e il nome di typedef appartengono a spazi dei nomi distinti; l’alias introdotto qui non è ancora disponibile all’interno delle graffe.
subs è un puntatore a un puntatore, non un array incorporato nella struttura. Nell’esempio punta al primo elemento di un array separato di puntatori Group *. La macro NULL è disponibile in <stddef.h>: subs == NULL indica che non c’è un array di sottogruppi, mentre il primo elemento NULL di un array esistente ne segna la fine. Senza questa sentinella, si rischia di leggere oltre i limiti dell’array. I valori locali si scorrono invece in base a value_count. Se value_count è diverso da zero, values deve puntare all’inizio di una sequenza di almeno value_count elementi accessibili in lettura.
find_value esegue una ricerca in profondità (DFS): controlla prima i valori del gruppo corrente, poi cerca ricorsivamente nei sottogruppi nell’ordine dell’array. Si ferma alla prima corrispondenza e restituisce 1; restituisce 0 se il puntatore al gruppo è nullo o se non trova corrispondenze. Passa &found, dove found è di tipo Group *, per ricevere il puntatore al gruppo tramite *out_group in caso di successo. Passa NULL se vuoi solo l’esito. Se non ci sono corrispondenze, la variabile di uscita resta invariata.
I gruppi e gli array non vengono copiati e devono rimanere in vita finché vengono usati tramite puntatori. La funzione presuppone che non ci siano cicli; se sono possibili, tieni traccia dei gruppi visitati. Per gerarchie molto profonde, valuta una pila esplicita al posto della ricorsione. Questo schema non richiede funzionalità introdotte in C23; il supporto della modalità C23 dipende dall’implementazione.
Esempi
#include <stddef.h>
#include <stdio.h>
typedef struct Group {
const char *name;
const int *values;
size_t value_count;
struct Group **subs;
} Group;
static int find_value(Group *group, int wanted, Group **out_group)
{
if (group == NULL)
return 0;
for (size_t i = 0; i < group->value_count; ++i) {
if (group->values[i] == wanted) {
if (out_group != NULL)
*out_group = group;
return 1;
}
}
if (group->subs != NULL) {
for (size_t i = 0; group->subs[i] != NULL; ++i) {
if (find_value(group->subs[i], wanted, out_group))
return 1;
}
}
return 0;
}
int main(void)
{
const int root_values[] = {7, 9};
const int deep_values[] = {7, 42};
const int right_values[] = {42};
Group deep = {"deep", deep_values, 2, NULL};
Group right = {"right", right_values, 1, NULL};
Group *left_subs[] = {&deep, NULL};
Group left = {"left", NULL, 0, left_subs};
Group *root_subs[] = {&left, &right, NULL};
Group root = {"root", root_values, 2, root_subs};
Group *found = NULL;
if (find_value(&root, 7, &found))
printf("7: %s\n", found->name);
if (find_value(&root, 42, &found))
printf("42: %s\n", found->name);
if (find_value(&root, 9, NULL))
puts("9: found without output parameter");
if (!find_value(&root, 99, &found))
printf("99: not found; previous result: %s\n", found->name);
return 0;
}
Risultato
7: root 42: deep 9: found without output parameter 99: not found; previous result: deep
`7` si trova in `root` prima di esaminare i sottogruppi. Per `42`, la ricerca scende attraverso `left` fino a `deep` e si ferma quando trova il valore. Il sottogruppo successivo di `root`, `right`, non viene quindi controllato. Per `9` non si richiede il puntatore di uscita; non trovando `99`, `found` continua a puntare a `deep`.
Lezioni correlate
- C · Lezione 79 · Avanzato · Versione: 3