Я пытаюсь реализовать кучу очистки (https://en.wikipedia.org/wiki/Pairing_heap), но у меня, похоже, возникают проблемы при написании оператора присваивания и конструктора копирования. Мой конструктор по умолчанию, а также функции push и pop, похоже, работают. Но когда я пытаюсь создать новую кучу с помощью конструкции копирования или выполнить задание, я сегментирую ошибки либо во время копирования, либо при первой последующей операции. Я включил соответствующие сегменты кода из того, что я считаю проблемой ниже. Если кто-нибудь может дать мне несколько советов о том, как поступить, это будет оценено.
template<typename T>
PairingHeap<T>::PairingHeap(const PairingHeap& other) {
length = 0;
copy(other.root);
}
template<typename T>
PairingHeap<T>& PairingHeap<T>::operator=(const PairingHeap & 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 T& 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];
}
Задача ещё не решена.
Других решений пока нет …