c语言实现赫夫曼编码完整代码

以下是 c 语言实现赫夫曼编码的完整代码：

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

#define MAX_TREE_HT 100

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

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

// 创建一个新节点
struct node* new_node(char data, int freq) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->left = NULL;
    temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
}

// 创建一个优先队列
struct priority_queue* create_priority_queue(int capacity) {
    struct priority_queue* pq = (struct priority_queue*)malloc(sizeof(struct priority_queue));
    pq->size = 0;
    pq->capacity = capacity;
    pq->array = (struct node**)malloc(pq->capacity * sizeof(struct node*));
    return pq;
}

// 交换两个节点
void swap(struct node** a, struct node** b) {
    struct node* t = *a;
    *a = *b;
    *b = t;
}

// 下滤操作
void min_heapify(struct priority_queue* pq, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < pq->size && pq->array[left]->freq < pq->array[smallest]->freq) {
        smallest = left;
    }
    if (right < pq->size && pq->array[right]->freq < pq->array[smallest]->freq) {
        smallest = right;
    }
    if (smallest != index) {
        swap(&pq->array[smallest], &pq->array[index]);
        min_heapify(pq, smallest);
    }
}

// 判断队列是否为空
int is_empty(struct priority_queue* pq) {
    return pq->size == 0;
}

// 取出队列中最小的节点
struct node* extract_min(struct priority_queue* pq) {
    struct node* node = pq->array[0];
    pq->array[0] = pq->array[pq->size - 1];
    pq->size--;
    min_heapify(pq, 0);
    return node;
}

// 将节点插入队列中
void insert(struct priority_queue* pq, struct node* node) {
    pq->size++;
    int i = pq->size - 1;
    while (i && node->freq < pq->array[(i - 1) / 2]->freq) {
        pq->array[i] = pq->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    pq->array[i] = node;
}

// 建造哈夫曼树
struct node* build_huffman_tree(char data[], int freq[], int size) {
    struct node *left, *right, *top;
    struct priority_queue* pq = create_priority_queue(size);
    for (int i = 0; i < size; i++) {
        insert(pq, new_node(data[i], freq[i]));
    }
    while (!is_empty(pq) && pq->size > 1) {
        left = extract_min(pq);
        right = extract_min(pq);
        top = new_node('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insert(pq, top);
    }
    return extract_min(pq);
}

// 打印哈夫曼编码
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 (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

// 哈夫曼编码
void huffman_encoding(char data[], int freq[], int size) {
    struct node* root = build_huffman_tree(data, freq, size);
    int arr[MAX_TREE_HT], top = 0;
    print_codes(root, arr, 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;
}

在代码中，`create_priority_queue()` 函数用于创建优先队列，`new_node()` 函数用于创建新的节点，`swap()` 函数用于交换两个节点，`min_heapify()` 函数用于下滤操作，`is_empty()` 函数用于判断队列是否为空，`extract_min()` 函数用于取出队列中最小的节点，`insert()` 函数用于将节点插入队列中，`build_huffman_tree()` 函数用于建造哈夫曼树，`print_codes()` 函数用于打印哈夫曼编码，`huffman_encoding()` 函数用于执行哈夫曼编码。

在 `main()` 函数中，我们定义了一个字符数组 `data` 和一个频率数组 `freq`，用于存储待编码的字符及其频率。然后，我们计算出 `data` 数组的大小，并调用 `huffman_encoding()` 函数进行哈夫曼编码。

运行程序，即可输出各个字符的哈夫曼编码。