C 语言哈夫曼树编码解码：完整代码及注释

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

// 定义哈夫曼树结构体 typedef struct HuffmanTreeNode { int weight; // 权重 char value; // 字符值 struct HuffmanTreeNode *left; // 左子树 struct HuffmanTreeNode *right; // 右子树 }HuffmanTreeNode;

// 定义哈夫曼编码结构体 typedef struct HuffmanCode { char value; // 字符值 char *code; // 编码 }HuffmanCode;

// 哈夫曼树建立函数 void createHuffmanTree(HuffmanTreeNode **root, int weight[], int n) { // 定义哈夫曼树节点数组 HuffmanTreeNode **nodes = (HuffmanTreeNode **)malloc(sizeof(HuffmanTreeNode *) * n); for(int i=0; i<n; i++) { // 初始化每个节点 HuffmanTreeNode *node = (HuffmanTreeNode *)malloc(sizeof(HuffmanTreeNode)); node->weight = weight[i]; node->value = '\0'; node->left = NULL; node->right = NULL; nodes[i] = node; }

// 建立哈夫曼树
while(n > 1)
{
    // 找到权重最小的两个节点
    int min1 = -1, min2 = -1;
    for(int i=0; i<n; i++)
    {
        if(nodes[i] != NULL)
        {
            if(min1 == -1)
            {
                min1 = i;
            }
            else if(min2 == -1)
            {
                min2 = i;
            }
            else
            {
                if(nodes[i]->weight < nodes[min1]->weight)
                {
                    min2 = min1;
                    min1 = i;
                }
                else if(nodes[i]->weight < nodes[min2]->weight)
                {
                    min2 = i;
                }
            }
        }
    }

    // 合并权重最小的两个节点
    HuffmanTreeNode *newNode = (HuffmanTreeNode *)malloc(sizeof(HuffmanTreeNode));
    newNode->weight = nodes[min1]->weight + nodes[min2]->weight;
    newNode->value = '\0';
    newNode->left = nodes[min1];
    newNode->right = nodes[min2];
    nodes[min1] = newNode;
    nodes[min2] = NULL;
    n--;
}

// 根节点即为哈夫曼树
*root = nodes[0];
free(nodes);

}

// 哈夫曼编码函数 void getHuffmanCode(HuffmanTreeNode *root, HuffmanCode *huffmanCode, char *code, int depth) { if(root == NULL) { return; }

if(root->left == NULL && root->right == NULL)
{
    // 给叶子节点赋值编码
    huffmanCode[root->value].value = root->value;
    huffmanCode[root->value].code = (char *)malloc(sizeof(char) * (depth + 1));
    strcpy(huffmanCode[root->value].code, code);
}

// 分别给左右子树赋值编码
int len = strlen(code);
char *newCode = (char *)malloc(sizeof(char) * (len + 2));
strcpy(newCode, code);
newCode[len] = '0';
newCode[len+1] = '\0';
getHuffmanCode(root->left, huffmanCode, newCode, depth+1);
newCode[len] = '1';
getHuffmanCode(root->right, huffmanCode, newCode, depth+1);
free(newCode);

}

// 哈夫曼编码主函数 void huffmanEncoding(HuffmanTreeNode *root, char *str, HuffmanCode *huffmanCode, char *huffmanStr) { int len = strlen(str); for(int i=0; i<len; i++) { // 按字符顺序加入哈夫曼编码字符串 strcat(huffmanStr, huffmanCode[str[i]].code); } }

// 哈夫曼解码函数 void huffmanDecoding(HuffmanTreeNode *root, char *huffmanStr, char *str) { int len = strlen(huffmanStr); HuffmanTreeNode *p = root; for(int i=0; i<len; i++) { if(huffmanStr[i] == '0') { // 转向左子树 p = p->left; } else { // 转向右子树 p = p->right; }

    if(p->left == NULL && p->right == NULL)
    {
        // 找到叶子节点，记录字符值
        *str++ = p->value;
        p = root;
    }
}

// 结束标志
*str = '\0';

}

int main() { // 举例：字符串'hello world' char str[] = "hello world";

// 统计每个字符出现的次数
int count[128] = {0};
int len = strlen(str);
for(int i=0; i<len; i++)
{
    count[str[i]]++;
}

// 建立哈夫曼树
HuffmanTreeNode *root = NULL;
createHuffmanTree(&root, count, 128);

// 生成哈夫曼编码
HuffmanCode huffmanCode[128];
char code[128] = "";
getHuffmanCode(root, huffmanCode, code, 0);

// 哈夫曼编码
char huffmanStr[1000] = "";
huffmanEncoding(root, str, huffmanCode, huffmanStr);
printf("Huffman code for ' %s ': %s\n", str, huffmanStr);

// 哈夫曼解码
char str2[100] = "";
huffmanDecoding(root, huffmanStr, str2);
printf("Decoded Huffman code: %s\n", str2);

// 释放内存
for(int i=0; i<128; i++)
{
    if(huffmanCode[i].code != NULL)
    {
        free(huffmanCode[i].code);
    }
}
return 0;