字典树的C++实现

时间:2021-10-20 15:06:42

此次代码使用了诸多新鲜玩意,比如自动类型推断,模板类等等,感觉真的超级好玩啊。

自己做了一个简易的测试,程序的健壮性什么的还是比较差的,此程序留待以后进行功能补全。

#pragma once
#include<cstddef>
#include<string>
using std::strlen;
using std::pair;
using std::make_pair; //字典树节点
template<int size>
class TrieNode
{
public:
TrieNode() :NodeSize(), TerminableSize()
{
for (size_t i = ; i < size; i++)
{
ChildNode[i] = NULL;
}
}
~TrieNode()
{
for (size_t i = ; i < size; i++)
{
delete ChildNode[i];
ChildNode[i] = NULL;
}
} public: //为了方便,此处将变量暴露,后续可以改进为通过接口操作
int NodeSize; //记录此节点子节点的个数
int TerminableSize; //存储以此节点结尾的字符串个数
TrieNode* ChildNode[size]; //记录指向子节点的指针
}; //字典树
template < int Size, typename Type> class Trie
{
public:
typedef TrieNode<Size> Node;
typedef TrieNode<Size>* pNode; public:
Trie() :root(new Node) {}
~Trie() { delete root; } public:
template<typename itr>
void insert(itr beg, itr end);
void insert(const char* str); template<typename itr>
pair<bool,int> find(itr beg, itr end);
pair<bool,int> find(const char* str); template<typename itr>
bool DownNodeAlone(itr beg); template<typename itr>
bool erase(itr beg, itr end);
bool erase(const char* str); int sizeAll(pNode);
int sizeNodeRedundant(pNode); public:
pNode root;
private:
Type index;
}; template < int Size, typename Type>
template<typename itr>
void Trie<Size, Type>::insert(itr beg, itr end)
{
pNode cur = root, pre = NULL; for (; beg != end; ++beg)
{
if (!cur->ChildNode[index[*beg]])
{
cur->ChildNode[index[*beg]] = new(Node);
++cur->NodeSize;
}
pre = cur;
cur = cur->ChildNode[index[*beg]];
}
if (pre)
++pre->TerminableSize;
} template < int Size, typename Type>
void Trie<Size, Type>::insert(const char* str)
{
return insert(str, str + strlen(str));
} template <int Size, typename Type>
pair<bool, int> Trie<Size, Type>::find(const char* str)
{
return find(str, str + strlen(str));
} template <int Size, typename Type>
template<typename itr>
pair<bool,int> Trie<Size, Type>::find(itr beg, itr end)
{
pNode cur = root, pre = NULL;
pair<bool, int> res(false, );
for (;beg != end;++beg)
{
if (!cur->ChildNode[index[*beg]])
{
return res;
}
pre = cur;
cur = cur->ChildNode[index[*beg]];
}
if (pre != NULL&&pre->TerminableSize > )
{
res.first = true;
res.second = pre->TerminableSize;
}
return res;
} template <int Size, typename Type>
template<typename itr>
bool Trie<Size, Type>::DownNodeAlone(itr beg)
{
pNode cur = root;
int terminableSum = ; while (cur->NodeSize != )
{
terminableSum += cur->TerminableSize;
if (cur->NodeSize > )
return false;
else
{
for (size_t i = ; i < Size; i++)
{
if (cur->ChildNode[i])
{
cur = cur->ChildNode[i];
}
}
}
}
if (terminableSum == )
return true;
else return false;
} template <int Size, typename Type>
template<typename itr>
bool Trie<Size, Type>::erase(itr beg, itr end)
{
auto var = find(beg, end);
if (var.first)
{
pNode cur = root, pre = NULL;
for (; beg != end; ++beg)
{
if (DownNodeAlone(cur))
{
delete cur;
cur = NULL;
return true;
}
pre = cur;
cur = cur->ChildNode[index[*beg]];
}
if (pre->TerminableSize > )
--pre->TerminableSize;
return true;
}
return false;
} template <int Size, typename Type>
bool Trie<Size, Type>::erase(const char* str)
{
auto var = find(str);
if (var.first)
{
erase(str, str + strlen(str));
return true;
}
return false;
} template <int Size, typename Type>
int Trie<Size, Type>::sizeAll(pNode ptr)
{
if (ptr == NULL)
return ;
int rev = ptr->TerminableSize;
for (size_t i = ; i < Size; i++)
{
rev += sizeAll(ptr->ChildNode[i]);
}
return rev;
} template <int Size, typename Type>
int Trie<Size, Type>::sizeNodeRedundant(pNode ptr)
{
if (NULL == ptr)
return ;
int i, rev = ;
if (ptr->TerminableSize > )
rev = ;
if (ptr->NodeSize != )
{
for (i = ; i < Size; ++i)
{
rev += sizeNodeRedundant(ptr->ChildNode[i]);
}
}
return rev;
} template<int Size>
class Index
{
public:
Index() {}
~Index() {} public:
int operator[](char vchar)
{
return (vchar - 'a') % Size;
}
};

测试:

int main(void)
{
{
Trie<, Index<>> temp;
temp.insert("hello");
temp.insert("he");
temp.insert("he");
temp.insert("her");
temp.insert("him");
temp.insert("fuck");
temp.insert("fuckyou");
temp.insert("hupu");
temp.insert("lady");
temp.insert("hahah");
temp.insert("lady");
temp.insert("lady");
temp.insert("lady"); auto var = temp.find("lady");
cout << "lady:" << boolalpha <<var.first <<" "<<var.second<< endl;
var = temp.find("heihei");
cout << "heihei:" << boolalpha << var.first << " " << var.second << endl; cout << "size:" << temp.sizeAll(temp.root) << endl;
cout << "size of NoneRedundant:" << temp.sizeNodeRedundant(temp.root) << endl; var = temp.find("hupu");
cout << "hupu:" << boolalpha << var.first <<" "<<var.second<< endl;
temp.erase("hupu");
var = temp.find("hupu");
cout << "hupu:" << boolalpha << var.first << " " << var.second << endl; cout << "size:" << temp.sizeAll(temp.root) << endl;
cout << "size of NoneRedundant:" << temp.sizeNodeRedundant(temp.root) << endl;
} cin.get();
_CrtDumpMemoryLeaks();
return ;
}