哈弗曼编码实现.pdf

: .

{ char ch;
int num[256]={ 0 };n=0;
freopen( "", "r", stdin);// 读文本文件
while( (ch=getchar()) != EOF )
num[ch]++;
for( int i=0; i<=255; i++ )
{ if( num[i] )
{ n++;
ht[n].w=num[i];
hc[n].ch=i;
}
}
}
void select1( int t, int *s1, int *s2)// 用两个数来记录没有在树上的最小的两个值，从而进一
步生成树。
{ int w1,w2;
w1=w2=INF;
for( int i=1; i<=t; i++ )
if( ht[i].parent==0 )
if( ht[i].w<w1 )
{ w2=w1;
*s2=*s1;w1=ht[i].w;
*s1=i;
}
else if( ht[i].w<w2 )
{ w2=ht[i].w;
*s2=i;
}
}
void createHufTreeHuCode()
{ int i, s1, s2;
int child, parent;
root=2*n-1;
for( i=n+1; i<=root; i++)
{ select1(i-1, &s1, &s2 );
ht[i].w=ht[s1].w+ht[s2].w;
ht[i].lch=s1;
ht[i].rch=s2;
ht[s1].parent=ht[s2].parent=i;
}
for( i=1; i<=n; i++)
{ child=i;while( child != root )
{ parent=ht[child].parent;
if( ht[parent].lch==child )
hc[i].code[hc[i].start++]=0;
else
hc[i].code[hc[i].start++]=1;
child=parent;
}
}
}
void txt2code()
{
int i,j,m;
char ch1[N+1]={0};
freopen( "", "r", stdin);
for ( int k=1;k<N+1;k++)
{
scanf("%c",&ch1[k]);
}
for( j=1,i=1; i<=N; i++)
{ if (ch1[i]==0){
break;
}
while (ch1[i]!=hc[j].ch)
{
if (hc[j].ch==0)
{continue;
}
j++;
}
for( m=hc[j].start-1; m>=0; m--)
printf("%d", hc[j].code[m]);
j=1;
}
}
int main()
{
readData();
createHufTreeHuCode();freopen("", "w", stdout)