博主：👍不许代码码上红
欢迎：🐋点赞、收藏、关注、评论。
格言：大鹏一日同风起，扶摇直上九万里。
马村ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为创新互联公司的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：18980820575（备注：SSL证书合作）期待与您的合作！ 文章目录- 一、定义结构
- 1.1 定义结点权值的数据类型
- 1.2 定义单个结点信息
- 1.3 字符指针数组中存储的元素类型
- 二、找出权值最小的两个值
- 三、构造哈夫曼树
- 四、计算哈夫曼编码
- 五、主函数
- 六、运行结果
一、定义结构
一个哈夫曼树中的结点，要包含三个信息：权值、父节点、孩子节点。
1.1 定义结点权值的数据类型
代码
typedef double DataType;
1.2 定义单个结点信息
代码
typedef struct HTNode
{DataType weight;
int parent;
int lc, rc;
}*HuffmanTree;
**
1.3 字符指针数组中存储的元素类型
**
代码
typedef char** HuffmanCode;
二、找出权值最小的两个值
代码
void Select(HuffmanTree& HT, int n, int& s1, int& s2)
{int min;
//找第一个最小值
for (int i = 1; i<= n; i++)
{if (HT[i].parent == 0)
{ min = i;
break;
}
}
for (int i = min + 1; i<= n; i++)
{if (HT[i].parent == 0 && HT[i].weight< HT[min].weight)
min = i;
}
s1 = min; //第一个最小值给s1
//找第二个最小值
for (int i = 1; i<= n; i++)
{if (HT[i].parent == 0 && i != s1)
{ min = i;
break;
}
}
for (int i = min + 1; i<= n; i++)
{if (HT[i].parent == 0 && HT[i].weight< HT[min].weight && i != s1)
min = i;
}
s2 = min; //第二个最小值给s2
}
三、构造哈夫曼树
代码
void CreateHuff(HuffmanTree& HT, DataType* w, int n)
{int m = 2 * n - 1; //哈夫曼树总结点数
HT = (HuffmanTree)calloc(m + 1, sizeof(HTNode)); //开m+1个HTNode，因为下标为0的HTNode不存储数据
for (int i = 1; i<= n; i++)
{HT[i].weight = w[i - 1]; //赋权值给n个叶子结点
}
for (int i = n + 1; i<= m; i++) //构建哈夫曼树
{//选择权值最小的s1和s2，生成它们的父结点
int s1, s2;
Select(HT, i - 1, s1, s2); //在下标为1到i-1的范围找到权值最小的两个值的下标，其中s1的权值小于s2的权值
HT[i].weight = HT[s1].weight + HT[s2].weight; //i的权重是s1和s2的权重之和
HT[s1].parent = i; //s1的父亲是i
HT[s2].parent = i; //s2的父亲是i
HT[i].lc = s1; //左孩子是s1
HT[i].rc = s2; //右孩子是s2
}
//打印哈夫曼树中各结点之间的关系
printf("哈夫曼树为:>\n");
printf("下标 权值 父结点 左孩子 右孩子\n");
printf("0 \n");
for (int i = 1; i<= m; i++)
{printf("%-4d %-6.2lf %-6d %-6d %-6d\n", i, HT[i].weight, HT[i].parent, HT[i].lc, HT[i].rc);
}
printf("\n");
}
四、计算哈夫曼编码
从根节点开始向下走往左为0，往右1。走到对应的字符的路径就是该字符的哈夫曼编码
代码
void HuffCoding(HuffmanTree& HT, HuffmanCode& HC, int n)
{HC = (HuffmanCode)malloc(sizeof(char*) * (n + 1)); //开n+1个空间，因为下标为0的空间不用
char* code = (char*)malloc(sizeof(char) * n); //辅助空间，编码最长为n(最长时，前n-1个用于存储数据，最后1个用于存放'\0')
code[n - 1] = '\0'; //辅助空间最后一个位置为'\0'
for (int i = 1; i<= n; i++)
{int start = n - 1; //每次生成数据的哈夫曼编码之前，先将start指针指向'\0'
int c = i; //正在进行的第i个数据的编码
int p = HT[c].parent; //找到该数据的父结点
while (p) //直到父结点为0，即父结点为根结点时，停止
{ if (HT[p].lc == c) //如果该结点是其父结点的左孩子，则编码为0，否则为1
code[--start] = '0';
else
code[--start] = '1';
c = p; //继续往上进行编码
p = HT[c].parent; //c的父结点
}
HC[i] = (char*)malloc(sizeof(char) * (n - start)); //开辟用于存储编码的内存空间
strcpy(HC[i], &code[start]); //将编码拷贝到字符指针数组中的相应位置
}
free(code); //释放辅助空间
}
五、主函数
代码
int main()
{int n = 0;
printf("请输入数据的个数：>");
scanf("%d", &n);
DataType* w = (DataType*)malloc(sizeof(DataType) * n);
if (w == NULL)
{printf("malloc fail\n");
exit(-1);
}
printf("请输入数据:>");
for (int i = 0; i< n; i++)
{scanf("%lf", &w[i]);
}
HuffmanTree HT;
CreateHuff(HT, w, n); //构建哈夫曼树
free(w);
return 0;
}
六、运行结果
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
文章标题：【C语言】哈夫曼树，再来一次解剖-创新互联
文章地址：
http://cdkjz.cn/article/dopgjh.html
