Trie與地圖實現

我今天正在解決一個問題。但我被困住了。我知道如何工作，但問題是，我知道如何用靜態數組和類來實現它。今天在網上衝浪，我讀到有一種方法可以實現使用stl :: map的嘗試。我今天嘗試過，但我仍然不知道如何在int上插入元素。這個結構。Trie與地圖實現

EDIT1：我試圖解決這個問題：spoj.com/problems/TAP2012D 我想知道如何與 EDIT2添加的話線索：我知道地圖是如何工作的，我只是不知道如何使用地圖工作。我想要一個知道嘗試的人。

這裏是香港專業教育學院迄今所做

const int ALPH_SIZE = 26; 
using namespace std; 

struct trie{ 
    map<char,int> M; 
    int x,y; 
    trie(); 
}; 

trie T[1000000]; 


trie::trie() 
{ 
    x=y=0; 
} 
int maximo; 


void addtrie(string palabra) 
{ 
    int tam=palabra.size(); 
    int pos=0; 
    for(int i=0;i<tam;i++) 
    { 
     if(T[pos].M.find(palabra[i])==T[pos].M.end()) 
     { 
      T[pos].M[palabra[i]]=new trie(); 
      T[pos].M[palabra[i]]= 
     } 

    } 

}

來源

2013-02-15 Giuseppe

你真正的問題是？也'trie T [1000000];'可能會溢出 – billz 2013-02-15 02:26:14

@billz我不知道如何添加元素。我的意思是添加功能，我想在它上面添加元素 – Giuseppe 2013-02-15 02:27:24

你的意思是將元素添加到'M'？ – billz 2013-02-15 02:34:09

字典樹節點存儲地圖存在的字符和指示節點是否對應於樹中的單詞的標誌。

struct Node 
{ map<char, Node*> a; 
    bool flag; 

    Node() { flag = false; } 
};

現在插入類似於你用靜態數組做的，除了你在這裏使用地圖。

void insert(Node *x, string s) 
{ for(int i = 0; i < s.size(); i++) 
    { if(x->a.count(s[i]) == 0) 
     /* no outgoing edge with label = s[i] so make one */ 
     { x->a[ s[i] ] = new Node; 
     } 
     x = x->a[ s[i] ]; 
    } 
    x->flag = true; /* new word */ 
}

來源

2015-01-21 20:32:33 saadtaame

非常感謝，這真的很有幫助！ – Giuseppe 2015-03-11 23:52:01

-3

將元素插入一個STL ::地圖正確的方法應該做以下方式

std::map<char,int> M; 


    M.insert (std::pair<char,int>('aaa',1)); 
    M.insert (std::pair<char,int>('bbb',2));

來源

2013-02-15 02:45:18 rockstar

感謝您的回答，但即時通訊嘗試使用地圖實現特里。 – Giuseppe 2013-02-15 02:46:48

實際上，'M [palabra [i]] = ...'對於在地圖中插入元素來說是非常好的。 – jogojapan 2013-02-15 02:57:23

在我看來，使用unordered_map更好。

struct TrieNode { 
     char c; 
     unordered_map<char, TrieNode*>links; 
     bool end; 
    }; 

    TrieNode* insert(TrieNode* root, string word) { 
     TrieNode* current = root; 

     for (auto it: word) { 
      if (current->links.find(it) == current->links.end()) { 
      TrieNode* node = new TrieNode(); // possible memory leak? 
      node->c = it; 
      node->links = {}; 
      node->end = false; 

      current->links[it] = node; 
      } 

     current = current->links[it]; 
     } 

    current->end = true; 
    return root; 
    };

Ofcourse，有可能是具有與您使用new運算符創建TrieNodes內存泄漏的問題。也許某種樹遍歷（基於DFS）以自下而上的方式訪問所有節點並刪除它們，可以幫助避免內存泄漏。

來源

2015-11-18 15:21:55

Trie與地圖實現

回答

相關問題