C语言中正确释放双链接节点

Question

我对 C 世界还很陌生，我不知道如何删除此数据结构以避免内存泄漏和段错误的正确方法。

数据结构是这样的:

typedef struct Node {
    int id;
    struct Node *parent;   /* node's parent */
    struct Node *suffix_node;
    int first_char_index;
    int last_char_index;
    bool is_leaf;
    struct Node **children;  /* node's children */
    int children_size;         /* size of children structure */
    int children_count;         /* # of children */
    int depth;
}Node;

typedef struct SuffixTree {
    Node *root;
    int nodes_count;
    char *string;
}SuffixTree;

我要做的是，从指向 SuffixTree 结构的指针，完全释放树。

我尝试过这样做:

void deleteSubTree(Node *nd)
{
    if (nd->is_leaf)
    {
        free(nd->children);
        free(nd);
        return;
    }
    int i = 0;
    for(;i < nd->children_count; ++i)
    {
        deleteSubTree(nd->children[i]);
    }
    free(nd->children);
    free(nd);
    return;
}

void deleteSuffixTree(SuffixTree *st)
{
    deleteSubTree(st->root);
    free(st);
}

但这是不正确的。

编辑:

这是主要的:

int main()
{   char *str = "BOOK\0";
    SuffixTree *st = createSuffixTree(str);
    deleteSuffixTree(st);
    return 0;
}

这就是我分配树和节点的方式:

Node* createNode(){
    Node *stn = (Node*)malloc(sizeof(Node));
    stn->id = node_id++;
    stn->parent = (Node*)malloc(sizeof(Node));
    stn->suffix_node = (Node*)malloc(sizeof(Node));
    stn->first_char_index = -1;
    stn->last_char_index = -1;
    stn->children_size = NODE_BASE_DEGREE;
    stn->children_count = 0;
    stn->children = (Node**)malloc(stn->children_size*sizeof(Node*));
    stn->is_leaf = true;
    stn->depth = 1;
    return stn;
}

SuffixTree* createSuffixTree(char *str)
{
    SuffixTree *st = (SuffixTree*)malloc(sizeof(SuffixTree));
    st->root = createNode();
    st->root->parent = (Node*)malloc(sizeof(Node));
    st->root->parent->id = -1;
    st->nodes_count = 1;
    st->string = str;

    makeTreeWithUkkonen(st);

    return st;
}

makeTreeWithUkkonen 是正确的，我可以在调用 createSuffixTree() 后显示正确的树。

Answer 1

正如 GeoMad89 所说，您在 createNode() 方法中分配了已经存在的节点。如果将 createNode() 代码更改为:

Node* createNode(Node* parent, Node* suffixNode){

Node *stn = (Node*)malloc(sizeof(Node));
stn->id = node_id++;
stn->parent = parent;   //(Node*)malloc(sizeof(Node));
if(suffixNode != NULL)
    stn->suffix_node = suffixNode;  //(Node*)malloc(sizeof(Node));
stn->first_char_index = -1;
stn->last_char_index = -1;
stn->children_size = NODE_BASE_DEGREE;
stn->children_count = 0;
stn->children = (Node**)malloc(stn->children_size*sizeof(Node*));
if(parent != NULL){
    parent->children[parent->children_count++] = stn;
    parent->is_leaf = false;
}
stn->is_leaf = true;
stn->depth = 1;
return stn;
}

如果你尝试使用 valgrind，使用这个玩具 main:

main(int argc, char** argv){

Node* root = createNode(NULL, NULL);
Node* node1 = createNode(root, NULL);
Node* node2 = createNode(root, NULL);
Node* node3 = createNode(node1, NULL);

deleteSubTree(root);

return 0;
}

您将看到所有 malloc 的内存都将被释放!

不用说，此代码仅适用于 NODE_BASE_DEGREE=2，否则，如果您使用更大的 NODE_BASE_DEGREE 值，则必须重新分配子数组。