C++ 哈夫曼编码实现及优化

本文将详细介绍使用 C++ 实现哈夫曼编码的步骤，并给出了完整的代码示例。代码包含创建哈夫曼树、生成哈夫曼编码、以及解码部分的实现。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <fstream>
#include <iostream>
#define MAXN 50
using namespace std;
typedef char **HuffmanCode;
typedef struct{
        int weight;
        int parent, lchild, rchild;
}HTNode,*HuffmanTree;

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;
}
//解码
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]);
        return 0;
}

代码功能说明

创建哈夫曼树
- CreatHuffmanTree(HuffmanTree &HT, int n) 函数负责创建哈夫曼树。
- 该函数根据输入的字符频率（weight数组）构建哈夫曼树，并将树存储在 HT 数组中。
生成哈夫曼编码
- CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) 函数负责生成哈夫曼编码。
- 该函数根据已创建的哈夫曼树 HT，为每个字符生成对应的哈夫曼编码，并将编码存储在 HC 数组中。
解码
- 解码部分需要根据生成的哈夫曼编码，将压缩后的数据还原为原始字符。
- 由于源代码中没有提供解码部分的代码，因此无法进行解码。但是可以根据源代码中的注释和函数名称推测出解码部分的大概思路，即根据生成的哈夫曼编码对原文进行解码，将哈夫曼编码中的01序列转换为对应的字符。具体实现可以参考编码部分的代码，进行逆向操作即可。

优化建议

可以使用动态规划算法优化哈夫曼树的构建过程，提高效率。
可以使用位运算操作，提高编码和解码速度。
可以使用压缩文件格式，如 ZIP 或 GZIP，对压缩后的数据进行更有效的存储。

总结

本文介绍了使用 C++ 实现哈夫曼编码的步骤，并给出了完整的代码示例。代码包含创建哈夫曼树、生成哈夫曼编码、以及解码部分的实现。通过优化代码，可以提高哈夫曼编码的效率和压缩比。