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与地图实现

回答

相关问题