一.问题描述
随意输入一些字符串，统计每一个输入字符出现的个数，然后以它们作为权值，设计一  
个四元Huffman编/译码系统。

二.基本要求
(1)统计输入的字符串含有几个字符，即是计算出需多少个码元。
(2)调整码元的个数，以达到可以建立Huffman树。
(3)输出字符串中符号（码元）的个数。
(4)以每个字符出现的次数为权值，建立Huffman树，求出Huffman码。
(5)计算出编码的效率。
(6)对输入字符串进行译码。

三.测试数据
  测试数据：abcd;  abbccddw;  aadasdweqweqedsg
,
四.算法思想
构造哈夫曼树算法：
（1）用给定的一组权值{W1,W2,…,Wn},生成一个有n棵树组成的森林F={T1,T2,…Tn},  其中每棵树Ti只有一个结点，即权值为 Wi的根结点（也是叶子结点）；
（2）从F中选择四个根结点权值最小的树，作为新树根的四个孩子，新树根的权值是四个孩 子根结点的权值之和；
（3）从F中删除这四棵树，另将新的四树加入F中；
（4）重复（2）和（3），直到F中只包含一棵树为止。

                       
 
编码   
   该函数实现对哈夫曼树的编码，先申请一个能存储字符编码的临时空间cd，编码从哈夫曼树的叶子结点开始，寻找其父母结点，然后根据父母结点判断孩子结点的位置，1的置0，2的置1，3的置2，4的置3，并将0,1,2,3这样的字符从后往前逆序存放在cd中，每求得一个叶子结点的编码，就将其复制到存储哈夫曼编码的头指正数组中，找完叶子结点的编码后就释放临时空间cd。            
                           
                      
对哈夫曼码译码  
   逐个读取存放在里边的编码字符，并与先前的编码相匹配，直到找到编码对应的原字符。
                              

五．模块划分

功能函数模块划分
void main()                                            //主函数
count(char *inp_str,int count_str[],char sa_str[])             //统计输入的字符和字符串
select(HuffmanTree HT,int k,int &s1,int &s2,int &s3,int &s4)   //挑选权值最小的的四个节点
creat_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int count_str[],char sa_str[])//建立霍夫曼树
HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)//给霍夫曼树的每个叶子节点分配二进制码
coding(HuffmanCode HC,char inp_str[],char get[])    //输出字符串的二进制编码
decode(HuffmanCode HC,char receive[],char s[])   //译码
code_ratio(char inp_str[],int count_str[],HuffmanCode HC)  //计算编码效率


六．源程序

#include
#include
#include
using namespace std;
#define n 100                    //设定输入最大的码元
#define m 133                   //在码元最大时，霍夫曼树的节点
int ad_num=0;                  //不平衡霍夫曼树时，调整的增加的个数
int tot_num=0;                  //霍夫曼树总的节点数
int num=0;                     //霍夫曼树的码元


//码点的存储结构
 struct CodeNode
{
    char ch;  //信源符号
    char bits[9]; //存放码字
    int len;//码字长度
};
typedef CodeNode HuffmanCode[n+1];//定义CodeNode存储结构的数组类型


//树节点的存储结构
 struct  HTNode
{
    int weight;
    int child1,child2,child3,child4;
    int parent;

};
 typedef HTNode HuffmanTree[m+1];

//统计输入的字符和字符串
int  count(char *inp_str,int count_str[],char sa_str[])
{
    char *p;
    int i,j;
    int temp[257];
    for(i=0;i<257;i++)
        temp[i]=0;
    for(p=inp_str;*p!='\0';p++)
    {
        temp[*p]++;
    }
    for(i=0,j=0;i<257;i++)
        if(temp[i]!=0)
        {
            j++;
            sa_str[j]=i;
            count_str[j]=temp[i];
        }


      if((j-1)%3!=0)
      {
        
          if(j%3==0)
          {
              count_str[++j]=0;
               ad_num=1;
          }
        
          else
          {
              count_str[++j]=0;
              count_str[++j]=0;
              ad_num=2;
          }
      }

      num=j;
      return j;
}


//挑选权值最小的的四个节点
void select(HuffmanTree HT,int k,int &s1,int &s2,int &s3,int &s4)
{
    int i,j;
    int minl=32767;
    //s1
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s1=j;
    //s2
    minl=32767;
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s2=j;
     //s3
    minl=32767;
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s3=j;
    //s4
    minl=32767;
    for(i=1;i<=k;i++)
    {
        if(HT[i].weight
        {
            j=i;
            minl=HT[i].weight;
        }
    }
    s4=j;

}
//建立霍夫曼树
void creat_HuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int count_str[],char sa_str[])
{
    int i,s1,s2,s3,s4;
    for(i=1;i<=tot_num;i++)
    {
        HT[i].child1=0;
        HT[i].child2=0;
        HT[i].child3=0;
        HT[i].child4=0;
        HT[i].parent=0;
        HT[i].weight=0;
    }
    for(i=1;i<=num;i++)
    {
        HT[i].weight=count_str[i];
    }

    for(i=num+1;i<=tot_num;i++)
    {
        select(HT,i-1,s1,s2,s3,s4);
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[s3].parent=i;
        HT[s4].parent=i;

        HT[i].child1=s1;
        HT[i].child2=s2;
        HT[i].child3=s3;
        HT[i].child4=s4;
       
        HT[i].weight=HT[s1].weight+HT[s2].weight+HT[s3].weight+HT[s4].weight;
    }
    for(i=1;i<=num-ad_num;i++)
    {
        HC[i].ch=sa_str[i];
      
    }
}



//给霍夫曼树的每个叶子节点分配二进制码
void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)
{
    int c,p,i;
    char cd[n];
    int start;
    cd[num]='\0';
    for(i=1;i<=num;i++)
    {
        start=num;
        c=i;
        while((p=HT[c].parent)>0)
        {
            start--;
            if(HT[p].child1==c)
              cd[start]='0';
            if(HT[p].child2==c)
              cd[start]='1';
            if(HT[p].child3==c)
             cd[start]='2';
            if(HT[p].child4==c)
             cd[start]='3';

            c=p;
        }
        strcpy(HC[i].bits,&cd[start]);
        HC[i].len=num-start;
    }
}
//输出字符串的二进制编码
void coding(HuffmanCode HC,char inp_str[],char get[])
{
    int i,j=0;
    while(inp_str[j]!='\0')
    {
        for(i=1;i<=num-ad_num;i++)
        if(HC[i].ch==inp_str[j])
        {
            strcat(get,HC[i].bits);
            break;
        }
        j++;
    }
    strcat(get,"\0");
}
//译码
void decode(HuffmanCode HC,char receive[],char s[])
{
    char str[268];
    char cd[9];
    int i,j,k=0,p=0,cjs;
    while(receive[p]!='\0')
    {
        cjs=0;
        for(i=0;i
        {
            cd[i]=' ';
            cd[i+1]='\0';
            cd[i]=receive[p++];
            for(j=1;j<=num-ad_num;j++)
              if(strcmp(HC[j].bits,cd)==0)
              {
                str[k]=HC[j].ch;
                k++;
                cjs=1;
                break;
              }
        }
    }
    str[k]='\0';
    strcpy(s,str);
}

//计算编码效率
double code_ratio(char inp_str[],int count_str[],HuffmanCode HC)
{
    double up=0.0,down=0.0,temp=0.0;
    int i,len=strlen(inp_str);
    for(i=1;i<=num-ad_num;i++)
    {
        temp=count_str[i]/double(len);
        up-=temp*(log(temp)/log(4));
        down+=temp*HC[i].len;
    }
    return (up/down)*100;
}

int main()
{
    char sa_str[257];
    char inp_str[1000],s[1000];
    int count_str[257];
    int i;
    char receive[1000];
    HuffmanTree HT;
    HuffmanCode HC;

    cout<<"输入要编码的字符串"<<"  ";
    cin>>inp_str;
    num=count(inp_str,count_str,sa_str);
    cout<<"共有多少种字符"<<num-ad_num<<endl;
    tot_num=num+num/3;

    creat_HuffmanTree(HT,HC,count_str,sa_str);
    HuffmanEncoding(HT,HC);
    for(i=1;i
        cout<<"字符"<<HC[i].ch<<"出现的次数"<<count_str[i]<<",编码为"<<HC[i].bits<<endl;

    char get[1000];
    get[0]='\0';
    coding(HC,inp_str,get);
    cout<<"Huffman编码为:"<<get<<endl;
    cout<<"编码效率:"<<code_ratio(inp_str, count_str, HC)<<endl;
    cout<<"译码输入:";
     cin>>receive;
    decode(HC,receive,s);
    cout<<"译码:"<<s<<endl;
return 0;
}
 
 

 




 
七.测试情况
程序编译采用g++ 4.6.3，