hafuman.cpp

哈夫曼函数哈夫曼函数哈夫曼函数哈夫曼函数哈夫曼函数

#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;      //将左孩子标记为0
                else
                    cd.bit[cd.start]=1;       //右孩子标记为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()
{
    string str;
    int i=0,j,n,m[200],h,k=0;
    char cha[100];
    cout<<"请输入一个字符串"<<endl;
    cin>>str;
    n=str.length();
    cout<<"字符串总共有字符"<<n<<"个"<<endl;
    for(i=0;i<n;i++)                               //统计字符出现的次数
    {
        j=0;h=0;
        while(str[i]!=str[j])
            j++;
        if(j==i)
        {
        cha[k]=str[i];
        cout<<"字符"<<cha[k]<<"出现";
        }
        else
            continue;
        for(j=i;j<n;j++)
        {
            if(str[i]==str[j])
                h++;
        }
        cout<<h<<"次"<<endl;
        m[k]=h;
        k++;
    }
    cout<<"每个字符的哈夫曼编码是："<<endl;              
    huf(cha,m,k);                                    //调用哈夫曼函数，得到各个字符的编码
    cin.get();
  
}