c++数据结构字典树
时间: 2023-11-26 20:47:24 浏览: 46
字典树(Trie)是一种树形结构,用于高效地存储和检索字符串数据集中的键值。它的核心思想是利用字符串之间的公共前缀,将重复的前缀合并在一起,从而减少存储空间和查询时间。下面是一个简单的C++实现:
```c++
#include <iostream>
#include <unordered_map>
using namespace std;
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool is_word;
TrieNode() {
is_word = false;
}
~TrieNode() {
for (auto& child : children) {
delete child.second;
}
}
};
class Trie {
public:
Trie() {
root = new TrieNode();
}
~Trie() {
delete root;
}
void insert(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c]; }
node->is_word = true;
}
bool search(string word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
return false;
}
node = node->children[c];
}
return node->is_word;
}
bool startsWith(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (!node->children.count(c)) {
return false;
}
node = node->children[c];
}
return true;
}
private:
TrieNode* root;
};
int main() {
Trie trie;
trie.insert("apple");
cout << trie.search("apple") << endl; // 输出:1
cout << trie.search("app") << endl; // 输出:0
cout << trie.startsWith("app") << endl; // 输出:1
trie.insert("app");
cout << trie.search("app") << endl; // 输出:1
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)