Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

哈夫曼树0ms详细版

Posted by LXY5201314 at 2018-04-14 03:18:04 on Problem 1521
```#include<cstdio>
#include<cstring>
struct HuffTree
{
int weight;
int lchild,rchild;
int parent;
}hufftree[250];
int w[250];
int wpl(int i,int len)
{
if(hufftree[i].lchild==-1&&hufftree[i].rchild==-1)
return hufftree[i].weight*len;
else return wpl(hufftree[i].lchild,len+1)+wpl(hufftree[i].rchild,len+1);
}
void Select(int &s1,int &s2,int n)
{
s1=s2=0;
int i;
for(i=1;i<=n;i++)
{
if(hufftree[i].parent==-1)
if(s1==0)
{
s1=i;
}
else
{
s2=i;
break;
}
}
if(hufftree[s1].weight>hufftree[s2].weight)
{
int t=s1;
s1=s2;
s2=t;
}
for(i=i+1;i<=n;i++)
{
if(hufftree[i].parent==-1)
{
if(hufftree[i].weight<hufftree[s1].weight)
{
s2=s1;
s1=i;
}
else
if(hufftree[i].weight<hufftree[s2].weight)
{
s2=i;
}
}
}
}
void tree(int n)
{
int i,i1,i2,num;
for(i=1;i<=2*n-1;i++)
{
hufftree[i].parent=-1;
hufftree[i].lchild=-1;
hufftree[i].rchild=-1;
}
for(i=1;i<=n;i++)
hufftree[i].weight=w[i];
num=n;
for(i=n+1;i<=2*n-1;i++)
{
Select(i1,i2,num);
num++;
hufftree[i].weight=hufftree[i1].weight+hufftree[i2].weight;
hufftree[i1].parent=i;
hufftree[i2].parent=i;
hufftree[i].lchild=i1;
hufftree[i].rchild=i2;
}
}
int main()
{
char str[240];
int i,j,w1[240];
while(1)
{
scanf("%s",str);
if(strcmp(str,"END")==0)break;
int len=strlen(str);
memset(w1,0,sizeof(w1));
memset(w,0,sizeof(w));
for(int i=0;i<len;i++){
if(str[i]=='_')
w1[1]++;
else
w1[str[i]-'A'+2]++;
}
int k=1;
for(int i=1;i<=27;i++){
if(w1[i]){
str[k]=w1[i];
w[k]=w1[i];
k++;
}
}
if(k==2){
printf("%d %d 8.0\n",8*len,len);
continue;
}
k--;
struct HuffTree *ftree;
tree(k);
ftree=hufftree;
for(i=1;i<=2*k-1;i++)
if(hufftree[i].parent==-1)break;
int lenwpl=wpl(i,0);
printf("%d %d %0.1lf\n",len*8,lenwpl,len*8.0/lenwpl);
}
return 0;
}
```

Followed by:

User ID:
Title:

Content: