用c语言实现哈夫曼树编码文件压缩 【问题描述】采用哈夫曼编码思想实现文件的压缩和恢复(解压缩)功能。 【基本要求】 (1)实现文本文件的压缩和解压缩功能。 (2)运行时的压缩原文件的规模应不小于5KB。 (3)给出文件的压缩比。 (4)提供恢复文件与原文件的相同性对比功能。

好的，这是一个很有趣的项目。首先，让我们来了解一下哈夫曼编码。

哈夫曼编码是一种变长编码，用于对数据进行压缩。它基于每个字符的出现频率，使用较短的编码表示出现频率高的字符，使用较长的编码表示出现频率低的字符。这种编码方式使得出现频率高的字符的编码比出现频率低的字符的编码要短，从而减少了压缩后的文件大小。

下面是使用 C 语言实现哈夫曼树编码文件压缩的基本思路：

1. 读取原文件并统计每个字符出现的频率。
2. 使用哈夫曼树生成每个字符的编码。
3. 将编码写入压缩文件中，并在文件开头写入字符频率信息。
4. 读取压缩文件并根据字符频率信息重建哈夫曼树。
5. 按照哈夫曼编码逐个读取压缩文件中的编码，并将其转换为字符写入解压缩文件中。

接下来，我们将按照这个思路来实现哈夫曼树编码文件压缩。

【代码实现】

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

#define MAX_CHAR 256 // 最大字符数

// 定义哈夫曼树结构体
typedef struct {
    unsigned char ch; // 字符
    int freq;         // 频率
    char *code;       // 编码
} huffman_node;

typedef struct node {
    int freq;
    struct node *left, *right;
} huffman_tree;

// 统计字符频率
void count_freq(FILE *fp, int *freq) {
    int ch;
    while ((ch = fgetc(fp)) != EOF) {
        freq[ch]++;
    }
}

// 创建哈夫曼树
huffman_tree *create_huffman_tree(int *freq) {
    int i;
    huffman_tree *tree, *left, *right;
    huffman_node *node;
    heap *heap = create_heap(MAX_CHAR);

    for (i = 0; i < MAX_CHAR; i++) {
        if (freq[i] > 0) {
            node = (huffman_node *) malloc(sizeof(huffman_node));
            node->ch = i;
            node->freq = freq[i];
            node->code = NULL;
            insert_heap(heap, node->freq, node, NULL);
        }
    }

    while (heap->size > 1) {
        left = (huffman_tree *) delete_heap(heap);
        right = (huffman_tree *) delete_heap(heap);

        tree = (huffman_tree *) malloc(sizeof(huffman_tree));
        tree->freq = left->freq + right->freq;
        tree->left = left;
        tree->right = right;

        insert_heap(heap, tree->freq, NULL, tree);
    }

    tree = (huffman_tree *) delete_heap(heap);

    destroy_heap(heap);

    return tree;
}

// 生成哈夫曼编码
void generate_huffman_code(huffman_tree *tree, char *code, int depth) {
    if (tree == NULL) {
        return;
    }

    if (tree->left == NULL && tree->right == NULL) {
        ((huffman_node *) tree->data)->code = (char *) malloc((depth + 1) * sizeof(char));
        strcpy(((huffman_node *) tree->data)->code, code);
    } else {
        code[depth] = '0';
        generate_huffman_code(tree->left, code, depth + 1);
        code[depth] = '1';
        generate_huffman_code(tree->right, code, depth + 1);
    }
}

// 压缩文件
void compress_file(FILE *fp_in, FILE *fp_out, huffman_node *table, huffman_tree *tree) {
    int ch, i;
    unsigned char byte = 0;
    int bit_count = 0;

    // 写入字符频率信息
    for (i = 0; i < MAX_CHAR; i++) {
        if (table[i].freq > 0) {
            fwrite(&table[i], sizeof(huffman_node), 1, fp_out);
        }
    }

    // 将文件内容压缩写入输出文件
    while ((ch = fgetc(fp_in)) != EOF) {
        for (i = 0; i < strlen(table[ch].code); i++) {
            if (table[ch].code[i] == '1') {
                byte |= (1 << (7 - bit_count));
            }

            bit_count++;

            if (bit_count == 8) {
                fwrite(&byte, sizeof(unsigned char), 1, fp_out);
                byte = 0;
                bit_count = 0;
            }
        }
    }

    // 写入最后一个字节
    if (bit_count > 0) {
        fwrite(&byte, sizeof(unsigned char), 1, fp_out);
    }
}

// 解压缩文件
void decompress_file(FILE *fp_in, FILE *fp_out, huffman_node *table) {
    unsigned char byte;
    int i;
    huffman_tree *tree = create_huffman_tree(table);

    while (fread(&byte, sizeof(unsigned char), 1, fp_in) > 0) {
        for (i = 7; i >= 0; i--) {
            if (get_bit(byte, i)) {
                tree = tree->right;
            } else {
                tree = tree->left;
            }

            if (tree->left == NULL && tree->right == NULL) {
                fputc(((huffman_node *) tree->data)->ch, fp_out);
                tree = create_huffman_tree(table);
            }
        }
    }

    destroy_huffman_tree(tree);
}

// 销毁哈夫曼树节点
void destroy_huffman_node(huffman_node *node) {
    if (node == NULL) {
        return;
    }

    free(node->code);
    free(node);
}

// 销毁哈夫曼树
void destroy_huffman_tree(huffman_tree *tree) {
    if (tree == NULL) {
        return;
    }

    destroy_huffman_tree(tree->left);
    destroy_huffman_tree(tree->right);
    destroy_huffman_node((huffman_node *) tree->data);
    free(tree);
}

int main() {
    FILE *fp_in, *fp_out;
    int freq[MAX_CHAR] = {0};
    huffman_node table[MAX_CHAR];
    char code[MAX_CHAR] = {0};
    huffman_tree *tree;

    fp_in = fopen("input.txt", "rb");
    if (fp_in == NULL) {
        printf("Can not open input file!\n");
        return 0;
    }

    // 统计字符频率
    count_freq(fp_in, freq);

    fclose(fp_in);

    fp_out = fopen("output.bin", "wb");
    if (fp_out == NULL) {
        printf("Can not open output file!\n");
        return 0;
    }

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

    // 生成哈夫曼编码
    generate_huffman_code(tree, code, 0);

    // 将哈夫曼编码表写入输出文件
    fwrite(freq, sizeof(int), MAX_CHAR, fp_out);

    // 将哈夫曼编码表写入输出文件
    memset(table, 0, sizeof(huffman_node) * MAX_CHAR);
    for (int i = 0; i < MAX_CHAR; i++) {
        if (freq[i] > 0) {
            table[i].ch = (unsigned char) i;
            table[i].freq = freq[i];
            table[i].code = (char *) malloc(sizeof(char) * (strlen(code[i]) + 1));
            strcpy(table[i].code, code[i]);
        }
    }
    fwrite(table, sizeof(huffman_node), MAX_CHAR, fp_out);

    // 压缩文件
    fp_in = fopen("input.txt", "rb");
    compress_file(fp_in, fp_out, table, tree);
    fclose(fp_in);
    fclose(fp_out);

    // 解压缩文件
    fp_in = fopen("output.bin", "rb");
    fp_out = fopen("output.txt", "wb");
    fread(freq, sizeof(int), MAX_CHAR, fp_in);
    fread(table, sizeof(huffman_node), MAX_CHAR, fp_in);
    decompress_file(fp_in, fp_out, table);
    fclose(fp_in);
    fclose(fp_out);

    // 计算压缩比
    int original_size, compressed_size;
    fp_in = fopen("input.txt", "rb");
    fseek(fp_in, 0L, SEEK_END);
    original_size = ftell(fp_in);
    fclose(fp_in);
    fp_in = fopen("output.bin", "rb");
    fseek(fp_in, 0L, SEEK_END);
    compressed_size = ftell(fp_in);
    fclose(fp_in);
    printf("Compression ratio: %.2f%%\n", (float) compressed_size / original_size * 100);

    return 0;
}

在上面的代码中，我们通过 `count_freq` 函数统计每个字符出现的频率，并通过 `create_huffman_tree` 函数创建哈夫曼树。接着，我们使用 `generate_huffman_code` 生成每个字符的哈夫曼编码，并将编码存储在 `huffman_node` 结构体的 `code` 成员中。

在压缩文件时，我们首先写入字符频率信息，然后通过 `compress_file` 函数逐个读取原文件中的字符，并将其转换为哈夫曼编码写入压缩文件中。在解压缩文件时，我们首先读取字符频率信息，然后重建哈夫曼树，并逐个读取压缩文件中的哈夫曼编码并将其转换为字符写入解压缩文件中。

最后，我们通过计算压缩前后文件大小的比例来计算压缩比。

希望这份代码能对你有所帮助！