请给出哈夫曼编码c语言实现的具体代码
时间: 2024-05-12 20:17:10 浏览: 6
以下是一个简单的哈夫曼编码的C语言实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100
// 结点定义
typedef struct Node {
int freq;// 该结点对应的字符出现的频率
char data;// 该结点对应的字符
struct Node *left, *right;// 左子树和右子树
} Node;
// 哈夫曼树定义
typedef struct {
Node* arr[MAX_TREE_HT];
int cur_size;
} Heap;
int min(int a, int b) {
return (a < b) ? a : b;
}
// Node 操作相关函数
Node* create_node(char data, int freq) {
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
void free_node(Node* node) {
if (node == NULL) return;
free_node(node->left);
free_node(node->right);
free(node);
}
void print_node(Node* node) {
printf("%c: %d\n", node->data, node->freq);
}
// Heap 相关函数
Heap* create_heap() {
Heap* h = (Heap*) malloc(sizeof(Heap));
h->cur_size = 0;
return h;
}
void free_heap(Heap* h) {
if (h == NULL) return;
int i;
for (i = 1; i <= h->cur_size; i++) {
free_node(h->arr[i]);
}
free(h);
}
Node* get_min_node(Heap* h) {
if (h == NULL || h->cur_size == 0) return NULL;
Node* min_node = h->arr[1];
Node* last_node = h->arr[h->cur_size];
h->cur_size--;
int i = 1, child;
while (i * 2 <= h->cur_size) {
child = i * 2;
if (child != h->cur_size && h->arr[child + 1]->freq < h->arr[child]->freq) {
child++;
}
if (last_node->freq > h->arr[child]->freq) {
h->arr[i] = h->arr[child];
} else {
break;
}
i = child;
}
h->arr[i] = last_node;
return min_node;
}
void insert_node(Heap* h, Node* node) {
if (h == NULL || node == NULL) return;
h->cur_size++;
h->arr[h->cur_size] = node;
int i = h->cur_size;
while (i > 1 && h->arr[i]->freq < h->arr[i / 2]->freq) {
Node* tmp = h->arr[i / 2];
h->arr[i / 2] = h->arr[i];
h->arr[i] = tmp;
i /= 2;
}
}
// 哈夫曼树相关函数
Node* build_huffman_tree(char* str) {
// 计算每个字符的出现频率
int freq[256] = {0};
int len = strlen(str);
for (int i = 0; i < len; i++) {
freq[str[i]]++;
}
// 将字符及其出现频率创建成一颗颗单结点树
Heap* h = create_heap();
for (int i = 0; i < 256; i++) {
if (freq[i] != 0) {
Node* node = create_node((char)i, freq[i]);
insert_node(h, node);
}
}
// 将单结点树组成哈夫曼树
while (h->cur_size > 1) {
Node* left = get_min_node(h);
Node* right = get_min_node(h);
Node* parent = create_node('^', left->freq + right->freq);
parent->left = left;
parent->right = right;
insert_node(h, parent);
}
Node* root = get_min_node(h);
free_heap(h);
return root;
}
void get_codes_helper(Node* root, char arr[], int len, char codes[][MAX_TREE_HT], int* index) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
memcpy(codes[root->data], arr, len);
codes[root->data][len] = '\0';
(*index)++;
}
arr[len] = '0';
get_codes_helper(root->left, arr, len + 1, codes, index);
arr[len] = '1';
get_codes_helper(root->right, arr, len + 1, codes, index);
}
void get_codes(Node* root, char codes[][MAX_TREE_HT]) {
int index = 0;
char arr[MAX_TREE_HT];
get_codes_helper(root, arr, 0, codes, &index);
}
// 测试代码
int main() {
char* str = "aaabbccdeeee";
Node* root = build_huffman_tree(str);
char codes[256][MAX_TREE_HT];
memset(codes, '\0', sizeof(codes));
get_codes(root, codes);
for (int i = 0; i < 256; i++) {
if (codes[i][0] != '\0') {
printf("%c: %s\n", (char)i, codes[i]);
}
}
free_node(root);
return 0;
}
```
注意:以上代码只是一个简单的演示,实际使用时需要考虑更多细节问题。