Перколяция левой кучи C ++ приводит к ошибке сегмента - PullRequest
Новая
       20

Перколяция левой кучи C ++ приводит к ошибке сегмента

0 голосов
/ 28 марта 2012

Я реализовал функцию removeSelection, которая удаляет определенный узел из левой кучи.Код находит узел через хеш-таблицу, которая отслеживает ключи, которые были вставлены в кучу.Затем узел перколируется в корень кучи и вызывается deleteMin для его удаления.Кажется, что код не работает в функции swapWithParent, которую вызывает percolateUp, и он генерирует ошибку сегмента.

Эта функция вызывается из main в куче: 

    bool removeSelection( const Comparable & x )
{
    LeftistNode * temp = locateNode( x ); //find the node with the item
    if(temp == NULL)
        return false;
    //percolate that node to the top
    percolateUp(temp);
    //delete the root
    int derp = 0; //deleteMin requires an int be passed
    deleteMin(derp);
    return true;

}

Функция percolateUp: 

    void percolateUp( LeftistNode * t )
{
    if(t != NULL)
    {
        while(t != root)
        {
            t = swapWithParent(t->parent, t);
        }
    }
}

Функция swapWithParent: 

    //swap h2 with its parent h1
//return pointer to h2's new location
LeftistNode * swapWithParent(LeftistNode * h1, LeftistNode * h2)
{
    //if h2 is its parent's left child
    if(h2 == h1->left)
    {
        LeftistNode *temp = new LeftistNode(h2->element, -1, h1->parent, h1->left, h1->right, h1->npl); //clone h1 and store as a temp

        temp->lines = h2->lines;

        //update all pointers
        h1->parent = h2;
        if(h1->right != NULL)
            h1->right->parent = h2;
        h1->left = h2->left;
        h1->right = h2->right;
        h2 = temp;
        return h2;
    }
    else
    {
        LeftistNode *temp = new LeftistNode(h2->element, -1, h1->parent, h1->left, h1->right, h1->npl); //clone h1 and store as a temp
        temp->lines = h2->lines;
        //update all pointers
        h1->parent = h2;
        if(h1->left != NULL)
            h1->left->parent = h2;
        h1->left = h2->left;
        h1->right = h2->right;
        h2 = temp;
        return h2;

    }
}

Возможно, есть ли места, где я могу разыменовать нулевой указатель?Я проверил, но не могу найти ошибку.

1 Ответ

0 голосов
/ 28 марта 2012

Если t->parent равен NULL в вызове t = swapWithParent(t->parent, t);, тогда вы будете задерживать указатель NULL в swapWithParent().Если parent разрешено принимать значение NULL, добавьте проверку в swapWithParent () и, если оно не должно быть NULL, по крайней мере, добавьте assert(), чтобы убедиться, что для него не установлено значение NULL.

...