0

我正在做一个红黑树实现，目前正在测试“转储”功能。

该函数是对树的有序遍历，它将树中的每个元素保存到一个动态数组中，并返回指向该数组的指针。

经过调试，我发现该功能正常工作，并且数组包含它应该包含的元素。但是当测试函数试图“计算”数组的第一个元素时，我得到

Assignment4.exe has triggered a breakpoint.

然后malloc.c打开这个：

__forceinline void * __cdecl _heap_alloc (size_t size)

{

    if (_crtheap == 0) {
        _FF_MSGBANNER();    /* write run-time error banner */

        _NMSG_WRITE(_RT_CRT_NOTINIT);  /* write message */
        __crtExitProcess(255);  /* normally _exit(255) */
    }

→    return HeapAlloc(_crtheap, 0, size ? size : 1);
}

所以这里是可能是罪魁祸首的代码：

功能：

int* /*T*/ RedBlackTree::dump(int& number)
{
    int* /*T*/ arr = new int(n);
    number = 0;

    inOrder(root, arr, number);

    return arr; //returns pointer to entire tree in ascending order
}

void RedBlackTree::inOrder(Node* nd, int* /*T*/ arr, int& num)
{
    if(nd != NULL)
    {
        inOrder(nd->left, arr, num);
        arr[num] = nd->data;
        num++;
        inOrder(nd->right, arr, num);
    }

}

和测试功能：

int main()
{
    RedBlackTree tree;

    //insert test
    tree.insert(15);
    tree.insert(20);
    tree.insert(20);
    tree.insert(21);
    tree.insert(48);
    tree.insert(18);
    tree.insert(1);
    tree.insert(7);
    tree.insert(25);

    //dump test
    int* arr = new int(tree.size());
    int n = 0;
    arr = tree.dump(n);

    for(int i = 0; i < n; i++)
    {
→       cout << arr[i] << " ";
    }

    return 0;
}

我在触发错误的行上放了一个箭头。

我检查了调试器并快速观察了从 i = 0 到 i = 8 的每个元素在执行该行之前确实存在于数组中。

谢谢大家的帮助！

4

1 回答 1

0 
int* arr = new int(tree.size());
int n = 0;
arr = tree.dump(n);

这是问题所在。

您首先将一个数组分配给arrwith tree.size()，看起来不错。但是，在tree.dump(n)您内部分配了另一个具有大小的数组n并返回到arr. 此时，arr实际上是一个大小n为 0 的数组。访问这个数组应该是非法的。

另一方面，如果你这样写，会导致内存泄漏，即原来指向的内存arr将丢失处理到另一个内存地址分配arr上tree.dump(n)。

记住delete你所拥有的new，这是一个很好的编程习惯。

于 2013-07-19T02:30:18.420 回答