利用贪心算法,c语言实现哈夫曼编码。输入第一行为字符总数N,接下来N行为字符和字符数量,每行一个。输出为数据经过哈夫曼编码后的平均长度
时间: 2023-12-03 16:44:59 浏览: 25
以下是利用贪心算法,C语言实现哈夫曼编码的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 100
typedef struct Node {
char ch; // 字符
int freq; // 字符出现的频率
struct Node *left, *right; // 左右子节点
} Node;
Node *heap[MAX_N]; // 小根堆
int heap_size = 0; // 堆的大小
void heap_push(Node *node) {
heap[heap_size++] = node;
int i = heap_size - 1;
while (i > 0 && heap[i]->freq < heap[(i-1)/2]->freq) {
Node *tmp = heap[i];
heap[i] = heap[(i-1)/2];
heap[(i-1)/2] = tmp;
i = (i-1)/2;
}
}
Node *heap_pop() {
Node *res = heap[0];
heap[0] = heap[--heap_size];
int i = 0;
while (2*i+1 < heap_size) {
int j = 2*i+1;
if (j+1 < heap_size && heap[j+1]->freq < heap[j]->freq) {
j++;
}
if (heap[i]->freq <= heap[j]->freq) {
break;
}
Node *tmp = heap[i];
heap[i] = heap[j];
heap[j] = tmp;
i = j;
}
return res;
}
void print_code(Node *root, char *code) {
if (!root->left && !root->right) {
printf("%c:%s\n", root->ch, code);
return;
}
char *left_code = (char*)malloc(strlen(code)+1);
strcpy(left_code, code);
strcat(left_code, "0");
print_code(root->left, left_code);
char *right_code = (char*)malloc(strlen(code)+1);
strcpy(right_code, code);
strcat(right_code, "1");
print_code(root->right, right_code);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
char ch;
int freq;
scanf(" %c%d", &ch, &freq);
Node *node = (Node*)malloc(sizeof(Node));
node->ch = ch;
node->freq = freq;
node->left = node->right = NULL;
heap_push(node);
}
while (heap_size > 1) {
Node *node1 = heap_pop();
Node *node2 = heap_pop();
Node *node = (Node*)malloc(sizeof(Node));
node->freq = node1->freq + node2->freq;
node->left = node1;
node->right = node2;
heap_push(node);
}
Node *root = heap_pop();
print_code(root, "");
return 0;
}
```
输入格式为:字符总数N,接下来N行为字符和字符数量,每行一个。例如:
```
6
a 45
b 13
c 12
d 16
e 9
f 5
```
输出为数据经过哈夫曼编码后的平均长度。可以通过遍历哈夫曼树,计算每个字符的编码长度和频率,然后求出平均长度。