我在用C ++写Prefix Tree类。树中的每个节点都有一个长度为Node*的27数组。这些是用来容纳字母和空格。我通过将所有字母都转换为小写字母并将所有符号转换为空格来清理对树的所有输入。在析构函数中,我调用一个名为clear的函数,该函数接受一个节点(首先是根节点)。编写单元测试时,它只能成功通过一个测试,而第二个调用Prefix类上的析构函数的测试将失败,并出现双重释放或损坏错误。我之前曾经遇到过这个问题,并且能够检测出问题并加以解决,但是我无法弄清楚是什么原因造成的,下面是一些代码:

节点结构:

const unsigned int B_FACTOR = 27;  // a..z plus space

struct Node_t {
    bool word;
    Node_t *links[B_FACTOR];
    Node_t(): word(false) {}
};


插入(公共和私人):

bool Prefix::insert(string thing) {
    sanitize(thing);
    if(!root) root = new Node_t();
    if(thing == "") return true;
    insertPrivate(thing, root);
    return true;
}

void Prefix::insertPrivate(string input, Node_t *node) {
    if(input == "") {
        node->word = true;
        return;
    }
    int idx = (int(input[0])-97) >= 0 ? (int(input[0])-97) : 26;
    if(!node->links[idx]) node->links[idx] = new Node_t();
    insertPrivate(input.substr(1, input.length()), node->links[idx]);
}


析构函数:

Prefix::~Prefix() {
    clear(root);
}


明确:

void Prefix::clear(Node_t *node) {
    if(!node) return;
    cout << "On Node " << endl;
    for (int i = 0; i < 26; ++i) {
        clear(node->links[i]);
    }
    delete node;
}


单元测试:

void testInsert0() {
    cout << "testInsert0" << endl;
    Prefix a;
    a.insert("a");
    TS_ASSERT(a.isStored("a"));
}

void testInsert1() {
    cout << "testInsert1" << endl;
    Prefix b;
    b.insert("dd");
    TS_ASSERT_EQUALS(b.isStored("d"), false);
}

void testInsert2() {
    cout << "testInsert2" << endl;
    Prefix a;
    a.insert("abcdef");
    TS_ASSERT(!a.isStored("abcd"));
}


进行测试的输出是这样的:

Running cxxtest tests (4 tests).testInsert0
On Node
On Node
.testInsert1
Post test
On Node
On Node
On Node
On Node
On Node
*** Error in `./testrunner': double free or corruption (out): 0x00000000019652a0 ***
make: *** [test] Aborted (core dumped)


当我注释掉析构函数中调用clear函数的代码时,所有代码都可以工作(当然会有很多内存错误),但是当析构函数处于活动状态时,它不能使其超过2个行使其功能的完整单元测试。

最佳答案

这可能是并非所有变量都被初始化的情况,这导致对delete的虚假调用。在使用每个链接之前,请确保将Node_t结构的每个链接设置为nullptr

还请检出Valgrind,它在虚拟机中运行程序以检查常见的内存问题-这对于这种情况非常有用。

07-28 04:32