I think it is not caused by library losing.And I am sure that I have implemented every function I declare.
The most of the codes are from the book < Data structures and algorithm analysis in c++ >.And I have searched many other similar questions,but I 'm still confused. Can anyone tell me how can I solve the problem?
heap.h
#pragma once
template <typename E, typename Comp>
class heap
{
private:
E* Heap; //Pointer to the heap array
int maxsize; //Maximum size of the heap
int n; //Number of elements now in the heap
//Helper function to put element in its correct place,and that moves the father node down
void siftdown(int pos);
public:
heap(E* h, int num, int max);
int size()const;
bool isLeaf(int pos)const;
int leftchild(int pos)const;
int rightchild(int pos)const;
int parent(int pos)const;
void buildHeap();
void insert(const E& it);
E removefirst();
E remove(int pos);
};
heap.cpp
#include "heap.h"
#include<assert.h>
//Swap two elements in the container
template<typename E>
void swap(E*array,int pos1,int pos2) {
int temp = array[pos1];
array[pos1] = array[pos2];
array[pos2] = temp;
}
//Heap class
// E is the element in heap
//Comp is a class used to compare two elements
//Helper function to put element in its correct place,and that moves the father node down
template <typename E, typename Comp>
void heap<E, Comp>::siftdown(int pos) {
while (!isLeaf(pos)) {//Stop if pos is a leaf
int j = leftchild(pos);
int rc = rightchild(pos);
if ((rc < n) && Comp::prior(Heap[rc], Heap[j]))
j = rc; //Set j to greater child's value
if (Comp::prior(Heap[pos], Heap[j]))
return; //Done
swap(Heap, pos, j);
pos = j; //Move down
}
}
template <typename E, typename Comp>
heap<E,Comp>::heap(E* h, int num, int max) {
Heap = h;
n = num;
maxsize = max;
}
//Return current heap size
template <typename E, typename Comp>
int heap<E, Comp>::size()const {
return n;
}
//True if pos is a leaf
template <typename E, typename Comp>
bool heap<E, Comp>::isLeaf(int pos)const {
return ((pos >= n / 2) && (pos < n));
}
//Return leftchild position
template <typename E, typename Comp>
int heap<E,Comp>::leftchild(int pos)const {
return 2 * pos + 1;
}
//Return rightchild position
template <typename E, typename Comp>
int heap<E,Comp>::rightchild(int pos)const {
return 2 * pos + 2;
}
//Return parent position
template <typename E, typename Comp>
int heap<E,Comp>::parent(int pos)const {
return (pos - 1) / 2;
}
//Heapify contents of Heap
template <typename E, typename Comp>
void heap<E, Comp>:: buildHeap() {
for (int i = n / 2 - 1; i >= 0; --i) {
siftdown(i);
}
}
//Insert "it" into the heap
template <typename E, typename Comp>
void heap<E,Comp>::insert(const E& it) {
assert(n < maxsize); //Terminate if heap is full
int curr = n++;
Heap[curr] = it; //Start at end of heap
//Move up until curr's parent > curr
while ((curr != 0) && (Comp::prior(Heap[curr], Heap[parent(curr)]))) {
swap(Heap, curr, parent(curr));
curr = parent(curr);
}
}
template <typename E, typename Comp>
E heap<E, Comp>::removefirst() {
assert(n > 0); //Interrupt if heap is empty
swap(Heap, 0, --n); //Swap first with last value.
if (n != 0)siftdown(0); //Siftdown new root val
return Heap[n]; //Return deleted value
}
template <typename E, typename Comp>
E heap<E, Comp>::remove(int pos) {
assert((pos >= 0) && (pos < n)); //Intertupt if it is in bad position
if (pos == n - 1)n--; //Last element,no work to do
else {
swap(Heap, pos, --n); //Swap with last value
while ((pos != 0) && (Comp::prior(Heap[pos], Heap[parent(pos)]))) {
swap(Heap, pos, parent(pos)); //Push up large key
pos = parent(pos);
}
if (n != 0)siftdown(pos); //Push down small key
}
return Heap[n];
}
main.cpp
#include"heap.h"
#include<time.h>
#include<iostream>
using namespace std;
//Huffman tree node abstract base class
template<typename E>
class HuffNode {
public:
virtual ~HuffNode(){} //Base destructor
virtual int weight() = 0; //Return frequency
virtual bool isLeaf() = 0; //Determine type
};
template<typename E> //Leaf node subclass
class LeafNode :public HuffNode<E> {
private:
E it; //Value
int wgt; //Weight
public:
LeafNode(const E& val, int freq) {
it = val;
wgt = freq;
}
int weight() { return wgt; }
E val() { return it; }
bool isLeaf() { return true; }
~LeafNode(){}
};
template<typename E> //Internal node subclass
class IntlNode : public HuffNode<E> {
private:
HuffNode<E>* lc; //Left child
HuffNode<E>* rc; //Right child
int wgt; //Subtree weight
public:
IntlNode(HuffNode<E>* l, HuffNode<E>* r) {
wgt = l->weight() + r->weight();
lc = l;
rc = r;
}
int weight() { return wgt; }
bool isLeaf() { return false; }
HuffNode<E>* left()const { return lc; }
void setLeft(HuffNode<E>* b) {
lc = b;
}
HuffNode<E>* right()const { return rc; }
void setRight(HuffNode<E>* b) {
rc = b;
}
~IntlNode(){}
};
template<typename E>
class HuffTree {
private:
HuffNode<E>* Root; //Tree root
public:
HuffTree(E& val, int freq) { //Leaf constructor
Root = new LeafNode<E>(val, freq);
}
//Internal node construtor
HuffTree(HuffTree<E>* l, HuffTree<E>* r) {
Root = new IntlNode<E>(l->root(), r->root());
}
HuffTree() { Root = NULL; }
~HuffTree(){}
HuffNode<E>* root() { return Root; }
int weight() { return Root->weight(); }
};
template<typename E>
class minTreeComp {
public:
bool prior(HuffTree<E>* a, HuffTree<E>* b) {
return b->weight() - a->weight();
}
};
//Build a Huffman tree from a collection of frequencies
template<typename E>
HuffTree<E>* buildHuff(HuffTree<E>** TreeArray, int count) {
heap<HuffTree<E>*, minTreeComp<E>>* forest =
new heap<HuffTree<E>*, minTreeComp<E>>(TreeArray, count, count);
HuffTree<char> *temp1, *temp2, *temp3 = NULL;
while (forest->size() > 1) {
temp1 = forest->removefirst(); //Pull first two trees
temp2 = forest->removefirst(); //off the list
temp3 = new HuffTree<E>(temp1, temp2);
forest->insert(temp3); //Put the new tree back on list
delete temp1; //Must delete the remnants
delete temp2; //of the trees we created
}
return temp3;
}
template<typename E>
void traverse(HuffNode<E>* forest) {
if (forest->isLeaf() == true) {
cout <<((LeafNode<E>*)forest)->val()<<" : "<<forest->weight() << endl;
}
else {
traverse(((IntlNode<E>*)forest)->left());
traverse(((IntlNode<E>*)forest)->right());
}
}
int main() {
srand((unsigned int)time(0));
char ch = 'A';
HuffTree<char>** forests= new HuffTree<char>*[10];
//vector<HuffTree<char>*>trees;
for (int i = 0; i < 10; ++i) {
ch += 1;
forests[i]= new HuffTree<char>(ch,rand() % 50 + 1);
}
HuffTree<char>* forest = buildHuff(forests, 4);
traverse(forest->root());
}
I have four errors:
1>Source.obj : error LNK2019: unresolved external symbol "public: __thiscall heap *,class minTreeComp >::heap *,class minTreeComp >(class HuffTree * *,int,int)" (??0?$heap@PAV?$HuffTree@D@@V?$minTreeComp@D@@@@QAE@PAPAV?$HuffTree@D@@HH@Z) referenced in function "class HuffTree * __cdecl buildHuff(class HuffTree * *,int)"
1>Source.obj : error LNK2019: unresolved external symbol "public: int __thiscall heap *,class minTreeComp >::size(void)const " (?size@?$heap@PAV?$HuffTree@D@@V?$minTreeComp@D@@@@QBEHXZ) referenced in function "class HuffTree * __cdecl buildHuff(class HuffTree * *,int)" (??$buildHuff@D@@YAPAV?$HuffTree@D@@PAPAV0@H@Z)
1>Source.obj : error LNK2019: unresolved external symbol "public: void __thiscall heap *,class minTreeComp >::insert(class HuffTree * const &)" (?insert@?$heap@PAV?$HuffTree@D@@V?$minTreeComp@D@@@@QAEXABQAV?$HuffTree@D@@@Z) referenced in function "class HuffTree * __cdecl buildHuff(class HuffTree * *,int)" (??$buildHuff@D@@YAPAV?$HuffTree@D@@PAPAV0@H@Z)
1>Source.obj : error LNK2019: unresolved external symbol "public: class HuffTree * __thiscall heap *,class minTreeComp >::removefirst(void)" (?removefirst@?$heap@PAV?$HuffTree@D@@V?$minTreeComp@D@@@@QAEPAV?$HuffTree@D@@XZ) referenced in function "class HuffTree * __cdecl buildHuff(class HuffTree * *,int)" (??$buildHuff@D@@YAPAV?$HuffTree@D@@PAPAV0@H@Z)
