哈夫曼
以7个权值：7，5，1，4，8，10，20为例，构造Huffman树。class HaffNode
{
int weight;
int flag;
int parent;
int leftChild;
int rightChild;
}
class Code
{
int MaxN =100 ;
int bit[]=new int[MaxN];
int start;
int weight;
}
public class H{
int MaxValue =10000 ;
public void Haffman(int weight[], int n ,HaffNode haffTree[])
{
int i,j,m1,m2,x1,x2;
for(i=0;i <2*n-1;i++)
{
haffTree[i]=new HaffNode();
if(i<n)haffTree[i].weight=weight[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
}
for(i=0;i <n-1;i++)
{
m1=m2=MaxValue;
x1=x2=0;
for(j=0;j <n+i;j++)
{
if(haffTree[j].weight <m1&&haffTree[j].flag==0)
{
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
}
else if(haffTree[j].weight <m2&&haffTree[j].flag==0)
{
m2=haffTree[j].weight;
x2=j;
}
}
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+1].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].leftChild=x2;
}
}
public void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
{
Code cd=new Code();
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd.start=n-1;
cd.weight=haffTree[i].weight;
child=i;
parent=haffTree[child].parent;
while(parent !=-1)
{
if(haffTree[parent].leftChild==child)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
child=parent;
parent=haffTree[child].parent;
}
haffCode[i]=new Code();
for(j=cd.start+1;j <n;j++)
haffCode[i].bit[j]=cd.bit[j];
haffCode[i].start=cd.start+1;
haffCode[i].weight=cd.weight;
}
}
public static void main(String args[])
{
int i,j,n=7;
int MaxN =100 ;
H h=new H();
int weight[]={7,5,1,4,8,10,20};
HaffNode myHaffTree[]=new HaffNode[2*n+1];
Code myHaffCode[]=new Code[n];
if(n>MaxN)
{
System.out.print("out\n");
System.exit(0);
}
h.Haffman(weight,n,myHaffTree);
h.HaffmanCode(myHaffTree,n,myHaffCode);
for(i=0;i <n;i++)
{
System.out.print("Weight="+myHaffCode[i].weight+"Code=");
for(j=myHaffCode[i].start;j <n;j++)
System.out.print(myHaffCode[i].bit[j]);
System.out.print("\n");
}
}
}
编译结果：
Weight=7Code=1110
Weight=5Code=11110
Weight=1Code=111111
Weight=4Code=111110
Weight=8Code=110
Weight=10Code=10
Weight=20Code=0
Process completed.
结果里的7和8应该是平行的 可是他们的编码却相差一位？ 哪位高人可以指点一下？
