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

哈夫曼树可用于构造使电文的编码总长最短的编码方案。具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn 作为叶结点，w1，w2，…，wn 作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0 和1 的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。

在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。

在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。例如表6.2 (d)的编码方案，字符A 的编码01 是字符B 的编码010 的前缀部分，这样对于代码串0101001，既是AAC 的代码，也是ABD 和BDA 的代码，因此，这样的编码不能保证译码的唯一性，我们称之为具有二义性的译码。

然而，采用哈夫曼树进行编码，则不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。

下面讨论实现哈夫曼编码的算法。实现哈夫曼编码的算法可分为两大部分：

（1）构造哈夫曼树；

（2）在哈夫曼树上求叶结点的编码。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶结点开始，沿结点的双亲链域回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。哈夫曼树 c语言我们可以设置一结构数组HuffCode 用来存放各字符的哈夫曼编码信息，数组元素的结构如下：

其中，分量bit 为一维数组，用来保存字符的哈夫曼编码，start 表示该编码在数组bit中的开始位置。所以，对于第i 个字符，它的哈夫曼编码存放在HuffCode[i].bit 中的从HuffCode[i].start 到n 的分量上。

哈夫曼编码算法描述如下。

#define MAXBIT 10 /*定义哈夫曼编码的最大长度*/

typedef struct {

int bit[MAXBIT];

int start;

}HCodeType;

void HaffmanCode ( )

{ /*生成哈夫曼编码*/

HNodeType HuffNode[MAXNODE];

HCodeType HuffCode[MAXLEAF],cd;

int i,j, c,p;

HuffmanTree (HuffNode ); /*建立哈夫曼树*/

for (i=0;i<n;i++) /*求每个叶子结点的哈夫曼编码*/

{ cd.start=n-1; c=i;

p=HuffNode[c].parent;

while(p!=0) /*由叶结点向上直到树根*/

{ 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++) /*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/

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