Suppression d'un noeud à partir d'une liste saut

Question

Je vais avoir quelques problèmes supprimer un nœud à partir d'une liste de saut. Je les structures suivantes:

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

Le problème, je pense, est la fonction qui recherche un noeud avec une valeur donnée et supprime ensuite. La fonction est implémentée comme ceci:

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

La fonction fonctionne très bien comme il est, mais la liste semble briser si je les deux lignes décommenter commentées. En pause, je veux dire que le code de test suivant ne se termine jamais:

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

Les mensonges de problème dans la dernière boucle de for qui insère plus de valeurs dans la liste. Si ces deux lignes sont commentées, le programme se termine en 10 secondes environ. Si je les décommenter, il semble entrer dans une boucle infinie car elle ne se termine pas même en quelques minutes. Je ne sais pas si c'est la bonne façon de supprimer un noeud à partir d'une liste de saut ou pas, donc je poste ma fonction d'insertion ainsi:

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

Alors, mes questions sont:

1. Pourquoi la rupture du programme, et comment puis-je le faire fonctionner tout en supprimant effectivement les nœuds que je veux supprimer de la mémoire?
2. Est-ce une manière correcte des listes de mise en œuvre, ou que j'utilise une mauvaise approche?

Answer 1

Il y a un problème avec la méthode Remove, comme vous l'aurez deviné:

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

Par souci d'exemple, supposons que le nœud que nous voulons apparaît supprimer dans 2 niveaux:. 0 et 1

La boucle for sur les niveaux L->H 2 ne fait rien.

Au niveau 1, il trouvera le nœud demandé, et le supprimer.

Au niveau 0, il tentera de suivre un pointeur vers le noeud déjà supprimé, conduisant à un comportement non défini.

Solution:

Supprimez uniquement le nœud quand au niveau 0. Tant que votre dans une couche supérieure, le noeud est toujours référencé et vous devez le garder en vie.

Answer 2

Dans votre fonction Supprimer votre boucle externe itère sur la liste pour le compte du nombre actuel d'entrées. Ensuite, dans la boucle vous supprimez un de ces ntries mais continuez à itérer sur le vieux comte.