用c语言写一个程序哈夫曼编码应用--文本压缩

以下是一个简单的示例程序，用C语言实现哈夫曼编码的文本压缩和解压缩。

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

#define MAX_CHARACTERS 256
#define MAX_BIT_LENGTH 1000

// 哈夫曼树节点结构体
typedef struct huffman_node {
    char character;  // 字符
    int frequency;   // 频率
    struct huffman_node *left;  // 左子节点
    struct huffman_node *right; // 右子节点
} huffman_node_t;

// 哈夫曼编码结构体
typedef struct huffman_code {
    char character;  // 字符
    char code[MAX_BIT_LENGTH];  // 编码
} huffman_code_t;

// 统计文本中每个字符出现的频率
void count_frequencies(char *text, int *frequencies) {
    int i;
    for (i = 0; i < strlen(text); i++) {
        frequencies[(int)text[i]]++;
    }
}

// 创建哈夫曼树节点
huffman_node_t *create_node(char character, int frequency) {
    huffman_node_t *node = (huffman_node_t*)malloc(sizeof(huffman_node_t));
    node->character = character;
    node->frequency = frequency;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建哈夫曼树
huffman_node_t *create_huffman_tree(int *frequencies) {
    int i;
    huffman_node_t *nodes[MAX_CHARACTERS];
    int num_nodes = 0;

    // 创建根节点
    huffman_node_t *root = NULL;

    // 创建叶子节点
    for (i = 0; i < MAX_CHARACTERS; i++) {
        if (frequencies[i] > 0) {
            nodes[num_nodes++] = create_node((char)i, frequencies[i]);
        }
    }

    // 构建哈夫曼树
    while (num_nodes > 1) {
        // 找到权值最小的两个节点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->frequency > nodes[min2]->frequency) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }
        for (i = 2; i < num_nodes; i++) {
            if (nodes[i]->frequency < nodes[min1]->frequency) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->frequency < nodes[min2]->frequency) {
                min2 = i;
            }
        }

        // 创建新节点
        huffman_node_t *new_node = create_node('\0', nodes[min1]->frequency + nodes[min2]->frequency);
        new_node->left = nodes[min1];
        new_node->right = nodes[min2];

        // 从节点列表中删除已合并的节点
        if (min1 < min2) {
            nodes[min1] = new_node;
            nodes[min2] = nodes[num_nodes-1];
        } else {
            nodes[min2] = new_node;
            nodes[min1] = nodes[num_nodes-1];
        }
        num_nodes--;
    }

    if (num_nodes > 0) {
        root = nodes[0];
    }

    return root;
}

// 生成哈夫曼编码
void generate_codes(huffman_node_t *node, char *prefix, int prefix_length, huffman_code_t *codes) {
    if (node == NULL) {
        return;
    }

    // 如果是叶子节点，则记录编码
    if (node->left == NULL && node->right == NULL) {
        codes[(int)node->character].character = node->character;
        memcpy(codes[(int)node->character].code, prefix, prefix_length);
        codes[(int)node->character].code[prefix_length] = '\0';
        return;
    }

    // 递归生成编码
    prefix[prefix_length] = '0';
    generate_codes(node->left, prefix, prefix_length + 1, codes);
    prefix[prefix_length] = '1';
    generate_codes(node->right, prefix, prefix_length + 1, codes);
}

// 压缩文本
void compress(char *text, huffman_code_t *codes, char *output) {
    int i;
    char buffer[MAX_BIT_LENGTH];
    int buffer_length = 0;

    // 将编码连接起来形成一个压缩后的二进制串
    for (i = 0; i < strlen(text); i++) {
        strcat(buffer, codes[(int)text[i]].code);
        buffer_length += strlen(codes[(int)text[i]].code);
    }

    // 将二进制串转换为字节流
    int num_bytes = (buffer_length + 7) / 8;
    for (i = 0; i < num_bytes; i++) {
        int byte = 0;
        int j;
        for (j = 0; j < 8; j++) {
            if (i * 8 + j < buffer_length) {
                byte = byte * 2 + (buffer[i * 8 + j] - '0');
            } else {
                byte *= 2;
            }
        }
        output[i] = (char)byte;
    }
    output[num_bytes] = '\0';
}

// 解压缩文本
void decompress(char *input, huffman_node_t *root, char *output) {
    int i;
    huffman_node_t *current = root;

    // 将字节流转换为二进制串
    char buffer[MAX_BIT_LENGTH];
    int buffer_length = 0;
    for (i = 0; i < strlen(input); i++) {
        int byte = (int)input[i];
        int j;
        for (j = 7; j >= 0; j--) {
            if (byte >= (1 << j)) {
                buffer[buffer_length++] = '1';
                byte -= (1 << j);
            } else {
                buffer[buffer_length++] = '0';
            }
        }
    }

    // 根据哈夫曼树解码二进制串
    int output_length = 0;
    for (i = 0; i < buffer_length; i++) {
        if (buffer[i] == '0') {
            current = current->left;
        } else {
            current = current->right;
        }
        if (current->left == NULL && current->right == NULL) {
            output[output_length++] = current->character;
            current = root;
        }
    }
    output[output_length] = '\0';
}

int main() {
    char text[] = "hello world";
    int frequencies[MAX_CHARACTERS] = {0};
    count_frequencies(text, frequencies);

    huffman_node_t *root = create_huffman_tree(frequencies);

    char prefix[MAX_BIT_LENGTH];
    huffman_code_t codes[MAX_CHARACTERS] = {{0}};
    generate_codes(root, prefix, 0, codes);

    char compressed[MAX_BIT_LENGTH];
    compress(text, codes, compressed);

    char decompressed[MAX_BIT_LENGTH];
    decompress(compressed, root, decompressed);

    printf("Original text: %s\n", text);
    printf("Compressed text: %s\n", compressed);
    printf("Decompressed text: %s\n", decompressed);

    return 0;
}

在这个示例程序中，我们先统计文本中每个字符出现的频率，然后构建哈夫曼树，并生成每个字符对应的哈夫曼编码。接着，将文本中的每个字符替换为其对应的哈夫曼编码，并将所有编码连接起来形成一个压缩后的二进制串，再将二进制串转换为字节流，最终写入文件。在解压缩时，读取保存的哈夫曼树结构，并使用该树对压缩后的二进制串进行解码，还原出原始文本。