插入Trie，NULL指針

我有一個關於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++映射或向量。有人對使用數組有任何分歧嗎？

來源

2012-01-04 CodeKingPlusPlus

在C++中，不能保證傳遞給函數的參數的順序被評估。所以，你的編譯器可能會決定傳入舊的curI作爲最後一個參數，但是使用新的（遞增的）值作爲單詞的索引。 – 2012-01-04 01:27:02

不是它與你的問題有任何關係（其他人已經解決了你的問題），但我會重構你的兩個'insert'調用（它們是相同的），從他們的'if/else'塊中，只是一個'if（root-> subNodes [...] == NULL）root-> subNodes [...] = new TrieNode（word [curI]）;''接着'insert（word，root-> subNodes [ ...]，curI + 1）;'（爲簡潔起見，添加了橢圓）。只是我的2c。 – Mac 2012-01-04 01:47:28

你的意思是++curl - 即遞增值傳遞給遞歸調用？就目前而言，由於curl++是後增加的，因此您將相同的值傳遞給每個遞歸。無論如何，只寫curl + 1可能會更容易，因爲您不需要再次使用捲曲值。

來源

2012-01-04 01:06:21 Rup

謝謝！ curI + 1的工作原理是@Eugen Constantin Dinca所說的函數參數順序必須爲真。 – CodeKingPlusPlus 2012-01-04 01:40:24

糟糕 - 我想你在同一個電話中再次使用捲曲。是的，絕對'捲曲+ 1'不是'++捲曲'。很高興它的工作！ – Rup 2012-01-04 01:42:18

這裏有兩個問題。

在兩個序列點之間，如果變量被修改，變量只能被訪問以確定要存儲的新值。在你的代碼中，當你調用insert（）時，curI會增加，並且也被作爲參數傳遞。這是錯誤的。
C標準沒有定義功能參數評估順序。

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

http://c-faq.com/expr/seqpoints.html

繼將解決這個問題。

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

來源

2012-01-04 01:39:48

插入Trie，NULL指針

回答

相關問題