基于哈夫曼树的数据压缩算法c语言

哈夫曼树是一种常用的数据压缩算法，其基本原理是将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，这样可以有效地减少数据的存储空间。

以下是基于哈夫曼树的数据压缩算法的C语言实现：

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

// 定义哈夫曼树节点结构体
typedef struct node {
    int freq;  // 字符频率
    char data; // 字符数据
    struct node *left, *right;
} node;

// 定义哈夫曼编码结构体
typedef struct code {
    char data;  // 字符数据
    char *code; // 字符编码
} code;

// 求取字符在字符串中出现的次数
void get_freq(char *str, int *freq) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        freq[str[i]]++;
    }
}

// 创建哈夫曼树
node *create_huffman_tree(int *freq) {
    node *root = NULL, *left = NULL, *right = NULL;
    node **nodes = (node **)malloc(sizeof(node *) * 256);
    for (int i = 0; i < 256; i++) {
        if (freq[i] != 0) {
            nodes[i] = (node *)malloc(sizeof(node));
            nodes[i]->data = i;
            nodes[i]->freq = freq[i];
            nodes[i]->left = NULL;
            nodes[i]->right = NULL;
        } else {
            nodes[i] = NULL;
        }
    }

    while (1) {
        int min1 = 256, min2 = 256;
        for (int i = 0; i < 256; i++) {
            if (nodes[i] != NULL) {
                if (nodes[i]->freq < nodes[min1]->freq) {
                    min2 = min1;
                    min1 = i;
                } else if (nodes[i]->freq < nodes[min2]->freq) {
                    min2 = i;
                }
            }
        }

        if (min2 == 256) {
            root = nodes[min1];
            break;
        }

        left = nodes[min1];
        right = nodes[min2];
        nodes[min1] = (node *)malloc(sizeof(node));
        nodes[min1]->freq = left->freq + right->freq;
        nodes[min1]->data = 0;
        nodes[min1]->left = left;
        nodes[min1]->right = right;
        nodes[min2] = NULL;
    }

    free(nodes);
    return root;
}

// 递归求取哈夫曼编码
void get_huffman_code(node *root, char *code, int depth, code *codes, int *idx) {
    if (root != NULL) {
        if (root->left == NULL && root->right == NULL) {
            codes[*idx].data = root->data;
            codes[*idx].code = (char *)malloc(sizeof(char) * (depth + 1));
            strcpy(codes[*idx].code, code);
            (*idx)++;
        } else {
            code[depth] = '0';
            code[depth + 1] = '\0';
            get_huffman_code(root->left, code, depth + 1, codes, idx);
            code[depth] = '1';
            code[depth + 1] = '\0';
            get_huffman_code(root->right, code, depth + 1, codes, idx);
        }
    }
}

// 哈夫曼编码压缩
void huffman_encode(char *str, char *encoded_str, code *codes) {
    int len = strlen(str), idx = 0;
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < 256; j++) {
            if (codes[j].data == str[i]) {
                strcat(encoded_str, codes[j].code);
                idx += strlen(codes[j].code);
                break;
            }
        }
    }
}

// 哈夫曼解码
void huffman_decode(char *encoded_str, char *decoded_str, node *root) {
    int len = strlen(encoded_str), idx = 0;
    node *p = root;
    while (idx < len) {
        if (encoded_str[idx] == '0') {
            p = p->left;
        } else {
            p = p->right;
        }
        if (p->left == NULL && p->right == NULL) {
            decoded_str[strlen(decoded_str)] = p->data;
            p = root;
        }
        idx++;
    }
}

int main() {
    char str[1000], encoded_str[100000], decoded_str[1000];
    int freq[256] = {0};
    code codes[256];
    node *root = NULL;

    printf("请输入字符串：");
    scanf("%s", str);

    // 计算字符出现频率
    get_freq(str, freq);

    // 创建哈夫曼树
    root = create_huffman_tree(freq);

    // 递归求取哈夫曼编码
    char code[256] = {'\0'};
    int idx = 0;
    get_huffman_code(root, code, 0, codes, &idx);

    // 哈夫曼编码压缩
    huffman_encode(str, encoded_str, codes);
    printf("压缩后的字符串：%s\n", encoded_str);

    // 哈夫曼解码
    huffman_decode(encoded_str, decoded_str, root);
    printf("解压后的字符串：%s\n", decoded_str);

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

该程序首先输入需要压缩的字符串，然后计算字符出现频率，创建哈夫曼树，求取哈夫曼编码，对字符串进行压缩和解压缩，并输出压缩后的字符串和解压后的字符串。

注意，该程序中使用了动态内存分配，需要注意释放内存以避免内存泄漏。