Kaldır/Yok İşlev mantığı (Yapı/Denemeler)

Question

Uygulama için bir Trie programı üzerinde çalışıyorum ve söz konusu kelimeleri kaldıran veya yok eden bir yöntem oluşturmaya çalışırken bazı mantıksal/kodlama sorunlarıyla karşılaşıyorum. trie şu anda:

#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: (Önemli şeyler neyse) ALPHA_SIZE 27.

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

olduğunu ben bu soruyu doğru biçimlendirilmiş umut ve ben mümkün için sitede baktım çözümler zaten vardı ama henüz bulamadı. Eğer birisi benim mantığımı kontrol etmeme yardımcı olabilir/bu yöntemlerin kodlanmasında bana yardımcı olabilir ki bu harika olurdu. Neden çalıştığını öğrenmek istediğim kodu istemiyorum!

Şimdiden teşekkürler.

Answer 1

Kaldır için, sen trayden gelen free'd işaretçileri kaldırmak gerekir:

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

için yok - kabaca Özyinelemeyi deneyin:

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

free (rootRef);