用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语言实现示例代码，您可以根据需要进行修改和优化。