给出一个前缀树的实现和使用的例子,用C++
时间: 2024-04-09 16:27:53 浏览: 62
C++前缀树trie的实现
以下是一个基本的前缀树的实现和使用示例,使用C++语言:
```cpp
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isEndOfWord;
TrieNode() {
isEndOfWord = false;
}
};
class Trie {
private:
TrieNode* root;
public:
Trie() {
root = new TrieNode();
}
void insert(string word) {
TrieNode* current = root;
for (char ch : word) {
if (current->children.find(ch) == current->children.end()) {
current->children[ch] = new TrieNode();
}
current = current->children[ch];
}
current->isEndOfWord = true;
}
bool search(string word) {
TrieNode* current = root;
for (char ch : word) {
if (current->children.find(ch) == current->children.end()) {
return false;
}
current = current->children[ch];
}
return current->isEndOfWord;
}
bool startsWith(string prefix) {
TrieNode* current = root;
for (char ch : prefix) {
if (current->children.find(ch) == current->children.end()) {
return false;
}
current = current->children[ch];
}
return true;
}
};
int main() {
Trie trie;
// 插入一些单词
trie.insert("apple");
trie.insert("banana");
trie.insert("orange");
// 搜索单词
cout << trie.search("apple") << endl; // 输出: 1 (true)
cout << trie.search("grape") << endl; // 输出: 0 (false)
// 检查前缀
cout << trie.startsWith("app") << endl; // 输出: 1 (true)
cout << trie.startsWith("gr") << endl; // 输出: 0 (false)
return 0;
}
```
上述代码中,我们定义了`TrieNode`类表示前缀树的节点,每个节点有一个`unordered_map`用于存储子节点。`Trie`类实现了插入、搜索和前缀匹配功能。在`main`函数中,我们创建了一个`Trie`对象,并插入了一些单词。然后我们进行了一些搜索和前缀匹配操作,并输出结果。
这只是一个简单的前缀树实现,你可以根据需要进行扩展和优化。
阅读全文