Wie rekursive Struktur (trie)

Question

FINAL EDIT

Meine Funktion zu befreien, die den Speicher richtig funktioniert befreit und als milevyo vorgeschlagen hat, liegt das Problem in Knoten Schöpfung, die ich festgelegt hatte. Ich habe jetzt ein separates Problem, wo das Programm segfolds, wenn normal ausgeführt wird, aber es kann in gdb oder valgrind nicht reproduziert werden. Das ist jedoch eine ganz andere Frage.

Ich habe seitdem herausgefunden, dass dieser segfault passierte, weil ich nicht für das EOF-Zeichen richtig prüfte. As per Cliff B's answer in this question erfolgt die Überprüfung auf EOF nur nach dem letzten Zeichen in der Datei. Als Ergebnis hatte ich in meiner Funktion, die die Wörterbuchdatei lädt, das letzte Zeichen der Datei an einige i zugewiesen (was in diesem Fall -1 gemäß einem printf-Aufruf war) und versucht, einen untergeordneten Knoten zu erstellen und darauf zuzugreifen Index -1. Dies verursachte einen Segmentierungsfehler und verursachte auch Probleme mit meiner Entladefunktion, die den letzten von mir erstellten Knoten nicht entladen würde.

Warum der Segmentierungsfehler nicht erscheint, wenn ich das Programm in gdb oder valgrind starte, habe ich keine Ahnung.

EDIT 3

Während meiner Ladefunktion Schritt, wo die Knoten Schöpfung geschieht, bemerke ich ein unerwartetes Verhalten. Ich glaube, das Problem liegt irgendwo in diesen Codezeilen, die in eine for Schleife eingebettet sind. Der Casting zu (node*) ist nur um sicher zu sein, obwohl es die Ausführung des Codes meines Wissens nicht beeinträchtigt.

// 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]; 

Während durch die Last Funktion treten, ich sehe, dass meine current_node->children[i] scheinen calloc ‚richtig ed zu sein (alle Kinder auf NULL), aber der Moment, als ich sollte in current_node->children[i] und untersuchen seine Kinder (siehe Bild unten) Ich sehe, dass die Adressen vermasselt werden. Insbesondere wird das i 'th-Kind in dem untergeordneten Knoten aus irgendeinem Grund auf 0x0 festgelegt. Während 0x0 gleich NULL sein soll (korrigieren Sie mich, wenn ich falsch liege), scheint meine free_all Funktion in den 0x0 Zeiger gehen zu wollen, was natürlich zu einem segfault führt. Kann jemand Licht darauf werfen, wie das passieren könnte?

Values of children[i]

EDIT 2: Ich verwende calloc meiner Knoten erstellen

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

Für mein Kind-Knoten, sie innerhalb einer for-Schleife erstellt werden, in dem ich über Zeichen von iterieren die Wörterbuchdatei, die ich gerade einlese.

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

c in diesem Fall stellt das Zeichen des Wortes in gelesenen ich i mit dem folgenden:.

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

EDIT: Ich denke, dass etwas in meinem Knoten Schöpfung fehlerhaft ist, wie milevyo vorgeschlagen.Dies liegt daran, wenn ich die Adressen ausdrucken, es 0x603250-0x603340 zu 0x603430-0x603520 geht, dann schließlich zu (nil), bevor es Segfaults. Ich habe überprüft, dass der Wurzelknoten korrekt übergeben wird, indem ich seinen Wert in gdb ausdrucke. Ich werde versuchen, es herauszufinden.

ORIGINAL FRAGE

ich in ein segfault renne, wenn eine rekursive Struktur zu befreien versucht, kann aber nicht herausfinden, warum, und würde etwas Hilfe.

Meine Struktur ist wie folgt definiert:

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

Dies soll eine Trie-Struktur implementieren, in der für die Zwecke einer Rechtschreibprüfung ein Wörterbuch in, zu laden. Nachdem die Rechtschreibprüfung abgeschlossen ist, muss ich den Speicher freigeben, den ich dem Trie zugewiesen habe.

Dies ist meine aktuelle Funktion, die die Trie wenn der Wurzelknoten weitergegeben befreien sollte, aber es Segfaults wenn dies zu tun, wenn auch nicht sofort:

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); 
} 

Wo könnte ich falsch gemacht habe? Wenn mehr Informationen benötigt werden, lass es mich wissen.

Answer 1

ich denke, Wurzelknoten fehlerhaft ist (vielleicht ist es null). Wenn nicht, schauen Sie woanders hin. zum Beispiel bei der Knotenerstellung.

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

Die free_all Funktion ist in Ordnung. Sie müssen prüfen, ob Sie alle nicht zugeordneten Kinder auf NULL setzen. Dazu gehören Knoten, die keine Blätter sind, haben aber nicht alle 27 Kinder.

Wenn das in Ordnung ist, oder die Reparatur nicht die segfault beheben, müssen Sie debuggen.