哈夫曼树 c语言_哈夫曼树的构造c语言_switch语句举例(2)

构造哈夫曼树时，首先将由n 个字符形成的n 个叶结点存放到数组HuffNode 的前n个分量中，然后根据前面介绍的哈夫曼方法的基本思想，不断将两个小子树合并为一个较大的子树，每次构成的新子树的根结点顺序放到HuffNode 数组中的前n 个分量的后面。

下面给出哈夫曼树的构造算法。

#define MAXVALUE 10000 /*定义最大权值*/

#define MAXLEAF 30 /*定义哈夫曼树中叶子结点个数*/

#define MAXNODE MAXLEAF*2-1

typedef struct {

int weight;

int parent;

int lchild;

int rchild;

}HNodeType;

void HaffmanTree(HNodeType HuffNode [ ])

{/*哈夫曼树的构造算法*/

int i,j,m1,m2,x1,x2,n;

scanf(“%d”,&n); /*输入叶子结点个数*/

for (i=0;i<2*n-1;i++) /*数组HuffNode[ ]初始化*/

{ HuffNode[i].weight=0;

HuffNode[i].parent=-1;

HuffNode[i].lchild=-1;

HuffNode[i].rchild=-1;

}

for (i=0;i<n;i++) scanf(“%d”,&HuffNode[i].weight); /*输入n 个叶子结点的权值*/

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;

}

}

算法6.25

3．哈夫曼树在编码问题中的应用

在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1 组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D 四种字符，若这四种字符采用表6.2 (a)所示的编码，则电文的代码为000010000100100111 000，长度为21。在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短，显然，这种编码方案产生的电文代码不够短。表6.2 (b)所示为另一种编码方案，用此编码对上述电文进行编码所建立的代码为00010010101100，长度为14。在这种编码方案中，四种字符的编码均为两位，是一种等长编码。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。如当字符A，B，C，D 采用表6.2 (c)所示的编码时，上述电文的代码为0110010101110，长度仅为13。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-22256-2.html