1
我正在處理二進制堆的鏈表的類型實現，並且在寫入時出現一些錯誤。現在我的main.cpp是一個簡單的測試，用於向堆中添加一個元素，但是當我調用我的「add to heap」函數時，它說它找不到它。下面是代碼：二進制堆無匹配函數錯誤
的main.cpp
#include <QtCore/QCoreApplication>
#include "Queue.h"
#include "Heap.h"
#include <bitset>
#include <cmath>
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
Heap<int> H;
H.AddToHeap(1);
return a.exec();
}
Heap.h
#ifndef HEAP_H
#define HEAP_H
#include "Node.h"
#include <iostream>
#include <bitset>
#include <cmath>
enum BOUNDARY_ERRORS{OUT_OF_BOUNDS, INVALID_NODE};
template <typename T>
class Heap
{
public:
Heap();
Heap(const Heap &other);
void operator=(const Heap &other);
~Heap();
void AddToHeap(T &data);
Heap& operator<<(T &data);
T& Pop();
Heap& operator>>(T &destination);
bool Empty() { return size==0; }
T Peek();
template <typename U> friend
ostream& operator<<(const ostream &out, const Heap<U> &H);
template <typename U> friend
istream& operator>>(const istream &in, const Heap<U> &H);
private:
int size;
Node<T> *rootptr;
void AddToVacantNode(T &data);
Node<T>* FindNode(int n);
Node<T>* FindParentNode(int n);
Node<T>* LargestChild(Node<T> *nodeptr);
Node<T>* SmallestChild(Node<T> *nodeptr);
void Upheap();
void Downheap();
void Switch(Node<T> *a, Node<T> *b);
void Replace(Node<T> *a, Node<T> *b);
void Copy(const Heap &other);
bool MIN;
void Clear();
};
template <typename T>
Heap<T>::Heap()
{
size = 0;
rootptr = NULL;
MIN = 0;
}
template <typename T>
Heap<T>::Heap(const Heap<T> &other)
: Heap()
{
Copy(other);
}
template <typename T>
void Heap<T>::operator=(const Heap<T> &other)
{
Copy(other);
}
template <typename T>
Heap<T>::~Heap()
{
Clear();
}
template <typename T>
void Heap<T>::AddToVacantNode(T &data)
{
if (Empty())
rootptr = new Node<T>(data);
else
{
int destination = size + 1;
Node<T> newnode(data);
Node<T> *parentptr = FindParentNode(destination);
if (!destination%2)
parentptr->AddLeftChild(newnode);
else
parentptr->AddRightChild(newnode);
}
}
template <typename T>
Node<T>* Heap<T>::FindParentNode(int n)
{
if (n == 1)
return NULL;
int parentnumber;
if (!n%2)
{
parentnumber = n/2;
Node<T> *nodeptr = FindNode(parentnumber);
return nodeptr;
}
else
{
parentnumber = (n - 1)/2;
Node<T> *nodeptr = FindNode(parentnumber);
return nodeptr;
}
}
template <typename T>
void Heap<T>::Upheap()
{
Node<T> *parentptr = FindParentNode(size);
Node<T> *childptr = FindNode(size);
if (MIN)
{
while (parentptr && *childptr < *parentptr)
{
switch(parentptr, childptr);
parentptr = FindParentNode(parentptr);
childptr = FindParentNode(childptr);
}
return;
}
else
{
while (parentptr && *childptr > *parentptr)
{
switch(parentptr, childptr);
parentptr = FindParentNode(parentptr);
childptr = FindParentNode(childptr);
}
return;
}
}
template <typename T>
Node<T>* Heap<T>::LargestChild(Node<T> *nodeptr)
{
if (!nodeptr->LeftChild() && !nodeptr->RightChild())
return NULL;
else if (nodeptr->LeftChild() && !nodeptr->RightChild())
return nodeptr->LeftChild();
else if (nodeptr->RightChild() && !nodeptr->LeftChild())
return nodeptr->RightChild();
else
return (*(nodeptr->LeftChild() > *(nodeptr->RightChild())))?
nodeptr->LeftChild() : nodeptr->RightChild();
}
template <typename T>
Node<T>* Heap<T>::SmallestChild(Node<T> *nodeptr)
{
if (!nodeptr->LeftChild() && !nodeptr->RightChild())
return NULL;
else if (nodeptr->LeftChild() && !nodeptr->RightChild())
return nodeptr->LeftChild();
else if (nodeptr->RightChild() && !nodeptr->LeftChild())
return nodeptr->RightChild();
else
return (*(nodeptr->LeftChild() < *(nodeptr->RightChild())))?
nodeptr->LeftChild() : nodeptr->RightChild();
}
template <typename T>
void Heap<T>::Downheap()
{
Node<T> *nodeptr = FindNode(size);
*rootptr = *nodeptr;
}
template <typename T>
void Heap<T>::Replace(Node<T> *a, Node<T> *b)
{
a->Data() = b->Data();
b->NullPtrs();
Node<T> *parentptr = FindParentNode(b);
if (parentptr->LeftChild() = b)
{
parentptr->NullLeftChild();
delete b;
b = NULL;
}
else
{
parentptr->NullRightChild();
delete b;
b = NULL;
}
return;
}
template <typename T>
void Heap<T>::AddToHeap(T &data)
{
AddToVacantNode(data);
Upheap();
size++;
}
template <typename T>
Heap<T>& Heap<T>::operator<<(T &data)
{
AddToHeap(data);
return *this;
}
template <typename T>
T& Heap<T>::Pop()
{
return rootptr->Data();
Downheap();
size--;
}
template <typename T>
Heap<T>& Heap<T>::operator>>(T &destination)
{
destination = rootptr->Data();
Downheap();
size--;
}
template <typename T>
T Heap<T>::Peek()
{
if (!Empty())
return rootptr->Data();
}
template <typename T>
ostream& operator<<(const ostream &out, const Heap<T> &H)
{
return;
}
template <typename T>
istream& operator>>(const istream &in, const Heap<T> &H)
{
return;
}
template <typename T>
void Heap<T>::Switch(Node<T> *a, Node<T> *b)
{
T temp;
temp = a->Data();
a->SetData(b->Data());
b->SetData(temp);
}
template <typename T>
void Heap<T>::Copy(const Heap &other)
{
if (this != &other && !other.Empty())
{
MIN = other.MIN;
Node<T> *nodeptr;
Clear();
for (int n=1; n<=other.size; n++)
{
nodeptr = other.FindNode(n);
AddToHeap(nodeptr->data);
}
}
}
template <typename T>
Node<T>* Heap<T>::FindNode(int n)
{
if (n > size || n < 1)
throw OUT_OF_BOUNDS;
int x = floor(log(n)/log(2)+1);
bitset<20> bs(n);
Node<T> *nodeptr = rootptr;
for (int i=x-2; i>=0; i--)
{
if (!bs[i])
nodeptr = nodeptr->LeftChild();
else
nodeptr = nodeptr->RightChild();
}
return nodeptr;
}
template <typename T>
void Heap<T>::Clear()
{
for (int n=size; n>0; n++)
{
Node<T> *nodeptr = FindNode(n);
nodeptr->NullPtrs();
delete nodeptr;
}
rootptr->NullPtrs();
delete rootptr;
}
#endif // HEAP_H
Node.h
#ifndef NODE_H
#define NODE_H
#include <iostream>
template <typename T>
class Node
{
public:
Node();
Node(T &DATA);
Node(const Node<T> &other);
Node<T>& operator=(const Node<T> &other);
Node<T>& operator<<(const T &nodedata);
bool operator==(const Node<T> &other);
bool operator<(const Node<T> &other);
bool operator>(const Node<T> &other);
bool operator<=(const Node<T> &other);
bool operator>=(const Node<T> &other);
bool operator!=(const Node<T> &other);
~Node();
T Data() const { return data; }
void SetData(const T &nodedata);
void AddLeftChild(const Node<T> *leftchildptr);
void AddRightChild(const Node<T> *rightchildptr);
Node<T> *LeftChild() { return leftchild; }
Node<T> *RightChild() { return rightchild; }
void NullLeftChild() { leftchild = NULL; }
void NullRightChild() { rightchild = NULL; }
void NullPtrs() { leftchild = rightchild = NULL; }
template <typename U> friend
ostream& operator<<(ostream &out, Node<U> &node);
private:
T data;
Node<T> *leftchild;
Node<T> *rightchild;
void Copy(const Node<T> &other);
};
template <typename T>
Node<T>::Node()
{
NullPtrs();
return;
}
template <typename T>
Node<T>::Node(T &DATA)
{
NullPtrs();
data = DATA;
return;
}
template <typename T>
Node<T>::Node(const Node<T> &other)
{
Copy(other);
return;
}
template <typename T>
Node<T>& Node<T>::operator=(const Node &other)
{
if (this != &other)
Copy(other);
return this;
}
template <typename T>
Node<T>& Node<T>::operator<<(const T &nodedata)
{
SetData(nodedata);
}
template <typename T>
bool Node<T>::operator==(const Node<T> &other)
{
return (data == other.data);
}
template <typename T>
bool Node<T>::operator<(const Node<T> &other)
{
return (data < other.data);
}
template <typename T>
bool Node<T>::operator>(const Node<T> &other)
{
return (data > other.data);
}
template <typename T>
bool Node<T>::operator<=(const Node<T> &other)
{
return (data < other.data || data == other.data);
}
template <typename T>
bool Node<T>::operator>=(const Node<T> &other)
{
return (data > other.data || data == other.data);
}
template <typename T>
bool Node<T>::operator!=(const Node<T> &other)
{
return (data != other.data);
}
template <typename T>
Node<T>::~Node()
{
NullPtrs();
}
template <typename T>
void Node<T>::SetData(const T &nodedata)
{
data = nodedata;
}
template <typename T>
void Node<T>::AddLeftChild(const Node<T> *leftchildptr)
{
leftchild = leftchildptr;
return;
}
template <typename T>
void Node<T>::AddRightChild(const Node<T> *rightchildptr)
{
rightchild = rightchildptr;
return;
}
template <typename U>
ostream& operator<<(ostream &out, Node<U> &node)
{
out << node.data;
return out;
}
template <typename T>
void Node<T>::Copy(const Node &other)
{
leftchild = other.leftchild;
rightchild = other.rightchild;
data = other.data;
}
#endif // NODE_H
任何幫助將是非常讚賞。