哈夫曼树和哈夫曼编码C语言

哈夫曼树和哈夫曼编码是一种常用的数据压缩算法，C语言可以很方便地实现。以下是一个简单的实现示例：

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

typedef struct node {
    char data;              // 结点存储的字符
    int freq;               // 结点出现的频率
    struct node *left;      // 左子树指针
    struct node *right;     // 右子树指针
} Node;

typedef struct heap {
    int size;               // 堆中元素的个数
    Node **array;           // 存储结点的数组
} Heap;

Node *create_node(char data, int freq) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

Heap *create_heap(int capacity) {
    Heap *heap = (Heap *)malloc(sizeof(Heap));
    heap->size = 0;
    heap->array = (Node **)malloc(capacity * sizeof(Node *));
    return heap;
}

void swap_node(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(Heap *heap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heap->size && heap->array[left]->freq < heap->array[smallest]->freq) {
        smallest = left;
    }

    if (right < heap->size && heap->array[right]->freq < heap->array[smallest]->freq) {
        smallest = right;
    }

    if (smallest != index) {
        swap_node(&heap->array[smallest], &heap->array[index]);
        heapify(heap, smallest);
    }
}

Node *extract_min(Heap *heap) {
    Node *node = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return node;
}

void insert(Heap *heap, Node *node) {
    heap->size++;
    int index = heap->size - 1;
    while (index > 0 && node->freq < heap->array[(index - 1) / 2]->freq) {
        heap->array[index] = heap->array[(index - 1) / 2];
        index = (index - 1) / 2;
    }
    heap->array[index] = node;
}

Heap *build_min_heap(char *data, int *freq, int size) {
    Heap *heap = create_heap(size);
    for (int i = 0; i < size; i++) {
        Node *node = create_node(data[i], freq[i]);
        insert(heap, node);
    }
    return heap;
}

Node *build_huffman_tree(char *data, int *freq, int size) {
    Heap *heap = build_min_heap(data, freq, size);
    while (heap->size > 1) {
        Node *left = extract_min(heap);
        Node *right = extract_min(heap);
        Node *parent = create_node('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        insert(heap, parent);
    }
    return extract_min(heap);
}

void print_codes(Node *root, int *codes, int top) {
    if (root->left) {
        codes[top] = 0;
        print_codes(root->left, codes, top + 1);
    }

    if (root->right) {
        codes[top] = 1;
        print_codes(root->right, codes, top + 1);
    }

    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", codes[i]);
        }
        printf("\n");
    }
}

void huffman_encoding(char *data, int *freq, int size) {
    Node *root = build_huffman_tree(data, freq, size);
    int codes[size];
    int top = 0;
    print_codes(root, codes, top);
}

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

以上代码实现了哈夫曼树和哈夫曼编码的功能，它的输出结果为：

a: 1100
b: 1101
c: 100
d: 101
e: 111
f: 0

这表示字符'a'的编码为1100，字符'b'的编码为1101，以此类推。