哈夫曼树——按字符出现频率自动编码

问题简述：

  只向程序内输入一串字符串或者一串数字，并不给权重，程序能自动统计每个字符出现的个数，然后分配权重，进行哈夫曼编码。

思路：

  该程序要解决两个问题：①统计字符频率，制成权重；②哈夫曼编码。

①统计字符频率

  由于在字符串读入过程中，遇到空格就停止了，所以采取循环地读入单个单词，并在每次读完单词后添空格。循环这里写的比较简单，所以需要手动输入单词个数，大家可以进行改进。
  对于每个字符出现的次数统计，我们建立一个能包含整个ASCII码的数组r[]，将ASCII码作为次数统计的下标，比如读入一个空格，因为空格的ASCII码值为32，则执行r[32]++。

②哈夫曼编码

  这个网上已经介绍的很多了，直接拿来用，把手动输入权重的地方改成由①建立权重就好了。

结果示意

代码：

#include<bits/stdc++.h>
using namespace std;
#define maxval 10000
#define MaxBit 100   //哈夫曼编码的最大位数

typedef struct{
    char ch;
    int weight;
    int flag;
    int lchild,rchild,parent;
}HuffmanTree;

typedef struct{
    char codeBit[MaxBit];   //位串
    int start;      //编码在位串中的起始位置
    int weight;
    char ch;        //字符
}CodeNode;

void CreateHuffmanTree(HuffmanTree HuffTree[],int r[],int n){
    int i,j,p1,p2,small1,small2;//x1,x2,
    int w;
    char c;
    int m = 2*n-1;
    for(i=0;i<m;i++){//初始化 
        HuffTree[i].parent=0;
        HuffTree[i].lchild=-1;
        HuffTree[i].rchild=-1;
        HuffTree[i].weight=0;
    }
    i=0;
    for(j=0;j<n;j++){
        while(!r[i])  i++;
        if(r[i]&&(i<255)&&(i>=0)){
            HuffTree[j].ch=i;
            HuffTree[j].weight=r[i];
        }
        i++;
//      哈夫曼树检测 
//      cout<<HuffTree[j].ch<<" "<<HuffTree[j].weight<<endl;
    }   
     for(i=n;i<m;i++){    
        p1=0;p2=0;
        small1=maxval;small2=maxval; 
        for(j=0;j<i;j++)   
            if(HuffTree[j].parent==0)
                if(HuffTree[j].weight<small1){ 
                    small2=small1; 
                    small1=HuffTree[j].weight;
                    p2=p1;
                    p1=j;
                }
                else if(HuffTree[j].weight<small2){
                        small2=HuffTree[j].weight;  
                        p2=j;
                }
                HuffTree[p1].parent=i;
                HuffTree[p2].parent=i;
                HuffTree[i].lchild=p1;  //最小转成新左孩子
                HuffTree[i].rchild=p2;  //次小转成新右孩子
                HuffTree[i].weight=HuffTree[p1].weight+HuffTree[p2].weight;
     }
     
}

//哈夫曼编码
void CalculateHuffmanCode(HuffmanTree HuffTree[],CodeNode HFCode[],int n){
    int i,c,p;
    CodeNode cd;   
    for(i=0;i<n;i++){
        cd.start=n;
        cd.ch=HuffTree[i].ch;
        c=i;     
        p=HuffTree[i].parent;   
        while(p!=0){
            cd.start--;
            if(HuffTree[p].lchild==c)   cd.codeBit[cd.start]='0';   //左'0'
            else    cd.codeBit[cd.start]='1';   //右'1'
            c=p;
            p=HuffTree[p].parent;
        }
        HFCode[i]=cd;    
    }
}

int main(){
    char *a=new char[1024];
    string str; 
    int r[1024]={0};
    int N,n=0;//n为叶子节点数 

    cout<<"单词数目: \n";
    cin>>N;
    cout<<"输入字符串: \n";
    for(int j=0;j<N;j++){
        cin>>a;
        while(*a!='\0'){ str+=*a; r[*a++]+=1;}  
        if(j!=(N-1)) { r[32]+=1; str+=" ";}
    }   
        for(int i=0;i<255;i++)
            if(r[i]) n++;
    
    cout<<"叶子节点数: "<<n<<endl;
    int m = 2*n-1;
    HuffmanTree tree[m];
    CodeNode code[n];
    
    CreateHuffmanTree(tree,r,n);//建立哈夫曼树
    CalculateHuffmanCode(tree,code,n);//哈夫曼编码
    cout<<"哈夫曼编码: "<<endl;
    for(int i=0;i<n;i++){
        printf("%c: ",code[i].ch);
        for(int j=code[i].start;j<n;j++)
        printf("%c ",code[i].codeBit[j]);
        printf("\n");
    }
    cout<<str<<"的哈夫曼编码为："<<endl;
    for(int i=0;i<str.length();i++){
        for(int j=0;j<n;j++)
            if(str[i]==code[j].ch)
                for(int p=code[j].start;p<n;p++) printf("%c ",code[j].codeBit[p]);
    }
    return 0;
}