编写一个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树,取树林中权值最小的两棵树T0,T1,作为左右子树合并为一棵新的二叉树TT,权值为左右子树的和,将TT有序插入树林。注意!!:若树林中有树结点的权值与TT相同,则TT应插入到其后!
时间: 2023-06-25 18:04:46 浏览: 15
以下是createHTree函数的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_CHAR 128 // ASCII码表中最大字符数
struct tnode {
char c; // 字符
int weight; // 权值
struct tnode *left; // 左子树
struct tnode *right; // 右子树
};
int Ccount[MAX_CHAR]; // 存放字符出现次数的全局数组
// 创建一个新的树节点
struct tnode* createNode(char c, int weight) {
struct tnode *node = (struct tnode*)malloc(sizeof(struct tnode));
node->c = c;
node->weight = weight;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入新的树节点到树林中
void insertTree(struct tnode **T, int *m, struct tnode *newTree) {
int i;
for (i = *m - 1; i >= 0; i--) {
if (newTree->weight < T[i]->weight || (newTree->weight == T[i]->weight && newTree->c < T[i]->c)) {
T[i + 1] = T[i];
} else {
break;
}
}
T[i + 1] = newTree;
(*m)++;
}
// 构造Huffman树
struct tnode* createHTree() {
struct tnode *T[MAX_CHAR]; // 树林
int m = 0; // 树林中树的数量
// 构造树林
int i;
for (i = 0; i < MAX_CHAR; i++) {
if (Ccount[i] != 0) {
struct tnode *node = createNode(i, Ccount[i]);
insertTree(T, &m, node);
}
}
// 合并树林中的树
while (m > 1) {
struct tnode *T0 = T[0];
struct tnode *T1 = T[1];
struct tnode *TT = createNode('\0', T0->weight + T1->weight);
TT->left = T0;
TT->right = T1;
insertTree(T, &m, TT);
for (i = 2; i < m; i++) {
T[i - 1] = T[i];
}
m--;
}
return T[0]; // 返回Huffman树的根节点
}
```
使用示例:
```c
int main() {
// 假设字符串为"hello, world!"
char str[] = "hello, world!";
int len = strlen(str);
int i;
for (i = 0; i < len; i++) {
Ccount[str[i]]++;
}
struct tnode *root = createHTree(); // 生成Huffman树
// TODO: 对生成的Huffman树进行后续处理,如编码、解码等操作
return 0;
}
```
相关推荐













