1
Trieのデータ構造と私のコードで何が起こっていないのかについて具体的な質問があります。再帰的に挿入を呼び出すと、関数パラメータのルートは常にNULLになります。ここに私のコードは次のとおりです。TrieにNULLポインタを挿入する
コード：
//subNodes is an array of TrieNode pointers that contains indices for all letters in the alphabet
bool insert(const string& word, TrieNode* root, int curI = 0)
//PRE: word must be a valid word in a dictionary
//POST: True when a word is inserted into the Trie, false otherwise
{
if(curI >= word.length()) //word has been scanned fully
{
root->isWord = true;
return true;
}
else //word has more letters to be scanned
{
if(root->subNodes[word[curI] - 'A'] == NULL) //if the current letter of the word is not in the trie
{ // insert the letter and advance the current letter of the word
root->subNodes[word[curI] - 'A'] = new TrieNode(word[curI]);
insert(word, root->subNodes[word[curI] - 'A'], curI++);
}
else //if the currrent letter of the word is in the trie
{ // advance the current letter of the word
insert(word, root->subNodes[word[curI] - 'A'], curI++);
}
}
}
私はsubNodes[word[13]]でsubNodes[word[curI] - 'A']を置き換えることで、これをテストした（13はアルファベットでNための指標であり、私がいない単語をテストしていた）とルートがありませんでしたその呼び出しのために長いNULL。したがって、インデックス作成に何か問題が生じています。誰が何が間違っているのか分かりますか？私はC++のマップやベクトルを使うことを考えました。配列を使用することで意見の相違がありますか？
C++では、関数に渡されたパラメータが評価される順序についての保証はありません。したがって、おそらく、あなたのコンパイラは古いcurIを最後のパラメータとして渡すことにしますが、新しい（増分された）値をwordへのインデックスとして使用します。 –
あなたの問題とは何の関係もない（他のものは既にあなたのためにそれを解決している）が、 'if/else'ブロックから2つの再帰的な' insert'呼び出し（同じもの）をリファクタリングして、 （ルートサブノード[...] == NULL）ルート - >サブノード[...] =新しいTrieNode（単語[curI]）; '続いて' insert（word、root-> subNodes [ ...]、curI + 1）; '（簡略化のために省略記号を追加）。ちょうど私の2c。 – Mac