使用c++写一个字典树程序
时间: 2023-12-10 18:06:30 浏览: 30
以下是使用C++编写的一个字典树程序:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1000005; // 字典树最大节点数
const int MAXM = 26; // 字符集大小
struct TrieNode {
int ch[MAXM]; // 子节点数组
int val; // 节点权值
} trie[MAXN];
int root; // 根节点
int tot = 0; // 当前节点总数
// 插入一个字符串
void insert(char* s) {
int len = strlen(s);
int u = root;
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
if (!trie[u].ch[c]) {
trie[u].ch[c] = ++tot;
}
u = trie[u].ch[c];
}
trie[u].val++; // 末尾节点权值加1
}
// 搜索一个字符串
int search(char* s) {
int len = strlen(s);
int u = root;
for (int i = 0; i < len; i++) {
int c = s[i] - 'a';
if (!trie[u].ch[c]) {
return 0; // 没有找到
}
u = trie[u].ch[c];
}
return trie[u].val; // 返回末尾节点权值
}
int main() {
root = tot = 0; // 初始化根节点和节点总数
char s[105];
while (cin >> s) {
if (s[0] == '#') {
break;
}
insert(s);
}
while (cin >> s) {
if (s[0] == '#') {
break;
}
cout << search(s) << endl;
}
return 0;
}
```
该程序实现了一个简单的字典树,可以进行单词的插入和搜索。其中,`trie`数组表示字典树的节点,每个节点有一个子节点数组`ch`和一个权值`val`,`root`表示字典树的根节点,`tot`表示当前节点总数。程序中的`insert`函数实现了单词的插入,`search`函数实现了单词的搜索。
在使用字典树时,主要的操作就是插入和搜索。插入操作是将单词的每个字符依次加入字典树中,如果该字符的子节点不存在,则新建一个节点。搜索操作是将单词的每个字符依次搜索字典树,如果搜索到某个节点不存在,则说明该单词不存在于字典树中。最后,返回末尾节点的权值即可。
字典树是一种非常实用的数据结构,可以用于解决许多字符串操作问题。在实际应用中,我们可以根据具体的问题需求,对字典树进行一些扩展和优化。