0

解决了

问题最终源于数据结构的设计。要删除根元素，必须有一个堆分配（新）指针指向它，这在数据直接由树保存的原始情况下是不可能的。现在有一个包含所有node数据的结构，其中tree包含所有方法和根指针的类。

我有一个双指针target_address初始化NULL，我必须稍后检查是否*target_address为 NULL。在这两者之间，一个函数保证*target_address指向一个未初始化的值，但 Valgrind 一直抱怨我只有在删除root element时才读取未初始化的值。

template <typename T>
int tree<T>::remove(T target) {
    if (!this)  // root is empty
        return EMPTY;

    tree<T>** target_address = NULL;

    if (tree_find(target, &target_address) == SUCCESS) {
        // expect there to be something in target_address
        if (*target_address == NULL) return EMPTY;  // <---- error happens

        tree_delete(target_address);
        return SUCCESS;
    }
    else return EMPTY;
}

操作的 tree_findtarget_address

template <typename T>
int tree<T>::tree_find(T key, tree<T>*** target_address_handle) {
    // find tree matched by key, or NULL pointer in correct location
    // give tree pointer address back
    tree<T>* root = this;   // <---- ensures *target_address points to valid value, maybe this is problematic?
    tree<T>** target_address = &root;
    while(*target_address) {
        tree<T>* current = *target_address;
        if(typeid(key) == typeid(current->data)) {  
            //  assume comparison operator exists
            if(key == current->data)
                break;
            else if(key < current->data)
                target_address = &current->left;
            else
                target_address = &current->right;
        }
        else return FAIL;
    }
    // if loop exited without breaking, will insert into an empty NULL position
    // else loop exited by matching/breaking, will delete non-NULL tree
    *target_address_handle = target_address;
    return SUCCESS;
}

tree_delete 也抱怨未初始化的值；我很确定它也在抱怨 *target_address

void tree<T>::tree_delete(tree<T>** target_address) {
    tree<T>* target = *target_address;
    // first case: no left subtree, replace with right subtree (or NULL for a leaf) 
    if (!target->left) 
        *target_address = target->right;

    // second case: no right subtree, replace with left subtree
    else if (!target->right) 
        *target_address = target->left;

    // third case: both subtrees, find second largest by taking rightmost left tree
    else {
        tree<T>** second_largest_address = &target->left;  // start at target's left tree
        while ((*second_largest_address)->right)  // keep going right
            second_largest_address = &((*second_largest_address)->right);  
        // reached the rightmost left
        tree<T>* second_largest = *second_largest_address;
        *target_address = second_largest;  // delete target by replacing it with second largest
        // second largest guranteed to not have a right subtree, so can treat as case 2 by shifting
        *second_largest_address = second_largest->left;  
        second_largest->left = target->left;
        second_largest->right = target->right;
    }
    delete target;
}

PS 让 Valgrind 显示行号的提示将不胜感激，编译标志 =-g -Wall -Werror -std=c++11和 Valgrind 的运行-q --track-origins=yes

我按照其他人的问题中的建议尝试了静态链接-static，但这引入了更多问题并且没有解决任何问题......

错误信息

==25887== Conditional jump or move depends on uninitialised value(s)
==25887==    at 0x401764: tree<int>::remove(int) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x4013AA: main (in /home/johnson/Code/tree/treetest)
==25887==  Uninitialised value was created by a stack allocation
==25887==    at 0x40175A: tree<int>::remove(int) (in /home/johnson/Code/tree/treetest)
==25887== 
After reading *target tree address
Before read
==25887== Use of uninitialised value of size 8
==25887==    at 0x401A75: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x40178E: tree<int>::remove(int) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x4013AA: main (in /home/johnson/Code/tree/treetest)
==25887==  Uninitialised value was created by a stack allocation
==25887==    at 0x401A46: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887== 
==25887== Use of uninitialised value of size 8
==25887==    at 0x401AA5: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x40178E: tree<int>::remove(int) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x4013AA: main (in /home/johnson/Code/tree/treetest)
==25887==  Uninitialised value was created by a stack allocation
==25887==    at 0x401A46: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887== 
==25887== Use of uninitialised value of size 8
==25887==    at 0x401AF2: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x40178E: tree<int>::remove(int) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x4013AA: main (in /home/johnson/Code/tree/treetest)
==25887==  Uninitialised value was created by a stack allocation
==25887==    at 0x401A46: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887== 
==25887== Invalid read of size 8
==25887==    at 0x401AF5: tree<int>::tree_delete(tree<int>**) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x40178E: tree<int>::remove(int) (in /home/johnson/Code/tree/treetest)
==25887==    by 0x4013AA: main (in /home/johnson/Code/tree/treetest)
==25887==  Address 0x801f0fc36d is not stack'd, malloc'd or (recently) free'd
4

1 回答 1

2

类似代码if (!this) return EMPTY;是高度可疑的。这是一个无操作，并表示其他地方的未定义行为。难怪 Valgrind 会报告您的代码存在问题。

更糟糕的是，看看里面的代码tree_find：

tree<T>* root = this;   // <-- ensures *target_address points to stack variable !
tree<T>** target_address = &root; // Set out pointer to stack variable

显然root不存在然后tree_find返回。毫无疑问，这是一个错误。

于 2014-07-15T06:56:19.420 回答