#if !defined(AFX_STDAFX_H__A87B32A8_6228_4C94_8D41_AE7E5FE3D9BC__INCLUDED_)
#define AFX_STDAFX_H__A87B32A8_6228_4C94_8D41_AE7E5FE3D9BC__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif 
#endif // !defined(AFX_STDAFX_H__A87B32A8_6228_4C94_8D41_AE7E5FE3D9BC__INCLUDED_)
#include <string.h>
#include <iostream.h>
typedef char *HuffmanCode;

class  HTNode
 {   public:
	int weight;
	int parent,lchild,rchild;
	HTNode( ):weight(0),parent(0),lchild(0),rchild(0){}
  };

void Select(HTNode * HT, int k ,int &s1,int &s2)
{ 
	int i;  s1=0;s2=0;
    for(i=1;i<=k;i++) 
		if(HT[i].parent ==0 && i!=s1 && i!=s2)
			if(HT[i].weight <HT[s1].weight ){
				if(HT[s1].weight <HT[s2].weight )
					s2=i;
				else
					s1=i;
			}
			else if (HT[i].weight <HT[s2].weight )
				s2=i;
}


void HuffmanCoding(HTNode *&HT, HuffmanCode *&HC, int *w,int n)
{
       
    int c,f,i,m,s1,s2,start;
	char *cd;
	HTNode *p;

	if(n<=1)return;
	m=2*n-1;
	HT=new HTNode[m+1]; 
	HT[0].weight =9999;
	for(p=&HT[1],i=1;i<=n;++i,++p,++w)
	    p->weight=*w;

	for(i=n+1;i<=m;++i)  
	 { 
		Select(HT,i-1,s1,s2);         
	    HT[s1].parent=i;
	    HT[s2].parent=i;
	    HT[i].lchild=s1;
	    HT[i].rchild=s2;
	    HT[i].weight=HT[s1].weight+HT[s2].weight;
	  }

       HC=new HuffmanCode[n+1];  
       cd=new char[n];  
       cd[n-1]='\0';        
       for(i=1;i<=n;i++)   
	   { 
		   start=n-1;
	       for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)                   
	       if(HT[f].lchild==c) cd[--start]='0';
	       else cd[--start]='1';
	       HC[i]=new char[n-start];
	       strcpy(HC[i],&cd[start]);
	   }
	delete cd;
}


int main(int argc, char* argv[])
{
   const int MAX=10;
   int myw[MAX],n,i;
   char mychar[MAX];
   cout<<"************哈夫曼編碼**************"<<endl;
   HuffmanCode *MyHC;
   HTNode* MyHT;
   do
   {
	   cout<<"請輸入字符集的個數(1<=n="<<MAX<<"):";
	   cin>>n;
   }while(!(n>=1&&n<=MAX));
   cout<<"請輸入字符集的各字符："<<endl;
   for(i=0;i<n;i++)
   {
	   cin>>mychar[i];
   } 
   cout<<"請輸入字符集的各字符對應的頻率："<<endl;
   for(i=0;i<n;i++)
   {
	   cin>>myw[i];
   }
   
   cout<<"**********其哈夫曼編碼為**************"<<endl;
   HuffmanCoding(MyHT,MyHC,myw,n);

   for (i=0;i<n;i++)
	   cout<< mychar[i] << " : "<<MyHC[i+1]<<endl;

	return 0;
}


/*
************哈夫曼編碼**************
請輸入字符集的個數(1<=n=10):5
請輸入字符集的各字符：
a d g j y
請輸入字符集的各字符對應的頻率：
45 67 98 23 07
**********其哈夫曼編碼為**************
a : 110
d : 10
g : 0
j : 1111
y : 1110
Press any key to continue
*/