3

スキップリストからノードを削除する際に問題が発生しました。私は次の構造を持っています：

struct Node
{
    int info;
    Node **link_;

    Node(int v, int levels)
    {
        info = v;
        link_ = new Node*[levels];

        for ( int i = 0; i < levels; ++i )
            link_[i] = NULL;
    }
};

struct List
{
    int H; // list height

    Node *Header;

    List()
    {
        Header = new Node(0, maxH);
        H = 1;
    }
};

問題は、与えられた値を持つノードを検索して削除する関数にあると思います。関数は次のように実装されます。

void Remove(int v, List *L)
{
    Node *current = L->Header;

    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
            if ( current->link_[i]->info > v )
                break;
            else if ( current->link_[i]->info == v )
            {
                // Node *del = current->link_[i];
                current->link_[i] = current->link_[i]->link_[i];

                // delete del;
                break;
            }
    }
}

関数はそのままで正常に動作しますが、コメントされた2行のコメントを外すと、リストが壊れているようです。ブレークとは、次のテストコードが終了しないことを意味します。

int main()
{
    srand((unsigned)time(0));

    List *SKL = new List();


    for ( int i = 0; i < 1000000; ++i )
        Insert(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Search(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Remove(rand() * rand(), SKL);

    for ( int i = 0; i < 1000000; ++i )
        Insert(rand() * rand(), SKL);


    return 0;
}

問題は、リストにさらに値を挿入する最後のforループにあります。これらの2行がコメントアウトされている場合、プログラムは約10秒で終了します。コメントを外すと、数分で終わらないので無限ループに入っているようです。それがスキップリストからノードを削除する正しい方法であるかどうかわからないので、挿入関数も投稿しています：

void Insert(int v, List *L)
{
    // this section just determines the levels the new node will be part of
    int newH = 0;

    int tmp;
    unsigned int rnd = rand() * rand(); 
    do
    {
        tmp = lookup[rnd & 255];
        rnd >>= 8;
        newH += tmp;
    } while ( tmp == 8 );

    if ( newH >= L->H )
        ++L->H;

    // this does the actual insertion
    Node *newNode = new Node(v, L->H);
    Node *current = L->Header;
    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
            if ( current->link_[i]->info >= v )
                break;

        if ( i <= newH )
        {
            newNode->link_[i] = current->link_[i];
            current->link_[i] = newNode;
        }
    }
}

だから、私の質問は次のとおりです。

  1. プログラムが壊れてしまうのはなぜですか。また、メモリから削除したいノードを実際に削除しながら、プログラムを機能させるにはどうすればよいですか。
  2. これはスキップリストを実装する正しい方法ですか、それとも間違ったアプローチを使用していますか？
4

2 に答える 2

2

Removeご想像のとおり、メソッドに問題があります。

void Remove(int v, List *L)
{
    Node *current = L->Header;

    for ( int i = L->H - 1; i >= 0; --i )
    {
        for ( ; current->link_[i] != NULL; current = current->link_[i] )
        {
            if ( current->link_[i]->info > v )
            {
                break;
            }
            else if ( current->link_[i]->info == v )
            {
                // Node *del = current->link_[i];
                current->link_[i] = current->link_[i]->link_[i];

                // if (0 == i) delete del;
                break;
            }
        }
    }
}

例として、削除したいノードが 0 と 1 の 2 つのレベルにあるとします。

レベル 2 までのforループL->Hは何もしません。

レベル 1 では、要求されたノードを見つけて削除します。

レベル 0 では、既に削除されたノードへのポインターをたどろうとするため、未定義の動作が発生します。

解決：

レベル 0 の場合にのみノードを削除します。上位層にある限り、ノードは参照されたままであり、存続させる必要があります。

于 2010-05-31T13:38:11.577 に答える
0

Remove 関数では、現在のエントリ数のカウントについて、外側のループがリストを反復処理します。次に、ループ内でそれらの ntries の 1 つを削除しますが、古いカウントを反復し続けます。

于 2010-05-31T09:25:26.900 に答える