C++ 哈夫曼编码解码实现：高效压缩与解压缩字符串

{ "title": "C++ 哈夫曼编码解码实现：高效压缩与解压缩字符串", "description": "本文提供 C++ 代码实现哈夫曼编码和解码功能，用于高效压缩和解压缩字符串。代码包含详细注释，并附带示例说明，帮助读者理解哈夫曼算法的原理和应用。", "keywords": "哈夫曼编码, 哈夫曼解码, C++, 字符串压缩, 数据压缩, 算法实现", "content": "#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); char result[MAXN]; // 用于存储解码后的字符串 int resultIndex = 0; // 解码字符串索引 for (int i = 0; i < len; i++) // 遍历编码字符串 { if (code[i] == '0') // 左子树 p = HT[p].lchild; else // 右子树 p = HT[p].rchild; if (HT[p].lchild == 0 && HT[p].rchild == 0) // 叶子节点，输出字符 { result[resultIndex++] = p - n + 'A' - 1; p = 2 * n - 1; // 重置为根节点 } } result[resultIndex] = '\0'; // 添加字符串结束符 printf("Decoding Result:\n"); printf("%s\n", result); // 输出解码后的字符串 } 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);
    HuffmanDecoding(code, HT, cnt);
    return 0;

}