Huffman编码C语言实现

发布网友 发布时间：2022-05-02 08:55

我来回答

共2个回答

热心网友 时间：2023-10-14 18:40

说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。
#pragmaonce
#include<stdio.h>
#include<tchar.h>
#include<stdlib.h>
#define MAX 100

typedefstruct{ //节点
int weight;
int parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedefchar **HuffmanCode; //字符串数组，用于存储叶子节点的编码

void SelectMinNode(HuffmanTree &HT, int m, int &i1, int &i2) //找出权值最小的两个节点对应的数组下标
{
HuffmanTree p = HT;
int s1, s2;
s1 = s2 = MAX;
i1 = i2 = 1;
for(int i=1; i<=m; i++)
{
if(!(p+i)->parent)
{
if((p+i)->weight < s1)
{
i2 = i;
s1 = (p+i)->weight ;
}
}
}
for(int i=1; i<=m; i++)
{
if(!(p+i)->parent && i!=i2)
{
if((p+i)->weight < s2)
{
i1 = i;
s2 = (p+i)->weight ;
}
}
}
}
void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制
{
char *c1, *c2;
c1 = p;
while(q[start] != '\0')
{
*c1 = q[start];
c1++;
start++;
}
*c1 = q[start];//别忘了将‘\n’复制过来
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数
int i, i1, i2, m;
HuffmanTree p;
if(n<=1) return;
m = 2 * n -1; //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。
HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //数组首元素不使用，故多分配一个空间
p = HT + 1;
for(i=1;i<=n;++i,++p,++w) //n个叶子节点初始化
{
p->weight = *w;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
for(;i<=m;++i,++p) //非叶子节点初始化
{
p->weight = 0;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
}
for(i=n+1;i<=m;++i) //对非叶子节点重新计算
{
SelectMinNode(HT, i-1, i1, i2);
HT[i1].parent = i;
HT[i2].parent = i;
HT[i].lchild = i1;
HT[i].rchild = i2;
HT[i].weight = HT[i1].weight + HT[i2].weight ;
}

///从叶子节点到根节点求赫夫曼编码
char* cd;
int start, c, f;
HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指针数组，同样多分配一个
cd = (char*)malloc(n*sizeof(char)); //零时变量，用于存储当前叶子节点的赫夫曼编码
cd[n-1] = '\0';
for(int i=1; i<=n; i++)
{
start = n-1;
for(c=i,f=HT[i].parent; f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild == c)
cd[--start] = '0';
else
cd[--start] = '1';
}
HC[i] = (char*)malloc((n-start)*sizeof(char));
StrCopy(HC[i], cd, start); //将存储的编码copy给HC的第i个数组
}
free(cd);
}
void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码
{
HuffmanCode p;
for(int i=1; i<=n; i++)
{
p = HC;
printf("The weight %d HuffmanCode is: ", HT[i]);
while(*p[i]!='\0')
{
printf("%c",*p[i]);
p[i]++;
}
printf("\n");
}
}
void main()
{
int n = 8;
HuffmanTree HT;
HuffmanCode HC;
int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信号源的概率分布，即P={p0, p1,…, pK-1}
HuffmanCoding(HT, HC, a, n);
PrintHuffmanCode(HT, HC, n);
system("pause");}

热心网友 时间：2023-10-14 18:41

#include <stdio.h>

#include <stdlib.h>
#include <io.h>
#define N 255
#define M 2*N - 1
char file[20] = "1.txt";
typedef struct
{
int data; /* 字符值 */
int weight; /* 权重 */
int parent; /* 双亲结点 */
int lchild; /* 左孩子结点 */
int rchild; /* 右孩子结点 */
}Tree;
typedef struct
{
char cd[N];
int start;
}Code;
Tree ht[M];
Code hcd[N];
int cmp(const void*, const void*);
int NumberOfChar();
void Reset();
void InputFile();
void Encode(int);
void Decode(int);
void OutputFile(int);
void PrintHuffmanCode(int);
void CreateHT(int);
void CreateHCode(int);
int main()
{
int x = 0;
int n = 0;
char ch;
Reset();
InputFile();
/* 排序使得有效字符在前面 */
qsort(ht, N, sizeof(Tree), cmp);
/* 记下有效字符的个数 */
n = NumberOfChar();
CreateHT(n);
CreateHCode(n);
OutputFile(n);
PrintHuffmanCode(n);
Encode(n);
Decode(n);
getchar();
return 0;
}
int cmp(const void *a ,const void *b)
{
return (*(Tree *)a).weight < (*(Tree *)b).weight ? 1 : -1;
}
int NumberOfChar()
{
int i, num = 0;
for (i = 0; i < N; i++)
{
if (ht[i].weight > 0) num++;
}
return num;
}
void Reset()
{
int i;
for (i = 0; i < M; i++)
{
ht[i].weight = 0;
ht[i].parent = -1;
ht[i].lchild = -1;
ht[i].rchild = -1;
}
}
void InputFile()
{
FILE *fp;
char ch;
system("cls");
fp = fopen(file, "rt");
/* 读入字符并处理权重 */
while (fscanf(fp, "%c", &ch) != EOF)
{
ht[ch].data = ch;
ht[ch].weight++;
}
fclose(fp);
printf("原文件 %s 读入成功!\n", file);
}
void Encode(int n)
{
int i, k;
char ch;
FILE *fp1, *fp2;
fp1 = fopen(file, "rt");
fp2 = fopen("Encode.txt", "wt+");
/* 一个字符一个字符替换 */
while (fscanf(fp1, "%c", &ch) != EOF)
{
for (i = 0; i < n; i++)
{
if (ht[i].data == ch)
{
for (k = hcd[i].start; k <= n; k++)
{
fprintf(fp2, "%c", hcd[i].cd[k]);
}
}
}
}
fclose(fp1);
fclose(fp2);
printf("编码成功，结果在 Encode.txt 中!\n");
}
void Decode(int n)
{
int i, k;
char ch;
FILE *fp1, *fp2;
fp1 = fopen("Encode.txt", "rt");
fp2 = fopen("Decode.txt", "wt+");
i = 2 * n - 2;
while (fscanf(fp1, "%c", &ch) != EOF)
{
if (ch == '0')
i = ht[i].lchild;
else
i = ht[i].rchild;
/* 找到叶子节点为止 */
if (ht[i].lchild == -1)
{
fprintf(fp2, "%c", ht[i].data);
/* 继续从根节点开始查找 */
i = 2 * n - 2;
}
}
fclose(fp1);
fclose(fp2);
printf("解码成功，结果在 Decode.txt 中!\n");
}
void OutputFile(int n)
{
FILE *fp;
int i, k;
fp = fopen("Huffman_Code.txt", "wt+");
for (i = 0; i < n; i++)
{
fprintf(fp, "%d ", ht[i].data);
for (k = hcd[i].start; k <= n; k++)
{
fprintf(fp, "%c", hcd[i].cd[k]);
}
if (i < n - 1) fprintf(fp, "\n");
}
fclose(fp);
printf("代码表文件 Huffman_Code.txt 生成成功!\n");
}
void PrintHuffmanCode(int n)
{
int i, k;
printf("ASCII \t Char \t HuffmanCode\n");
for (i = 0; i < n; i++)
{
printf("%d \t \"%c\" \t ", ht[i].data, ht[i].data);
for (k = hcd[i].start; k <= n; k++)
{
printf("%c", hcd[i].cd[k]);
}
printf("\n");
}
}
void CreateHT(int n)
{
int i, k ,lmin, rmin;
int min1, min2;
/* 一共有2n-1个节点 */
for (i = n; i < 2 * n - 1; i++)
{
/*lmin和rmin为最小权重的两个节点置*/
min1 = min2 = 0x7FFFFFFF;
lmin = rmin = -1;
for (k = 0; k <= i - 1; k++)
{
/*只在尚未构造二叉树的节点中查找*/
if (ht[k].parent == -1)
{
if (ht[k].weight < min1)
{
min2 = min1;
rmin = lmin;
min1 = ht[k].weight;
lmin = k;
}
else if (ht[k].weight < min2)
{
min2 = ht[k].weight;
rmin = k;
}
}
}
/* 修改2个小权重节点的双亲 */
ht[lmin].parent = i;
ht[rmin].parent = i;
/* 修改双亲的权重 */
ht[i].weight = ht[lmin].weight + ht[rmin].weight;
/* 修改双亲的孩子 */
ht[i].lchild = lmin;
ht[i].rchild = rmin;
}
}
void CreateHCode(int n)
{
int i, f, c;
Code hc;
for (i = 0; i < n; i++)
{
hc.start = n;
c = i;
f = ht[i].parent;
/* 循序直到树根结点 */
while (f != -1)
{
/* 处理左孩子结点 */
if (ht[f].lchild == c)
hc.cd[hc.start--] = '0';
/* 处理右孩子结点 */
else
hc.cd[hc.start--] = '1';
c = f;
f = ht[f].parent;
}
/* start指向哈夫曼编码最开始字符 */
hc.start++;
hcd[i] = hc;
}
}