Вставка в Trie, пустые указатели

Question

У меня есть конкретный вопрос относительно структуры данных Trie и что не так с моим кодом. Параметр функции root всегда равен NULL, когда я рекурсивно вызываю insert. Вот мой код:

Код:

//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[curI] - 'A'] на subNodes[word[13]] (13 - индекс для N в алфавите, и я проверял слово not), и root больше не был NULL для этого вызова. Поэтому с индексацией что-то не так. Кто-нибудь знает что не так? Я решил использовать карту C ++ или вектор. У кого-нибудь есть разногласия с использованием массива?

Answer 1

Здесь есть два вопроса.

1. Между двумя точками последовательности, если переменная изменена, доступ к переменной возможен только для определения нового значения, которое будет сохранено. В вашем коде, когда вы вызываете insert (), curI увеличивается, а также вызывается для передачи в качестве аргумента. Это неправильно.
2. Стандарт C не определяет порядок оценки параметров функции.

http://en.wikipedia.org/wiki/Sequence_point

http://c -faq.com / выражение / seqpoints.html

Следующее исправит проблему.

insert(word, root->subNodes[word[curI] - 'A'], curI);
curI++;

Answer 2

Вы имели в виду ++curl - т.е. передать увеличенное значение рекурсивному вызову?В существующем состоянии вы передаете одно и то же значение в каждую рекурсию, поскольку curl++ является постинкрементным.В любом случае, проще написать curl + 1, поскольку вам больше не нужно значение curl.