编写一个C语言函数createHTree,根据每个字符的出现次数(字符出现次数存放在全局数组Ccount中,Ccount[i]表示ASCII码值为i的字符出现次数),按照Huffman树生成规则,生成一棵Huffman树。1.依据数组Ccount中出现次数不为0的项,构造出树林F={T0,T1,...,Tm},初始时Ti(0<=i<=m)为只有一个根结构的树,且根结点(叶结点)的权值为相应字符的出现次数的二叉树(每棵树结点的类型为struct tnode,其成员c为字符,weight为树节点权值); 2.对树林F中每棵树按照其根节点的权值由小到大进行排序(若权值weight相同,字符c小的排在前面),得到一个有序树林F; 3.构造Huffman树。
时间: 2023-06-24 17:08:08 浏览: 94
哈夫曼树的建立(Huffman Tree C语言实现)
5星 · 资源好评率100%
以下是createHTree函数的实现:
```c
#include <stdio.h>
#include <stdlib.h>
struct tnode { // 树节点类型
char c;
int weight;
struct tnode *left, *right;
};
int Ccount[256]; // 记录每个字符出现的次数
// 比较函数,用于qsort排序
int cmp(const void *a, const void *b) {
struct tnode *ta = *(struct tnode **)a;
struct tnode *tb = *(struct tnode **)b;
if (ta->weight != tb->weight) {
return ta->weight - tb->weight;
} else {
return ta->c - tb->c;
}
}
// 创建Huffman树
struct tnode *createHTree() {
// 构造树林F
struct tnode *F[256];
int i, m = 0;
for (i = 0; i < 256; i++) {
if (Ccount[i] != 0) {
F[m] = (struct tnode *)malloc(sizeof(struct tnode));
F[m]->c = i;
F[m]->weight = Ccount[i];
F[m]->left = F[m]->right = NULL;
m++;
}
}
// 对树林F中每棵树按照其根节点的权值进行排序
qsort(F, m, sizeof(struct tnode *), cmp);
// 构造Huffman树
while (m > 1) {
// 取出权值最小的两棵树合并
struct tnode *t1 = F[0], *t2 = F[1];
struct tnode *t = (struct tnode *)malloc(sizeof(struct tnode));
t->c = '\0';
t->weight = t1->weight + t2->weight;
t->left = t1;
t->right = t2;
// 从树林F中删除这两棵树,将合并后的树插入树林F
int j;
for (j = 2; j < m; j++) {
F[j - 2] = F[j];
}
F[m - 2] = t;
m--;
// 对树林F中每棵树按照其根节点的权值进行排序
qsort(F, m, sizeof(struct tnode *), cmp);
}
return F[0];
}
```
该函数首先根据全局数组`Ccount`中出现次数不为0的项,构造出树林F,然后对树林F中每棵树按照其根节点的权值进行排序。接着,循环取出权值最小的两棵树合并,将合并后的树插入树林F中,并且对树林F中每棵树按照其根节点的权值进行排序。当树林F中只剩下一棵树时,该树即为生成的Huffman树,函数返回该树的根节点指针。
阅读全文