1

Java を使用して、教科書のアルゴリズム入門、第 3 版からアルゴリズムを実装しようとしましたが、あまり成功しませんでした。それらを実装しようとするたびに、作成者自身が独自の疑似コードを実装しようとしたかどうかわからないほど、多数のエラーに遭遇します。しかし、具体的には、この場合、Btree アルゴリズムに問題があります。問題は B-Tree-Insert-Nonfull メソッドのどこかにあると思います。プログラムを実行しようとすると、次の行で Null Pointer Exception が発生します。

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);
    }
}
4

1 に答える 1

1

アレックスからのアイデアを詳しく説明します。アルゴリズムの最後の部分を見ると、次の行があります。

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

それx.children[i] == nullは可能性があることを示唆しています。アルゴリズムの最後の行はbTreeInsertNonfull(x.children[i], k);、最初のパラメーターが null かどうかをチェックせずに呼び出します。

于 2012-10-19T09:07:42.140 に答える