錯誤執行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樹

回答

相關問題