Remove/Destroy 函数逻辑 (Struct/Tries)

Question

我一直在研究一个用于练习的 Trie 程序，在尝试创建一种方法来删除或销毁当前存在的单词时，我运行遇到了一些 logic/coding 问题在 trie 中：

#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 = '[=12=]';
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：（无论如何重要的东西）ALPHA_SIZE 是 27。

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

我希望我正确地格式化了这个问题，并且我已经在该网站上寻找可能的解决方案，但尚未找到任何解决方案。如果有人可以帮助我检查我的逻辑/协助我编写这些方法的代码，那将是非常棒的。我不只是想要代码我想了解它的工作原理！

提前致谢。

Answer 1

对于删除，您需要从 trie 中删除已释放的指针：

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

对于销毁 - 尝试递归，大致：

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

free (rootRef);

Remove/Destroy 函数逻辑 (Struct/Tries)

Remove/Destroy Function logic (Struct/Tries)

c

struct

logic

trie