贪心策略哈夫曼编码C语言实现

哈夫曼编码是一种无损压缩算法，它的核心是构造一棵哈夫曼树，然后利用哈夫曼树进行编码和解码。贪心策略是哈夫曼编码的基础，它的思想是将出现频率较高的字符用较短的编码表示，出现频率较低的字符用较长的编码表示，以达到压缩数据的目的。

以下是哈夫曼编码的C语言实现：

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

#define MAX_NODES 256

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

typedef struct heap {
    int size;
    Node *nodes[MAX_NODES];
} Heap;

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

Heap *new_heap() {
    Heap *heap = (Heap *) malloc(sizeof(Heap));
    heap->size = 0;
    return heap;
}

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

void heapify(Heap *heap, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < heap->size && heap->nodes[left]->freq < heap->nodes[smallest]->freq) {
        smallest = left;
    }
    if (right < heap->size && heap->nodes[right]->freq < heap->nodes[smallest]->freq) {
        smallest = right;
    }
    if (smallest != i) {
        swap(&heap->nodes[i], &heap->nodes[smallest]);
        heapify(heap, smallest);
    }
}

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

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

Node *build_huffman_tree(int *freq) {
    Heap *heap = new_heap();
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            insert(heap, new_node(i, freq[i]));
        }
    }
    while (heap->size > 1) {
        Node *left = extract_min(heap);
        Node *right = extract_min(heap);
        Node *parent = new_node(0, left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        insert(heap, parent);
    }
    Node *root = extract_min(heap);
    free(heap);
    return root;
}

void encode(Node *root, int *code, int len, char **codes) {
    if (root->left == NULL && root->right == NULL) {
        code[len] = '\0';
        codes[root->ch] = (char *) malloc(sizeof(char) * (len + 1));
        strcpy(codes[root->ch], (char *) code);
    } else {
        code[len] = '0';
        encode(root->left, code, len + 1, codes);
        code[len] = '1';
        encode(root->right, code, len + 1, codes);
    }
}

void print_codes(char **codes) {
    for (int i = 0; i < 256; i++) {
        if (codes[i] != NULL) {
            printf("%c: %s\n", i, codes[i]);
        }
    }
}

void destroy_tree(Node *root) {
    if (root != NULL) {
        destroy_tree(root->left);
        destroy_tree(root->right);
        free(root);
    }
}

void destroy_codes(char **codes) {
    for (int i = 0; i < 256; i++) {
        if (codes[i] != NULL) {
            free(codes[i]);
        }
    }
    free(codes);
}

int main() {
    int freq[256] = {0};
    char c;
    while ((c = getchar()) != EOF) {
        freq[c]++;
    }
    Node *root = build_huffman_tree(freq);
    int code[256];
    char **codes = (char **) malloc(sizeof(char *) * 256);
    encode(root, code, 0, codes);
    print_codes(codes);
    destroy_tree(root);
    destroy_codes(codes);
    return 0;
}

该实现中，首先定义了一个`Node`结构体用于表示哈夫曼树中的节点，包括字符、出现频率以及左右子节点。`Heap`结构体用于表示最小堆，包括堆的大小和节点数组。`new_node`函数用于新建一个节点，`new_heap`函数用于新建一个最小堆。`swap`函数用于交换两个节点，`heapify`函数用于从指定位置开始调整最小堆，`insert`函数用于插入一个新节点到最小堆中，`extract_min`函数用于取出最小节点，`build_huffman_tree`函数用于构建哈夫曼树。

当哈夫曼树构建完成后，调用`encode`函数对每个字符进行编码，`print_codes`函数用于输出每个字符的编码，`destroy_tree`函数用于销毁哈夫曼树，`destroy_codes`函数用于销毁编码数组，释放动态分配的内存。

以上就是贪心策略哈夫曼编码的C语言实现。