code.txt

Huffman于1952年提出了这种方法,开始主要用于电报报文的编码,常用的英文字母E,T应该如何编码,不常用的应该如何编码,

//**函数模板：建立霍夫曼树的算法**//
template <class Type> 
ExtBinTree <Type> HuffmanTree 
        (Type *fr,char *s , int n)
    /* 频率数组 数组长度  */
{
    if ( n > DefaultSize ) {
        cerr << "大小 n " << n 
            << "超出了数组边界 " << endl;  
        exit(0);
    }
        //两棵根结点的权值最小的扩充二叉树
    ExtBinTree <Type>  first, second;
        // first和second的合并树
    ExtBinTree <Type> * newtree;  
        //具有 n 棵扩充二叉树的森林 
    ExtBinTree <Type> Node[DefaultSize];    
        //每棵扩充二叉树 Node[i] 只有一 个带权值
        // fr[i] 的根结点, 其左、右子树均为空。    
    for ( int i = 0; i < n; i++ ) 
        Node[i].SetRootData(fr[i],s[i],NULL,NULL);
    //定义一个最小堆，数据类型为扩充二叉树
    MinHeap < ExtBinTree <Type> > hp( Node, n ); 
        //建立存储扩充二叉树森林的最小堆
    //hp.MinHeap ( Node, n );    
        //重复 n-1趟, 逐步形成霍夫曼树
    for ( i = 0; i < n-1; i++ ) {
            //把两个最小的元素从堆中删除
        hp.RemoveMin ( first );  
        hp.RemoveMin ( second ); 
        newtree = new ExtBinTree<Type> (first, second);     
        //重新插入到最小堆中
        hp.Insert ( *newtree );    
    }
    return *newtree;
}
//**函数模板：计算路径长度的算法**//
template <class Type>
int WelightPathLength(Element<Type> *p,int i)
{
    if(p==NULL)return 0;
    else
    {
        if(p->leftChild==NULL&&p->rightChild==NULL)
        {
            return p->data*i;
        }
        else
        {
            return   WelightPathLength(p->leftChild,i+1)+
                        WelightPathLength(p->rightChild,i+1);
        }
    }
}
//**函数模板：建立自动打印霍夫曼代码的算法**//
template <class Type>
void Huffman_code (Element<Type> *p,int i,field *q,int l)
{
    
    if(p!=NULL)
    {    
        static int a[10];
        if(p!=NULL)
        {    
            if(p->leftChild==NULL&&p->rightChild==NULL)
            {    
            
            q[l].name=p->GetName();
                cout<<p->GetName()<<": ";
                for(int j=0;j<i;j++)
                cout<<a[j];
                cout<<endl;
            }
        else
            a[i]=0;Huffman_code(p->leftChild,i+1,q,l);
            a[i]=1;Huffman_code(p->rightChild,i+1,q,l);
            
        }
    }
}
int * weight(int *f)
{    
    int *a=f,c;
    for(int i=0;i<26;i++)
        a[i]=0;
    FILE *fp;
    char *filename="out.txt";
    if((fp=fopen(filename,"r"))==NULL)
    {   printf("cannot open file\n");
         exit(0);
    }
    while((c=fgetc(fp))!=EOF)
    {
        if(96<c&&c<123)
        a[c-97]=a[c-97]+1;
    }
    fclose(fp);
    return a;
}

//主函数
void main()
{    
    int i=0,len=0,l=0;
    field ss[26];
    char c[26];
    //叶子结点的频率（权重）表
    int f[26];
    weight(f);
    for(int v=0;v<26;v++)
    {
        c[v]=v+97;
    }
    int n=26; //叶子结点数目
    //生成霍夫曼树
    ExtBinTree <int> H=HuffmanTree(f,c,n);
    Huffman_code(H.Getroot(),i,ss,l);
    H.PreOrder(H.Getroot());
    cout<<endl;
    cout<<"路径长度: "<<WelightPathLength(H.Getroot(),len)<<endl;
}