我正在使用二进制最大堆处理模板优先级队列。我有 3 个文件：
主要课程：
#include "PriorityQueue.h"
#include <iostream>
#include <string>
using namespace std;
int main()
{
PriorityQueue<string> queue;
queue.insert("Hello World",20.0f);
queue.insert("Lorem Ipsum",10.0f);
queue.insert(" is a phrase ",4.0f);
queue.insert("used by ",7.0f);
queue.insert("C++",12.0f);
queue.insert(" developers.",6.0f);
queue.remove("C++");
queue.pop();
queue.changePriority(" is a phrase ",9.0f);
queue.insert("commonly ",8.0f);
queue.changePriority(" developers.",2.0f);
queue.insert("web",4.0f);
cout << "The Max-Heap should spell out 'Lorem Ipsum is a phrase commonly used by web developers.'" << endl;
for(int i=0;i<queue.getSize();i++) {
cout << (i+1) << ": " << queue.getObject(i) << endl;
}
return 0;
}
源类：
#include "PriorityQueue.h"
// Constructor for the PQObj class.
template <class T> PQObj<T>::PQObj()
{
obj = NULL;
priority = 0;
}
// Constructor with parameters for the PQObj class.
template <class T> PQObj<T>::PQObj(T obj,float priority)
{
this->obj = obj;
this->priority = priority;
}
// Getter for the PQObj's obj.
template <class T> T PQObj<T>::getObj()
{
return obj;
}
// Setter for the PQObj's obj.
template <class T> void PQObj<T>::setObj(T obj)
{
this->obj = obj;
}
// Getter for the PQObj's priority.
template <class T> float PQObj<T>::getPriority()
{
return priority;
}
// Setter for the PQObj's priority.
template <class T> void PQObj<T>::setPriority(float priority)
{
this->priority = priority;
}
// Constructor for the PriorityQueue's class. Initializes the sort array to a size 10.
template <class T> PriorityQueue<T>::PriorityQueue()
{
head = 0;
tail = 0;
size = 10;
sort = new PQObj<T>[10];
pQueue = NULL;
}
// Destructor for the PriorityQueue's class.
template <class T> PriorityQueue<T>::~PriorityQueue()
{
if(sort!=NULL)
delete [] sort;
if(pQueue!=NULL)
delete [] pQueue;
}
// Inserts a new object with a given priority. If the priority is larger than the front, the two objects will be swapped.
template <class T> void PriorityQueue<T>::insert(T obj,float priority)
{
sort[tail] = new PQObj<T>(obj,priority);
if(priority>sort[head].getPriority())
swap(sort,head,tail);
tail++;
if(tail==size)
increaseCapacity();
}
// Returns the object in front of the Priority Queue, i.e. with the highest priority.
template <class T> T PriorityQueue<T>::front()
{
if(isEmpty())
return NULL;
else
return sort[head].getObj();
}
// Returns the object in front of the Priority Queue, as well as removing it.
template <class T> T PriorityQueue<T>::pop()
{
PQObj<T> temp = sort[head];
sort[head] = NULL;
head++;
return temp.getObj();
}
// Checks to see if the Priority Queue is empty. Returns true if it is empty.
template <class T> bool PriorityQueue<T>::isEmpty()
{
if((tail-head)==0)
return true;
else
return false;
}
// Finds a specific object within the Priority Queue and changes its priority.
template <class T> void PriorityQueue<T>::changePriority(T obj,float new_priority)
{
for(int i=head;i<tail;i++) {
if(sort[i].getObj()==obj) {
sort[i].setPriority(new_priority);
if(i!=head)
swap(sort,head,i);
break;
}
}
}
// Removes a certain object from the Priority Queue by making it max priority, then popping it.
template <class T> void PriorityQueue<T>::remove(T obj)
{
changePriority(obj,sort[head].getPriority()+1);
pop();
}
// Sorts the regular array into a Max Heap, storing the heap into an exclusive array.
template <class T> void PriorityQueue<T>::createHeap()
{
int curr = (tail-head)/2;
for(int i=curr;i>0;i--) {
percolateDown(i);
}
int unSort = (tail-head);
int temp;
while(unSort > 0) {
temp = sort[1];
sort[1] = sort[unSort];
sort[unSort] = temp;
unSort--;
percolateDown(1);
}
pQueue = sort;
}
// Get the specific object within the Max-Heap.
template <class T> T PriorityQueue<T>::getObject(int index)
{
return pQueue[index].getObj();
}
// Get the size of the Max-Heap.
template <class T> int PriorityQueue<T>::getSize()
{
return (tail-head);
}
// Increases the size of the Priority Queue when necessary.
template <class T> void PriorityQueue<T>::increaseCapacity()
{
PQObj<T> *newSort = new PQObj<T>[size*2];
for(int i=0;i<size;i++)
newSort[i] = sort[i];
size *= 2;
sort = newSort;
delete [] newSort;
}
// Percolate Down in the Max Heap.
template <class T> void PriorityQueue<T>::percolateDown(int index)
{
int left = index * 2;
int right = (index * 2) + 1;
if(right <= (tail-head)) {
if(sort[left].getPriority() > sort[right].getPriority()) {
if(sort[index].getPriority() < sort[left].getPriority()) {
swap(sort,left,index);
percolateDown(left);
}
}
else {
if(sort[index].getPriority() < sort[right].getPriority()) {
swap(sort,right,index);
percolateDown(right);
}
}
}
else {
if(left <= (tail-head)) {
if(sort[index].getPriority() < sort[left].getPriority()) {
swap(sort,left,index);
percolateDown(left);
}
}
}
}
// Swaps the content of two specific spots of the Priority Queue.
template <class T> void PriorityQueue<T>::swap(PQObj<T> toSwap[],int pos1,int pos2)
{
PQObj<T> temp = toSwap[pos1];
toSwap[pos1] = toSwap[pos2];
toSwap[pos2] = temp;
}
和头类：
#ifndef _PRIORITYQUEUE_H_
#define _PRIORITYQUEUE_H_
#include <cstddef>
using namespace std;
template <class T> class PQObj
{
public:
PQObj();
PQObj(T obj,float priority);
T getObj();
float getPriority();
void setObj(T obj);
void setPriority(float priority);
private:
T obj;
float priority;
};
template <class T> class PriorityQueue
{
public:
PriorityQueue();
~PriorityQueue();
void insert(T obj,float priority);
T front();
T pop();
bool isEmpty();
void changePriority(T obj,float new_priority);
void remove(T obj);
void createHeap();
T getObject(int index);
int getSize();
private:
void increaseCapacity();
void percolateDown(int index);
void swap(PQObj<T> toSwap[],int pos1,int pos2);
PQObj<T> * pQueue, * sort;
int head,tail,size;
};
#endif
当我尝试使用 g++ 进行编译时，我收到了一个未定义的参考错误，我在整个互联网上搜索了一个关于原因的答案。错误构成了构造函数，以及主类中使用的所有方法。请帮忙！