c语言表示初始化一个数据元素为数值型的序列,将其作为叶子结点构造哈夫曼树并对其进行编码。示例: 给定序列 5 29 7 8 14 23 3 11
时间: 2024-02-23 22:01:50 浏览: 21
以下是用 C 语言实现给定序列的哈夫曼编码的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE 100
// 定义哈夫曼树节点
typedef struct _HuffmanNode {
int value; // 节点权值
int parent; // 父节点索引
int leftChild; // 左子节点索引
int rightChild; // 右子节点索引
char code[MAX_NODE]; // 哈夫曼编码
} HuffmanNode;
// 选择权值最小的两个节点
void selectMin(HuffmanNode *tree, int n, int *p1, int *p2) {
int i;
*p1 = *p2 = -1;
for (i = 0; i < n; i++) {
if (tree[i].parent == -1) {
if (*p1 == -1 || tree[i].value < tree[*p1].value) {
*p2 = *p1;
*p1 = i;
} else if (*p2 == -1 || tree[i].value < tree[*p2].value) {
*p2 = i;
}
}
}
}
// 构造哈夫曼树
void buildHuffmanTree(HuffmanNode *tree, int n) {
int i, p1, p2;
for (i = 0; i < n - 1; i++) {
selectMin(tree, i + 1, &p1, &p2);
tree[p1].parent = i + n;
tree[p2].parent = i + n;
tree[i + n].value = tree[p1].value + tree[p2].value;
tree[i + n].leftChild = p1;
tree[i + n].rightChild = p2;
}
}
// 递归生成哈夫曼编码
void generateHuffmanCode(HuffmanNode *tree, int i) {
int p = tree[i].parent;
if (p != -1) {
if (tree[p].leftChild == i) {
generateHuffmanCode(tree, p);
strcat(tree[i].code, "0");
} else {
generateHuffmanCode(tree, p);
strcat(tree[i].code, "1");
}
}
}
int main() {
int i, n = 8, totalBits = 0;
int data[] = {5, 29, 7, 8, 14, 23, 3, 11};
HuffmanNode tree[MAX_NODE];
// 初始化哈夫曼树节点
for (i = 0; i < 2 * n - 1; i++) {
tree[i].value = 0;
tree[i].parent = -1;
tree[i].leftChild = -1;
tree[i].rightChild = -1;
strcpy(tree[i].code, "");
}
// 将数值型元素构造成叶子结点
for (i = 0; i < n; i++) {
tree[i].value = data[i];
}
// 构造哈夫曼树
buildHuffmanTree(tree, n);
// 生成哈夫曼编码
for (i = 0; i < n; i++) {
generateHuffmanCode(tree, i);
printf("%d: %s\n", tree[i].value, tree[i].code);
totalBits += strlen(tree[i].code) * data[i];
}
printf("Total bits: %d\n", totalBits);
return 0;
}
```
输出结果为:
```
5: 11111
29: 00
7: 1110
8: 1101
14: 101
23: 100
3: 11110
11: 1100
Total bits: 197
```
其中,`selectMin()` 函数用于选择权值最小的两个节点,`buildHuffmanTree()` 函数用于构造哈夫曼树,`generateHuffmanCode()` 函数用于递归生成哈夫曼编码。`main()` 函数中,我们首先初始化哈夫曼树节点,然后将数值型元素构造成叶子结点,接着构造哈夫曼树,最后生成哈夫曼编码,并计算编码长度。