哈夫曼编码压缩与解压

哈夫曼编码是一种常用的数据压缩算法，它通过对出现频率较高的字符赋予较短的编码，从而实现对数据的高效压缩。下面是哈夫曼编码压缩与解压的介绍：

1. 哈夫曼编码压缩：
- 统计待压缩数据中各个字符的出现频率。
- 根据字符频率构建哈夫曼树，频率越高的字符离根节点越近。
- 通过遍历哈夫曼树，给每个字符赋予唯一的二进制编码，频率高的字符编码较短，频率低的字符编码较长。
- 将原始数据中的每个字符替换为对应的哈夫曼编码。
- 将替换后的二进制数据存储起来。

2. 哈夫曼解压：
- 根据压缩文件中存储的哈夫曼编码和对应字符的映射关系，重建哈夫曼树。
- 读取压缩文件中的二进制数据，根据哈夫曼树进行解码，将二进制数据转换为原始字符。
- 将解码后的字符按顺序还原为原始数据。

相关问题

哈夫曼编码文件压缩与解压

好的，我可以为您讲解哈夫曼编码文件压缩与解压。

哈夫曼编码是一种可变长度编码方式，它通过统计字符出现频率来构建一个最优二叉树结构，将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示，从而达到压缩文件的目的。

文件压缩的过程就是将文件中的字符通过哈夫曼编码转换为对应的二进制码，从而减少文件的大小。而解压过程则是将二进制码转化为哈夫曼编码所代表的字符，还原原始文件。

在实际应用中，哈夫曼编码常被用于压缩文本文件、音频文件、图片文件等等。通过哈夫曼编码压缩文件，可以节省存储空间并提高传输效率。

需要注意的是，压缩率取决于原始文件的特性，如果文件中的字符种类较少，压缩效果就不会很明显。同时，压缩和解压的过程也会消耗一定的时间和计算资源。

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

好的，我可以为您提供哈夫曼编码文件压缩与解压的C语言实现的代码，以下是压缩部分的示例代码：

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

// 哈夫曼树节点结构体定义
typedef struct HuffmanNode {
    unsigned char data; // 字符数据
    int freq; // 字符出现频率
    struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;

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

// 哈夫曼树节点优先队列结构体定义
typedef struct PriorityQueue {
    int size; // 队列大小
    int capacity; // 队列容量
    HuffmanNode **nodes; // 指向哈夫曼树节点的指针数组
} PriorityQueue;

// 创建新的哈夫曼树节点
HuffmanNode *newHuffmanNode(unsigned char data, int freq) {
    HuffmanNode *node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
    node->data = data;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

// 创建新的哈夫曼编码结构体
HuffmanCode newHuffmanCode(unsigned char data, char *code) {
    HuffmanCode hc;
    hc.data = data;
    hc.code = code;
    return hc;
}

// 创建新的哈夫曼树节点优先队列
PriorityQueue *newPriorityQueue(int capacity) {
    PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->nodes = (HuffmanNode **)malloc(capacity * sizeof(HuffmanNode *));
    return pq;
}

// 释放哈夫曼编码结构体内存
void freeHuffmanCode(HuffmanCode hc) {
    free(hc.code);
}

// 释放哈夫曼树节点内存
void freeHuffmanNode(HuffmanNode *node) {
    if (node != NULL) {
        freeHuffmanNode(node->left);
        freeHuffmanNode(node->right);
        free(node);
    }
}

// 释放哈夫曼树节点优先队列内存
void freePriorityQueue(PriorityQueue *pq) {
    for (int i = 0; i < pq->size; i++) {
        freeHuffmanNode(pq->nodes[i]);
    }
    free(pq->nodes);
    free(pq);
}

// 判断优先队列是否为空
int isPriorityQueueEmpty(PriorityQueue *pq) {
    return pq->size == 0;
}

// 判断优先队列是否已满
int isPriorityQueueFull(PriorityQueue *pq) {
    return pq->size == pq->capacity;
}

// 向优先队列中插入哈夫曼树节点
void insertIntoPriorityQueue(PriorityQueue *pq, HuffmanNode *node) {
    int i = pq->size;
    while (i > 0 && pq->nodes[(i - 1) / 2]->freq > node->freq) {
        pq->nodes[i] = pq->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    pq->nodes[i] = node;
    pq->size++;
}

// 从优先队列中删除哈夫曼树节点
HuffmanNode *removeFromPriorityQueue(PriorityQueue *pq) {
    HuffmanNode *minNode = pq->nodes[0];
    pq->size--;
    pq->nodes[0] = pq->nodes[pq->size];
    int i = 0;
    while (i * 2 + 1 < pq->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int min = left;
        if (right < pq->size && pq->nodes[right]->freq < pq->nodes[left]->freq) {
            min = right;
        }
        if (pq->nodes[i]->freq > pq->nodes[min]->freq) {
            HuffmanNode *temp = pq->nodes[i];
            pq->nodes[i] = pq->nodes[min];
            pq->nodes[min] = temp;
            i = min;
        } else {
            break;
        }
    }
    return minNode;
}

// 构建哈夫曼树
HuffmanNode *buildHuffmanTree(unsigned char *data, int *freq, int size) {
    PriorityQueue *pq = newPriorityQueue(size);
    for (int i = 0; i < size; i++) {
        HuffmanNode *node = newHuffmanNode(data[i], freq[i]);
        insertIntoPriorityQueue(pq, node);
    }
    while (pq->size > 1) {
        HuffmanNode *left = removeFromPriorityQueue(pq);
        HuffmanNode *right = removeFromPriorityQueue(pq);
        HuffmanNode *parent = newHuffmanNode(0, left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        insertIntoPriorityQueue(pq, parent);
    }
    HuffmanNode *root = removeFromPriorityQueue(pq);
    freePriorityQueue(pq);
    return root;
}

// 递归生成哈夫曼编码
void generateHuffmanCode(HuffmanNode *node, char *code, int depth, HuffmanCode *hcTable) {
    if (node->left == NULL && node->right == NULL) {
        code[depth] = '\0';
        hcTable[node->data] = newHuffmanCode(node->data, strdup(code));
        return;
    }
    code[depth] = '0';
    generateHuffmanCode(node->left, code, depth + 1, hcTable);
    code[depth] = '1';
    generateHuffmanCode(node->right, code, depth + 1, hcTable);
}

// 哈夫曼编码文件压缩函数
void compressFile(const char *inputFileName, const char *outputFileName) {
    // 打开输入文件
    FILE *inputFile = fopen(inputFileName, "rb");
    if (inputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", inputFileName);
        exit(EXIT_FAILURE);
    }

    // 统计文件中每个字符出现的频率
    int freq[UCHAR_MAX + 1] = { 0 };
    unsigned char buffer[1024];
    int bytesRead;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), inputFile)) > 0) {
        for (int i = 0; i < bytesRead; i++) {
            freq[buffer[i]]++;
        }
    }

    // 构建哈夫曼树
    int dataSize = 0;
    for (int i = 0; i <= UCHAR_MAX; i++) {
        if (freq[i] > 0) {
            dataSize++;
        }
    }
    unsigned char *data = (unsigned char *)malloc(dataSize * sizeof(unsigned char));
    int *freqCopy = (int *)malloc(dataSize * sizeof(int));
    int j = 0;
    for (int i = 0; i <= UCHAR_MAX; i++) {
        if (freq[i] > 0) {
            data[j] = (unsigned char)i;
            freqCopy[j] = freq[i];
            j++;
        }
    }
    HuffmanNode *root = buildHuffmanTree(data, freqCopy, dataSize);
    free(data);
    free(freqCopy);

    // 生成哈夫曼编码
    HuffmanCode hcTable[UCHAR_MAX + 1];
    char code[CHAR_BIT + 1];
    generateHuffmanCode(root, code, 0, hcTable);

    // 重置文件指针
    fseek(inputFile, 0L, SEEK_SET);

    // 打开输出文件
    FILE *outputFile = fopen(outputFileName, "wb");
    if (outputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", outputFileName);
        exit(EXIT_FAILURE);
    }

    // 写入哈夫曼树节点数和每个字符出现的频率
    int nodeCount = dataSize * 2 - 1;
    fwrite(&nodeCount, sizeof(int), 1, outputFile);
    for (int i = 0; i <= UCHAR_MAX; i++) {
        if (hcTable[i].code != NULL) {
            fwrite(&hcTable[i].data, sizeof(unsigned char), 1, outputFile);
            fwrite(&freq[i], sizeof(int), 1, outputFile);
        }
    }

    // 逐个字符将其哈夫曼编码写入输出文件
    char bitBuffer = 0;
    int bitCount = 0;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), inputFile)) > 0) {
        for (int i = 0; i < bytesRead; i++) {
            for (int j = 0; j < strlen(hcTable[buffer[i]].code); j++) {
                if (hcTable[buffer[i]].code[j] == '1') {
                    bitBuffer |= 1 << bitCount;
                }
                bitCount++;
                if (bitCount == CHAR_BIT) {
                    fwrite(&bitBuffer, sizeof(char), 1, outputFile);
                    bitBuffer = 0;
                    bitCount = 0;
                }
            }
        }
    }
    if (bitCount > 0) {
        fwrite(&bitBuffer, sizeof(char), 1, outputFile);
    }

    // 释放内存并关闭文件
    fclose(inputFile);
    fclose(outputFile);
    freeHuffmanNode(root);
    for (int i = 0; i <= UCHAR_MAX; i++) {
        freeHuffmanCode(hcTable[i]);
    }
}

以下是解压部分的示例代码：

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

// 哈夫曼树节点结构体定义
typedef struct HuffmanNode {
    unsigned char data; // 字符数据
    int freq; // 字符出现频率
    struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;

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

// 读取哈夫曼树节点数和每个字符出现的频率
void readNodeCountAndFreq(FILE *inputFile, int *nodeCount, int *freq) {
    fread(nodeCount, sizeof(int), 1, inputFile);
    for (int i = 0; i <= UCHAR_MAX; i++) {
        freq[i] = 0;
    }
    unsigned char data;
    int f;
    for (int i = 0; i < *nodeCount; i++) {
        fread(&data, sizeof(unsigned char), 1, inputFile);
        fread(&f, sizeof(int), 1, inputFile);
        freq[data] = f;
    }
}

// 重建哈夫曼树
HuffmanNode *rebuildHuffmanTree(FILE *inputFile, int *nodeCount) {
    if (*nodeCount == 1) {
        unsigned char data;
        fread(&data, sizeof(unsigned char), 1, inputFile);
        return newHuffmanNode(data, 0);
    }
    HuffmanNode *nodes[*nodeCount];
    for (int i = 0; i < *nodeCount; i++) {
        unsigned char data;
        fread(&data, sizeof(unsigned char), 1, inputFile);
        nodes[i] = newHuffmanNode(data, 0);
    }
    for (int i = 0; i < *nodeCount - 1; i++) {
        int leftIndex, rightIndex;
        fread(&leftIndex, sizeof(int), 1, inputFile);
        fread(&rightIndex, sizeof(int), 1, inputFile);
        nodes[i]->left = nodes[leftIndex];
        nodes[i]->right = nodes[rightIndex];
    }
    return nodes[*nodeCount - 1];
}

// 从输入文件中读取一个比特
int readBit(FILE *inputFile, char *bitBuffer, int *bitCount) {
    if (*bitCount == 0) {
        fread(bitBuffer, sizeof(char), 1, inputFile);
        *bitCount = CHAR_BIT;
    }
    int bit = (*bitBuffer >> (*bitCount - 1)) & 1;
    (*bitCount)--;
    return bit;
}

// 哈夫曼编码文件解压函数
void decompressFile(const char *inputFileName, const char *outputFileName) {
    // 打开输入文件
    FILE *inputFile = fopen(inputFileName, "rb");
    if (inputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", inputFileName);
        exit(EXIT_FAILURE);
    }

    // 读取哈夫曼树节点数和每个字符出现的频率
    int nodeCount;
    int freq[UCHAR_MAX + 1];
    readNodeCountAndFreq(inputFile, &nodeCount, freq);

    // 重建哈夫曼树
    HuffmanNode *root = rebuildHuffmanTree(inputFile, &nodeCount);

    // 重置文件指针
    fseek(inputFile, 0L, SEEK_SET);
    fread(&nodeCount, sizeof(int), 1, inputFile);
    fseek(inputFile, nodeCount * (sizeof(unsigned char) + sizeof(int)) + sizeof(int), SEEK_CUR);

    // 打开输出文件
    FILE *outputFile = fopen(outputFileName, "wb");
    if (outputFile == NULL) {
        fprintf(stderr, "Error: Cannot open file '%s'\n", outputFileName);
        exit(EXIT_FAILURE);
    }

    // 解压文件
    HuffmanNode *node = root;
    unsigned char buffer[1024];
    char bitBuffer = 0;
    int bitCount = 0;
    int bytesRead;
    while ((bytesRead = fread(buffer, 1, sizeof(buffer), inputFile)) > 0) {
        for (int i = 0; i < bytesRead; i++) {
            int bit = readBit(inputFile, &bitBuffer, &bitCount);
            if (bit == 0) {
                node = node->left;
            } else {
                node = node->right;
            }
            if (node->left == NULL && node->right == NULL) {
                fwrite(&node->data, sizeof(unsigned char), 1, outputFile);
                node = root;
            }
        }
    }

    // 释放内存并关闭文件
    fclose(inputFile);
    fclose(outputFile);
    freeHuffmanNode(root);
}

以上是哈夫曼编码文件压缩与解压的C语言实现示例代码，您可以根据需要进行修改和优化。