错误执行Trie树

我想插入一个字符串，并使用trie数据结构进行搜索运行。这是我第一次使用指针的实现，所以我真的很困惑我在代码中做了什么错误，它给编译错误。请帮助调试它，并请告诉我在我的指针逻辑中出了什么问题。错误执行Trie树

typedef struct trie { 
    unordered_multimap<char, struct trie> child; 
    bool isEnd; 
} trie; 
trie* newtrienode() 
{ 
    trie* newnode = (trie*)malloc(sizeof(trie)); 
    newnode->isEnd = false; 
    return newnode; 
} 
trie* root = newtrienode(); 
void insert(string word) 
{ 
    trie* current = root; 
    for (int i = 0; i < word.length(); i++) { 
     char ch = word[i]; 
     trie* node = current->child[ch]; 
     if (node == NULL) { 
      trie* node = newtrienode(); 
      current->child.insert(pair<char, trie>(ch, node)); 
     } 
     current = node; 
    } 
    current->isEnd = true; 
} 
bool search(string word) 
{ 
    trie* current = root; 
    for (int i = 0; i < word.length(); i++) { 
     char ch = word[i]; 
     trie* node = current->child[ch]; 
     if (node == NULL) { 
      return false; 
     } 
     current = node; 
    } 
    return true; 
}

来源

2017-01-21 query

什么是编译错误？ – Sabuncu

@Sabuncu如果你编译它并且看到它们会更好，因为它是一个很长的错误线程。把这个错误留在这里会使它很难阅读，我希望你明白。 – query

a）你应该发布错误，以便为未来的读者提供一个很好的问题。 b）代码不是一个完整的最小例子。 – drescherjm

除了在评论中提到的内容，我看到了一些代码问题。

trie* newnode = (trie*)malloc(sizeof(trie));

这并不创建trie类型的对象，它仅分配存储块的trie大小和分配指向它的指针到可变newnode。特别是，它不会调用unordered_multimap的构造函数。任何通过该指针访问child成员都会产生未定义的行为。此外，你永远不会释放内存。

typedef struct trie { 
    unordered_multimap<char, struct trie> child; 
    bool isEnd; 
} trie;

在第二线您正在声明一个unordered_multimap数据成员与一个不完全类型trie作为第二个模板参数。一些编译器允许这样做，但标准并不要求它们。另一方面，需要将shared_ptr作为模板参数与不完整类型一起使用。而且，一个节点每个字符只能有一个子树，所以你不需要一个multimap;一张地图就足够了。所以我建议使用unordered_map<char, shared_ptr<trie>>并用shared_ptr<trie>替换所有出现的。它也将负责在发布root之后删除对象。

的newtrienode()功能看起来像这样：

shared_ptr<trie> newtrienode() 
{ 
    shared_ptr<trie> newnode (new trie()); 
    newnode->isEnd = false; 
    return newnode; 
}

trie* node = current->child[ch]; 
if (node == NULL) {

operator[]不会返回NULL当键不存在。它将一个默认构造的对象插入到容器中，并将引用返回给它。为了检查密钥是否存在，请使用find或count。

trie* node = current->child[ch]; 
if (node == NULL) { 
    trie* node = newtrienode(); 
    current->child.insert(pair<char, trie>(ch, node)); 
} 
current = node;

注意的是，在第三行你宣布一个新的变量。第一行声明的变量node不会更改。

来源

2017-01-22 00:37:54 Anton

错误执行Trie树

回答

相关问题