算法 - 優文庫

-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

算法

回答

相關問題