0

我正在尝试将所有单词放在字符串中的 trie 中，单词由eowtrie 数据结构中某个字符的字段为真表示，因此 trie 可以有字母而不是导致没有单词，例如“abc”在 trie 中，但“c”的 eow 字段为假，因此“abc”不是单词

这是我的数据结构

struct Trie {

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

};

这是我尝试的 print-all 函数，基本上是试图返回一个字符串中的所有单词，单词之间用空格分隔

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 "";
}

它没有输出我想要的东西，有什么建议吗？

4

1 回答 1

1

您没有使用递归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-20T17:00:21.580 回答