Entfernen/Zerstören Funktionslogik (Struct/Tries)

Question

Ich habe an einem Trie-Programm für die Praxis gearbeitet und ich bin in einigen Logik/Codierung Probleme, wenn es darum geht, eine Methode zu erstellen, die Wörter entfernt oder zerstört derzeit in der Trie sind:

#include "trie.h" 
/**************************************************************************/ 
/* Helper Functions 
* trie_node_t * trie_new( void); 
*   Allocates memory for a new trie node 
*   Returns NULL if memory allocation was not possible or 
*   a memory address to a trie_node in the heap 
/**************************************************************************/ 
trie_node_t * trie_new( void){ 
    trie_node_t * tmp = NULL; 
    int i; 
    if ((tmp = (trie_node_t *) malloc (sizeof(trie_node_t))) == NULL) 
    return NULL; 
    for(i = 0; i < ALPHA_SIZE; i++) { 
     tmp->child[ i ] = NULL; 
     tmp->end = 1; 
    } 
return tmp; 
} 
/**************************************************************************/ 
/* Functions functions  
* int trie_size  (trie_node_t * root); 
*   Returns the number of words in the trie 
* int trie_contains (trie_node_t * root, char word[ ]); 
*   Returns 1 if a the word is in the trie 
*     0 otherwise 
* int trie_insert (trie_node_t ** rootRef, char word[ ]); 
*   Returns 1 if the word is inserted in the trie 
*     0 otherwise 
* int trie_remove (trie_node_t ** rootRef, char word[ ]); 
*   Returns 1 if the word is removed from the trie 
*     0 otherwise 
* int trie_destroy (trie_node_t ** Tref); 
*   Returns 1 if the trie and all its node are destroyed 
**************************************************************************/ 
int trie_size  (trie_node_t * root) { 
    int i = 0; 
    int count = 0; 
    trie_node_t *temp = root; //Creates a temp variable (Because its being modified) 
    //if the reference does not exist(no more children) 
    if (temp == NULL){ 
    return EXIT_FAILURE; 
} 
//loops through the child array 
for (i = 0; i < ALPHA_SIZE; i++){ 
    //if the reference to next child is not null 
    if(temp->child[i] != NULL){ 
     //and the end character is '/0' (or not) 
     if(temp->child[i]->end == '/0'){ 
      count += 1; 
     } 
     //add the return of trie_size to count, then run through the method again at the lower level. 
     count += trie_size(temp->child[i]); 
    } 
} 
return count; 
} 
/**************************************************************************/ 
int trie_contains (trie_node_t * root, char word[ ]){ 
trie_node_t *temp = root; //Create a temp variable, can't use the default root. (just a location). 
int i = 0; 
int length = strlen(word); //finds the length of array 
int index = 0; 
if (temp == NULL){ 
    return EXIT_FAILURE; 
} 
if(!valid_word(word)){ 
    return 0; 
} 
for (i = 0; i < length; i++){ 
    index = charToInt(tlower(word[i])); 
    if (!temp->child[index]){ 
     return 0; 
    } 
    temp = temp->child[index]; 
} 
if (temp->end != '/0'){ //Checks if the end character at the last index is '/0' if it is not, it is not a word. Return 0 (not found) 
    return 0; 
} 
return 1; 
} 
/**************************************************************************/ 
int trie_insert (trie_node_t ** rootRef, char word[ ]){ 
trie_node_t *temp = *rootRef; //Create a temp variable, can't use the default rootRef. (just a location). 
int i = 0; 
int length = strlen(word); //finds the length of array 
int index = 0; 
if (temp == NULL){ //checks that the reference is not null 
    return EXIT_FAILURE; 
} 
if (!valid_word(word)){//checks if word is valid. 
    return 0; 
} 
for (i = 0; i < length; i++){ 
    if (word[i] == '/0'){ 
     index = 26; 
    } else if (word[i] >= 'A' || word[i] <= 'Z'){ 
     index = charToInt(tolower(word[i])); //turns the word[i] into a usable integer. 
    } 
    else { 
     return EXIT_FAILURE; 
    } 
    if (!temp->child[index]){ //if there is not a child reference. 
     temp->child[index] = trie_new(); //create one. 
    } 
    temp = temp->child[index]; //move down to next level (next child) 
} 
temp->end = '\0'; 
return 1; 
} 
/************************************************************************** 
* I'm pretty sure the majority of this method is incorrect, this was just an attempt I had. From what I understand I have to do is this: 
* (1) Find the last character in the word (Found with the '/0' end char) and as long as there are no nodes connected at a lower level free the memory. 
* (2) Move up (recursion is probably the easiest way to do this, but I haven't been able to figure out how) and check again. 
* (3) Continue until the first letter of the word is reached, then exit. 
* My question is how do I check to see if another node is connected? Also what would be the format of the recursive call? 
**************************************************************************/ 
void trie_remove (trie_node_t ** rootRef, char word[ ]){ 
trie_node_t *temp = *rootRef; 
int i = 0; 
int index = 0; 
int length = strlen(word); 
if (temp == NULL){ 
    return; 
} 
if (!valid_word(word)){ 
    return; 
} 
//Code is incomplete, just an attempt. 
for (i = 0; i < length; i++){ 
    index = charToInt(tolower(word[i])); //not sure if this is necessary. 
    if (temp->child[i]->end == '/0'){ 
     free(temp->child[i]); 
    } 

} 
return; 
} 
/**************************************************************************/ 
int trie_destroy (trie_node_t ** rootRef){ 

//issues with logic here, not exactly sure how to do this. 

return 1; 
} 
/**************************************************************************/ 
int trie_init(trie_node_t **rootRef){ 
if (*rootRef == NULL) { 
    *rootRef = trie_new(); 
} 
return 1; 
} 
/**************************************************************************/ 
int valid_word (char word[]){ 
int length = 0; 
int i = 0; 
for (i = 0; i < length; i++){ 
    if(charToInt(word[i]) > 26 || charToInt(word[i]) < 0){ 
     return 0; 
    } 
} 
return 1; 
} 
/**************************************************************************/ 
int charToInt(char c){ 
return (int)c-(int)'a'; 
} 

Trie.h: (Wichtige Sachen sowieso) ALPHA_SIZE 27.

typedef struct trie_node { 
    char end; 
    struct trie_node *child[ ALPHA_SIZE ]; //reference to trie node. 
}trie_node_t; 

ist ich hoffe, dass ich diese Frage richtig formatiert, und ich habe für möglich auf der Website sah Lösungen schon aber noch nicht gefunden. Wenn jemand mir helfen kann, meine Logik zu überprüfen/mir bei der Codierung dieser Methoden behilflich zu sein, wäre das erstaunlich. Ich möchte nicht nur den Code, den ich lernen möchte, warum es funktioniert!

Vielen Dank im Voraus.

Answer 1

für entfernen, müssen Sie free'd Zeiger aus dem Trie entfernen:

for (i = 0; i < length; i++){ 
    index = charToInt(tolower(word[i])); //not sure if this is necessary. 
    if (temp->child[i]->end == '/0'){ 
     free(temp->child[i]); 
     temp->child[i]=0; // lets not point to free'd elements 
    } 
} 

Für zerstören - versuchen Rekursion, etwa:

for (int i=ALPHA_MIN; i < ALPHA_MAX; ++i) 
{ 
    if (rootRef->child[i]) 
    { 
     trie_destroy(rootRef->child[i]); 
    } 
} 

free (rootRef);