用c语言写一段Huffman编码程序

好的，以下是用 C 语言写的 Huffman 编码程序示例：

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

struct node {
    int val;
    int freq;
    struct node* left;
    struct node* right;
};

struct priority_queue {
    int size;
    int capacity;
    struct node** values;
};

struct node* new_node(int val, int freq) {
    struct node* n = (struct node*) malloc(sizeof(struct node));
    n->val = val;
    n->freq = freq;
    n->left = NULL;
    n->right = NULL;
    return n;
}

struct priority_queue* create_pq(int capacity) {
    struct priority_queue* pq = (struct priority_queue*) malloc(sizeof(struct priority_queue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->values = (struct node**) malloc(capacity * sizeof(struct node*));
    return pq;
}

void swap_nodes(struct node** a, struct node** b) {
    struct node* temp = *a;
    *a = *b;
    *b = temp;
}

void min_heapify(struct priority_queue* pq, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < pq->size && pq->values[left]->freq < pq->values[smallest]->freq)
        smallest = left;
    if (right < pq->size && pq->values[right]->freq < pq->values[smallest]->freq)
        smallest = right;
    if (smallest != i) {
        swap_nodes(&pq->values[i], &pq->values[smallest]);
        min_heapify(pq, smallest);
    }
}

void push_pq(struct priority_queue* pq, struct node* value) {
    if (pq->size == pq->capacity) {
        printf("Priority queue overflow.\n");
        return;
    }
    int i = pq->size;
    pq->size++;
    pq->values[i] = value;
    while (i > 0 && pq->values[(i - 1) / 2]->freq > pq->values[i]->freq) {
        swap_nodes(&pq->values[i], &pq->values[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

struct node* pop_pq(struct priority_queue* pq) {
    if (pq->size == 0) {
        printf("Priority queue underflow.\n");
        return NULL;
    }
    struct node* value = pq->values[0];
    pq->size--;
    pq->values[0] = pq->values[pq->size];
    min_heapify(pq, 0);
    return value;
}

int is_leaf(struct node* node) {
    return node->left == NULL && node->right == NULL;
}

void print_arr(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d", arr[i]);
    printf("\n");
}

void print_codes(struct node* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        print_codes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        print_codes(root->right, arr, top + 1);
    }
    if (is_leaf(root)) {
        printf("%d: ", root->val);
        print_arr(arr, top);
    }
}

void huffman_codes(int data[], int freq[], int size) {
    struct priority_queue* pq = create_pq(size);
    for (int i = 0; i < size; i++)
        push_pq(pq, new_node(data[i], freq[i]));

    while (pq->size > 1) {
        struct node* left = pop_pq(pq);
        struct node* right = pop_pq(pq);
        struct node* parent = new_node(-1, left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        push_pq(pq, parent);
    }

    int arr[100];
    int top = 0;
    struct node* root = pop_pq(pq);
    print_codes(root, arr, top);
}

int main() {
    int data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(data) / sizeof(data[0]);
    huffman_codes(data, freq, size);
    return 0;
}

在这个示例中，我们通过使用优先队列（最小堆）和哈夫曼树的经典算法来生成哈夫曼编码。 首先，我们将每个字符视为节点，并使用其出现频率作为该节点的频率。 将这些节点插入优先队列中，通过找到两个具有最小频率的节点（通过弹出优先队列顶部）。我们将它们的和作为新节点的频率，并将该新节点插入优先队列中。如此反复，直到我们获得一个包含所有节点的树。 遍历这个树，将左侧的子树标记为「0」，右侧子树标记为「1」，并将该操作递归地应用于整个树。当遇到叶节点时，它的路径就是该节点的哈夫曼编码。最后，打印字符和它们的哈夫曼编码。

这是一个朴素的哈夫曼编码实现，但足以说明其基本工作原理。