huffman.cpp

huffman 编码。typedef struct { int weight int flag int parent int lchild int rchild }

#include<iostream>
#include<string>
using namespace std;
typedef struct 
{
    int weight;
    int flag;
    int parent;
    int lchild;
    int rchild;
}hnodetype;
typedef struct 
{
    int bit[10];
    int start;
    char leaf;
}hcodetype;
void huf(char cha[],int m[],int n)
{                                   
    int i,j,m1,m2,x1,x2,c,p;
    hnodetype *huffnode=new hnodetype[2*n-1];
    hcodetype *huffcode=new hcodetype[n],cd;
    for(i=0;i<2*n-1;i++)
    {                                     //初始化哈夫曼树
        huffnode[i].weight=0;
        huffnode[i].parent=0;
        huffnode[i].flag=0;
        huffnode[i].lchild=-1;
        huffnode[i].rchild=-1;
    }
    for(i=0;i<n;i++)
    {                                    //哈夫曼结点赋初值
        huffnode[i].weight=m[i];
        huffcode[i].leaf=cha[i];
    }
    for(i=0;i<n-1;i++) 
    {                                    //对结点进行编码
        m1=m2=10000000;
        x1=x2=0;
        for(j=0;j<n+i;j++)
        {
            if(huffnode[j].weight<=m1&&huffnode[j].flag==0)
            {
                m2=m1;
                x2=x1;
                m1=huffnode[j].weight;
                x1=j;
            }
            else if(huffnode[j].weight<=m2&&huffnode[j].flag==0)
            {
                m2=huffnode[j].weight;
                x2=j;
            }
        }
        huffnode[x1].parent=n+i;
        huffnode[x2].parent=n+i;
        huffnode[x1].flag=1;
        huffnode[x2].flag=1;
        huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
        huffnode[n+i].lchild=x1;
        huffnode[n+i].rchild=x2;
    }
    for(i=0;i<n;i++)
 {                                         //生成哈夫曼树
            cd.start=n-1;
            c=i;
            p=huffnode[c].parent;
            while(p!=0)
            {
                if(huffnode[p].lchild==c)
                    cd.bit[cd.start]=0;
                else
                    cd.bit[cd.start]=1;
                cd.start--;
                c=p;
                p=huffnode[c].parent;
            }
            cout<<huffcode[i].leaf<<":";
            for(j=cd.start+1;j<n;j++)
            {
                huffcode[i].bit[j]=cd.bit[j];
                cout<<cd.bit[j];
            }
            cout<<endl;
            huffcode[i].start=cd.start;
    }
    delete[] huffcode;
    delete[] huffnode;
}
void main()
{
    int i=0;
 int m[10]={30,23,10,10,9,8,7,3};
    char cha[10]="abcdefgh";
 float f;
    cout<<"该字符串为:\t";
 for (i=0;i<strlen(cha);i++)
 { cout<<cha[i]<<"\t"; }
 cout<<"字符加权为:\t";
 for (i=0;i<strlen(cha);i++)
 {
  f=(float)m[i]/100;
  cout<<f<<"\t";
 }
    cout<<"各字符的哈夫曼码为："<<endl;
 i=strlen(cha);
    huf(cha,m,i);
}