#include
#include
#include
using namespace std;
/*************************************************************************************************/
template
class Node//结点类
{
public:
T Date;
T* Right;
T* Left;
T* Parent;
Node(){Date=0;Right=Left=Parent=NULL;}
Node(T t){Date=t;Right=Left=Parent=NULL;}
};
/*****************************************************************************************************/
template
class MinHeap
{
private:
T * Array;
int CurrentSize;
int MaxSize;
public:
MinHeap(int n);
virtual ~MinHeap(){delete []Array;};
void BuildHeap();
void ShiftDown(int left);//left:开始处理的数组的下标
void ShiftUp(int pos);//从pos位置向上调整
void Print();
bool Insert(const T& node);
int GetParentPos(int pos){return (pos-1)/2;}//得到父节点的位置
bool DelPink(T& node);//删除堆顶
};
template
MinHeap::MinHeap(int n)
{
MaxSize=n;
Array=new Node[MaxSize];
CurrentSize=0;
}
template
void MinHeap::Print()
{
for(int i=0;i<CurrentSize;i++)
cout<<Array[i]<<" ";
cout<<"\n";
}
template
void MinHeap::ShiftDown(int left)
{
int i=left;//父结点
int j=2*i+1;//父结点的左孩子
T temp=Array[i];//存放父结点
while(j
{
if((jArray[j+1].Date))
j++;//如果当前父结点有有孩子,比较两个孩子取大的
if(temp.Date>Array[j].Date)
{
Array[i]=Array[j];//父结点小于孩子,将孩子的值赋给父结点
i=j;//继续向下筛,新的父结点为当前孩子
j=j*2+1;//新的孩子为当前孩子的孩子
}
else
break;//父结点大于孩子
}
Array[i]=temp;//交换父子结点的值
}
template
void MinHeap::ShiftUp(int pos)
{
int j=pos;//当前位置
T tem=Array[j];
while((j>0)&&Array[GetParentPos(j)].Date>tem.Date)//父结点大于孩子
{
cout<<Array[GetParentPos(j)].Date<<"父结点大于孩子"<<endl;
Array[j]=Array[GetParentPos(j)];//将父结点的值赋给孩子
j=GetParentPos(j);//继续向上筛
}
Array[j]=tem;
}
template
void MinHeap::BuildHeap()
{
for(int i=CurrentSize/2-1;i>=0;i--)
ShiftDown(i);//从右到左依次筛
}
template
bool MinHeap::Insert(const T & node)
{
if(CurrentSize==MaxSize)
{
cout<<"堆已满,不能插入!"<
return false;
}
Array[CurrentSize]=node;
// cout
ShiftUp(CurrentSize);
// cout
CurrentSize++;
return true;
}
template
bool MinHeap::DelPink(T & node)
{
if(CurrentSize==0)
{
cout<<"堆已空,不能删"<
return false;
}
node=Array[0];
Array[0]=Array[--CurrentSize];
ShiftDown(0);
return true;
}
/**************************************************************************************************
*************************霍夫曼树类***************************************************************/
template
class Huffman
{
private:
Node * root;
public:
void MergeTree(Node & ht1,Node & ht2,Node * parent);//将ht1和ht2合并成以parent为父结点树
Huffman(T weight[],int n);
void visit(Node * R);
void LevelOrder(Node * R);
Node* getroot();
};
template
void Huffman::MergeTree(Node & ht1,Node & ht2,Node * parent)
{
parent->Left=&ht1;
parent->Right=&ht2;
parent->Date=ht1->Date+ht2->Date;
}
template
Huffman::Huffman(T weight[],int n)
{
MinHeap >heap(n);
Nodeparent;
Node first,second;
Node *NodeList=new Node[n];
for(int i=0;i
{
NodeList[i].Date=weight[i];
NodeList[i].Left=NodeList[i].Right=NodeList[i].Parent=NULL;
heap.Insert(NodeList[i]);
}
for(int j=0;j
{
parent=new Node;
heap.DelPink(first);
heap.DelPink(second);
MergeTree(first,second,parent);
heap.Insert(*parent);
root=parent;
}
delete []NodeList;
}
template
void Huffman::visit(Node * R)
{
cout<Date<<" ";
}
template
void Huffman::LevelOrder(Node * R)
{
queue *> nodequeue;
Node * p=R;
if(p)
nodequeue.push(p);
while(!nodequeue.empty())
{
p=nodequeue.front();
visit(p);
nodequeue.pop();
if(p->Left)
nodequeue.push(p->Left);
if(p->Right)
nodequeue.push(p->Right);
}
}
template
Node Huffman::getroot()
{
return root;
}
int main()
{
int Weight[8]={5,29,7,8,14,23,3,11};
int n=8;
Huffman<int>H(Weight,n);
Node<int>* P=H.getroot();
H.LevelOrder(P);
return 0;
}
程序报错,看不懂这个错是什么意思、??有哪位大神能指点一下吗
G:_learning\shujie\li\Ch_3_Huffiman.cpp||In member function 'void Huffman::LevelOrder(Node) [with T = int]':|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|207|instantiated from here|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|189|error: no matching function for call to 'std::queue, std::deque, std::allocator> > >::push(int*&)'|
d:\software\codeblocks\mingw\bin..\lib\gcc\mingw32\4.4.1\include\c++\bits\stl_queue.h|218|note: candidates are: void std::queue<_Tp, _Sequence>::push(const typename _Sequence::value_type&) [with _Tp = Node, _Sequence = std::deque, std::allocator> >]|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|191|error: no matching function for call to 'std::queue, std::deque, std::allocator> > >::push(int*&)'|
d:\software\codeblocks\mingw\bin..\lib\gcc\mingw32\4.4.1\include\c++\bits\stl_queue.h|218|note: candidates are: void std::queue<_Tp, _Sequence>::push(const typename _Sequence::value_type&) [with _Tp = Node, _Sequence = std::deque, std::allocator> >]|
G:_learning\shujie\li\Ch_3_Huffiman.cpp||In constructor 'MinHeap::MinHeap(int) [with T = Node]':|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|150|instantiated from 'Huffman::Huffman(T, int) [with T = int]'|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|205|instantiated from here|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|42|error: cannot convert 'Node >' to 'Node' in assignment|
G:_learning\shujie\li\Ch_3_Huffiman.cpp||In member function 'void Huffman::MergeTree(Node&, Node&, Node) [with T = int]':|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|165|instantiated from 'Huffman::Huffman(T, int) [with T = int]'|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|205|instantiated from here|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|143|error: cannot convert 'Node' to 'int' in assignment|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|144|error: cannot convert 'Node' to 'int' in assignment|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|145|error: base operand of '->' has non-pointer type 'Node'|
G:_learning\shujie\li\Ch_3_Huffiman.cpp|145|error: base operand of '->' has non-pointer type 'Node'|
||=== Build finished: 7 errors, 0 warnings ===|