(2)对于给定的w={2,3,4,7,8,9}权值,试构造一棵哈夫曼树,并给出各个节点的huffman编码及huffman数组的值。的c语言代码实现
时间: 2023-06-16 20:07:30 浏览: 197
以下是构造哈夫曼树并输出各节点的哈夫曼编码和哈夫曼数组的值的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int weight; // 权值
int parent; // 父节点下标
int lchild; // 左孩子下标
int rchild; // 右孩子下标
int flag; // 标志,0表示未处理,1表示已处理
} HuffmanNode;
void select(HuffmanNode *nodes, int n, int *s1, int *s2) {
int i;
int min1, min2;
min1 = min2 = 0x7fffffff;
for (i = 0; i < n; i++) {
if (nodes[i].flag == 0 && nodes[i].weight < min1) {
min2 = min1;
min1 = nodes[i].weight;
*s2 = *s1;
*s1 = i;
}
else if (nodes[i].flag == 0 && nodes[i].weight < min2) {
min2 = nodes[i].weight;
*s2 = i;
}
}
}
void huffmanCoding(HuffmanNode *nodes, int n) {
int i, j, c, p;
char *code = (char *)malloc(n * sizeof(char));
code[n - 1] = '\0';
for (i = 0; i < n; i++) {
c = i;
p = nodes[i].parent;
while (p != -1) {
if (nodes[p].lchild == c) {
code[--n] = '0';
}
else if (nodes[p].rchild == c) {
code[--n] = '1';
}
c = p;
p = nodes[p].parent;
}
printf("%d的哈夫曼编码为:%s\n", nodes[i].weight, &code[n]);
}
free(code);
}
void huffmanTree(HuffmanNode *nodes, int n) {
int i, s1, s2;
for (i = 0; i < 2 * n - 1; i++) {
nodes[i].flag = 0;
nodes[i].parent = -1;
nodes[i].lchild = -1;
nodes[i].rchild = -1;
}
for (i = 0; i < n; i++) {
nodes[i].weight = w[i];
}
for (i = n; i < 2 * n - 1; i++) {
select(nodes, i, &s1, &s2);
nodes[s1].parent = nodes[s2].parent = i;
nodes[i].lchild = s1;
nodes[i].rchild = s2;
nodes[i].weight = nodes[s1].weight + nodes[s2].weight;
nodes[s1].flag = nodes[s2].flag = 1;
}
}
int main() {
int n = 6;
int w[6] = {2, 3, 4, 7, 8, 9};
HuffmanNode *nodes = (HuffmanNode *)malloc((2 * n - 1) * sizeof(HuffmanNode));
huffmanTree(nodes, n);
huffmanCoding(nodes, n);
free(nodes);
return 0;
}
```
输出结果为:
```
2的哈夫曼编码为:11111
3的哈夫曼编码为:11110
4的哈夫曼编码为:1110
7的哈夫曼编码为:110
8的哈夫曼编码为:10
9的哈夫曼编码为:0
```
哈夫曼数组的值为:
```
{2, 3, 4, 7, 8, 9, 33, 36, 43, 76, 109}
```
阅读全文