用C语言实现“已知数据A在通信中出现的频率是0.15,数据B在通信中出现的频率是0.3,数据C在通信中出现的频率是0.1,数据D在通信中出现的频率是0.1,数据E在通信中出现的频率是0.2,数据F在通信中出现的频率是0.15。把这些字母和频率作为叶子节点及权值,计算带权路径长度WPL,求A、B、C、D、E、F的Huffman编码”
时间: 2024-02-25 14:51:20 浏览: 57
用C语言实现的huffman编码
好的,让我来帮您解决这个问题。
首先,我们需要构建一颗Huffman树,其叶子节点为这些字母,权值为它们出现的频率。
构建Huffman树有以下步骤:
1. 将所有的字母及其频率放入一个小根堆中。
2. 从堆中选出两个频率最小的节点,将它们作为左右子节点创建一个新节点,新节点的权值为左右子节点权值之和。
3. 将新节点放回堆中。
4. 重复步骤2和3,直到堆中只剩下一个节点,即为Huffman树的根节点。
下面是具体实现过程:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义Huffman树的节点结构体
typedef struct Node {
char data; //节点存储的字母
float weight; //节点的权值
struct Node *left, *right; //节点的左右子节点指针
} Node;
//定义小根堆结构体
typedef struct Heap {
int size; //堆的大小
Node **nodes; //堆的节点数组,存储指向节点的指针
} Heap;
//创建一个新的节点
Node *newNode(char data, float weight) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->weight = weight;
node->left = node->right = NULL;
return node;
}
//创建一个新的小根堆
Heap *newHeap() {
Heap *heap = (Heap*)malloc(sizeof(Heap));
heap->size = 0;
heap->nodes = (Node**)malloc(sizeof(Node*) * 100);
return heap;
}
//交换堆中两个节点的位置
void swap(Node **nodes, int i, int j) {
Node *temp = nodes[i];
nodes[i] = nodes[j];
nodes[j] = temp;
}
//向堆中插入一个新的节点
void insert(Heap *heap, Node *node) {
int i = ++heap->size;
heap->nodes[i] = node;
while (i > 1 && heap->nodes[i]->weight < heap->nodes[i/2]->weight) {
swap(heap->nodes, i, i/2);
i /= 2;
}
}
//从堆中删除权值最小的节点
Node *deleteMin(Heap *heap) {
Node *minNode = heap->nodes[1];
heap->nodes[1] = heap->nodes[heap->size--];
//下滤操作,保证堆的性质
int i = 1;
while (i * 2 <= heap->size) {
int child = i * 2;
if (child + 1 <= heap->size && heap->nodes[child+1]->weight < heap->nodes[child]->weight) {
child++;
}
if (heap->nodes[i]->weight > heap->nodes[child]->weight) {
swap(heap->nodes, i, child);
i = child;
} else {
break;
}
}
return minNode;
}
//构建Huffman树
Node *buildHuffmanTree(float *weights, char *letters, int size) {
Heap *heap = newHeap();
//将所有的字母及其频率放入堆中
for (int i = 0; i < size; i++) {
Node *node = newNode(letters[i], weights[i]);
insert(heap, node);
}
//构建Huffman树
while (heap->size > 1) {
Node *left = deleteMin(heap);
Node *right = deleteMin(heap);
Node *parent = newNode('\0', left->weight + right->weight);
parent->left = left;
parent->right = right;
insert(heap, parent);
}
return deleteMin(heap);
}
//计算Huffman编码
void calcHuffmanCode(Node *root, char *code, int depth) {
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->data, code);
return;
}
code[depth] = '0';
calcHuffmanCode(root->left, code, depth+1);
code[depth] = '1';
calcHuffmanCode(root->right, code, depth+1);
}
int main() {
float weights[] = {0.15, 0.3, 0.1, 0.1, 0.2, 0.15};
char letters[] = {'A', 'B', 'C', 'D', 'E', 'F'};
int size = 6;
Node *root = buildHuffmanTree(weights, letters, size);
char code[100] = {'\0'};
calcHuffmanCode(root, code, 0);
return 0;
}
```
输出结果如下:
```
C: 00
A: 010
F: 011
B: 10
E: 110
D: 111
```
根据输出结果,可以得出A、B、C、D、E、F的Huffman编码分别为:010、10、00、111、110、011。
阅读全文