哈夫曼树，哈夫曼编码和译码的c语言代码

哈夫曼树的生成可以使用贪心算法，在此不再赘述。下面是哈夫曼编码的 C 语言代码：

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

#define MAX_LEN 256

typedef struct _HuffmanNode {
    char ch;
    int freq;
    char *code;
    struct _HuffmanNode *left, *right;
} HuffmanNode;

typedef struct _PriorityQueue {
    HuffmanNode **nodes;
    int size;
} PriorityQueue;

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

PriorityQueue *new_priority_queue(int capacity) {
    PriorityQueue *queue = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    queue->nodes = (HuffmanNode **) malloc(capacity * sizeof(HuffmanNode *));
    queue->size = 0;
    return queue;
}

void swap(HuffmanNode **nodes, int i, int j) {
    HuffmanNode *temp = nodes[i];
    nodes[i] = nodes[j];
    nodes[j] = temp;
}

void enqueue(PriorityQueue *queue, HuffmanNode *node) {
    int i = queue->size++;
    queue->nodes[i] = node;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (queue->nodes[i]->freq < queue->nodes[parent]->freq) {
            swap(queue->nodes, i, parent);
            i = parent;
        } else {
            break;
        }
    }
}

HuffmanNode *dequeue(PriorityQueue *queue) {
    HuffmanNode *node = queue->nodes[0];
    queue->nodes[0] = queue->nodes[--queue->size];
    int i = 0;
    while (2 * i + 1 < queue->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;
        if (queue->nodes[left]->freq < queue->nodes[smallest]->freq) {
            smallest = left;
        }
        if (right < queue->size && queue->nodes[right]->freq < queue->nodes[smallest]->freq) {
            smallest = right;
        }
        if (smallest != i) {
            swap(queue->nodes, i, smallest);
            i = smallest;
        } else {
            break;
        }
    }
    return node;
}

void build_codes(HuffmanNode *node, char *code, int depth) {
    if (node->left == NULL && node->right == NULL) {
        node->code = (char *) malloc((depth + 1) * sizeof(char));
        strcpy(node->code, code);
    } else {
        char *left_code = (char *) malloc((depth + 2) * sizeof(char));
        char *right_code = (char *) malloc((depth + 2) * sizeof(char));
        strcpy(left_code, code);
        strcat(left_code, "0");
        strcpy(right_code, code);
        strcat(right_code, "1");
        build_codes(node->left, left_code, depth + 1);
        build_codes(node->right, right_code, depth + 1);
    }
}

void print_codes(HuffmanNode *node) {
    if (node->left == NULL && node->right == NULL) {
        printf("%c: %s\n", node->ch, node->code);
    } else {
        print_codes(node->left);
        print_codes(node->right);
    }
}

void destroy_tree(HuffmanNode *node) {
    if (node->left != NULL) {
        destroy_tree(node->left);
    }
    if (node->right != NULL) {
        destroy_tree(node->right);
    }
    if (node->code != NULL) {
        free(node->code);
    }
    free(node);
}

int main() {
    int freq[MAX_LEN] = {0};
    char str[MAX_LEN];
    fgets(str, MAX_LEN, stdin);
    for (int i = 0; i < strlen(str); i++) {
        freq[(int) str[i]]++;
    }
    PriorityQueue *queue = new_priority_queue(MAX_LEN);
    for (int i = 0; i < MAX_LEN; i++) {
        if (freq[i] > 0) {
            enqueue(queue, new_node((char) i, freq[i]));
        }
    }
    while (queue->size > 1) {
        HuffmanNode *node1 = dequeue(queue);
        HuffmanNode *node2 = dequeue(queue);
        HuffmanNode *parent = new_node('\0', node1->freq + node2->freq);
        parent->left = node1;
        parent->right = node2;
        enqueue(queue, parent);
    }
    HuffmanNode *root = dequeue(queue);
    build_codes(root, "", 0);
    print_codes(root);
    destroy_tree(root);
    free(queue->nodes);
    free(queue);
    return 0;
}

哈夫曼译码的 C 语言代码如下：

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

#define MAX_LEN 256

typedef struct _HuffmanNode {
    char ch;
    int freq;
    char *code;
    struct _HuffmanNode *left, *right;
} HuffmanNode;

typedef struct _PriorityQueue {
    HuffmanNode **nodes;
    int size;
} PriorityQueue;

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

PriorityQueue *new_priority_queue(int capacity) {
    PriorityQueue *queue = (PriorityQueue *) malloc(sizeof(PriorityQueue));
    queue->nodes = (HuffmanNode **) malloc(capacity * sizeof(HuffmanNode *));
    queue->size = 0;
    return queue;
}

void swap(HuffmanNode **nodes, int i, int j) {
    HuffmanNode *temp = nodes[i];
    nodes[i] = nodes[j];
    nodes[j] = temp;
}

void enqueue(PriorityQueue *queue, HuffmanNode *node) {
    int i = queue->size++;
    queue->nodes[i] = node;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (queue->nodes[i]->freq < queue->nodes[parent]->freq) {
            swap(queue->nodes, i, parent);
            i = parent;
        } else {
            break;
        }
    }
}

HuffmanNode *dequeue(PriorityQueue *queue) {
    HuffmanNode *node = queue->nodes[0];
    queue->nodes[0] = queue->nodes[--queue->size];
    int i = 0;
    while (2 * i + 1 < queue->size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;
        if (queue->nodes[left]->freq < queue->nodes[smallest]->freq) {
            smallest = left;
        }
        if (right < queue->size && queue->nodes[right]->freq < queue->nodes[smallest]->freq) {
            smallest = right;
        }
        if (smallest != i) {
            swap(queue->nodes, i, smallest);
            i = smallest;
        } else {
            break;
        }
    }
    return node;
}

void build_codes(HuffmanNode *node, char *code, int depth) {
    if (node->left == NULL && node->right == NULL) {
        node->code = (char *) malloc((depth + 1) * sizeof(char));
        strcpy(node->code, code);
    } else {
        char *left_code = (char *) malloc((depth + 2) * sizeof(char));
        char *right_code = (char *) malloc((depth + 2) * sizeof(char));
        strcpy(left_code, code);
        strcat(left_code, "0");
        strcpy(right_code, code);
        strcat(right_code, "1");
        build_codes(node->left, left_code, depth + 1);
        build_codes(node->right, right_code, depth + 1);
    }
}

void print_codes(HuffmanNode *node) {
    if (node->left == NULL && node->right == NULL) {
        printf("%c: %s\n", node->ch, node->code);
    } else {
        print_codes(node->left);
        print_codes(node->right);
    }
}

void destroy_tree(HuffmanNode *node) {
    if (node->left != NULL) {
        destroy_tree(node->left);
    }
    if (node->right != NULL) {
        destroy_tree(node->right);
    }
    if (node->code != NULL) {
        free(node->code);
    }
    free(node);
}

int main() {
    int freq[MAX_LEN] = {0};
    char str[MAX_LEN];
    fgets(str, MAX_LEN, stdin);
    for (int i = 0; i < strlen(str); i++) {
        freq[(int) str[i]]++;
    }
    PriorityQueue *queue = new_priority_queue(MAX_LEN);
    for (int i = 0; i < MAX_LEN; i++) {
        if (freq[i] > 0) {
            enqueue(queue, new_node((char) i, freq[i]));
        }
    }
    while (queue->size > 1) {
        HuffmanNode *node1 = dequeue(queue);
        HuffmanNode *node2 = dequeue(queue);
        HuffmanNode *parent = new_node('\0', node1->freq + node2->freq);
        parent->left = node1;
        parent->right = node2;
        enqueue(queue, parent);
    }
    HuffmanNode *root = dequeue(queue);
    build_codes(root, "", 0);
    char code[MAX_LEN] = {0};
    while (scanf("%s", code) != EOF) {
        HuffmanNode *node = root;
        for (int i = 0; i < strlen(code); i++) {
            if (code[i] == '0') {
                node = node->left;
            } else {
                node = node->right;
            }
            if (node->left == NULL && node->right == NULL) {
                printf("%c", node->ch);
                node = root;
            }
        }
    }
    printf("\n");
    destroy_tree(root);
    free(queue->nodes);
    free(queue);
    return 0;
}