c - 이진 검색 트리 삽입으로 메모리 누수

Question

Valgrind를 사용했으며 코드가 insert() 및 buildName() 함수에서 메모리 누수 위치를 확인할 수 없습니다. Valgrind는 이러한 기능이 있다고 말하지만 정확한 위치를 정확히 알 수는 없습니다. 나는 코드로 메모리를 새기라는 개념에 대해 아주 새로운 것이다. 누구 한테 도움을 줘? 건배! 빈

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 


/* Node of tree */ 
typedef struct Node { 
    int order; 
    char value; 
    struct Node * left; 
    struct Node * right; 
} Node; 

Node * insert(Node * node, char value, int order){ 
    if(node == NULL){ 
     /* free(node); */ 
     node = (Node *)malloc(sizeof(Node)); 
     node->value = value; 
     node->order = order; 
     node->left = NULL; 
     node->right = NULL; 
     return node; 
    } 
    if(order > node->order){ 
     node->right = insert(node->right, value, order); 
    } 
    else if(order < node->order){ 
     node->left = insert(node->left, value, order); 
    } 
    return node; 
} 

char * buildName(const char * old, const char * newpart) { 
    char * dot; 
    char * buf = NULL; 

    dot = strrchr(old, '.'); 
    if (dot) { 
     size_t len; 
     len = snprintf(NULL, 0, "%.*s%s.%s", 
        (int)(dot - old) + 1, old, newpart, dot + 1); 
     buf = malloc(len + 1); 
     if (buf) { 
     snprintf(buf, len + 1, "%.*s%s.%s", 
       (int)(dot - old) + 1, old, newpart, dot + 1); 
     } 
    } 
    return buf; 
} 

void decode(Node * root, Node * origRoot, char * bitString, char * filename) { 
    FILE * fp; 
    int i = 0; 

    fp = fopen(filename, "w"); 

    if (fp) { 
     while(bitString[i] != '2'){ 
      if(bitString[i] == '0'){ 
       if(root->left == NULL && root->right == NULL) { 
        root = origRoot; 
        i--; 
       } 
       else root = root->left;    
      } 
      else if(bitString[i] == '1'){  
       if(root->right == NULL && root->left == NULL) { 
        root = origRoot; 
        i--; 
       } 
       else root = root->right;      
      } 
      if(root->value != -1){ 
       fputc(root->value, fp); 
       printf("%c", root->value); 
      } 
      i++; 
     } 
    } 
    fclose(fp); 
} 

int main(int argc, char * argv[]){ 

    FILE * fp; 
    Node * root = NULL; 
    char bitString[256]; 
    char * filename; 
    int numNodes; 
    int value; 
    int order; 
    int i = 0; 
    char c; 

    if (argc < 2 || argc > 2) { 
     printf("No file specified or too many arguments. Exiting...\n"); 
     exit(1); 
    } 

    fp = fopen(argv[1], "r"); 

    if(!fp){ 
     printf("Cound not open command file: %s", argv[1]); 
     return 0; 
    } 

    if(fp){ 
     fscanf(fp, "%d", &numNodes); 

     while(i < numNodes){ 
      fscanf(fp, "%d", &value); 
      fscanf(fp, "%d", &order); 
      root = insert(root, value, order); 
      i++; 
     } 

     i = 0; 
     while((c = fgetc(fp)) != EOF){ 
      bitString[i] = c; 
      i++; 
     } 
    } 

    fclose(fp); 

    filename = buildName(argv[1], "decoded"); 

    decode(root, root, bitString, filename); 

    return 0; 
} 

추가 :

void empty(Node * node) { 
    node = NULL; 
    if(node != NULL){ 
    Node * left = node->left; 
    Node * right = node->right; 
    free(node); 
    if (left) 
     empty(left); 
    if (right) 
     empty(right); 
    } 
} 

Answer 1

은 당신이 함수에서, "다른 사람을"누락 생각합니다. 새로운 노드를 만들 때 즉시 반환하지 않으면 다음 if로 진행합니다. 이로 인해 바이너리 검색 트리가 올바르게 구성되지 않을 수도 있습니다. 이것을 시도하십시오 :

Node * insert(Node * node, char value, int order){ 
if(node == NULL){ 
    /* free(node); */ 
    node = (Node *)malloc(sizeof(Node)); 
    node->value = value; 
    node->order = order; 
    node->left = NULL; 
    node->right = NULL; 
    return node; 
} 
else if(order > node->order){ 
    node->right = insert(node->right, value, order); 
} 
else if(order < node->order){ 
    node->left = insert(node->left, value, order); 
} 
return node; 
}