0

すべての単語を文字列のトライに入れようとしています。単語はeow、トライデータ構造内の特定の文字に対して真であるフィールドによって示されます。したがって、トライには、単語がなくなるよりも文字が含まれる可能性があります。 「abc」はトライに含まれていますが、「c」の eow フィールドが false であるため、「abc」は単語ではありません

これが私のデータ構造です

struct Trie {

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

};

基本的に、単語のスペースで区切られた1つの文字列ですべての単語を返そうとしています

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各再帰呼び出しには、作成、返され、破棄される独自の文字列があります。すべての単語を 1 つの文字列に追加する方がよいでしょう。

また、単語をスペースで追加するのではなく、単語のベクトルを使用することを検討することもできます。そうすれば、各単語をより簡単に反復できます。

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 に答える