哈夫曼樹構造哈夫曼編碼
程序如下：#include<stdio.h>
#define MaxSize 50
typedef struct
{
char data; //結點值
int weight;//權重
int parent;//父結點
int left;//左結點
int right; //右結點
}huffnode;
typedef struct
{
char cd;
int start;
}huffcode;
void creahuffman(huffnode ht[],int n) // 構造哈夫曼樹
{
int i,k,l,r,m1,m2;
for(i=0;i<2*n-1;i++)
ht.parent=ht.left=ht.right=0;
for(i=n;i<2*n-1;i++)
{
m1=m2=32767; //l,r為最小權重的兩個結點位置
l=r=0;
for(k=0;k<i-1;k++)
if(ht.parent==0)
if(ht.weight<m1)
{
m2=m1;r=l;
m1=ht.weight;
l=k;
}
else if(ht.weight<m2)
{
m2=ht.weight;
r=k;
}
ht.parent=i;ht.parent=i;
ht.weight=ht.weight+ht.weight;
ht.left=l;ht.right=r;
}
}
void creahfcode(huffnode ht[],huffcode hcd[],int n) //求哈夫曼編碼
{
int i,f,c;
huffcode d;
for(i=0;i<n;i++)
{
d.start=n+1;c=i;
f=ht.parent;
while(f!=0)
{
if(ht.left==c)
d.cd[--d.start]='0';
else
d.cd[--d.start]='1';
c=f;f=ht.parent;
}
hcd=d;
}
}
void disphuffman(huffnode ht[],huffcode hcd[],int n) //輸出哈夫曼編碼
{
int i,k;
printf("輸出哈夫曼編碼：\n");
for(i=0;i<n;i++)
{
printf("%c:",ht.data);
for(k=hcd.start;k<=n;k++)
printf("%c",hcd.cd);
printf("\n");
}
}
void main()
{
int n=6;
huffnode ht;
huffcode hcd;
ht.data='a'; ht.data='b';
ht.data='c'; ht.data='d';
ht.data='e'; ht.data='f';
ht.weight=10; ht.weight=2;
ht.weight=6;ht.weight=4;
ht.weight=3;ht.weight=1;
creahuffman(ht,n);
creahfcode(ht,hcd,n);
disphuffman(ht,hcd,n);
}
牠是結點在左子樹上編碼就為0,在右子樹上就為1。
大蝦們能詳細解釋下嗎？我實在是不太理解是怎麼實現的。 呃……其实左子树用1右子树用0也可以倒是……就是编码和它相反，平均码长还是一样的……
举个例子吧：
比如有a，b，c，d，e共5个字符，每个字符在某篇文章中，且文章中只含这几个字符（这文章估计很2 - -|）它们出现的概率（即权值）分别为0.2，0.05，0.4，0.25，0.1，现在需要对它们进行2进制编码，原则是出现概率大的编码长度要短，且各个编码不能出现歧义（歧义即为某一个编码的前n个字符为另一个编码）。这个问题思路其实是这样的：
先选两个权值最小的，即b和e，将它们作为一棵树的两个结点，它们的父结点定义为f，那f的权值应该是0.05 + 0.1 = 0.15
再从a，c，d，f中选两个权值最小的（注意现在f是一棵树，其余都只有结点），选出来f和a，再次把二者合成为一颗新树，定义f与a的父结点为g，g的权值为0.15 + 0.2 = 0.35
再从c，d，g中选两个权值最小的……
……
最后会形成一种最优二叉树的结构……然后分别对每个结点的左右分支进行0，1编码，最后就可以得到从root到任意结点的编码
以上是程序的一般思路……
程序主要实现还是在选择2个最小权值子树和将二者合成为一个新子树上……啊，突然有点头晕 …… 我差不多忘记了,才有人回答, 以后复习时再看
页:
[1]