• 日期: 2026-10-09
  • 标签: 常规

使用C语言构建哈夫曼树并实现编码解码

哈夫曼树是一种用于数据压缩和编码的树形结构，它可以将出现频率较高的字符用较短的编码表示，从而达到压缩数据的目的。下面是用C语言实现哈夫曼树的代码。

1. 定义结构体

首先，我们需要定义哈夫曼树中的节点结构体。每个节点包含一个字符和它在文本中出现的频率，以及指向左右子节点的指针。

typedef struct node {
    char symbol;
    int frequency;
    struct node* left;
    struct node* right;
} Node;

2. 构造哈夫曼树

构造哈夫曼树的过程可以分为以下几步：

  • 统计每个字符在文本中出现的频率。
  • 将每个字符及其频率作为一个节点，构成一个森林。
  • 将森林中的节点按照频率从小到大排序。
  • 取出频率最小的两个节点，合并成一个新节点，频率为两个节点的频率之和，左右子节点分别为原来的两个节点。
  • 将新节点插入森林中，并重新排序。
  • 重复以上步骤，直到森林中只剩下一个节点，这就是哈夫曼树的根节点。

下面是实现构造哈夫曼树的代码：

Node* buildHuffmanTree(char* text) {
    int frequencies[256] = { 0 };
    // 统计每个字符出现的频率
    for (int i = 0; i < strlen(text); i++) {
        frequencies[(int)text[i]]++;
    }
    // 将每个字符及其频率作为一个节点
    Node* forest[256] = { NULL };
    int count = 0;
    for (int i = 0; i < 256; i++) {
        if (frequencies[i] > 0) {
            Node* node = (Node*)malloc(sizeof(Node));
            node->symbol = (char)i;
            node->frequency = frequencies[i];
            node->left = NULL;
            node->right = NULL;
            forest[count++] = node;
        }
    }
    // 构造哈夫曼树
    while (count > 1) {
        // 将森林中的节点按照频率从小到大排序
        for (int i = 0; i < count - 1; i++) {
            for (int j = i + 1; j < count; j++) {
                if (forest[i]->frequency > forest[j]->frequency) {
                    Node* temp = forest[i];
                    forest[i] = forest[j];
                    forest[j] = temp;
                }
            }
        }
        // 取出频率最小的两个节点，合并成一个新节点
        Node* node = (Node*)malloc(sizeof(Node));
        node->symbol = '\0';
        node->frequency = forest[0]->frequency + forest[1]->frequency;
        node->left = forest[0];
        node->right = forest[1];
        // 将新节点插入森林中
        forest[0] = node;
        count--;
        for (int i = 1; i < count; i++) {
            forest[i] = forest[i + 1];
        }
    }
    return forest[0];
}

3. 编码

在哈夫曼树中，每个字符都可以用一个二进制编码表示，编码的长度等于该字符在哈夫曼树中的深度。为了方便编码和解码，我们可以使用一个哈希表来存储每个字符对应的编码。

编码的过程可以通过从根节点开始遍历哈夫曼树，如果遇到左子节点就将编码的最后一位设为0，如果遇到右子节点就将编码的最后一位设为1，直到遍历到叶子节点为止。

下面是实现编码的代码：

void encode(Node* node, char* code, int depth, char** table) {
    if (node == NULL) {
        return;
    }
    if (node->symbol != '\0') {
        // 叶子节点，存储编码
        code[depth] = '\0';
        table[(int)node->symbol] = (char*)malloc(strlen(code) + 1);
        strcpy(table[(int)node->symbol], code);
    } else {
        // 非叶子节点，继续遍历
        code[depth] = '0';
        encode(node->left, code, depth + 1, table);
        code[depth] = '1';
        encode(node->right, code, depth + 1, table);
    }
}

char** buildEncodingTable(Node* root) {
    char** table = (char**)malloc(256 * sizeof(char*));
    char code[256];
    encode(root, code, 0, table);
    return table;
}

4. 解码

解码的过程可以通过从根节点开始遍历哈夫曼树，根据每个二进制位的值来确定遍历方向，直到遍历到叶子节点为止，该叶子节点所代表的字符就是解码结果。

下面是实现解码的代码：

char decode(Node* node, char* code, int index) {
    if (node == NULL) {
        return '\0';
    }
    if (node->symbol != '\0') {
        // 叶子节点，返回字符
        return node->symbol;
    } else {
        // 非叶子节点，继续遍历
        if (code[index] == '0') {
            return decode(node->left, code, index + 1);
        } else {
            return decode(node->right, code, index + 1);
        }
    }
}

char* decodeString(Node* root, char* code) {
    char* result = (char*)malloc(strlen(code) + 1);
    int index = 0;
    for (int i = 0; i < strlen(code);) {
        char c = decode(root, code, i);
        if (c != '\0') {
            result[index++] = c;
        }
        i += strlen(encodingTable[(int)c]);
    }
    result[index] = '\0';
    return result;
}

完整代码如下：

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

typedef struct node {
    char symbol;
    int frequency;
    struct node* left;
    struct node* right;
} Node;

Node* buildHuffmanTree(char* text) {
    int frequencies[256] = { 0 };
    // 统计每个字符出现的频率
    for (int i = 0; i < strlen(text); i++) {
        frequencies[(int)text[i]]++;
    }
    // 将每个字符及其频率作为一个节点
    Node* forest[256] = { NULL };
    int count = 0;
    for (int i = 0; i < 256; i++) {
        if (frequencies[i] > 0) {
            Node* node = (Node*)malloc(sizeof(Node));
            node->symbol = (char)i;
            node->frequency = frequencies[i];
            node->left = NULL;
            node->right = NULL;
            forest[count++] = node;
        }
    }
    // 构造哈夫曼树
    while (count > 1) {
        // 将森林中的节点按照频率从小到大排序
        for (int i = 0; i < count - 1; i++) {
            for (int j = i + 1; j < count; j++) {
                if (forest[i]->frequency > forest[j]->frequency) {
                    Node* temp = forest[i];
                    forest[i] = forest[j];
                    forest[j] = temp;
                }
            }
        }
        // 取出频率最小的两个节点，合并成一个新节点
        Node* node = (Node*)malloc(sizeof(Node));
        node->symbol = '\0';
        node->frequency = forest[0]->frequency + forest[1]->frequency;
        node->left = forest[0];
        node->right = forest[1];
        // 将新节点插入森林中
        forest[0] = node;
        count--;
        for (int i = 1; i < count; i++) {
            forest[i] = forest[i + 1];
        }
    }
    return forest[0];
}

void encode(Node* node, char* code, int depth, char** table) {
    if (node == NULL) {
        return;
    }
    if (node->symbol != '\0') {
        // 叶子节点，存储编码
        code[depth] = '\0';
        table[(int)node->symbol] = (char*)malloc(strlen(code) + 1);
        strcpy(table[(int)node->symbol], code);
    } else {
        // 非叶子节点，继续遍历
        code[depth] = '0';
        encode(node->left, code, depth + 1, table);
        code[depth] = '1';
        encode(node->right, code, depth + 1, table);
    }
}

char** buildEncodingTable(Node* root) {
    char** table = (char**)malloc(256 * sizeof(char*));
    char code[256];
    encode(root, code, 0, table);
    return table;
}

char decode(Node* node, char* code, int index) {
    if (node == NULL) {
        return '\0';
    }
    if (node->symbol != '\0') {
        // 叶子节点，返回字符
        return node->symbol;
    } else {
        // 非叶子节点，继续遍历
        if (code[index] == '0') {
            return decode(node->left, code, index + 1);
        } else {
            return decode(node->right, code, index + 1);
        }
    }
}

char* decodeString(Node* root, char* code) {
    char* result = (char*)malloc(strlen(code) + 1);
    int index = 0;
    for (int i = 0; i < strlen(code);) {
        char c = decode(root, code, i);
        if (c != '\0') {
            result[index++] = c;
        }
        i += strlen(encodingTable[(int)c]);
    }
    result[index] = '\0';
    return result;
}

int main() {
    char* text = "This is a test string.";
    Node* root = buildHuffmanTree(text);
    char** encodingTable = buildEncodingTable(root);
    char* encodedString = malloc(strlen(text) * 8 + 1);
    int index = 0;
    for (int i = 0; i < strlen(text); i++) {
        strcpy(encodedString + index, encodingTable[(int)text[i]]);
        index += strlen(encodingTable[(int)text[i]]);
    }
    encodedString[index] = '\0';
    printf("Encoded string: %s\n", encodedString);
    char* decodedString = decodeString(root, encodedString);
    printf("Decoded string: %s\n", decodedString);
    return 0;
}
C语言实现哈夫曼树编码解码：简洁代码和详细注释

原文地址: http://www.cveoy.top/t/topic/lOer 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录