大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie的简单实现(插入、查询)
#include <stdio.h>
#include <string>
using namespace std;
const int branchNum = 26;
struct Trie_node
{
bool isStr;
Trie_node *next[branchNum];
Trie_node()
{
isStr = false;
memset(next, NULL, sizeof(next));
}
};
class Trie
{
public:
Trie();
~Trie();
void insert(const char* word);
bool search(char* word);
void deleteTrie(Trie_node* root);
Trie_node* root;
};
Trie::Trie()
{
root = new Trie_node();
}
Trie::~Trie()
{
deleteTrie(root);
}
void Trie::insert(const char* word)
{
Trie_node *location = root;
while (*word)
{
if (location->next[*word - 'a'] == NULL)
{
location->next[*word - 'a'] = new Trie_node();
}
location = location->next[*word-'a'];
word ++;
}
location->isStr = true;
}
void Trie::deleteTrie( Trie_node* root )
{
if (root == NULL)
{
return;
}
for (int i = 0; i < branchNum; i ++)
{
deleteTrie(root->next[i]);
}
delete root;
}
bool Trie::search( char* word )
{
Trie_node *locaton = root;
while (*word && locaton)
{
locaton = locaton->next[*word - 'a'];
word ++;
}
return(locaton != NULL && locaton->isStr);
}
int main()
{
Trie trie;
trie.insert("helloworld!");
trie.insert("he!");
trie.insert("helloworlda!");
if (trie.search("helloworld!"))
{
printf("true\n");
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/120235.html原文链接：https://javaforall.net
