用C语言编写出该题目完整版完成代码实现:设用于通信的电文由6个字母(A、B、C、D、E、F)组成,统计字母在某电文中出现的频率分别为0.24,0.02,0.12,0.08,0.36,0.18。要求构建哈夫曼树,求出其带权路径长度,并给出字母对应的哈夫曼编码。
时间: 2024-12-28 13:30:30 浏览: 8
在C语言中,我们可以先创建一个结构体来存储每个字符及其频率,然后利用优先队列(这里可以使用二叉堆)来构建哈夫曼树。最后计算带权路径长度并生成哈夫曼编码。以下是完整的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义字符和频率的结构体
typedef struct Node {
char letter;
double freq;
struct Node *left, *right;
} Node;
// 创建节点
Node* newNode(char letter, double freq) {
Node* node = (Node*)malloc(sizeof(Node));
node->letter = letter;
node->freq = freq;
node->left = node->right = NULL;
return node;
}
// 比较节点的频率
int compare(const void* a, const void* b) {
return ((Node*)a)->freq - ((Node*)b)->freq;
}
// 插入节点到堆
void insert(Node** heap, Node* node) {
if (*heap == NULL) {
*heap = node;
} else {
Node* temp = *heap;
while (temp && temp->freq > node->freq) {
if (temp->freq < node->freq) {
*heap = node;
break;
}
if (node->letter < temp->letter) {
temp = temp->left;
} else {
temp = temp->right;
}
}
if (node->letter < temp->letter) {
temp->left = node;
} else {
temp->right = node;
}
}
}
// 构建哈夫曼树
Node* buildHuffmanTree(Node** heap) {
if (*heap == NULL || (*heap)->left == NULL) {
return *heap;
}
Node* left = buildHuffmanTree(&(*heap)->left);
Node* right = buildHuffmanTree(&(*heap)->right);
Node* newNode = newNode('\0', (*heap)->freq + left->freq + right->freq);
newNode->left = left;
newNode->right = right;
insert(heap, newNode);
return *heap;
}
// 计算带权路径长度
double calculateWPL(Node* root) {
if (root == NULL) {
return 0;
}
return root->freq + calculateWPL(root->left) + calculateWPL(root->right);
}
// 生成哈夫曼编码
char getHuffmanCode(Node* node, char prevCode, char* codes) {
if (node->left == NULL && node->right == NULL) {
codes[node->letter] = prevCode;
return '\0';
}
codes[node->letter] = '0' + getHuffmanCode(node->left, '1' + codes[node->letter], codes);
return codes[node->letter];
}
// 主函数
int main() {
// 初始化字符和频率
Node letters[] = { {'A', 0.24}, {'B', 0.02}, {'C', 0.12}, {'D', 0.08}, {'E', 0.36}, {'F', 0.18} };
int numLetters = sizeof(letters) / sizeof(letters[0]);
Node* heap = NULL;
// 将数据插入堆
for (int i = 0; i < numLetters; ++i) {
insert(&heap, &letters[i]);
}
// 构建哈夫曼树
Node* root = buildHuffmanTree(&heap);
// 计算带权路径长度
double wpl = calculateWPL(root);
printf("带权路径长度 (WPL): %.2f\n", wpl);
// 生成哈夫曼编码
char codes[256] = {0};
getHuffmanCode(root, '\0', codes);
printf("哈夫曼编码:\n");
for (int i = 0; i < numLetters; ++i) {
printf("%c: %s\n", letters[i].letter, codes[letters[i].letter]);
}
return 0;
}
```
运行这个程序后,它会输出带权路径长度以及每个字符的哈夫曼编码。
阅读全文