用c语言实现哈夫曼编码
时间: 2023-10-16 09:33:38 浏览: 154
哈夫曼编码是一种无损数据压缩算法,它的核心思想是将出现频率较高的字符用较短的编码表示,而出现频率较低的字符用较长的编码表示,从而达到压缩数据的目的。下面是用C语言实现哈夫曼编码的基本步骤:
1. 定义哈夫曼树的节点结构体
```c
typedef struct HuffmanNode {
char ch; // 字符
int freq; // 字符出现的频率
struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;
```
2. 统计每个字符出现的频率
```c
int freq[256] = {0}; // 存储每个字符出现的频率,ASCII码共有256个字符
// 遍历字符串,统计每个字符出现的频率
char *str = "hello world";
for (int i = 0; i < strlen(str); i++) {
freq[str[i]]++;
}
```
3. 构建哈夫曼树
```c
// 比较函数,用于按照字符出现频率从小到大排序
int cmp(const void *a, const void *b) {
HuffmanNode **node1 = (HuffmanNode**)a;
HuffmanNode **node2 = (HuffmanNode**)b;
return (*node1)->freq - (*node2)->freq;
}
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int *freq) {
// 构建叶子节点
HuffmanNode *nodes[256];
int count = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->ch = (char)i;
node->freq = freq[i];
node->left = node->right = NULL;
nodes[count++] = node;
}
}
// 构建哈夫曼树
while (count > 1) {
qsort(nodes, count, sizeof(HuffmanNode*), cmp); // 按照频率从小到大排序
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->left = nodes[0];
node->right = nodes[1];
node->freq = nodes[0]->freq + nodes[1]->freq;
nodes[0] = node;
count--;
for (int i = 1; i < count; i++) {
nodes[i] = nodes[i+1];
}
}
return nodes[0];
}
```
4. 生成哈夫曼编码
```c
// 生成哈夫曼编码
void genHuffmanCode(HuffmanNode *root, char *code, int depth) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->ch, code);
return;
}
code[depth] = '0';
genHuffmanCode(root->left, code, depth+1);
code[depth] = '1';
genHuffmanCode(root->right, code, depth+1);
}
// 生成哈夫曼编码表
void genHuffmanCodeTable(HuffmanNode *root, char *codeTable[]) {
char code[256];
memset(code, 0, sizeof(code));
genHuffmanCode(root, code, 0);
}
```
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct HuffmanNode {
char ch; // 字符
int freq; // 字符出现的频率
struct HuffmanNode *left, *right; // 左右子节点指针
} HuffmanNode;
int freq[256] = {0}; // 存储每个字符出现的频率,ASCII码共有256个字符
// 比较函数,用于按照字符出现频率从小到大排序
int cmp(const void *a, const void *b) {
HuffmanNode **node1 = (HuffmanNode**)a;
HuffmanNode **node2 = (HuffmanNode**)b;
return (*node1)->freq - (*node2)->freq;
}
// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int *freq) {
// 构建叶子节点
HuffmanNode *nodes[256];
int count = 0;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->ch = (char)i;
node->freq = freq[i];
node->left = node->right = NULL;
nodes[count++] = node;
}
}
// 构建哈夫曼树
while (count > 1) {
qsort(nodes, count, sizeof(HuffmanNode*), cmp); // 按照频率从小到大排序
HuffmanNode *node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
node->left = nodes[0];
node->right = nodes[1];
node->freq = nodes[0]->freq + nodes[1]->freq;
nodes[0] = node;
count--;
for (int i = 1; i < count; i++) {
nodes[i] = nodes[i+1];
}
}
return nodes[0];
}
// 生成哈夫曼编码
void genHuffmanCode(HuffmanNode *root, char *code, int depth) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->ch, code);
return;
}
code[depth] = '0';
genHuffmanCode(root->left, code, depth+1);
code[depth] = '1';
genHuffmanCode(root->right, code, depth+1);
}
// 生成哈夫曼编码表
void genHuffmanCodeTable(HuffmanNode *root, char *codeTable[]) {
char code[256];
memset(code, 0, sizeof(code));
genHuffmanCode(root, code, 0);
}
int main() {
// 统计每个字符出现的频率
char *str = "hello world";
for (int i = 0; i < strlen(str); i++) {
freq[str[i]]++;
}
// 构建哈夫曼树
HuffmanNode *root = buildHuffmanTree(freq);
// 生成哈夫曼编码表
char *codeTable[256] = {0};
genHuffmanCodeTable(root, codeTable);
return 0;
}
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)