Come liberare struct ricorsiva (trie)

Question

montaggio finale

La mia funzione che libera la memoria funziona correttamente, e come milevyo ha suggerito, il problema sta nella creazione dei nodi, che avevo fisso. Ora ho un problema separato in cui il programma segfaults quando viene eseguito normalmente, ma non può essere riprodotto in gdb o valgrind. Tuttavia, questa è una domanda separata del tutto.

Da allora ho scoperto che questo segfault è accaduto perché non ho controllato correttamente il carattere EOF. As per Cliff B's answer in this question, il controllo per EOF si verifica solo dopo l'ultimo carattere nel file. Di conseguenza, nella mia funzione che carica il file dizionario, ho assegnato l'ultimo carattere del file a un numero i (che in questo caso era -1 in base a una chiamata printf) e ho cercato di creare e accedere a un nodo figlio se indice -1. Ciò ha causato un errore di segmentazione e ha anche causato problemi con la mia funzione di scaricamento, che non avrebbe scaricato l'ultimo nodo che ho creato.

Per quanto riguarda il motivo per cui l'errore di segmentazione non viene visualizzato quando eseguo il programma in gdb o valgrind, non ne ho idea.

EDIT 3

Mentre passando attraverso la mia funzione di carico dove la creazione del nodo accade, ho notato un comportamento imprevisto. Credo che il problema si trovi da qualche parte in queste righe di codice, che sono incorporate all'interno di un ciclo for. Il casting su (node*) deve essere sicuro, sebbene non influenzi l'esecuzione del codice per quanto ne so.

// if node doesnt exist, calloc one, go to node 
if (current_node->children[i] == NULL) 
{ 
    current_node->children[i] = (node*) calloc(1, sizeof(node)); 
    nodes++; 
} 
current_node = current_node->children[i]; 

Mentre passando attraverso la funzione di caricamento, vedo che la mia current_node->children[i] sembrano essere calloc 'Ed correttamente (tutti i bambini impostati NULL), ma il momento faccio un passo in current_node->children[i] ed esaminare i suoi figli (vedi immagine sotto) , Vedo che gli indirizzi si rovinano. In particolare, il figlio i nel nodo figlio viene impostato su 0x0 per qualche motivo. Mentre 0x0 deve essere uguale a NULL (correggimi se ho torto), la mia funzione free_all sembra voler andare nel puntatore 0x0, che ovviamente si traduce in un segfault. Qualcuno può far luce su come questo potrebbe accadere?

Values of children[i]

EDIT 2: sto usando calloc per creare i miei nodi

root = calloc(1, sizeof(node));

Per i miei nodi figli, essi sono creati all'interno di un ciclo in cui ho iterare su personaggi di il file dizionario che sto leggendo.

if (current_node->children[i] == NULL) 
{ 
    current_node->children[i] = calloc(1, sizeof(node)); 
    nodes++; 
} 

c in questo caso rappresenta il carattere della parola che viene letta in ottengo i utilizzando la seguente:.

if (c == '\'') 
    i = 26; 
else if (isalpha(c)) 
    i = c - 97; 

EDIT: Sto pensando che qualcosa nella mia creazione nodo è difettoso, come milevyo suggerito.Questo perché se stampo gli indirizzi, passa da 0x603250 a 0x603340 a 0x603430 a 0x603520, quindi infine a (nil), prima di segfault. Ho verificato che il nodo radice viene passato correttamente stampando il suo valore in gdb. Proverò a capirlo.

domanda iniziale

che sto funzionando in un segfault quando si cerca di liberare una struttura ricorsiva, ma non riesco a capire perché, e vorrei qualche aiuto.

mio struct è definito come segue:

typedef struct node 
{ 
    bool is_word; 
    struct node* children[27]; 
} 
node; 

Ciò ha lo scopo di realizzare una struttura trie in cui caricare un dizionario in, ai fini di un controllo ortografico. Dopo che il controllo ortografico è terminato, ho bisogno di liberare la memoria che ho assegnato al trie.

Questa è la mia attuale funzione che dovrebbe liberare il trie quando superato il nodo principale, ma segfaults quando farlo, anche se non subito:

void free_all(node* curs) 
{ 
    int i; 

    // recursive case (go to end of trie) 
    for (i = 0; i < 27; i++) 
    { 
     if (curs->children[i] != NULL) 
     { 
      free_all(curs->children[i]); 
     } 
    } 

    // base case 
    free(curs); 
} 

Dove avrei potuto andato storto? Se sono necessarie ulteriori informazioni, per favore fatemelo sapere.

Answer 1

Penso che il nodo radice sia difettoso (forse è nullo). se no, guarda altrove. nella creazione del nodo, per esempio.

void free_all(node* curs) 
{ 
    int i; 
    if(!curs) return; // safe guard including root node. 

    // recursive case (go to end of trie) 
    for (i = 0; i < 27; i++) 
     free_all(curs->children[i]); 


    // base case 
    free(curs); 
} 

Answer 2

La funzione free_all è ok. Devi controllare che tu abbia impostato su NULL tutti i bambini non assegnati. Ciò include nodi che non sono foglie, ma non hanno tutti i bambini 27.

Se ciò è ok, o il suo fissaggio non corregge il segfault, è necessario eseguire il debug.