我已经开始使用trie实现一个字典。基本上,我有一个根节点,它有一个定义(指向代表与键关联的值的T
指针)和子节点(指向包含256个节点指针的数组,每个字母一个节点)。请查看以下定义:
template<typename T>
class DiccString {
public:
DiccString() : root(NULL);
DiccString(const DiccString<T>&);
~DiccString() {delete root;}
void define(const string& key, const T& value);
bool isDefined(const string& key) const;
const T& getDefinition(const string& key) const;
T& getDefinition(const string& key);
void remove(const string& key);
const Set<string>& keys() const;
private:
struct Node{
Node** childs;
T* definition;
Node(){
std::cout << "Node has been created " << this << std::endl;
childs = new Node*[256];
definition = NULL;
}
~Node(){
std::cout << "Node has been deleted " << this << std::endl;
delete definition;
delete [] childs;
}
};
Node* root;
};
所以,假设没有其他键,如果我想要存储值为14的"John"(
T
将会是int
),那么我需要创建一个根节点,然后在root->childs[(int)'j']
上创建另一个节点“nodeJ”,然后是nodeJ->childs[(int)'o']
,一直到达最后一个节点“nodeN”,该节点将包含值(nodeN->definition = 14
)。问题出在当我执行以下操作时:
int main() {
DiccString<int> d;
d.define("john",20);
d.define("jane",25);
return 0;
}
我希望所有创建的节点都能被销毁,但请看输出结果:
Node created 0x61fc20 // root
Node created 0x620860 // for letter 'j'
Node created 0x621090 // for letter 'o' (child of 'j' 0x620860)
Node created 0x6218c0 // for letter 'h' (child of 'o' 0x621090)
Node created 0x6220f0 // for letter 'n' (child of 'h' 0x6218c0), value: 20
Node created 0x622990 // for letter 'a' (child of 'j' 0x620860)
Node created 0x6231c0 // for letter 'n' (child of 'a' 0x622990)
Node created 0x6239f0 // for letter 'e' (child of 'n' 0x6231c0), value: 25
Node deleted 0x61fc20 // root
只删除了根。所以显然,在
Node
的析构函数中执行delete [] childs
时,它没有删除数组的所有元素,我确定这些元素实际上是存在的:例如,在调用根的析构函数时(实际上只有这个被调用),我评估了childs[(int)'j']
,它肯定是0x620860,所以当执行delete [] childs
时,它应该调用这个元素(至少)的析构函数,对吗?我做错了什么?