数据结构 用c语言对任意一个文件的内容实现哈夫曼编码解码程序

哈夫曼编码是一种用于数据压缩的编码方式，它基于字符出现的频率来构建一棵二叉树，并且使得出现频率高的字符用较短的编码来表示，出现频率低的字符用较长的编码来表示。

在C语言中，我们可以通过以下步骤来实现哈夫曼编码解码程序：

1. 定义一个结构体，在结构体中包含字符和对应的频率，以及左右子树的指针。
2. 统计待编码文件中每个字符出现的频率，并根据频率构建哈夫曼树。这可以通过使用一个优先队列来实现。优先队列中的每个元素都是一个结构体对象，按照频率的升序排列。
3. 构建完哈夫曼树后，通过遍历哈夫曼树的方式，生成每个字符对应的哈夫曼编码。对于每个字符，从根节点开始，若走左子树则编码添加0，若走右子树则编码添加1，直到达到叶子节点为止。将生成的编码保存到一个哈希表中，以便后续的解码使用。
4. 遍历待编码文件的每个字符，根据哈希表中对应的哈夫曼编码，将字符转换成一串二进制；
5. 将二进制转换为字符，并输出到解码后的文件中，即完成了哈夫曼编码解码的过程。

值得注意的是，为了确保哈夫曼编码的正确性，需要在编码和解码过程中使用相同的哈夫曼树。因此，在解码过程中需要重建一棵与编码过程中相同的哈夫曼树。

通过以上步骤，我们可以使用C语言对任意一个文件的内容实现哈夫曼编码解码程序。

相关问题

c语言写一个对txt文件进行哈夫曼编码并将编码存储在txt文件中的程序

好的，根据您的要求，我可以为您提供一份C语言的哈夫曼编码程序。首先，我们需要创建一个函数来生成huffman编码树：

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

#define END_OF_TEXT '\0'
#define MAX_INPUT_SIZE 1024*1024
#define MAX_NODES 256
#define MAX_CODE_LENGTH 256

struct huff_tree {
    int frequency;
    unsigned char symbol;
    struct huff_tree *left;
    struct huff_tree *right;
};

struct huff_code_table {
    char code[MAX_CODE_LENGTH];
    int length;
};

void calculate_frequencies(unsigned int *frequencies, unsigned char *input_text);
void create_huff_tree(struct huff_tree **root, unsigned int *frequencies);
void create_code_table(struct huff_tree *root, struct huff_code_table *code_table, unsigned char *current_code, int code_length);
void free_huff_tree(struct huff_tree *node);

int main(int argc, char **argv) {
    // Check command line arguments
    if (argc < 3) {
        printf("Usage: %s input_file output_file\n", argv[0]);
        return 1;
    }

    // Open input and output files
    FILE *input_file = fopen(argv[1], "rb");
    if (input_file == NULL) {
        printf("Error: Unable to open input file\n");
        return 1;
    }
    FILE *output_file = fopen(argv[2], "wb");
    if (output_file == NULL) {
        printf("Error: Unable to open output file\n");
        fclose(input_file);
        return 1;
    }

    // Read input file into memory
    unsigned char *input_text = (unsigned char *)malloc(MAX_INPUT_SIZE);
    if (input_text == NULL) {
        printf("Error: Unable to allocate memory for input text\n");
        fclose(input_file);
        fclose(output_file);
        return 1;
    }
    int input_size = fread(input_text, sizeof(unsigned char), MAX_INPUT_SIZE, input_file);
    if (input_size == 0) {
        printf("Error: Unable to read input file\n");
        free(input_text);
        fclose(input_file);
        fclose(output_file);
        return 1;
    }

    // Calculate symbol frequencies
    unsigned int frequencies[MAX_NODES];
    memset(frequencies, 0, sizeof(frequencies));
    calculate_frequencies(frequencies, input_text);

    // Create Huffman tree
    struct huff_tree *root = NULL;
    create_huff_tree(&root, frequencies);

    // Create code table from Huffman tree
    struct huff_code_table code_table[MAX_NODES];
    memset(code_table, 0, sizeof(code_table));
    unsigned char current_code[MAX_CODE_LENGTH];
    create_code_table(root, code_table, current_code, 0);

    // Write Huffman tree to output file
    fwrite(&input_size, sizeof(int), 1, output_file); // write input size to output file
    unsigned char symbol;
    int frequency;
    for (int i = 0; i < MAX_NODES; i++) {
        symbol = (unsigned char)i;
        frequency = frequencies[i];
        fwrite(&symbol, sizeof(unsigned char), 1, output_file);
        fwrite(&frequency, sizeof(int), 1, output_file);
    }

    // Encode input text using code table
    int bit_index = 0;
    unsigned char current_byte = 0;
    for (int i = 0; i < input_size; i++) {
        for (int j = 0; j < code_table[input_text[i]].length; j++) {
            if (code_table[input_text[i]].code[j] == '1') {
                current_byte |= (1 << (7 - bit_index));
            }
            bit_index++;
            if (bit_index == 8) {
                fwrite(&current_byte, sizeof(unsigned char), 1, output_file);
                current_byte = 0;
                bit_index = 0;
            }
        }
    }
    if (bit_index != 0) {
        fwrite(&current_byte, sizeof(unsigned char), 1, output_file);
    }

    // Cleanup memory and files
    fclose(input_file);
    fclose(output_file);
    free(input_text);
    free_huff_tree(root);

    return 0;
}

void calculate_frequencies(unsigned int *frequencies, unsigned char *input_text) {
    int i = 0;
    while (input_text[i] != END_OF_TEXT && i < MAX_INPUT_SIZE) {
        frequencies[input_text[i]]++;
        i++;
    }
}

void create_huff_tree(struct huff_tree **root, unsigned int *frequencies) {
    struct huff_tree *nodes[MAX_NODES];
    int node_count = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        if (frequencies[i] > 0) {
            struct huff_tree *node = (struct huff_tree *)malloc(sizeof(struct huff_tree));
            node->frequency = frequencies[i];
            node->symbol = (unsigned char)i;
            node->left = NULL;
            node->right = NULL;
            nodes[node_count++] = node;
        }
    }
    while (node_count > 1) {
        // Find nodes with lowest frequencies
        int lowest1, lowest2;
        lowest1 = lowest2 = -1;
        for (int i = 0; i < node_count; i++) {
            if (lowest1 == -1 || nodes[i]->frequency < nodes[lowest1]->frequency) {
                lowest2 = lowest1;
                lowest1 = i;
            } else if (lowest2 == -1 || nodes[i]->frequency < nodes[lowest2]->frequency) {
                lowest2 = i;
            }
        }
        // Create new node from lowest frequency nodes
        struct huff_tree *new_node = (struct huff_tree *)malloc(sizeof(struct huff_tree));
        new_node->frequency = nodes[lowest1]->frequency + nodes[lowest2]->frequency;
        new_node->left = nodes[lowest1];
        new_node->right = nodes[lowest2];
        nodes[lowest1] = new_node;
        nodes[lowest2] = nodes[--node_count];
    }
    *root = nodes[0];
}

void create_code_table(struct huff_tree *node, struct huff_code_table *code_table, unsigned char *current_code, int code_length) {
    if (node->left == NULL && node->right == NULL) {
        code_table[node->symbol].length = code_length;
        strcpy(code_table[node->symbol].code, (const char *)current_code);
        return;
    }
    if (node->left != NULL) {
        current_code[code_length] = '0';
        create_code_table(node->left, code_table, current_code, code_length + 1);
    }
    if (node->right != NULL) {
        current_code[code_length] = '1';
        create_code_table(node->right, code_table, current_code, code_length + 1);
    }
}

void free_huff_tree(struct huff_tree *node) {
    if (node == NULL) {
        return;
    }
    free_huff_tree(node->left);
    free_huff_tree(node->right);
    free(node);
}

本程序通过 `calculate_frequencies()` 函数计算输入文本中每个字符出现的频率。接下来，它使用 `create_huff_tree()` 函数生成哈夫曼树，再使用 `create_code_table()` 函数生成每个字符的哈夫曼编码。最后，它根据编码表对输入文本进行编码，并将哈夫曼编码和树信息写入输出文件中。

此程序依赖以下内容：

- `END_OF_TEXT`：文本的结束符。
- `MAX_INPUT_SIZE`：可能的最大输入文本大小。
- `MAX_NODES`：哈夫曼树中的最大节点数。
- `MAX_CODE_LENGTH`：可能的最大哈夫曼编码长度。

请注意，此代码可能需要根据您的实际需求进行微调和优化。

用c语言写一个哈夫曼编码实现文件压缩与解压

哈夫曼编码是一种无损压缩算法，可以将输入的数据流进行压缩，减小数据存储空间，提高数据传输效率。以下是使用 C 语言实现哈夫曼编码的程序，包括文件压缩和解压两个部分。

#### 哈夫曼编码压缩

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

#define MAX_NODES 256

typedef struct {
    unsigned char ch;
    int freq;
} Node;

typedef struct {
    int left_child;
    int right_child;
    int parent;
    int weight;
} HuffmanNode;

void count_frequency(char *filename, int *freq) {
    FILE *fp;
    unsigned char ch;
    if ((fp = fopen(filename, "rb")) == NULL) {
        printf("Cannot open file %s\n", filename);
        return;
    }
    while (fread(&ch, sizeof(unsigned char), 1, fp) == 1) {
        freq[ch]++;
    }
    fclose(fp);
}

int select_min(HuffmanNode *huffman_tree, int n, int *min1, int *min2) {
    int i, cnt = 0;
    for (i = 0; i < n; i++) {
        if (huffman_tree[i].parent == -1) cnt++;
    }
    if (cnt < 2) return 0;
    *min1 = -1, *min2 = -1;
    for (i = 0; i < n; i++) {
        if (huffman_tree[i].parent == -1) {
            if (*min1 == -1 || huffman_tree[i].weight < huffman_tree[*min1].weight) {
                *min2 = *min1;
                *min1 = i;
            } else if (*min2 == -1 || huffman_tree[i].weight < huffman_tree[*min2].weight) {
                *min2 = i;
            }
        }
    }
    return 1;
}

int build_huffman_tree(int *freq, int n, HuffmanNode *huffman_tree) {
    int i, j, min1, min2;
    for (i = 0; i < n; i++) {
        huffman_tree[i].left_child = -1;
        huffman_tree[i].right_child = -1;
        huffman_tree[i].parent = -1;
        huffman_tree[i].weight = freq[i];
    }
    for (i = n; i < 2 * n - 1; i++) {
        if (select_min(huffman_tree, i, &min1, &min2) == 0) break;
        huffman_tree[min1].parent = i;
        huffman_tree[min2].parent = i;
        huffman_tree[i].left_child = min1;
        huffman_tree[i].right_child = min2;
        huffman_tree[i].weight = huffman_tree[min1].weight + huffman_tree[min2].weight;
    }
    return i;
}

int encode(char *filename, char *filename_out, HuffmanNode *huffman_tree, int n) {
    FILE *fp_in, *fp_out;
    unsigned char ch, byte = 0;
    int i, bit_cnt = 0;
    if ((fp_in = fopen(filename, "rb")) == NULL) {
        printf("Cannot open file %s\n", filename);
        return 0;
    }
    if ((fp_out = fopen(filename_out, "wb")) == NULL) {
        printf("Cannot open file %s\n", filename_out);
        return 0;
    }
    while (fread(&ch, sizeof(unsigned char), 1, fp_in) == 1) {
        i = n - 1;
        while (i >= 0) {
            if (huffman_tree[i].left_child != -1 && huffman_tree[huffman_tree[i].left_child].weight <= bit_cnt) {
                byte |= (1 << (7 - bit_cnt));
                i = huffman_tree[i].left_child;
                bit_cnt++;
            } else if (huffman_tree[i].right_child != -1 && huffman_tree[huffman_tree[i].right_child].weight <= bit_cnt) {
                i = huffman_tree[i].right_child;
                bit_cnt++;
            } else {
                break;
            }
            if (bit_cnt == 8) {
                fwrite(&byte, sizeof(unsigned char), 1, fp_out);
                byte = 0;
                bit_cnt = 0;
            }
        }
    }
    if (bit_cnt > 0) {
        fwrite(&byte, sizeof(unsigned char), 1, fp_out);
    }
    fclose(fp_in);
    fclose(fp_out);
    return 1;
}

int decode(char *filename_out, char *filename, HuffmanNode *huffman_tree, int root, int size) {
    FILE *fp_in, *fp_out;
    unsigned char ch, byte = 0;
    int i, bit_cnt = 0, node = root;
    if ((fp_in = fopen(filename_out, "rb")) == NULL) {
        printf("Cannot open file %s\n", filename_out);
        return 0;
    }
    if ((fp_out = fopen(filename, "wb")) == NULL) {
        printf("Cannot open file %s\n", filename);
        return 0;
    }
    while (fread(&ch, sizeof(unsigned char), 1, fp_in) == 1) {
        for (i = 0; i < 8; i++) {
            if (ch & (1 << (7 - i))) {
                node = huffman_tree[node].left_child;
            } else {
                node = huffman_tree[node].right_child;
            }
            if (node < size && node >= 0) {
                fwrite(&huffman_tree[node].weight, sizeof(unsigned char), 1, fp_out);
                node = root;
            }
        }
    }
    fclose(fp_in);
    fclose(fp_out);
    return 1;
}

int main(int argc, char *argv[]) {
    if (argc != 4) {
        printf("Usage: %s [-c/-d] input_file output_file\n", argv[0]);
        return 0;
    }
    if (strcmp(argv[1], "-c") == 0) {
        int freq[MAX_NODES] = {0};
        count_frequency(argv[2], freq);
        HuffmanNode huffman_tree[2 * MAX_NODES - 1];
        int root = build_huffman_tree(freq, MAX_NODES, huffman_tree);
        encode(argv[2], argv[3], huffman_tree, root);
    } else if (strcmp(argv[1], "-d") == 0) {
        int freq[MAX_NODES] = {0};
        count_frequency(argv[3], freq);
        HuffmanNode huffman_tree[2 * MAX_NODES - 1];
        int root = build_huffman_tree(freq, MAX_NODES, huffman_tree);
        decode(argv[2], argv[3], huffman_tree, root, MAX_NODES);
    } else {
        printf("Usage: %s [-c/-d] input_file output_file\n", argv[0]);
        return 0;
    }
    return 0;
}

程序中首先定义了两个结构体 `Node` 和 `HuffmanNode`，分别用于存储字符频率和哈夫曼树节点信息。在 `count_frequency` 函数中，程序读入输入文件中的每个字符，并统计每个字符出现的频率，存储在 `freq` 数组中。接着，在 `build_huffman_tree` 函数中，程序构建哈夫曼树，并返回根节点的位置。在构建哈夫曼树的过程中，程序使用了 `select_min` 函数来选择权值最小的两个节点进行合并。最后，在 `encode` 函数中，程序读入输入文件中的每个字符，并使用哈夫曼树进行编码，并将编码后的结果输出到输出文件中。

#### 哈夫曼编码解压

在解压过程中，程序使用 `decode` 函数来读入输入文件中的每个编码，并使用哈夫曼树进行解码，并将解码后的结果输出到输出文件中。需要注意的是，在解码过程中，程序需要记录当前所在的哈夫曼树节点位置，以便进行下一位的解码。

以上是使用 C 语言实现的哈夫曼编码程序，包括文件压缩和解压两个部分。