请用C语言写下面题目代码: 给定元素序列a,b,c,d,e,f,g,h,i,j对应的权重集合{1,4,24,5,6,10,8,31,22,11},建立一棵哈夫曼树。
时间: 2023-10-01 17:02:09 浏览: 96
哈夫曼树 基于C语言的数据结构代码
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct node{
int weight;
int parent, lchild, rchild;
} HNodeType;
void HuffmanTree(HNodeType HuffNode[], int n)
{
int i, j, k;
int min1, min2; // 两个最小权值的下标
int len = 2 * n - 1; // 哈夫曼树的节点数
// 初始化哈夫曼树
for (i = 0; i < n; i++) {
HuffNode[i].weight = 1;
HuffNode[i].parent = -1;
HuffNode[i].lchild = -1;
HuffNode[i].rchild = -1;
}
for (i = 0; i < n; i++) {
scanf("%d", &HuffNode[i].weight);
}
// 构造哈夫曼树
for (i = n; i < len; i++) {
min1 = -1;
min2 = -1;
for (j = 0; j < i; j++) {
if (HuffNode[j].parent == -1) {
if (min1 == -1) {
min1 = j;
} else if (min2 == -1) {
min2 = j;
} else if (HuffNode[j].weight < HuffNode[min1].weight) {
min2 = min1;
min1 = j;
} else if (HuffNode[j].weight < HuffNode[min2].weight) {
min2 = j;
}
}
}
HuffNode[min1].parent = i;
HuffNode[min2].parent = i;
HuffNode[i].lchild = min1;
HuffNode[i].rchild = min2;
HuffNode[i].weight = HuffNode[min1].weight + HuffNode[min2].weight;
}
}
int main()
{
HNodeType HuffNode[MAXSIZE];
int n, i;
printf("请输入元素个数:");
scanf("%d", &n);
printf("请输入%d个元素的权值:", n);
HuffmanTree(HuffNode, n);
printf("哈夫曼树的结构如下:\n");
printf(" 节点编号 权值 双亲编号 左孩子编号 右孩子编号\n");
for (i = 0; i < 2 * n - 1; i++) {
printf("%6d%8d%10d%14d%14d\n", i, HuffNode[i].weight, HuffNode[i].parent, HuffNode[i].lchild, HuffNode[i].rchild);
}
return 0;
}
```
注意,这里只是简单实现了哈夫曼树的构建过程,并没有进行编码和解码。如果需要进行编码和解码,可以根据哈夫曼树的结构进行相应的实现。
阅读全文