C++ Huffman 编码解码算法实现

#include <stdio.h> #include<stdlib.h> #include<string.h> #include

HuffmanTree HT; HuffmanCode HC; int m,s1,s2,start,c,f; char *cd; int z[30]; int weight[MAXN] ;

void Select(HuffmanTree HT,int n,int &s1,int &s2)//Select函数 { int min1 =0x3f3f3f3f; int min2 =0x3f3f3f3f; for(int i=1;i<=n;i++) { if(HT[i].parent) continue;//不是根节点 if(HT[i].weight < min1) { min1 = HT[i].weight; s1 = i; continue; } if(HT[i].weight < min2 && HT[i].weight >= min1) { min2 = HT[i].weight; s2 = i; } } }

void CreatHuffmanTree(HuffmanTree &HT ,int n ) { if ( n <= 1 ) return; int m = 2 * n ; HT = new HTNode[m+1] ; for (int a = 1 ; a <= m ; a ++ ) { HT[a].parent = HT[a].lchild = HT[a].rchild = HT[a].weight = 0; } for (int j = 1 ; j <= n ; j ++ ) { HT[j].weight = weight[j] ; } int s1 ,s2 ; for (int i = n + 1 ; i <= m ; i ++ ) { Select(HT ,i - 1 ,s1 ,s2 ); HT[s1].parent = i ; HT[s2].parent = i ; HT[i].lchild = s1 ,HT[i].rchild = s2 ; HT[i].weight = HT[s1].weight + HT[s2].weight ; } } //编码 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) { HC = new char*[n+1]; cd = new char[n]; cd[n-1] = '\0'; for(int i=1; i<=n; ++i) { start = n-1; c = i; f = HT[i].parent; while(f!=0)// { --start; if(HT[f].lchild == c) cd[start]='0'; else cd[start]='1'; c = f; f = HT[f].parent;//向上回溯 } HC[i] = new char[n-start]; strcpy(HC[i],&cd[start]); } delete cd; }

//解码函数 void Decode(HuffmanTree HT,int n,char s) { int p=2n-1; for(int i=0;i<strlen(s);i++) { if(s[i]=='0') p=HT[p].lchild; else p=HT[p].rchild; if(HT[p].lchild==0 && HT[p].rchild==0) { printf("%c",p-1+'A'); p=2*n-1; } } }

//主函数 int main() { // freopen("in.txt", "r", stdin);//文件要和代码放在同一个文件夹 // freopen("out.txt", "w", stdout); char s[MAXN]; scanf("%s",s); int len = strlen(s); memset(z,0,sizeof(z)); for(int i=0;i<len;i++)//统计字符个数 z[s[i]-'A'+1]++; int cnt=0; for(int j=1;j<=26;++j) if(z[j]) cnt++; for(int k=1;k<=26;k++) if(z[k]) printf("%c:%d\n",'A'+k-1,z[k]);

    CreatHuffmanTree(HT,cnt);

    //输出一下看看是否建立好哈夫曼数
    printf("\n i   weight  parent  lchild  rchild \n");
    for(int x=1; x<=m; ++x)
            printf("%2d %5d %8d %8d %8d\n",x,HT[x].weight,HT[x].parent,HT[x].rchild,HT[x].lchild);


    CreatHuffmanCode(HT,HC,cnt);
    printf("\n\nHuffmanCode:\n");
    printf(" i  Char   Code\n\n");
    for(int t=1; t<=cnt; ++t)
            printf("%2d   %c     %s\n",t,t+'A'-1,HC[t]);

    puts("");
    for(int z=0;z<len;z++)
            printf("%s",HC[s[z]-'A'+1]);

    printf("\n\nDecode:\n");
    Decode(HT,cnt,HC[s[0]-'A'+1]);//解码
    return 0;

}