對於任務,我必須製作兩種方法,一種是打印出一個存儲幾個單詞的數字樹,並在實際單詞旁邊標記*
。另一種方法應該是找到這個數字樹中最長的單詞。下面是定義的類(我已完成的打印方法):從C++的數字樹(trie)中找出最長的單詞
class DTN {
public:
DTN() :
is_word(false), word_to_here(""), children()
{}
DTN (bool iw, std::string wth) :
is_word(iw), word_to_here(wth), children()
{}
bool is_word;
std::string word_to_here;
ics::ArrayMap<char,DTN> children;
};
//Add a word correctly into a Digital Tree (of strings)
void add_a_word (DTN& dtn, std::string prefix, std::string postfix) {
if (postfix.size() == 0) {
dtn.is_word = true;
return;
} else {
char first = postfix[0];
if (!dtn.children.has_key(first))
dtn.children[first] = DTN(false,prefix+first);
return add_a_word(dtn.children[first],prefix+first,postfix.substr(1));
}
}
//Print dtn, its n children indenter, their n children indented....
void print_DTN_tree(const DTN& dtn, std::string indent) {
std::cout << indent << dtn.word_to_here << (dtn.is_word? "*" : "") << std:: endl;
for (auto n : dtn.children)
print_DTN_tree(n.second, indent+" ");
}
bool is_a_word (const DTN& dtn, std::string remaining_letters) {
if (remaining_letters.empty())
return dtn.is_word; //all letters in tree; is it a word?
else if (dtn.children.has_key(remaining_letters[0]) == false)
return false; //some letters not in truee: it isn't a word
else
return is_a_word(dtn.children[remaining_letters[0]], //check the next letter
remaining_letters.substr(1));
}
void add_a_word (DTN& dtn, std::string word) {
add_a_word(dtn,"",word);
}
std::string longest_word (const DTN& dtn) {
// add this method
}
我得到了印刷法迭代和遞歸的混合工作,並認爲找到最長的單詞是相似的,這意味着所有我會的需要做的是迭代我的樹,調用一個函數來檢查它是否是一個單詞,如果是,將它與當前最長的單詞進行比較,但是當它找到最長的單詞時,它不會自動返回,並且繼續前進到下一個單詞。我應該如何着手解決這個問題,(或者甚至是關於如何解決這個問題的一般想法,我會讚賞,因爲這個課程),以我目前的實施?
您是否使用過調試器並單步執行代碼,使用小數據樣本? – 2015-02-10 23:38:36
它怎麼能知道它剛剛找到的單詞是樹中最長的一個詞,而沒有繼續檢查其餘的單詞? – Beta 2015-02-11 00:34:00
「ics :: ArrayMap children'的關鍵是什麼? 'is_word'是什麼意思?即什麼是不是一個單詞的節點?只有沒有孩子的葉子有詞嗎? –
tofi9
2015-02-11 03:35:40