用Btree算法掙扎

我已經嘗試過使用Java來實現從教科書算法入門算法第3版算法，沒有很多的成功。幾乎每次我嘗試實現它們時，都會遇到很多錯誤，以至於我不確定作者本身是否嘗試過實現自己的僞代碼。但具體而言，在這種情況下，我遇到了Btree算法的問題。我認爲問題出在B-Tree-Insert-Nonfull方法的某處。當我嘗試運行該程序，這條線將導致一個空指針異常：用Btree算法掙扎

INT I = x.totalKeys - 1;

但是，這沒有任何意義。所有的節點，比如這個例子中的x，在它們的構造函數中初始化爲0，那麼他的錯誤是如何發生的？我要附上以下功能：

public void bTreeInsertNonfull(Node x, Integer k) 
{ 
    int i = x.totalKeys - 1; 
    if (x.leaf || (x.children[i] == null)) 
    { 
     while((i >= 0) && (k < x.keys[i])) 
     { 
      x.keys[i+1] = x.keys[i]; 
      i = i - 1; 
     } 
     x.keys[i+1] = k; 
     x.totalKeys = x.totalKeys + 1; 
    } 
    else 
    { 
     while ((i >= 0) && x.keys[i] != null) 
     { 
      if (k < x.keys[i]) 
      { 
       i = i - 1; 
      } 
     } 

     i = i + 1; 

     if ((x.children[i] != null) && (x.children[i].totalKeys == tUpper)) 
     { 
      bTreeSplitChild(x, i, x.children[i]); 
      if (k > x.keys[i]) 
      { 
       i = i + 1; 
      } 
     } 
     bTreeInsertNonfull(x.children[i], k); 
    } 
}

來源

2012-10-19 Richard Waher

是'x' null還是'x.totalkeys' null？代碼發佈到空引用發生在第一行的功能並不能幫助我們（編輯：這是一個遞歸函數，所以也許錯誤實際上是在此功能） - 的錯誤造成的，因爲無論是x'傳遞到節點'該函數爲null或變量'x.totalkeys'未初始化。 –

檢查在書中數組索引從1，因爲他們經常在算法僞代碼，並確保你適應你的Java代碼（從0哪些索引陣列）。要麼讓1個做大Java數組，並留下指數0未使用，或適應算法使用索引一個比僞小。 – hyde

在闡述亞歷克斯的想法：如果你看一下算法的最後部分，有這樣一行：

if ((x.children[i] != null) && (x.children[i].totalKeys == tUpper))

那暗示x.children[i] == null是一種可能性。算法的最後一行調用bTreeInsertNonfull(x.children[i], k);而不檢查第一個參數是否爲空。

來源

2012-10-19 09:07:42 Eduardo

好的，夥計們，給了我一些很好的提示來解決這個混亂。謝謝。 –

請接受這個答案。 – alexraasch

用Btree算法掙扎

回答

相關問題