C++ 哈夫曼编码解码实现

#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 ;//将这两个节点的父节点设为新建节点i HT[i].lchild = s1 ,HT[i].rchild = s2 ;//将这两个节点作为新建节点i的左右孩子 HT[i].weight = HT[s1].weight + HT[s2].weight ;//i的权值为这两个节点的权值之和 } }

void HuffmanDecoding(char* code, HuffmanTree HT, int n) { int p = 2 * n - 1; // 根节点 int len = strlen(code); int cnt = 0; while (cnt < len) // 遍历编码字符串 { if (code[cnt] == '0') // 左子树 p = HT[p].lchild; else // 右子树 p = HT[p].rchild; cnt++; if (HT[p].lchild == 0 && HT[p].rchild == 0) // 叶子节点，输出字符 { printf('%c', p - n + 'A' - 1); p = 2 * n - 1; // 重置为根节点 } } } 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';//如果是左孩子，则编码为0 else cd[start]='1';//如果是右孩子，则编码为1 c = f; f = HT[f].parent; } HC[i] = new char[n-start]; strcpy(HC[i],&cd[start]);//将编码复制到HC中 } delete cd;//释放内存 }

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<=2*cnt-1; ++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]);//输出原字符串的哈夫曼编码		        
    puts('');
    char code[1000];
    scanf('%s',code);
    printf('Decoding Result:\n');

\tprintf('\n%s\n', code); // 输出原字符串 HuffmanDecoding(code, HT, cnt); return 0; }