用C语言实现哈夫曼编码
时间: 2023-07-19 15:10:30 浏览: 54
以下是使用C语言实现哈夫曼编码的基本步骤:
1. 定义结构体来表示每个字符及其对应的频率和编码:
```
struct node {
char ch;
int freq;
char *code;
};
```
2. 统计每个字符出现的频率,并将其存储到一个数组中:
```
int freq[256] = {0};
for (int i = 0; i < strlen(input); i++) {
freq[input[i]]++;
}
```
3. 构建哈夫曼树,可以使用优先队列(也称为堆)来实现:
```
struct node *buildHuffmanTree(int freq[]) {
priority_queue<struct node*, vector<struct node*>, compare> pq;
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
struct node *n = new node;
n->ch = (char)i;
n->freq = freq[i];
n->left = NULL;
n->right = NULL;
pq.push(n);
}
}
while (pq.size() > 1) {
struct node *n1 = pq.top();
pq.pop();
struct node *n2 = pq.top();
pq.pop();
struct node *n = new node;
n->freq = n1->freq + n2->freq;
n->left = n1;
n->right = n2;
pq.push(n);
}
return pq.top();
}
```
其中,compare是一个比较函数,用于将节点按照频率从小到大排序。
4. 通过递归遍历哈夫曼树,生成每个字符的编码:
```
void generateCodes(struct node *root, char *code, int index) {
if (root->left == NULL && root->right == NULL) {
code[index] = '\0';
root->code = strdup(code);
return;
}
code[index] = '0';
generateCodes(root->left, code, index + 1);
code[index] = '1';
generateCodes(root->right, code, index + 1);
}
```
5. 使用生成的编码对原始数据进行编码:
```
char *encodeData(char *input, struct node *root) {
char *output = (char*)malloc(sizeof(char) * strlen(input) * 8);
int index = 0;
for (int i = 0; i < strlen(input); i++) {
struct node *n = findNode(root, input[i]);
strcat(output, n->code);
}
return output;
}
```
其中,findNode函数用于在哈夫曼树中查找指定字符对应的节点。
6. 使用生成的编码对压缩后的数据进行解码:
```
char *decodeData(char *input, struct node *root) {
char *output = (char*)malloc(sizeof(char) * strlen(input));
int index = 0;
struct node *n = root;
for (int i = 0; i < strlen(input); i++) {
if (input[i] == '0') {
n = n->left;
} else {
n = n->right;
}
if (n->left == NULL && n->right == NULL) {
output[index++] = n->ch;
n = root;
}
}
output[index] = '\0';
return output;
}
```
以上就是使用C语言实现哈夫曼编码的基本步骤。