哈夫曼编解码（C语言）

示例

输入：
helllllllo

生成码表：
a:00010010
b:00010011
c:00010100
d:00010101
e:001
f:00010110
g:00010111
h:010
i:00011000
j:00011001
k:00011010
l:1
m:00011011
n:00011100
o:011
p:00011101
q:00011110
r:00011111
s:0000000
t:0000001
u:0000010
v:0000011
w:0000100
x:0000101
y:0000110
z:0000111

编码结果：
0100011111111011

解码结果：
helllllllo

代码实现

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define maxsize 1000 /* 编码函数中，被编译的字符串的最大长度 */
#define max 1000 /* 最大字符的个数 */

typedef struct {
    char data;    /* 数据域 */
    int weight;   /* 权值域 */
    int parent;
    int left;
    int right;
} huffNode;

typedef struct {
    char code[max]; // 存放哈夫曼编码
    int start;
} huffCode;

huffNode *initFrequency(int count[]) // 初始化带权结点
{
    static huffNode ht[2 * max];
    ht[0].weight = 27;   /* 字符个数 */
    ht[1].data = ' ';
    ht[1].weight = count[26]; // space
    for (int i = 1; i <= 27; i++) {
        ht[i].data = (char) ('a' + i - 1);
        ht[i].weight = count[i - 1];
    }
    return ht;
}

void buildTree(huffNode *ht) {
    /* m1为最小权值，x1为其在ht中的下标；m2为第二小权值，x2为其下标 */
    int i, k, x1, x2, n, m1, m2;

    n = ht[0].weight;
    for (i = 1; i <= 2 * n - 1; i++)
        ht[i].parent = ht[i].left = ht[i].right = 0;  /* 对ht的parent，left，right域进行初始化 */
    for (i = n + 1; i <= 2 * n - 1; i++) {
        m1 = m2 = 10000;  /* m1，m2初值无限大 */
        x1 = x2 = 0;      /* x1, x2初值为0 */
        for (k = 1; k <= i - 1; k++) {/* k为可以进行比较的结点的下标 */
            if (ht[k].parent == 0) { /* 当前结点的父结点不存在时 */
                if (ht[k].weight < m1)   /* 当前结点的权值比最小权值还小时 */
                {
                    m2 = m1;
                    x2 = x1;
                    m1 = ht[k].weight;
                    x1 = k;
                } else if (ht[k].weight < m2) {  /* 当前结点的权值比最小权值大但比第二最小权值小时 */
                    m2 = ht[k].weight;
                    x2 = k;
                }
            }
        }
        ht[x1].parent = i;
        ht[x2].parent = i;
        ht[i].weight = ht[x1].weight + ht[x2].weight;
        ht[i].left = x1;
        ht[i].right = x2;
    }
}

huffCode *printHuffmanCode(huffNode *hNode) {
    static huffCode hCode[max];
    huffCode d;
    int i, n, c, f, k, x;
    n = hNode[0].weight;
    for (i = 1; i <= n; i++) {
        d.start = n + 1;
        c = i;
        f = hNode[i].parent;
        while (f != 0) {
            if (hNode[f].left == c) d.code[--d.start] = '0';
            else d.code[--d.start] = '1';
            c = f;
            f = hNode[f].parent;
        }
        hCode[i] = d;
    }
    printf("huffman code table:\n");
    for (i = 1; i <= n; i++) {
        printf("%c:", hNode[i].data);
        x = hCode[i].start;
        for (k = x; k <= n; k++) {
            printf("%c", hCode[i].code[k]);
        }
        printf("\n");
    }
    return hCode;
}

huffCode *encoding(huffCode *hCode, huffNode *hNode) {
    int i, j, n, m, k, x;
    char in[maxsize], out[2 * maxsize];
    int count[27] = {0};
    m = 0;
    printf("input a string:");
    getchar();
    gets(in);
    n = strlen(in);

    for (i = 0; i < n; i++) {
        if (in[i] >= 'a' && in[i] < 'z') {
            count[in[i] - 'a']++;
        }
        if (in[i] == ' ')count[26]++;
        if (in[i] == '0') break;
    }
    hNode = initFrequency(count);
    buildTree(hNode);
    hCode = printHuffmanCode(hNode);

    for (i = 0; i < n; i++) {
        for (j = 1; j <= hNode[0].weight; j++) {
            if (in[i] == hNode[j].data) {
                x = hCode[j].start;
                for (k = x; k <= hNode[0].weight; k++) {
                    out[m++] = hCode[j].code[k];
                }
            }
        }
    }

    printf("\nThe encoding result is:\n");
    for (i = 0; i < m; i++) {
        printf("%c", out[i]);
    }
    return hNode;
}

void decoding(huffCode hcd[], huffNode ht[]) {
    int i, j, n, k, x, m, w;
    char in[maxsize * 2], out[maxsize];
    printf("\nenter huffman code:\n");
    scanf("%s", in);
    n = strlen(in);
    i = 0;
    m = 0;

    while (i < n) {
        for (j = 1; j <= ht[0].weight; j++) {
            x = hcd[j].start;
            for (k = x, w = i; k <= ht[0].weight; k++, w++) {
                if (in[w] != hcd[j].code[k]) {
                    break;
                }
            }
            if (k > ht[0].weight) {
                out[m++] = ht[j].data;
                break;
            }
        }
        i = w;
    }
    for (i = 0; i < m; i++) {
        printf("%c", out[i]);
    }
}

int main() {
    int select;
    huffNode *hNode;
    huffCode *hCode;
    do {
        printf("\n\n");
        printf("--------------------------Menu-----------------------------\n");
        printf("1. input string\n");
        printf("2. input code\n");
        printf("-----------------------------------------------------------\n\n");
        printf("choose 1 or 2: ");
        scanf("%d", &select);
        if (select == 1) {
            hNode = encoding(hCode, hNode);
        } else if (select == 2) {
            hCode = printHuffmanCode(hNode);
            decoding(hCode, hNode);
        } else {
            printf("No such option. Exit.\n");
            exit(1);
        }
    } while (1);
}