C语言实现哈夫曼编码解码

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef char DataType; typedef struct // 哈夫曼树结点的结构 { DataType data; // 数据用字符表示 int weight; // 权值 int parent; // 双亲 int lchild, rchild; // 左右孩子 } HuffNode;

typedef struct // 哈夫曼编码的存储结构 { DataType cd[50]; // 存放编码位串 int start; // 编码的起始位置 } HuffCode;

//创建哈夫曼树 int HuffmanCreate(HuffNode *ht) { int n = 0; int i, j, p1, p2, m1, m2; char c;

int frequency[60] = { 0 };

while ((c = getchar()) != '\n') // 得到字符频率
{
    frequency[c - 65]++;
}
for ( i = 0; i < 58; i++) //付给哈夫曼结点
{
    if (frequency[i] != 0) 
    {
        n++;
        ht[n].data = i + 65;
        ht[n].weight = frequency[i];
    }
}
for (i = 1; i < n + 1; i++)   // 输出结点
{
    printf('%c', ht[i].data); 
    printf('%d', ht[i].weight);
    printf('\n');
}
for (i = 1; i <= 2 * n - 1; i++) // 对数组初始化，共2n-1个结点
{
    ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
}
for (i = n + 1; i <= 2 * n - 1; i++)
{
    m1 = m2 = 32767; // 令 m1 、m2 为整数最大值
    p1 = p2 = 1;
    for (j = 1; j < i; j++) // 找出 parent 为 0 且权值最小的两个叶子结点
    {
        if (ht[j].parent == 0)
        {
            if (ht[j].weight < m1)
            {
                m2 = m1;
                p2 = p1;

                m1 = ht[j].weight;
                p1 = j;
            }
            else if (ht[j].weight < m2)
            {
                m2 = ht[j].weight;
                p2 = j;
            }
        }
    }
    ht[i].lchild = p1;     //p1 为新结点的左孩子
    ht[i].rchild = p2;  //p2 为新结点的右孩子
    ht[i].weight = m1 + m2; 
    ht[p1].parent = i;
    ht[p2].parent = i;
}
printf('哈夫曼树已成功建立！\n');
return n;                   //返回叶子结点个数

}

//编码 void Encoding(HuffNode *ht, HuffCode *hcd, int n) { HuffCode Code; int i, j, f; for (i = 1; i <= n; i++) //向上回溯法 { Code.start = n + 1; // 起始位置 f = ht[i].parent; // 双亲的位置 for (j = i; f != 0; j = f, f = ht[j].parent) { if (ht[f].lchild == j) Code.cd[--Code.start] = '0'; // 规定左树代码为0 else Code.cd[--Code.start] = '1'; // 规定右树代码为1 } hcd[i] = Code; }

printf('输出哈夫曼编码：\n');
for (i = 1; i <= n; i++)
{
    printf('%c', ht[i].data); // 先输出结点
    for (j = hcd[i].start; j <= n; j++)  // 再输出其对应编码
        printf('%c', hcd[i].cd[j]);
    printf('\n');
}

}

//解码 void Decoding(HuffNode *ht, char *str, int n) { int i, j, p; p = 2 * n - 1; for (i = 0; i < strlen(str); i++) //遍历编码串 { if (str[i] == '0') p = ht[p].lchild; //左子树 else p = ht[p].rchild; //右子树 if (ht[p].lchild == 0 && ht[p].rchild == 0) //叶子结点 { printf('%c', ht[p].data); //输出字符 p = 2 * n - 1; //从根节点重新开始 } } }

//主函数 void main() { int n = 0; HuffNode ht[100]; // 定义存放哈夫曼树的数组 HuffCode hcd[50]; // 定义存放编码的数组 char str[1000]; printf('请输入字符串：'); gets(str); //改为 gets 输入完整字符串 n = HuffmanCreate(ht); Encoding(ht, hcd, n); printf('请输入哈夫曼编码：'); gets(str); Decoding(ht, str, n); }