Valgrind錯誤在釋放AVL樹

我已經爲字符串做了AVL樹，並且樹本身運行良好：插入，刪除，搜索都工作正常。但是，valgrind正在給我一個錯誤。 Valgrind說這個錯誤出現在我的stringDuplicate函數中（我對valgrind指出的特定行號發表了評論），並且這個stringDuplicate函數被我的treeInsert函數調用（我在treeInsert調用stringDuplicate時做了一個註釋）。有人能幫我找到我的valgrind錯誤嗎？Valgrind錯誤在釋放AVL樹

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdint.h> 
#include "tree.h" 

//NODES OF TREE 
struct node{ 
    char *word; 
    int balance; 
    struct node *children[2]; 
}; 

//STRUCT TREE WHICH CONTAINS A POINTER TO THE ROOT AND NUMBER OF ELEMENTS 
struct tree{ 
    struct node *root; 
    size_t numElements; 
}; 

//MALLOC SPACE FOR TREE 
struct tree *treeCreate(void){ 
    struct tree *s = malloc(sizeof(struct tree)); 
    s->root = NULL; 
    s->numElements = 0; 
    return s; 
} 

//CREATE A DUPLICATE OF THE STRINGS TO BE INSERTED/DELETED 
char *stringDuplicate (const char *s) { 
    char *d = malloc (strlen (s) + 1); //VALGRIND POINTS TO THIS LINE FOR ERROR 
    if (d == NULL) return NULL;   
    strcpy (d,s);       
    return d;        
} 

//RETURN THE SIZE OF THE TREE 
size_t treeSize(const struct tree *s){ 
    return s->numElements; 
} 

//CREATE A NEW NODE OF THE TREE 
struct node *make_node(char *word){ 
    struct node *temp = malloc(sizeof(struct node)); 

    if(temp != NULL){ 
     temp->word = word; 
     temp->children[0] = temp->children[1] = NULL; 
     temp->balance = 0; 
    } 

    return temp; 
} 

//CHANGE THE BALANCE OF NODE/NODES IN THE TREE 
void adjustBalance(struct node *root, int direction, int temp_bal){ 
    struct node *temp1 = root->children[direction]; 
    struct node *temp2 = temp1->children[!direction]; 

    if(temp2->balance == 0){ 
     root->balance = temp1->balance = 0; 
    }else if(temp2->balance == temp_bal){ 
     root->balance = -temp_bal; 
     temp1->balance = 0; 
    }else{ 
     root->balance = 0; 
     temp1->balance = temp_bal; 
    } 

    temp2->balance = 0; 
} 

//SINGLE ROTATION OF TREE 
struct node *singleRotation(struct node *root, int direction){ 
    struct node *temp = root->children[!direction]; 

    root->children[!direction] = temp->children[direction]; 
    temp->children[direction] = root; 

    return temp; 
} 

//DOUBLE ROTATION OF TREE 
struct node *doubleRotation(struct node *root, int direction){ 
    struct node *temp = root->children[!direction]->children[direction]; 

    root->children[!direction]->children[direction] = temp->children[!direction]; 
    temp->children[!direction] = root->children[!direction]; 
    root->children[!direction] = temp; 

    temp = root->children[!direction]; 
    root->children[!direction] = temp->children[direction]; 
    temp->children[direction] = root; 

    return temp; 
} 

//CHANGE THE BALANCE OF NODES WHEN INSERTING 
struct node *insertBalance(struct node *root, int direction){ 
    struct node *temp = root->children[direction]; 
    int temp_bal; 

    if(direction == 0){ 
     temp_bal = -1; 
    }else{ 
     temp_bal = 1; 
    } 

    if(temp->balance == temp_bal){ 
     root->balance = temp->balance = 0; 
     root = singleRotation(root, !direction); 
    }else{ 
     adjustBalance(root, direction, temp_bal); 
     root = doubleRotation(root, !direction); 
    } 

    return root; 
} 

//INSERT INTO TREE RECURSIVELY 
struct node *insertRecursive(struct node *root, char *word, int *flag){ 
    if(root == NULL){ 
     root = make_node(word); 
    } 
    else{ 
     //IF word < root->word, WE NEED TO GO LEFT AND direction < 0 
     //IF word > root->word, WE NEED TO GO RIGHT AND direction > 0 
     int direction = strcmp(word, root->word); 
     if(direction > 0){ 
      direction = 1; 
     }else if(direction < 0){ 
      direction = 0; 
     } 

     root->children[direction] = insertRecursive(root->children[direction], word, flag); 

     if(!*flag){ 
      if(direction == 0){ 
       root->balance += -1; 
      }else{ 
       root->balance += 1; 
      } 

      if(root->balance == 0){ 
       *flag = 1; 
      }else if(abs(root->balance) > 1){ 
       root = insertBalance(root, direction); 
       *flag = 1; 
      } 
     } 
    } 

    return root; 
} 

//SEARCH FOR A STRING IN TREE: 1 IF IN TREE, 0 IF NOT 
int searchTree(struct node *root, char *word){ 
    int flag = 0; 
    struct node *current = root; 
    while(!flag){ 
     if(current){ 
      int direction = strcmp(word, current->word); 
      if(direction == 0){ 
       flag = 1; 
       break; 
      }else if(direction > 0){ 
       direction = 1; 
      }else{ 
       direction = 0; 
      } 

      current = current->children[direction]; 
     }else{ 
      break; 
     } 
    } 

    return flag; 
} 

//INSERT NEW ELEMENT INTO TREE 
void treeInsert(struct tree *tree, const char *word){ 
    char *newWord = stringDuplicate(word); 
    int flag = searchTree(tree->root, newWord); 
    int temp = 0; 
    if(flag == 0){ 
     tree->root = insertRecursive(tree->root, newWord, &temp); 
     tree->numElements = tree->numElements + 1; 
    } 
} 

//CHANGE THE BALANCE OF NODES WHEN DELETING FROM TREE 
struct node *deleteBalance(struct node *root, int direction, int *flag){ 
    struct node *temp = root->children[!direction]; 
    int temp_bal; 
    if(direction == 0){ 
     temp_bal = -1; 
    }else{ 
     temp_bal = 1; 
    } 
    if(temp->balance == -temp_bal){ 
     root->balance = temp->balance = 0; 
     root = singleRotation(root, direction); 
    }else if(temp->balance == temp_bal){ 
     adjustBalance(root, !direction, -temp_bal); 
     root = doubleRotation(root, direction); 
    }else{ 
     root->balance = -temp_bal; 
     temp->balance = temp_bal; 
     root = singleRotation(root, direction); 
     *flag = 1; 
    } 

    return root; 
} 

//DELETE A STRING FROM TREE ITERATIVELY 
void treeDelete(struct tree *tree, const char *word){ 
    if(tree->root != NULL){ 
     char *newWord = stringDuplicate(word); 
     struct node *iterator, *ancestor_array[32]; 
     int ancestor_direction[32]; 
     int current_index = 0; 
     int flag = 0; 

     iterator = tree->root; 

     for(;;){ 
      if(iterator == NULL){ 
       return; 
      }else if(strcmp(newWord, iterator->word) == 0){ 
       tree->numElements = tree->numElements - 1; 
       break; 
      } 

      int direction = strcmp(word, iterator->word); 
      if(direction > 0){ 
       direction = 1; 
      }else if(direction < 0){ 
       direction = 0; 
      } 

      ancestor_direction[current_index] = direction; 
      ancestor_array[current_index++] = iterator; 

      iterator = iterator->children[ancestor_direction[current_index - 1]]; 
     } 

     if(iterator->children[0] == NULL || iterator->children[1] == NULL){ 
      int dir = iterator->children[0] == NULL; 

      if(current_index != 0){ 
       ancestor_array[current_index - 1]->children[ancestor_direction[current_index - 1]] = iterator->children[dir]; 
      }else{ 
       tree->root = iterator->children[dir]; 
      } 

      free(iterator); 
     }else{ 
      struct node *heir = iterator->children[1]; 
      ancestor_direction[current_index] = 1; 
      ancestor_array[current_index++] = iterator; 

      while(heir->children[0] != NULL){ 
       ancestor_direction[current_index] = 0; 
       ancestor_array[current_index++] = heir; 
       heir = heir->children[0]; 
      } 

      iterator->word = heir->word; 
      ancestor_array[current_index - 1]->children[ancestor_array[current_index - 1] == iterator] = heir->children[1]; 

      free(heir); 
     } 
     while(--current_index >= 0 && !flag){ 
      ancestor_array[current_index]->balance += ancestor_direction[current_index] != 0 ? -1 : 1; 

      if(abs(ancestor_array[current_index]->balance) == 1){ 
       break; 
      }else if(abs(ancestor_array[current_index]->balance) > 1){ 
       ancestor_array[current_index] = deleteBalance(ancestor_array[current_index], ancestor_direction[current_index], &flag); 

       if(current_index != 0){ 
        ancestor_array[current_index - 1]->children[ancestor_direction[current_index - 1]] = ancestor_array[current_index]; 
       }else{ 
        tree->root = ancestor_array[0]; 
       } 
      } 
     } 
    } 
    return; 
} 

//FREE TREE 
void treeDestroyHelper(struct node *root){ 
    if(root == NULL){ 
     return; 
    } 

    if(root->children[0] == NULL && root->children[1] == NULL){ 
     free(root->word); 
     free(root); 
    }else if(root->children[0] == NULL && root->children[1] != NULL){ 
     treeDestroyHelper(root->children[1]); 
     free(root->word); 
     free(root); 
    }else if(root->children[0] != NULL && root->children[1] == NULL){ 
     treeDestroyHelper(root->children[0]); 
     free(root->word); 
     free(root); 
    }else{ 
     treeDestroyHelper(root->children[0]); 
     treeDestroyHelper(root->children[1]); 
     free(root->word); 
     free(root); 
    } 
} 

//FREE TREE 
void treeDestroy(struct tree *s){ 
    treeDestroyHelper(s->root); 
    free(s); 
}

編輯：只是想添加註釋以防萬一有人想知道tree.h只是我使用的函數標題。

來源

2015-04-07 jsmith102894

爲什麼不使用'strdup'？什麼是錯誤？ –

簡化'treeDestroyHelper（）'：只保留'NULL'的測試並對兩個孩子遞歸。它有助於避免在您釋放''free''後免費'雙'free''設置'NULL'的指針。 – chqrlie

@Ôrel：我同意你的意見（像往常一樣;-)，但是令人遺憾的事實是'strdup'不是標準C函數。它在Posix兼容的系統上定義，但可能不在OP上提供，儘管不太可能。 – chqrlie

您複製word在treeDelete()並忘記釋放它。在那裏不需要複製。 valgrind抱怨stringDuplicate()分配的內存未被釋放。

順便說一句，這個函數名稱很混亂，你應該使用treeDeleteString。 treeInsert - >treeInsertString和其他一些相同。

編輯：你也忘了free(iterator);和free(heir);前免費treeDelete()的字符串。我無法分辨treeDelete()中的邏輯是否正確，但是這些缺失的free()肯定會導致內存丟失並被valgrind報告。

來源

2015-04-07 06:07:04 chqrlie

不幸的是，這似乎還不能解決Valgrind的錯誤。現在我只是'2000個塊中的7,786個字節肯定丟失在1'的丟失記錄1中。當我在treeDelete函數中釋放（迭代器）和釋放（繼承人）時，我應該免費調用嗎？（我現在已經更改爲treeDeleteString）。 – jsmith102894

@ jsmith102894：我在'treeDelete（）'中發現更多缺少'free（）'的東西。往上看。 – chqrlie

Valgrind錯誤在釋放AVL樹

回答

相關問題