0
Je travaille sur un projet C++ simple pour implémenter une classe Heap et utiliser ses fonctions. J'ai écrit la plupart du code, et quand je suis allé essayer certaines des fonctions, la console me disait que j'ai des symboles non référencés quand j'essaye de compiler. Voici le code.C++ référence non définie à l'objet
Heap.h:
#ifndef HEAP_H
#define HEAP_H
template<typename T>
class Heap {
T arr[100];
int heapSize;
//int parent(int);//returnts the index of the parent
int leftChild(int);//returns the index of the left child
int rightChild(int);//returns the index of the right child
void heapify(T*,int);//made to build the heap;
void buildHeap();//constructs the heap
public:
Heap();//default constructor
Heap(T[], int);//custom constructer accepts an array of type T and size
~Heap();//destructor
void insert(T);//insert a node into the array
// void heapSort(T*);
T extractMax(); //return root value and remove it from heap
T maximum();//return the maximum
void printHeap();//print the values of the heap
};
#endif
Heap.cpp:
#include "Heap.h"
#include <iostream>
template<typename T>
Heap<T>::Heap() { heapSize = 0; }
template<typename T>
Heap<T>::Heap(T a[], int size) {//accepts an array of Type T
for(int i =0; i < size; i++)
arr[i] = a[i];
heapSize = size;
buildHeap();
}
template<typename T>
Heap<T>::~Heap() { }
template<typename T>
int Heap<T>::leftChild(int i) { return ((i*2) + 1); } //the left child is given by index*2 +1
template<typename T>
int Heap<T>::rightChild(int i) { return ((i*2) + 2); } //the right child is given by index*2 +2
template<typename T>
void Heap<T>::heapify(T* a, int i)
{
int left, right, largest;
T temp;
left = leftChild(i);//get the index for the left child
right = rightChild(i);//get the index for the right child
if((left <= heapSize) && a[left] > a[i])//check which index has the largest value and store it
//also checks if the index is within the heap size
largest = left;
else
largest = i;
if((right <= heapSize) && a[right] > a[largest])//check if right child is larger
largest = right;
if(largest != i)//swap the values of the child is larger than parent
{
temp = a[i];
a[i] = a[largest];
a[largest] = temp;
heapify(a, largest);
}
}
template<typename T>
void Heap<T>::buildHeap()
{
int hSize = heapSize;//takes the size of the heap
for(int i = ((hSize/2)-1); i >= 0 ; i--)//loops through every node to make sure they are sorted
heapify(arr, i);
}
template<typename T>
T Heap<T>::maximum() { return arr[0]; } //return the first element or root element;
template<typename T>
T Heap<T>::extractMax() //removes the root element and returns it
{
T max = arr[0];
T* temp = new T[heapSize-1];//create a temp array
for(int i = 0; i < heapSize; i++)//store all old vals to temp arr except for first element;
temp[i] = arr[i+1];
arr = temp;//set arr to temp array
heapSize--;//decerease heapsize
buildHeap(); //rebuild heap
return max; //return root value;
}
template<typename T>
void Heap<T>::insert(T add) //add is the new element for the heap
{
arr[heapSize] = add;//add the new element to the end of the arr
heapSize++;//increase heapsize
buildHeap(arr, heapSize);//call buildHeap to rebuild and resort the heap with the new element
}
template<typename T>
void Heap<T>::printHeap()
{
for(int i =0; i < heapSize; i++)
std::cout<<arr[i];
}
Main.cpp:
#include "Heap.h"
#include <iostream>
using namespace std;
int main()
{
int arr[] = {6,7,9,10,2,4,5};
Heap<int> heap(arr, 7);
heap.printHeap();
return 0;
}
Mon makefile:
all: heapmake
heapmake: Main.o Heap.o
g++ Main.o Heap.o -o heapmake
Main.o:Main.cpp
g++ -c Main.cpp
Heap.o:Heap.cpp
g++ -c Heap.cpp
clean:
rm *o heapmake
Je pense que je ne suis pas en train de lier les fichiers correctement, mais j'ai pensé que je posterais tout le code juste au cas où.