1
Je travaille sur une implémentation de type liste chaînée d'un tas binaire, et comme il est écrit, j'obtiens quelques erreurs. En ce moment mon main.cpp est un test simple pour ajouter un élément au tas, mais quand j'appelle ma fonction "ajouter au tas" il dit qu'il ne peut pas le trouver. Voici le code:Binary Heap Aucune fonction de correspondance Erreur
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
Toute aide serait très apprécié.