#include <iostream>
using namespace std;
#define N 20     /*待编码字符的个数，即树中叶结点的最大个数*/
#define M 2*N-1 /*树中总的结点数目*/

#include <iostream>
using namespace std;
#define N 20     /*待编码字符的个数，即树中叶结点的最大个数*/
#define M 2*N-1 /*树中总的结点数目*/

class Huffman{
    private:
        typedef struct{
            unsigned int weight;
            unsigned int parent,lchild,rchild;
        }HTNode;            //树的结构
        HTNode *HT;            
        
        typedef struct{
            char data;     //待编码的字符
            int weight;    //字符的权值
            char code[N]; //字符的编码
        }HTCode;           //编码表
        HTCode *HC;
        char *cd;          //需要的编码空间
        int n;
        
    public:
        Huffman();
        ~Huffman();
        void SetValue();   //设置字符数,和权值
        void Select(int k,int &s1,int &s2); //选择parent为0且weight最小的2个结点
        void HuffmanCoding();
};

Huffman::Huffman(){
    HT=new HTNode[N];
    HC=new HTCode[M];
    cd=new char[N];
    n=0;
}

Huffman::~Huffman(){
    delete []HT;
    delete []HC;
    delete []cd;
}

void Huffman::SetValue(){
    int i;
    cout<<"Input code number: "<<endl;
    cin>>n;
    cout<<"Input "<<n<<" charactor: "<<endl;
    for(i=0;i<n;++i)
        cin>>HC[i].data;
    cout<<"Input code weight:   "<<endl;
    for(i=0;i<n;++i)
        cin>>HC[i].weight;   
}

void Huffman::Select(int k,int &s1,int &s2){
    int i;
    for(i=0;i<k;++i)
    if(!HT[i].parent)
       s1=i;
    for(i=0;i<k;++i)
        if(!HT[i].parent&&HT[i].weight<HT[s1].weight)
           s1=i;
    for(i=0;i<k;++i)
        if(!HT[i].parent&&i!=s1)
           s2=i;
    for(i=0;i<k;++i)      
        if(!HT[i].parent&&HT[i].weight<HT[s2].weight&&i!=s1)
           s2=i;
}

void Huffman::HuffmanCoding(){
    //构造赫夫曼树HT,求出n个字符的赫夫曼编码HC
    int i,m=0,s1=0,s2=0;
    m=2*n-1;
    for(i=0;i<m;++i)               //初始化赫夫曼树
    {
        if(i<n)
        HT[i].weight=HC[i].weight;
        else
        HT[i].weight=0;
        HT[i].parent=HT[i].lchild=HT[i].rchild=0;
    }
    for(i=n;i<m;++i)           //构造赫夫曼树
    {
        Select(i,s1,s2);
        HT[s1].parent=i;     HT[s2].parent=i;
        HT[i].lchild=s1;     HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;

    }
    cout<<"\nHuffmanTree: "<<endl;
    cout<<"weight\tparent\tlchild\trchild"<<endl;
    for(i=0;i<m;++i)
        cout<<HT[i].weight<<"\t"<<HT[i].parent
            <<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
    cout<<endl<<endl;
   
    cd[n-1]='\0';            
    int c=0,f=0,start=0;
    for(i=0;i<n;++i)              //逐个求赫夫曼编码
    {
        start=n-1;                //编码结束符下标
        for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)//从叶子到根结点求编码
        if(HT[f].lchild==c)
           cd[--start]='1';//左分支1
           else
              cd[--start]='0'; //右分支0
        strcpy(HC[i].code,&cd[start]);
    }
   
    for(i=0;i<n;++i)           
        cout<<HC[i].data<<" --- "<<HC[i].code<<endl;
        
}
   
int main(){
    Huffman h;
    h.SetValue();
    h.HuffmanCoding();
   
    system("pause");
    return 0;
}
   

Huffman::Huffman(){
    HT=new HTNode[N];
    HC=new HTCode[M];
    cd=new char[N];
    n=0;
}

Huffman::~Huffman(){
    delete []HT;
    delete []HC;
    delete []cd;
}

void Huffman::SetValue(){
    int i;
    cout<<"Input code number: "<<endl;
    cin>>n;
    cout<<"Input "<<n<<" charactor: "<<endl;
    for(i=0;i<n;++i)
        cin>>HC[i].data;
    cout<<"Input code weight:   "<<endl;
    for(i=0;i<n;++i)
        cin>>HC[i].weight;   
}

void Huffman::Select(int k,int &s1,int &s2){
    int i;
    for(i=0;i<k;++i)
    if(!HT[i].parent)
       s1=i;
    for(i=0;i<k;++i)
        if(!HT[i].parent&&HT[i].weight<HT[s1].weight)
           s1=i;
    for(i=0;i<k;++i)
        if(!HT[i].parent&&i!=s1)
           s2=i;
    for(i=0;i<k;++i)      
        if(!HT[i].parent&&HT[i].weight<HT[s2].weight&&i!=s1)
           s2=i;
}

void Huffman::HuffmanCoding(){
    //构造赫夫曼树HT,求出n个字符的赫夫曼编码HC
    int i,m=0,s1=0,s2=0;
    m=2*n-1;
    for(i=0;i<m;++i)               //初始化赫夫曼树
    {
        if(i<n)
        HT[i].weight=HC[i].weight;
        else
        HT[i].weight=0;
        HT[i].parent=HT[i].lchild=HT[i].rchild=0;
    }
    for(i=n;i<m;++i)           //构造赫夫曼树
    {
        Select(i,s1,s2);
        HT[s1].parent=i;     HT[s2].parent=i;
        HT[i].lchild=s1;     HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;

    }
    cout<<"\nHuffmanTree: "<<endl;
    cout<<"weight\tparent\tlchild\trchild"<<endl;
    for(i=0;i<m;++i)
        cout<<HT[i].weight<<"\t"<<HT[i].parent
            <<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<endl;
    cout<<endl<<endl;
   
    cd[n-1]='\0';            
    int c=0,f=0,start=0;
    for(i=0;i<n;++i)              //逐个求赫夫曼编码
    {
        start=n-1;                //编码结束符下标
        for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)//从叶子到根结点求编码
        if(HT[f].lchild==c)
           cd[--start]='0';//左分支0
           else
              cd[--start]='1'; //右分支1
        strcpy(HC[i].code,&cd[start]);
    }
   
    for(i=0;i<n;++i)           
        cout<<HC[i].data<<" --- "<<HC[i].code<<endl;
        
}
   
int main(){
    Huffman h;
    h.SetValue();
    h.HuffmanCoding();
   
    system("pause");
    return 0;
}

[[it] 本帖最后由 无聊人士 于 2008-6-10 23:01 编辑 [/it]]

偶以前写的,码有点糙.. 希望对你有帮助！

楼上要是早点给出啦。。我就不写了。。呵呵。。