学步园

#include <iostream>   
using namespace std;  
const int MaxN = 100;  
  
  
template <class T>   
class MinHeap  
{  
public:  
    MinHeap(int maxSize);  
    MinHeap(T a[], int n);  
    ~MinHeap()  
    {  
        delete []heapArray;  
    }  
    int Insert(T &d);//最小堆的插入方法   
    T * DeleteMin();//删除最小堆的堆顶元素   
  
    T * heapArray;//存放数据的数组   
    T * imputArray;//存放输入的数组   
    T * saveNode[100];  
    int saveNodeCount;//已存储节点的数目   
    int heapCurrentSize;  
    int heapMaxSize;  
    void FilterDown(int p);  
    void FilterUp(int p);  
};  
  
template <class T> MinHeap <T> :: MinHeap(int maxSize)  
{  
    heapMaxSize = maxSize;  
    heapArray = new T [heapMaxSize];  
    heapCurrentSize = 0;  
}  
  
//给定数组构成最小堆   
template<class T> MinHeap<T>::MinHeap(T a[],int n)  
{  
    heapMaxSize = n;  
    heapArray = new T[heapMaxSize+1];  
    saveNodeCount=n;  
    for(int j=0;j<n;j++)  
        heapArray[j]=a[j];  
    imputArray=a;  
    heapCurrentSize=n;  
    int i=(heapCurrentSize-2)/2;  
    while(i>=0)  
    {  
        FilterDown(i);  
        i--;  
    }  
    if (heapMaxSize%2==0){  
        for(int k=0;k<n;k++){  
            heapArray[k]=heapArray[k+1];  
        }  
    }  
}  
template <class T> void MinHeap<T>::FilterDown(const int start)  
{  
    int i=start,j;  
    T temp=heapArray[i];  
    j=2*i+1;  
    while(j<=heapCurrentSize-1)  
    {  
        if(j<=heapCurrentSize-1 && heapArray[j].data>heapArray[j+1].data) j++;  
        if(temp.data <=heapArray[j].data) break;  
        else {heapArray[i]=heapArray[j];i=j;j=2*j+1;}  
    }  
    heapArray[i]=temp;  
}  
template<class T> int MinHeap<T>::Insert(T&d)  
{  
    heapArray[heapCurrentSize]=d;  
    heapArray[heapCurrentSize].arrkey=saveNodeCount;  
    FilterUp(heapCurrentSize);  
    heapCurrentSize++;  
    saveNode[saveNodeCount++]=&d;  
    return 1;  
}  
template <class T> void MinHeap<T>::FilterUp(int p)  
{  
    int j=p,i;  
    T temp = heapArray[j];  
    i=(j-1)/2;  
    while(j>0)  
    {  
        if(heapArray[i].data<=temp.data) break;  
        else  
        {  
            heapArray[j]=heapArray[i];  
            j=i;i=(j-1)/2;  
        }  
    }  
    heapArray[j]=temp;  
}  
template<class T> T * MinHeap<T>::DeleteMin()  
{  
    T * temp=new HuffmanTreeNode<double>;  
    (*temp)=heapArray[0];  
    heapArray[0]= heapArray[heapCurrentSize-1];  
    heapCurrentSize--;  
    FilterDown(0);  
    if(temp->arrkey>-1 && temp->arrkey<heapMaxSize)  
        return &imputArray[temp->arrkey];  
    else if(temp->arrkey>=heapMaxSize && temp->arrkey<100)  
        return saveNode[temp->arrkey];  
    return NULL;  
}  
  
template <class T> class HuffmanTree;  
template <class T> class HuffmanTreeNode  
{  
    friend class HuffmanTree;  
public:  
    int arrkey;  
    T data;  
    HuffmanTreeNode <T>  *leftChild, *rightChild, *parent;  
};  
template <class T> class HuffmanCodeNode  
{  
    friend class HuffmanTree;  
public:  
    HuffmanTreeNode <T> *dataptr;  
    int bit[MaxN];  
    int start;  
};  
template <class T> class HuffmanTree  
{  
    friend class HuffmanTreeNode;  
    friend class HuffmanCodeNode;  
public:  
    HuffmanTree(){};  
    HuffmanTree(T weight[], int n);  
    HuffmanCode();  
protected:  
    HuffmanTreeNode <T> *hfTree;  
    HuffmanCodeNode <T> *hfCode;  
    int currentSize;  
    void MergeTree(HuffmanTreeNode <T> &bt1, HuffmanTreeNode <T>  
        &bt2, HuffmanTreeNode <T> *pt)  
    {  
        pt->leftChild = &bt1; pt->rightChild = &bt2;  
        pt->data = bt1.data + bt2.data;  
        pt->parent = NULL; bt1.parent = pt; bt2.parent = pt;  
    }  
};  
template <class T> HuffmanTree <T> :: HuffmanTree(T weight[], int n)  
{  
    HuffmanTreeNode <T> *firstchild, *secondchild, *parent;  
    HuffmanTreeNode <T> *TNode;  
    if(n > MaxN)  
    {  
        cout<<"Error!"<<endl;exit(0);  
    }  
    currentSize = n;  
    hfCode = new HuffmanCodeNode <T> [n];  
    TNode = new HuffmanTreeNode <T> [n];  
    for(int i = 0;i < n;i++)  
    {  
        hfCode[i].dataptr = &TNode[i];  
        TNode[i].data = weight[i];  
        TNode[i].arrkey = i;  
        TNode[i].parent = TNode[i].leftChild = TNode[i].rightChild = NULL;  
    }  
    MinHeap <HuffmanTreeNode <T> > hp(TNode,n);  
    for(i = 0;i < n-1;i++)  
    {  
        parent = new HuffmanTreeNode <T>;  
        firstchild = hp.DeleteMin();  
        secondchild = hp.DeleteMin();  
        MergeTree(*firstchild, *secondchild, parent);  
        hp.Insert(*parent);  
    }  
    hfTree = parent;  
}  
template <class T> HuffmanTree <T> :: HuffmanCode()  
{  
    HuffmanCodeNode <T> *cd = new HuffmanCodeNode<T>;  
    HuffmanTreeNode <T> *child, *parent;  
    for(int i=0;i < currentSize;i++)  
    {  
        cd->start = currentSize -1;  
        child = hfCode[i].dataptr;  
        parent = child->parent;  
        while(parent != NULL)  
        {  
            if(parent->leftChild == child)  
                cd->bit[cd->start] = 1;  
            else  
                cd->bit[cd->start] = 0;  
            child = parent;  
            parent = parent->parent;  
            cd->start--;  
        }  
        for(int k=0;k < currentSize;k++)  
        {  
            hfCode[i].bit[k] = cd->bit[k];  
            hfCode[i].start = cd->start+1;  
        }  
    }  
    cout<<endl<<"输出："<<endl;  
    for(i=0;i<currentSize;i++)  
    {       cout<<hfCode[i].dataptr->data<<":  ";  
    for(int j=hfCode[i].start;j<currentSize;j++)  
        cout<<hfCode[i].bit[j];  
    cout<<endl;  
    }  
}  
  
int main()  
{  
    double weight[MaxN];  
    int n;  
    cout<<"How many numbers are you going to input?"<<endl;  
    cin >> n;  
    cout<<"Input:"<<endl;  
    for(int i=0;i<n;i++)  
        cin>>weight[i];  
    HuffmanTree <double> a(weight,n);  
    a.HuffmanCode();  
    return 0;  
}