C++ 中的 TRIE 数据结构实现

Question

我写了一个简单的代码来用 c++ 实现 trie 数据结构。但是当我运行这个程序时，它会给出分割错误作为输出。 请纠正我，我错了。

#include <bits/stdc++.h> 
using namespace std; 
struct trienode {
struct trienode * child[26];
bool isEnd;
trienode()
{
isEnd = false;
for(int i = 0; i < 26; i++)
{
child[i] = NULL;
}
}
};
struct trienode * root;
void insert_str(string &s, int n)
{
trienode * curr = root;
int i;
for(i = 0; i < n; i++)
{
int index = s[i] - 'a';
if(curr -> child[index] == NULL)
{
curr -> child[index] = new trienode();
}
else
{
curr = curr -> child[index];
}
}
curr -> isEnd = true;
}
int main()
{
string s1 = "yash";
insert_str(s1, 4);
}

Answer 1

您尚未为根节点分配任何内存。

通常，您将有一个单独的类来处理整个尝试。然后，它可以分配根节点。

class trie
{
public:
trie()
{
root = new trienode();
}
void insert_str(string &s, int n)
{
...
}
private:
trienode* root;
};
int main()
{
trie t;
string s1 = "yash";
t.insert_str(s1, 4);
}