#include<iostream>
#include<algorithm>
using namespace std;

template<class T>
class node
{
	public:
		node(){left=right=NULL;}
	T data;
	node<T>*left,*right;
	bool operator <(node<T>&l){return data<l.data;}
	bool operator <=(node<T>&l){return data<=l.data;}
	bool operator >(node<T>&l){return data>l.data;}
	operator T (){ return data;}
};


class frequency
{
public:
	int i;
	char c;
	bool operator <(frequency&l)
	{
		return i<l.i;
	}
   operator int (){ return i;}
    bool operator =(frequency&l)
    {
	   i=l.i;
	   c=l.c;
	   return true;
    }
	 frequency operator +(frequency&l)
	 {
		 frequency x;
		 x.i=i+l.i;
	   return x; 
	 }

};

template<class T>
class minheap
{
public:
   minheap(int n)
   {
     array=new node<T>*[n+1];
	 len=0;
	}

   int length(){return len;}
   //bool isempty(){return len==0;}
   //添加
   void insert(node<T>*& e)
   {
	  len++;
	  int i=len;
	  while(i!=1&&*e<*array[i/2])
	  {
		array[i]=array[i/2];
		i/=2;
	  }
    	array[i]=e;
   }
   //删除
   void delet(node<T>* &x)
   {
	   x=array[1];
      node<T> *y=array[len--];
      int i=1;
      int ch=2,fa=1;
      while(ch<=len)
	  {
	   if(ch<len&&*array[ch]>*array[ch+1]) 
		   ch++;
	   if(*y<=*array[ch]) break;
	   array[fa]=array[ch];
	   fa=ch;
	   ch*=2;
	  }
      array[fa]=y;
   }

public:
	node<T> **array;
	int len;
};

template<class T>
class hmtree
{
   public:
	   hmtree(int n)
	   {
		   root=NULL; 
		   num=new frequency[n];
		   len=0;
	   }
	   node<T>* maketree(T a[],int n)
	   {		   
		   node<T> *x,*y;
		   minheap<T> heap(n);
		   for(int i=0;i<n;i++)
		   {
			   node<T>*temp=new node<T>;
			   temp->data=a[i];
			   heap.insert(temp);
		   }
		   
		   while(heap.length()!=1)
		   {
             heap.delet(x);
			 heap.delet(y);
			 node<T>*z=new node<T>;
			 z->data.i=x->data.i+y->data.i;
			 z->left=y;
			 z->right=x;
			 heap.insert(z);
		   }
		   heap.delet(root);
		   return root;
	   }
	  frequency* hmtree_code_len(node<T>*ro,int count)
	   {
	       if(ro==NULL) 
		   {
			   return num;
		   }
		   count++;
		   if(ro->left==NULL&&ro->right==NULL)
		   {
			   num[len].c=ro->data.c;
			   num[len++].i=count-1;
			   return num;
		   }
		   else //有一个子节点为空
		   {
		    hmtree_code_len(ro->left,count);
		    hmtree_code_len(ro->right,count);

		   	  if(ro->left==NULL||ro->right==NULL)
			  {
				num[len].c=ro->data.c;
				num[len++].i=count-1;
			  }			
		   }
		   return num;
	   }
	
	  private:
	   frequency *num;
	   int len;
	   node<T>*root;
};


bool cmp1(frequency&l1,frequency&l2)
{
	return int(l1.c)>int(l2.c);
}
bool cmp2(frequency&l1,frequency&l2)
{
	return l1.i>l2.i;
}

int main()
{
	char ch[100000];
	while(cin>>ch&&strcmp(ch,"END")!=0)
	{
		frequency letter[27];
		int i;
		for(i=0;i<27;i++)
		{
			letter[i].i=0;
			letter[i].c='A'+i;
		}
		int other=0;
		for(i=0;i<strlen(ch);i++)
		{
			if(ch[i]!='_')
			 letter[ch[i]-'A'].i++;
			else other++;
		}
        sort(letter,letter+26,cmp2);
		for(i=0;i<26&&letter[i].i!=0;i++);
		if(i==1) 
		{
			printf("%d %d %0.1f\n",letter[0].i*8,letter[0].i,float(letter[0].i*8)/float(letter[0].i));
			continue;
		}
		letter;
		if(other!=0)
		{
			letter[i].i=other;
			letter[i++].c='_';
		}

		letter;
		int len=i;

		hmtree<frequency> tree(len);
		node<frequency>* root;
		root=tree.maketree(letter,len);		
        frequency *num=tree.hmtree_code_len(root,0);
        sort(num,num+len,cmp1);
		num;
		sort(letter,letter+len,cmp1);
        letter;
	
		int sum=0;
		for(i=0;i<len;i++)
			if(letter[i].c==num[i].c)
			   sum+=letter[i].i*num[i].i;
			else cout<<"error"<<endl;
		len=strlen(ch)*8;

		printf("%d %d %0.1f\n",len,sum,float(len)/float(sum));
	}
	return 0;

}

• 你这个有问题 (16) niuniu2006 2012-04-11 19:07:31