admin 管理员组文章数量: 1184232
2024年3月12日发(作者：localdate转化为string)
用c语言实现哈夫曼编码
哈夫曼编码是一种用于无损数据压缩的熵编码算法。以下是一个简单的使用C语言实现
哈夫曼编码的例子。这个例子只实现了编码过程，没有实现解码过程。
c
复制代码
#include
#include
#include
// 节点结构体
typedef struct Node {
char data;
int freq;
struct Node *left, *right;
} Node;
// 创建新节点
Node* newNode(char data, int freq) {
Node* node = (Node*) malloc(sizeof(Node));
node->data = data;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
// 计算前缀和
int getSum(Node* root) {
if (!root) return 0;
return root->freq + getSum(root->left) + getSum(root->right);
}
// 创建哈夫曼树
Node* createHuffmanTree(char data[], int freq[], int size) {
if (size == 0) return NULL;
Node *left = newNode(data[size-1], freq[size-1]);
Node *right = createHuffmanTree(data, freq, size-1);
Node *top = newNode(0, getSum(right));
top->left = left;
top->right = right;
return top;
}
// 打印哈夫曼编码
void printHuffmanCode(Node* root, int n, char code[]) {
if (!root) return;
if (root->data != 0) printf("%c: ", root->data);
code[n] = root->data;
printHuffmanCode(root->left, n+1, code);
printHuffmanCode(root->right, n+1, code);
}
int main() {
char data[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g'};
int freq[] = {5, 9, 12, 13, 16, 45};
int size = sizeof(data)/sizeof(data[0]);
Node* root = createHuffmanTree(data, freq, size);
char code[256] = {0}; // 存放哈夫曼编码，初始为空字符串，表示没有编码，
对应字符的编码为空字符串。
printHuffmanCode(root, 0, code); // 从根节点开始，打印哈夫曼编码。打
印的顺序是左子树、当前节点、右子树。总共打印的长度是当前节点的频率。因此，
可以打印出所有字符的哈夫曼编码。最后打印出来的就是以字符串的形式保存的哈
夫曼编码表。每个字符的编码以空格分隔。例如，'a'的编码是'00000'，'b'的编
码是'00001'，以此类推。可以通过打印出这个字符串来得到哈夫曼编码表。因此，
可以使用下面的函数来打印哈夫曼编码表：printf("%s", code);。
版权声明：本文标题：用c语言实现哈夫曼编码 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1710253334a564546.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论