c 语言实现哈夫曼编码
要实现哈夫曼编码,需要以下步骤:
统计字符出现的频率
构建哈夫曼树
遍历哈夫曼树,给不同的字符赋予不同的编码
将编码后的字符写入文件中
下面是一个简单的 C 语言实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_HT 100
// 节点结构体
struct MinHeapNode {
char data; // 字符
unsigned freq; // 频率
struct MinHeapNode *left, *right; // 左右子节点
};
// 哈夫曼树结构体
struct MinHeap {
unsigned size; // 大小
unsigned capacity; // 容量
struct MinHeapNode** array; // 数组
};
// 创建节点
struct MinHeapNode* newNode(char data, unsigned freq) {
struct MinHeapNode* temp = (struct MinHeapNode*) malloc(sizeof(struct
MinHeapNode));
temp->left = temp->right = NULL;
temp->data = data;
temp->freq = freq;
return temp;
}
// 创建一个大小为 capacity 的空的 MinHeap
struct MinHeap* createMinHeap(unsigned capacity) {
struct MinHeap* minHeap = (struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->size = 0; // 初始化大小为 0
minHeap->capacity = capacity;