哈夫曼树编码与解码c++

哈夫曼编码是一种可变字长编码（VLC）的一种。它是由David A. Huffman在1952年发明的。它是一种树形结构，在编码过程中，权值较小的叶节点会被编码为较短的比特串，而权值较大的叶节点会被编码为较长的比特串，这样可以实现对数据的高效压缩。下面是哈夫曼树的编码与解码的C语言实现：

先定义哈夫曼树的节点结构体：

typedef struct node {
    int weight;
    int parent;
    int lchild;
    int rchild;
}HuffNode, *HuffTree;

接着，定义哈夫曼树的构建函数，该函数的输入参数为存储字符频率的数组 `weight[]`，以及字符的个数 `n`。

HuffTree createHuffTree(int weight[], int n) {
    HuffTree huffTree;
    int m = 2 * n - 1;
    huffTree = (HuffNode*)malloc((m + 1) * sizeof(HuffNode));
    for(int i = 1; i <= n; i++) {
        huffTree[i].weight = weight[i - 1];
        huffTree[i].parent = 0;
        huffTree[i].lchild = 0;
        huffTree[i].rchild = 0;
    }
    for(int i = n + 1; i <= m; i++) {
        huffTree[i].weight = 0;
        huffTree[i].parent = 0;
        huffTree[i].lchild = 0;
        huffTree[i].rchild = 0;
    }
    int s1, s2;
    for(int i = n + 1; i <= m; i++) {
        select(huffTree, i - 1, &s1, &s2);
        huffTree[s1].parent = i;
        huffTree[s2].parent = i;
        huffTree[i].lchild = s1;
        huffTree[i].rchild = s2;
        huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
    }
    return huffTree;
}

其中，`select()`函数用于选择权值最小的两个节点（即叶节点或新节点）。

void select(HuffTree huffTree, int n, int *s1, int *s2) {
    int i, j;
    i = 1;
    while(huffTree[i].parent != 0) i++;
    *s1 = i;
    j = i + 1;
    while(huffTree[j].parent != 0) j++;
    *s2 = j;
    if(huffTree[*s2].weight < huffTree[*s1].weight) {
        int temp = *s1;
        *s1 = *s2;
        *s2 = temp;
    }
    for(int k = i + 1; k <= n; k++) {
        if(huffTree[k].parent == 0) {
            if(huffTree[k].weight < huffTree[*s1].weight) {
                *s2 = *s1;
                *s1 = k;
            } else if(huffTree[k].weight >= huffTree[*s1].weight && huffTree[k].weight < huffTree[*s2].weight) {
                *s2 = k;
            }
        }
    }
}

接下来，是对字符串进行编码的函数，该函数的输入参数为待编码的字符串 `str`，以及哈夫曼树 `huffTree`。

void encode(char *str, HuffTree huffTree) {
    printf("编码结果：\n");
    while(*str != '\0') {
        int i;
        char c = *str;
        str++;
        for(i = 1; i <= strlen(huffCode[c]); i++) {
            printf("%c", huffCode[c][i - 1]);
        }
    }
    printf("\n");
}

其中，`huffCode[]`数组存储了每个字符的哈夫曼编码。

最后，是对编码进行解码的函数，该函数的输入参数为待解码的字符串 `str`，以及哈夫曼树 `huffTree`。

void decode(char *str, HuffTree huffTree) {
    printf("解码结果：\n");
    int p = 2 * strlen(huffCode) - 1;
    while(*str != '\0') {
        if(*str == '0') {
            p = huffTree[p].lchild;
        } else {
            p = huffTree[p].rchild;
        }
        if(huffTree[p].lchild == 0 && huffTree[p].rchild == 0) {
            printf("%c", huffTree[p].weight);
            p = 2 * strlen(huffCode) - 1;
        }
        str++;
    }
    printf("\n");
}

最终，将上述函数整合在一起即可实现哈夫曼编码与解码。