c - *** 检测到 glibc *** ./bst : munmap_chunk(): invalid pointer: 0xbf91f3d8 *** C Programming

Question

我正在使用 C 语言工作，这让我在二叉搜索树中使用指针时遇到了困难。一切都编译正常，没有错误或警告，但是当我在输入值后尝试运行它时，出现此错误:

Enter 5 integer values to place in tree:
5
1
4
6
2
Input values:
5
1
4
6
2
*** glibc detected *** ./bst: munmap_chunk(): invalid pointer: 0xbfd6e988 ***
======= Backtrace: =========
/lib/i386-linux-gnu/libc.so.6(+0x75ee2)[0xb763eee2]
/lib/i386-linux-gnu/libc.so.6(+0x765c5)[0xb763f5c5]
./bst[0x80486f0]
./bst[0x80488c7]
/lib/i386-linux-gnu/libc.so.6(__libc_start_main+0xf3)[0xb75e24d3]
./bst[0x80484b1]
======= Memory map: ========
08048000-08049000 r-xp 00000000 00:1a 18031111       /home
08049000-0804a000 r--p 00000000 00:1a 18031111       /home
0804a000-0804b000 rw-p 00001000 00:1a 18031111       /home
08232000-08253000 rw-p 00000000 00:00 0          [heap]
b758c000-b75a8000 r-xp 00000000 08:01 22544428   /lib/i386-linux-gnu/libgcc_s.so.1
b75a8000-b75a9000 r--p 0001b000 08:01 22544428   /lib/i386-linux-gnu/libgcc_s.so.1
b75a9000-b75aa000 rw-p 0001c000 08:01 22544428   /lib/i386-linux-gnu/libgcc_s.so.1
b75c8000-b75c9000 rw-p 00000000 00:00 0
b75c9000-b776d000 r-xp 00000000 08:01 22551295   /lib/i386-linux-gnu/libc-2.15.so
b776d000-b776f000 r--p 001a4000 08:01 22551295   /lib/i386-linux-gnu/libc-2.15.so
b776f000-b7770000 rw-p 001a6000 08:01 22551295   /lib/i386-linux-gnu/libc-2.15.so
b7770000-b7773000 rw-p 00000000 00:00 0
b778e000-b7793000 rw-p 00000000 00:00 0
b7793000-b7794000 r-xp 00000000 00:00 0          [vdso]
b7794000-b77b4000 r-xp 00000000 08:01 22551285   /lib/i386-linux-gnu/ld-2.15.so
b77b4000-b77b5000 r--p 0001f000 08:01 22551285   /lib/i386-linux-gnu/ld-2.15.so
b77b5000-b77b6000 rw-p 00020000 08:01 22551285   /lib/i386-linux-gnu/ld-2.15.so
bfd4e000-bfd6f000 rw-p 00000000 00:00 0          [stack]
Aborted (core dumped)

这是我的 bst.c

/// Recursively traverses the tree and prints 
/// the value of each node.
/// @param root - a pointer to the root of the tree to traverse
/// @param type - the traversal type
void traverse(const TreeNode* root, const TraversalType type)
{
if( root == NULL ) return;

//PREORDER
if( type == 0 )
{
    printf( "%d\n", root->data );
    traverse( root->left, PREORDER );
    traverse( root->right, PREORDER );
}
//INORDER
else if( type == 1 )
{
    traverse( root->left, INORDER );
    printf( "%d\n", root->data );
    traverse( root->right, INORDER );
}
//POSTORDER
else if( type == 2 )
{
    traverse( root->left, POSTORDER );
    traverse( root->right, POSTORDER );
    printf( "%d\n", root->data );
}
}
/// Helper method of build_tree. Recursively adds the second
/// TreeNode to the passed root.
/// @param root - a pointer to the pointer to the root of the tree
///               to build this tree on to.
/// @param next - The TreeNode to be added to the Tree
static void addToTree( struct TreeNode** root, struct TreeNode* next)
{
if( (*root)->data >= next->data )
{
    if( (*root)->left == NULL )
    {
        (*root)->left = next;
    }
    else
    {
        addToTree( &(*root)->left, next );
    }
}
else
{
    if( (*root)->right == NULL )
    {
        (*root)->right = next;
    }
    else
    {
        addToTree( &(*root)->left, next );
    }
}
}
/// Dynamically build BST by allocating nodes on the heap
/// Note that the BST will support duplicate values by
/// placing them into the left child's subtree
/// @param root - a pointer to the pointer to the root of the tree
///               to build this tree on to.
/// @param elements - array of integers to add to the tree
/// @param count - the number of integers in the array
void build_tree(TreeNode** root, const int elements[], const int count)
{
struct TreeNode *new = (struct TreeNode*) malloc( sizeof( struct TreeNode ));
new->data = elements[0];
new->left = NULL;
new->right = NULL;
free( root );
*root = new;
int i;
for( i = 1; i < count; i++ )
{
    struct TreeNode next = {elements[i], NULL, NULL};
    addToTree( root, &next );
}
}
/// The main function presents the core features of the C language.
/// @param argc  number of command line arguments, including program name
/// @param argv  supplied command line arguments, including program name
/// @returns error_code  the error Code; 0 if no error
int main(int argc, char* argv[])
{
if( argc != 2 )
{
    printf( "Usage: bst #\n" );
    return 1;
}
int numNodes = atoi( argv[1] );
if( numNodes <= 0 )
{
    printf( "# must be greater than 0\n" );
    return 1;
}

char buff[80];
int nodeVals[numNodes];
printf( "Enter %d integer values to place in tree:\n", numNodes );
int i;
for( i = 0; i < numNodes; i++ )
{
    if(fgets(buff, 80, stdin) == NULL)
    {
        printf("\nError reading Node Values.\n");
        return 1;
    }
    else
    {
        nodeVals[i] = atoi( buff );
    }
}

printf( "Input values:\n" );
for( i = 0; i < numNodes; i++ )
{
    printf( "%d\n", nodeVals[i] );
}

TreeNode *root = malloc( sizeof( TreeNode ) );
build_tree( &root, nodeVals, numNodes);
printf( "Preorder:\n" );
traverse( root, PREORDER );
printf( "Inorder:\n" );
traverse( root, INORDER );
printf( "Postorder\n" );
traverse( root, POSTORDER );
return 0;
}

这是我的bst.h

#ifndef BST_H
#define BST_H

typedef struct TreeNode {
int data ;                  // the data stored in the node
struct TreeNode* left ;     // node's left child
struct TreeNode* right ;    // node's right child
} TreeNode;

typedef enum {
PREORDER,           // parent -> left -> right
INORDER,            // left -> parent -> right
POSTORDER           // left -> right -> parent
} TraversalType;

void build_tree(TreeNode** root, const int elements[], const int count);

void traverse(const TreeNode* root, const TraversalType type);

void cleanup_tree(TreeNode* root);

#endif

这是一些示例输出

$ bst 7
Enter 7 integer values to place in tree:
6
1
42
3
24
18
5
Input values:
6
1
42
3
24
18
5
Preorder:
6
1
3
5
42
24
18
Inorder:
1
3
5
6
18
24
42
Postorder:
5
3
1
18
24
42
6

有人可以帮我吗？也许还可以解释一下指针。

Answer 1

这段代码有问题:

for( i = 1; i < count; i++ )
{
    struct TreeNode next = {elements[i], NULL, NULL};
    addToTree( root, &next );
}

addToTree 函数只是将您给它的指针放入树中。然而，这是一个指向在当前循环迭代结束时不再存在的对象的指针。

我想您想在每次迭代中动态分配next，而不是使用本地对象。

(可能还有其他问题，在快速扫描代码时，我只发现了这个问题)。