用c语言编写哈夫曼树

在C语言中，哈夫曼树（Huffman Tree）通常用于数据压缩，其构建过程是基于贪心算法。下面是基本步骤：

1. **初始化**：首先，创建一个队列，存储所有需要编码的字符及其频率。你可以用结构体如`struct node`来表示节点，包含字符、频率以及左右子节点。

typedef struct node {
    char data;
    int freq;
    struct node *left, *right;
} Node;

2. **构建队列**：将每个字符和它们的频率添加到队列中。

3. **循环构建**：重复直到队列只剩下一个元素：
- 从队列中取出两个频率最低的节点，合并成一个新的节点，新节点的频率是这两个节点频率之和，左孩子是第一个节点，右孩子是第二个节点。
- 将新节点放回队列中。

4. **生成编码**：最后剩下的节点就是根节点，它是哈夫曼树的编码起点。从根开始遍历，如果向左走就记录0，向右走则记录1。这个过程可以用递归实现。

5. **存储编码表**：遍历过程中，可以建立一个字典或者数组，记录每个字符对应的编码。

6. **压缩数据**：当需要压缩文本时，替换每个字符为对应的哈夫曼编码。

以下是一个简单的哈夫曼树构建函数示例：

Node* buildHuffmanTree(Queue* queue) {
    // ... 实现队列操作和节点合并...
}

相关问题

用c语言编写哈夫曼树解码的代码并在main函数中实现输出解码后的结果

好的，以下是用C语言编写哈夫曼树解码的代码，并在main函数中实现输出解码后的结果的示例：

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

#define MAX_TREE_NODE 1000

// 哈夫曼树节点结构体
typedef struct huffman_node {
    char data;
    int weight;
    int parent;
    int left_child;
    int right_child;
} HuffmanNode;

// 哈夫曼树结构体
typedef struct huffman_tree {
    HuffmanNode nodes[MAX_TREE_NODE];
    int node_count;
} HuffmanTree;

// 构建哈夫曼树
void build_huffman_tree(HuffmanTree* tree, char* data, int* weights, int count) {
    // 初始化节点
    for (int i = 0; i < count; i++) {
        tree->nodes[i].data = data[i];
        tree->nodes[i].weight = weights[i];
        tree->nodes[i].parent = -1;
        tree->nodes[i].left_child = -1;
        tree->nodes[i].right_child = -1;
    }
    tree->node_count = count;

    // 构建哈夫曼树
    for (int i = count; i < MAX_TREE_NODE; i++) {
        tree->nodes[i].data = '\0';
        tree->nodes[i].weight = 0;
        tree->nodes[i].parent = -1;
        tree->nodes[i].left_child = -1;
        tree->nodes[i].right_child = -1;
    }

    for (int i = count; i < 2 * count - 1; i++) {
        int left_child = -1;
        int right_child = -1;
        int min_weight = INT_MAX;
        for (int j = 0; j < i; j++) {
            if (tree->nodes[j].parent == -1) {
                if (tree->nodes[j].weight < min_weight) {
                    right_child = left_child;
                    left_child = j;
                    min_weight = tree->nodes[j].weight;
                }
                else if (tree->nodes[j].weight == min_weight) {
                    right_child = j;
                }
            }
        }
        tree->nodes[left_child].parent = i;
        tree->nodes[right_child].parent = i;
        tree->nodes[i].left_child = left_child;
        tree->nodes[i].right_child = right_child;
        tree->nodes[i].weight = tree->nodes[left_child].weight + tree->nodes[right_child].weight;
    }
}

// 哈夫曼树解码
void huffman_decode(HuffmanTree* tree, char* encoded_data, char* decoded_data) {
    int i = 0;
    int j = 0;
    int current_node = 2 * tree->node_count - 2;
    while (encoded_data[i] != '\0') {
        if (encoded_data[i] == '0') {
            current_node = tree->nodes[current_node].left_child;
        }
        else if (encoded_data[i] == '1') {
            current_node = tree->nodes[current_node].right_child;
        }
        if (tree->nodes[current_node].left_child == -1 && tree->nodes[current_node].right_child == -1) {
            decoded_data[j] = tree->nodes[current_node].data;
            j++;
            current_node = 2 * tree->node_count - 2;
        }
        i++;
    }
    decoded_data[j] = '\0';
}

int main() {
    // 假设编码为："0010101111011110101"
    char encoded_data[] = "0010101111011110101";

    // 假设字符和权重分别为：{'a', 'b', 'c', 'd', 'e'} 和 {5, 7, 2, 8, 4}
    char data[] = {'a', 'b', 'c', 'd', 'e'};
    int weights[] = {5, 7, 2, 8, 4};
    int count = sizeof(data) / sizeof(data[0]);

    // 构建哈夫曼树
    HuffmanTree tree;
    build_huffman_tree(&tree, data, weights, count);

    // 解码
    char decoded_data[MAX_TREE_NODE];
    memset(decoded_data, 0, sizeof(decoded_data));
    huffman_decode(&tree, encoded_data, decoded_data);

    // 输出解码后的结果
    printf("Decoded data: %s\n", decoded_data);

    return 0;
}

在上述示例中，我们假设编码为："0010101111011110101"，字符和权重分别为：{'a', 'b', 'c', 'd', 'e'} 和 {5, 7, 2, 8, 4}，然后构建哈夫曼树并解码，最后输出解码后的结果。

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