c - 在红黑树中插入元素时出现 Malloc 错误

Question

#include<stdio.h>
#include<stdlib.h>
typedef struct treenode{
    int elem;
    int color;
    struct treenode *left,*right,*parent;
}treenode_t;
treenode_t *create_node(int elem){
    treenode_t *newnode=(treenode_t *)malloc(sizeof(treenode_t *));
    newnode->elem=elem;
    newnode->left=NULL;
    newnode->right=NULL;
    newnode->color=0;
    newnode->parent=NULL;
    return newnode;
}
void insert(treenode_t **node,int elem){
    if(*node==NULL){
        *node=create_node(elem);
    }else{
        treenode_t *store_parent;
        treenode_t *ptr;
        ptr=*node;
        while(ptr!=NULL){
            store_parent=ptr;
            if(elem<ptr->elem){
                if(ptr->left==NULL){
                    ptr->left=create_node(elem);
                    (ptr->left)->parent=store_parent;
                    (ptr->left)->color=1;
                }
                ptr=ptr->left;
            }
            else if(elem>ptr->elem){
                if(ptr->right==NULL){
                ptr->right=create_node(elem);
                (ptr->right)->parent=store_parent;
                (ptr->right)->color=1;
                }
                ptr=ptr->right;
            }
        }
    }
}
void print_tree(treenode_t *node){
    if(node==NULL)
        return;
    print_tree(node->left);
    printf("%d\n",node->elem);
    print_tree(node->right);
}
void main(){
    treenode_t *root=NULL;
    insert(&root,10);
    insert(&root,5);
    insert(&root,14);
    print_tree(root);
}

我能够插入第一个元素，但第二次 malloc 失败。

使用 GDB:当我使用 gdb 时，我发现一旦创建了第一个节点(树的根)，当我插入第二个元素(即 5)时，行 ptr->left=create_node(elem) 重定向到函数 create_node()。分配给malloc的地址与根目录中存储的地址相同，从而导致错误。

我收到以下错误:

a.out: malloc.c:2372: sysmalloc: Assertion `(old_top == (((mbinptr) (((char *) &((av)->bins[((1) - 1) * 2])) - __builtin_offsetof (struct malloc_chunk, fd)))) && old_size == 0) || ((unsigned long) (old_size) >= (unsigned long)((((__builtin_offsetof (struct malloc_chunk, fd_nextsize))+((2 *(sizeof(size_t))) - 1)) & ~((2 *(sizeof(size_t))) - 1))) && ((old_top)->size & 0x1) && ((unsigned long) old_end & pagemask) == 0)' failed.

Program received signal SIGABRT, Aborted. 0x00007ffff7a4af79 in __GI_raise (sig=sig@entry=6) at ../nptl/sysdeps/unix/sysv/linux/raise.c:56 56 ../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or directory.

现在我是否必须更改由 malloc 分配的内存的地址(如果是这样，如何？)或者代码中是否存在其他问题？

Answer 1

我认为问题在于您用来调用 malloc 的参数:

treenode_t *newnode=(treenode_t *)malloc(sizeof(treenode_t *));

你要求内存，但我认为你要求的还不够。 sizeof(treenode_t *) 返回指向 treenode_t 的指针的大小；你需要的是整个结构有足够的空间。尝试使用 sizeof(treenode_t) 来代替，看看是否有帮助。