реализовать tr ie in cpp - PullRequest
Новая
       48

реализовать tr ie in cpp

1 голос
/ 11 марта 2020

Я хочу реализовать tr ie в cpp. Когда я попытался распечатать все строки в tr ie, ничего не было напечатано. Но код был успешно скомпилирован. Я думаю, что-то не так с моей вставкой. Я предполагаю, что я должен пройти по ссылке где-нибудь, чтобы tr ie был действительно изменен, но я не уверен, где или в чем проблема.

Моя структура: 

struct Node {
    unordered_map<char, Node*> children;
    bool completeWord;
};

class Trie {
private:
    Node* root;
    void printAll(Node* tmp);
public:
    Trie();
    void insert(string s);
    void printAll();
};

Trie::Trie() {
    root = new Node();
    root->completeWord = false;
}

Методы: 

void Trie::insert(string s) {
    Node* p = root;
    for(char c : s) {
        auto m = p->children;
        if(!m.count(c)) {
            Node* n = new Node();
            m.insert(pair<char, Node*>(c,n));
        }
        else
            p = m[c];
    }
    p->completeWord = true;
}

printВсе для отладки: 

void Trie::printAll() {
    printAll(root);
}

void Trie::printAll(Node* tmp) {
    Node* t = tmp;
    auto m = t->children;
    if(!m.empty()){
        for(auto p : m) {
            cout << p.first << " ";
            printAll(p.second); 
        }
    }
}

Контрольные примеры: 


int main() {
    Trie* t = new Trie();
    string arr[] = {"abc", "abcd", "lmn", "edf"};
    for(string s : arr) 
        t->insert(s);
    t->printAll();
    return 0;
}

1 Ответ

0 голосов
/ 12 марта 2020

Благодаря @ Hitobat и @ Code-Apprentice Я понял, что я сделал не так. В моем insert это должно быть: 

void Trie::insert(string s) {
    Node* p = root;
    for(char c : s) {
        auto &m = p->children; //m -> &m
        if(!m.count(c)) {
            Node* n = new Node();
            m.insert(pair<char, Node*>(c,n));
        }
        p = m[c]; //remove else
    }
    p->completeWord = true;
}

m раньше был просто указателем на пары карт, без & он просто вносил бы изменения в копии этих пар, а не в сами эти пары , Поэтому мне нужно было передать их по ссылке. И p не обновлялся при вставке нового узла.

...