我正在尝试实现 trie 数据结构并编写了以下代码
#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
struct trie_node{
map<char, trie_node> child;
int pos=-1;
};
map<char, trie_node> baap;
void lex_insert(string s, int pos){ // lexiographically insert into map
trie_node t = baap[s[0]];
for(int i=1; i<s.size(); i++){
t = t.child[s[i]];
}
t.pos = pos;
}
int find(string s, int r){ // find in trie structure
trie_node t = baap[s[0]];
int pos = t.pos;
for(int i=1; i<s.size(); i++){
if(t.child.find(s[i])!=t.child.end()){
t = t.child[s[i]];
if(t.pos<=r)
pos = t.pos;
}
else
return pos;
}
return pos;
}
void ans(int &found, string s){ // find lexiographically matching prefix
trie_node t = baap[s[0]];
if(found<0){
while(t.pos<0){
auto x = t.child.begin();
t = x->second;
}
found = t.pos;
}
}
int main(){
int n; cin>>n;
vector<string> vs(n);
for(int i=0; i<n; i++){
cin>>vs[i];
lex_insert(vs[i],i);
}
int found = 0;
int q; cin>>q;
for(int i=0; i<q; i++){
int r; string p;
cin>>r>>p;
found = find(p,r);
ans(found, p);
cout<<vs[found]<<'\n';
}
}
请关注lex_insert()
代码执行无误,但当我尝试取消引用 map 时 - baap
,出现段错误。我想这是因为我没有像我在某些代码中看到的那样在 lex_insert
中的每个级别构建新节点。但是, map 应该进行动态分配。有人可以解释一下,为什么我无法访问 map 的元素 - baap
吗?
注意 - 它不是一个精确的 trie 实现,而是派生自它
最佳答案
问题的一个可能原因:
trie_node t = baap[s[0]];
此处 t
将是 baap[s[0]]
的拷贝。您对 t
所做的任何更改都不会反射(reflect)在原始文件中。
由于您稍后在循环中重新分配给 t
(再次制作拷贝),因此您不能使用引用(不能重新绑定(bind)引用)。相反,您必须使用指针。要么在映射中存储指针,要么使用 address-of 运算符获取指针:
trie_node* t = &baap[s[0]]; // Get a pointer to the node
至于崩溃,如果上面没有解决,那你应该learn how to debug your programs .尤其是对于崩溃,您应该学习如何使用调试器来捕获正在发生的崩溃,以及如何在代码中找到它发生的位置。
关于c++ - 在不创建新节点的情况下使用 map 实现 trie,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50692707/