哈夫曼树及哈夫曼编码译码的实现（根据程序画流程图及对每句程序注释）

这是以前写的，可是我不想加注释了，Huffman编码其实原理很简单的，你自己好好学下吧，一句一句注释也太夸张了啊。

#include<string.h>

#include<stdlib.h>

#include<stdio.h>

int m,s1,s2

typedef struct {

unsigned int weight

unsigned int parent,lchild,rchild

}HTNode,*HuffmanTree

typedef char ** HuffmanCode

void Select(HuffmanTree HT,int n)

{

int i,j

for(i=1i<=ni++)

if(HT[i].parent==0)

{s1=i

break

}

for(j=i+1j<=nj++)

if(HT[j].parent==0)

{

s2=j

break

}

for(i=1i<=ni++)

{

if(HT[i].parent==0)

if(HT[s1].weight>HT[i].weight)

if(s2!=i)

s1=i

}

for(j=1j<=nj++)

{

if(HT[j].parent==0)

if(HT[s2].weight>HT[j].weight)

if(s1!=j)

s2=j

}

if(s1>s2)

{

int temp=s1

s1=s2

s2=temp

}

}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)

{

int i,j

char *cd

int p

int cdlen

if (n<=1) return

m = 2 * n - 1

HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode))

for (i=1i<=ni++)

{

HT[i].weight=w[i-1]

HT[i].parent=0

HT[i].lchild=0

HT[i].rchild=0

}

for (i=n+1i<=mi++)

{

HT[i].weight=0

HT[i].parent=0

HT[i].lchild=0

HT[i].rchild=0

}

//添加查看，便于调试

printf("构造过程显示：\n")

for(i=1i<=mi++)

printf("%4d%4d%4d%4d%4d\n",i,HT[i].weight, HT[i].parent,HT[i].lchild, HT[i].rchild)

system("pause")

for(i=n+1i<=mi++)

{

Select(HT,i-1)

HT[s1].parent = iHT[s2].parent = i

HT[i].lchild = s1HT[i].rchild = s2

HT[i].weight = HT[s1].weight + HT[s2].weight

//添加查看，便于调试

/*printf("s1=%d,s2=%d\n",s1,s2)

for(j=1j<=ij++)

printf("%d%4d%4d%4d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild)

system("pause")

*/

}

cd = (char *)malloc(n*sizeof(char))

p=m

cdlen=0

for(i=1i<=mi++)

HT[i].weight=0

while(p)

{

if(HT[p].weight==0)

{

HT[p].weight=1

if(HT[p].lchild!=0)

{

p=HT[p].lchild

cd[cdlen++]='0'

}

else if(HT[p].rchild==0)

{

HC[p]=(char *)malloc((cdlen+1)*sizeof(char))

cd[cdlen]='\0'

strcpy(HC[p],cd)

}

}

else if(HT[p].weight==1)

{

HT[p].weight=2

if(HT[p].rchild!=0)

{

p=HT[p].rchild

cd[cdlen++]='1'

}

}

else

{

HT[p].weight=0

p=HT[p].parent

--cdlen

}

}

}

int main()

{

HuffmanTree HT

HuffmanCode HC

int *w,n,i

printf("请输入节点数：\n")

scanf("%d",&n)

HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode))

w=(int *)malloc(n*sizeof(int))

printf("请输入节点的权值：\n")

for(i=0i<ni++)

scanf("%d",&w[i])

HuffmanCoding(HT,HC,w,n)

printf("输出编码：\n")

for(i=1i<=ni++)

printf("%2d(%4d):%s\n",i,w[i-1],HC[i])

return 0

system("pause")

}

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。

扩展资料

赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率

和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。

每次相

加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，

将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。

例如a7从左至右，由U至U″″，其码字为1000；

a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…

用赫夫曼编码所得的平均比特率为：Σ码长×出现概率

上例为：0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

可以算出本例的信源熵为2.61bit，二者已经是很接近了。

参考资料来源：百度百科-哈夫曼编码

属于数字压缩编码技术：

霍夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。下面引证一个定理，该定 理保证了按字符出现概率分配码长，可使平均码长最短。

� 定理：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平 均码字长度为最小。

� 现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 ： �

U： ( a1 a2 a3 a4 a5 a6 a7 )

0.20 0.19 0.18 0.17 0.15 0.10 0.01

� 给概率最小的两个符号a6与a7分别指定为“1”与“0”，然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为：

U′： ( a1 a2 a3 a4 a5 a6′ )

0.20 0.19 0.18 0.17 0.15 0.11

� 对a5与a′6分别指定“1”与“0”后，再作概率相加并重新按概率排序得

U〃：（0.26 0.20 0.19 0.18 0.17）…

� 直到最后得 U〃〃：（0.61 0.39）

� 分别给以“0”，“1”为止，如图4－4所示。}

� 霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。

� 例如a7从左至右，由U至U〃〃，其码字为0000；

� a6按践线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为0001…

� 用霍夫曼编码所得的平均比特率为：∑码长×出现概率

� 上例为：� 0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit

� 可以算出本例的信源熵为2.61bit，二者已经是很接近了。

---