#include <iostream>
#include <string>
using namespace std;
#define N 30
int w[N];
string text;
typedef struct{
	char ch;
	int w,p,l,r;
}Node;
Node node[2*N];
int L_code[N];

void Coding(int m); 
void Coding(int m){
	int a,b; //记录当前权值最小两个节点的下标
	
	//生成哈夫曼树 
	for(int i=m+1;i<=2*m-1;i++)
		{
			//找到当前a,b 
			int min=INT_MAX,c;
			for(int j=1;j<i;j++)
				{
					if(node[j].p==0 && node[j].w!=0)
						{
							if(node[j].w<min)
								{
									min=node[j].w;
									a=j;
									c=j;
								}
						}
				}
			min=INT_MAX;
			for(int j=1;j<i;j++)
				{
					if(node[j].p==0 && node[j].w!=0 && j!=c)
						{
							if(node[j].w<min)
								{
									min=node[j].w;
									b=j;
								}
						}
				}
				
			node[a].p=i; node[b].p=i;
			node[i].l=a; node[i].r=b; node[i].w=node[a].w+node[b].w;

		 } 
		
}
void Length(int m);
void Length(int m){
	for(int i=1;i<=m;i++)
		L_code[i]=0;
	for(int i=1;i<=m;i++){
		int j;
		j=i;
		while(j!=2*m-1)   //不是0，是2*m-1
			{
				L_code[i]++;
				j=node[j].p;  //***
			}
	}
	
}

int main(){
	while(cin>>text){
		if(text=="END") break;
		//对w数组赋初值0 
		for(int i=1;i<=27;i++)
			w[i]=0;
		char n,m=0; //n为每组文本长度，m为字符种类数 
		n=text.length(); //或text.size();
		//统计文本中字符的权值 
		for(int i=0;i<n;i++)
			{
				if(text[i]=='_')
					w[27]++;
				else
					{
						w[text[i]-'A'+1]++;
					}
			}
		for(int i=1;i<=2*N;i++)
			{
				node[i].w =0;
				node[i].p =0;
				node[i].l =0;
				node[i].r =0;
			}
		for(int i=1;i<=26;i++)
			{
				if(w[i]!=0)
					{
						m++;
						node[m].ch = 'A'+i-1;
						node[m].w=w[i];
					}
			}
		if(w[27]!=0)
			{
				m++;
				node[m].ch = '_';
				node[m].w = w[27];
			}
		//*****不要忘了m==1，即只有一种字符的特殊情况！！！ 
		if(m==1) 
			{
				printf("%d %d %.1f\n",8*node[1].w,node[1].w,8*1.0);	
				continue;	
			 } 
		//*************初始化了叶节点
		
		//编码 
		Coding(m);
		
		//统计每个字符哈夫曼编码长度
		Length(m);
		
		int sum=0;
		for(int i=1;i<=m;i++)
			sum=sum+L_code[i]*node[i].w;
		printf("%d %d %.1f\n",8*n,sum,(8*1.0*n)/(1.0*sum));
		//或double(n*8/sum) 
	}
	
	
	
	return 0;
} 

• Re:始终是Runtime Error，老哥们看看咋回事 (2433) 20162430723 2018-06-21 14:56:55