时间:2021-05-19
我们设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息。根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为 2n-1 。HuffNode 结构中有 weight, lchild, rchild 和 parent 域。其中,weight 域保存结点的权值, lchild 和 rchild 分别保存该结点的左、右孩子的结点在数组 HuffNode 中的序号,从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中,可通过 parent 域的值来确定。初始时 parent 的值为 -1。当结点加入到树中去时,该结点 parent 的值为其父结点在数组 HuffNode 中的序号,而不会是 -1 了。
求叶结点的编码:
该过程实质上就是在已建立的哈夫曼树中,从叶结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的 0、1 序列,因此先得到的分支代码为所求编码的低位,后得到的分支代码为所求编码的高位码。我们可以设置一个结构数组 HuffCode 用来存放各字符的哈夫曼编码信息,数组元素的结构中有两个域:bit 和 start。其中,域 bit 为一维数组,用来保存字符的哈夫曼编码, start 表示该编码在数组 bit 中的开始位置。所以,对于第 i 个字符,它的哈夫曼编码存放在 HuffCode[i].bit 中的从 HuffCode[i].start 到 n 的 bit 位中。
复制代码 代码如下:
/*-------------------------------------------------------------------------
* Name: 哈夫曼编码源代码。
* 在 Win-TC 下测试通过
* 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
* 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
* 父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
*------------------------------------------------------------------------*/
#include <stdio.h>
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1
typedef struct
{
int bit[MAXBIT];
int start;
} HCodeType;
typedef struct
{
int weight;
int parent;
int lchild;
int rchild;
} HNodeType;
void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)
{
int i, j, m1, m2, x1, x2;
for (i=0; i<2*n-1; i++)
{
HuffNode[i].weight = 0;
HuffNode[i].parent =-1;
HuffNode[i].lchild =-1;
HuffNode[i].lchild =-1;
}
for (i=0; i<n; i++)
{
printf ("Please input weight of leaf node %d: \n", i);
scanf ("%d", &HuffNode[i].weight);
}
for (i=0; i<n-1; i++)
{
m1=m2=MAXVALUE;
x1=x2=0;
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
HuffNode[x1].parent = n+i;
HuffNode[x2].parent = n+i;
HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
HuffNode[n+i].lchild = x1;
HuffNode[n+i].rchild = x2;
printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);
printf ("\n");
}
}
int main(void)
{
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF], cd;
int i, j, c, p, n;
printf ("Please input n:\n");
scanf ("%d", &n);
HuffmanTree (HuffNode, n);
for (i=0; i < n; i++)
{
cd.start = n-1;
c = i;
p = HuffNode[c].parent;
while (p != -1)
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for (j=cd.start+1; j<n; j++)
{ HuffCode[i].bit[j] = cd.bit[j];}
HuffCode[i].start = cd.start;
}
for (i=0; i<n; i++)
{
printf ("%d 's Huffman code is: ", i);
for (j=HuffCode[i].start+1; j < n; j++)
{
printf ("%d", HuffCode[i].bit[j]);
}
printf ("\n");
}
getch();
return 0;
}
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下//哈夫曼树C语言实现#include#includetypedefstructHuf
本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下代码来自于《小甲鱼C++快速入门》主程序main.cpp#include"stdaf
前言本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。1.基本概念哈夫曼树(Huffman(H
本文实例讲述了基于C++实现的哈夫曼编码解码操作。分享给大家供大家参考,具体如下:哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:‘0'与‘1'
本文实例为大家分享了C++实现哈夫曼编码的具体代码,供大家参考,具体内容如下#include#include#include#includeusingnames