在特里數據結構

我試圖把所有單詞的線索在一個串中，詞由eow場表示在特里數據結構中的某些字符是真正的所有的話，因此特里樹能可能有字母比導致了無字，爲前「ABC」是該線索，但「C」的酸性氧化電位水場是假的那麼‘ABC’不是一個單詞在特里數據結構

這裏是我的數據結構

struct Trie { 

    bool eow; //when a Trie field isWord = true, hence there is a word 
    char letter; 
    Trie *letters[27]; 

};

，這裏是我的attemped打印所有功能，基本上是試圖返回由空格單詞分隔在一個字符串中的所有單詞

點

string printAll(string word, Trie& data) 
{ 
    if (data.eow == 1) 
    return word + " "; 
    for (int i = 0; i < 26; i++) { 
    if (data.letters[i] != NULL) 
    printAll(word + data.letters[i]->letter, *(data.letters[i])); 
} 
    return ""; 
}

它不是輸出我想要什麼，有什麼建議？

來源

2012-10-20 John Smith

我不認爲「引爆」是你想要的字。 – zwol

你不使用你的遞歸調用printAll()的返回值，讓你產生子的話都將丟失。嘗試這樣的：

string printAll(string word, const Trie& data) 
{ 
    string words; 

    if (data.eow) 
    words += word + " "; 
    for (int i = 0; i < 26; i++) { 
    if (data.letters[i] != NULL) 
    words += printAll(word + data.letters[i]->letter, *(data.letters[i])); 
    } 
    return words; 
}

它是值得的，這是有點低效的，因爲它分配大量的臨時字符串。每個遞歸調用都有自己的words字符串，它被構建，返回並銷燬。將所有單詞添加到一個字符串會更好。

你也可以考慮用字的載體，而不是用空格將它們放在一起。這樣你可以更輕鬆地迭代每個單詞。

void getWords(const Trie& data, vector<string> &words, string word = "") 
{ 
    if (data.eow) 
    words.push_back(word); 

    for (int i = 0; i < 26; i++) { 
    if (data.letters[i] != NULL) 
     getWords(*(data.letters[i]), words, word + data.letters[i]->letter); 
    } 
}

然後調用它：

vector<string> words; 
getWords(trie, words); 

for (size_t i = 0; i < words.size(); ++i) { 
    if (i > 0) 
    cout << " "; 

    cout << words[i]; 
} 

cout << endl;

來源

2012-10-20 17:00:21

非常感謝！ :) –

- 約翰Kugelman - 如果我有一個前綴作爲輸入，並希望只打印從前綴的單詞向前？ ..我想設置一個指向前綴的最後一個字母的指針，但我覺得很難，因爲我的printall函數會在前綴前面打印單詞，因爲這些都是單詞？有任何想法嗎？ –

在特里數據結構

回答

相關問題