Сопряжение кучи — реализация оператора присваивания / конструктора копирования

#c #pairing-heap

#c #сопряжение-куча

Вопрос:

Я пытаюсь реализовать кучу очистки (https://en.wikipedia.org/wiki/Pairing_heap ), но у меня, похоже, возникают проблемы с написанием оператора присваивания и конструктора копирования. Мой конструктор по умолчанию, а также мои функции push и pop, похоже, работают. Но когда я пытаюсь создать новую кучу с помощью построения копии или выполнить присваивание, я допускаю ошибку либо во время копирования, либо при первой последующей операции. Я включил соответствующие сегменты кода из того, что я считаю проблемой ниже. Если бы кто-нибудь мог дать мне несколько советов о том, как действовать, это было бы оценено.

 template<typename T>
PairingHeap<T>::PairingHeap(const PairingHeapamp; other) {
    length = 0;
    copy(other.root);
}

template<typename T>
PairingHeap<T>amp; PairingHeap<T>::operator=(const PairingHeap amp; rhs) {
    length = 0;
    if(root != rhs.root){
        destroy(root);
        copy(rhs.root);
    }

    return *this;
}


void destroy(Node* A){
    if( A != NULL ){
        destroy( A->child );
        destroy( A->sibling );
        delete A;
    }
}

void copy(Node* A){
    if(A == nullptr) return;
    else push(A->elt);

    if(A->child != nullptr) copy(A->child);
    if(A->sibling != nullptr) copy(A->sibling);
}


template<typename T>
typename PairingHeap<T>::Node* PairingHeap<T>::push(const Tamp; val ) {
    length  ;

    Node* node = new Node(val);
    if(root == NULL)
        root = node;
    else root = meld(root, node);
    return node;
}

Node* meld(Node* A, Node* B){
    if(B == nullptr)
        return nullptr;
    if(A->elt < B->elt){
        B->prev = A->prev;
        A->prev = B;
        A->sibling = B->child;
        if(A->sibling != nullptr)
            A->sibling->prev = A;
        B->child = A;
        A = B;
        return A;
    }
    else{
        B->prev = A;
        A->sibling = B->sibling;
        if(A->sibling != nullptr)
            A->sibling->prev = A;
        B->sibling = A->child;
        if(B->sibling != nullptr)
            B->sibling->prev = B;
        A->child = B;
        return A;
    }
}


template<typename T>
void PairingHeap<T>::pop() {
    Node *oldRoot = root;

    if(root->child == nullptr)
        root = nullptr;
    else
        root = merge(root->child);

    delete oldRoot;
    length--;
}


Node* merge(Node* A)
    std::vector<Node*> v;

    if(A == nullptr || A->sibling == nullptr)
       return A;

    for(int i = 0; A != nullptr; i  ){
        v.push_back(A);
        A->prev->sibling = nullptr;
        A = A->sibling;
    }

    for(int i = 1; i < (int)v.size(); i  ){
        v[i] = meld(v[i-1],v[i]);
    }

   return v[v.size()-1];
}
  

Комментарии:

1. Если вы запустите его в отладчике, где произойдет сбой? что такое трассировка стека? Кроме того, вы должны опубликовать полный пример, который может воспроизвести проблему. Кроме того, в предоставленном вами коде нет конструктора копирования, так что вы просто имели в виду метод копирования?

2. Извините, я, должно быть, забыл конструктор копирования, я отредактирую его сейчас. Я получаю ошибку segfault при попытке отключить pop () или push () в кучу сопряжения после использования конструктора присваивания или копирования.

3. destroy(root) оставляет root висячий указатель (ненулевой указатель, указатель которого был удален). addNode вероятно, не справляется с этой ситуацией изящно