算法 - VoidCC

-4

我正在编写一个多路树，它将加载到需要单词和短语的字典中。所以首先将字典加载到trie中。算法

来源

2016-02-14 user5746449

你想让我们做什么？根据你的描述为你写一个函数？ –

和你指的是什么意思？给你一个链接到dfs？向你解释什么是dfs，实施你的dfs？ –

示例算法会非常有帮助，但我不确定此网站是为了这个吗？我是新人，所以我不确定。 – user5746449

这是一些（几乎）C++改编自下面的文章： http://www.toptal.com/java/the-trie-a-neglected-data-structure

，一个是用Java编写的，所以我已经采取的把它给你在C++中的礼貌。

struct Alphabet{ 
    char[] x = 'abcdefghijklmnopqrstuvwxyz'; 

    int findIndex(const char* s){ 
     for(int i = 0; i < 26; ++i){ 
      if(x[i] == *s){ 
       return i; 
      } 
     } 

     return -1; 
    } 
}; 

struct MWTrieNode{ 
    std::vector::<MWTrieNode*> children; 
    bool isLast = false; 
} 

MWTrieNode* getWord(const char* s, int len, MWTrieNode* root){ 

    MWTrieNode* node = root; 
    Alphabet a; 
    for(int i = 0; i < len; i++){ 
     const char* currChar = s[i]; 
     int index = a.findIndex(currChar); 

     MWTrieNode* child = node->children[index]; 

     if(!child){ 
      // No such word 
      return NULL; 
     } 

     // step into the MWTrieNode 
     node = child; 
    } 

    return node; 
} 

// * corrected comparison between char* and char. (using *(char*))

您可以修改getWord功能采取一些参数来修改你如何回报你的话。

但是这应该让你开始。

对于完成，您需要找到某个前缀下的所有单词（我想象一下）。因此，您希望'从搜索前缀的根部（即“House” - >“Housewife”，“Housing”，“Household”等）开始构建多个“子树”。

如果您通过在'Ho'中，你会发现一个没有Node的'部分单词'，最后说到这里，你可以从'o'节点开始。存储既是他们自己的单词，又是长单词的一部分的单词，例如家庭，房主，家庭破坏者

那些节点必须有

isLast == true

，但也有子节点。特殊情况下，应该可以帮助你找到自动完成的多个选项。你是ru对单个搜索使用

getWord

方法几次，使用不同的前缀和条件。结果应该是包含所有你想要的前缀的单词列表。

来源

2016-02-14 08:19:23 Decoded

'findIndex'好像不对 - 比较'char'和'char *' –

嘿！接得好。正如我所说这是“几乎”C++，我写了它匆忙。 :)。只是想让他开始。我想它应该是std :: string，因为我们正在谈论C++。 – Decoded

kfsone我喜欢你所做的改变，但是如果你要以const的形式传递它，你不应该在循环中将char *设置为const char *吗？或者提醒后来的编码人员不要修改字符是一种很好的做法。 – Decoded

-1

我相信阿尔瓦拉多和米尔扎教授会对你的文章内容高度兴趣。

来源

2016-02-16 08:47:18

算法

回答

相关问题