#include<iostream>
#include<string>
using namespace std;
class hufTree
{
public:
    int weight;
    int flag;
    int parent;
    int lchild;
    int rchild;
};
class leafnode 
{
public:
    int bit[10];
    int start;
    char leaf;
};
void huf(char cha[],int m[],int
n)/*m[]存放每個字符出現的頻率,cha[]存放輸入的字符*/
{
    int i,j,m1,m2,x1,x2,c,p;
    hufTree *huffnode=new hufTree[2*n-1];
    leafnode *huffcode=new leafnode[n],cd;
    for(i=0;i<2*n-1;i++)
    {
        huffnode[i].weight=0;
        huffnode[i].parent=0;
        huffnode[i].flag=0;
        huffnode[i].lchild=-1;
        huffnode[i].rchild=-1;
    }
    for(i=0;i<n;i++)
    {
        huffnode[i].weight=m[i];
        huffcode[i].leaf=cha[i];
    }
    for(i=0;i<n-1;i++)
    {
        m1=m2=10000000;
        x1=x2=0;
        for(j=0;j<n+i;j++)
        {
            if(huffnode[j].weight<=m1&&huffnode[j].flag==0)
            {
                m2=m1;
                x2=x1;
                m1=huffnode[j].weight;
                x1=j;
            }
            else if(huffnode[j].weight<=m2&&huffnode[j].flag==0)
            {
                m2=huffnode[j].weight;
                x2=j;
            }
        }
        huffnode[x1].parent=n+i;
        huffnode[x2].parent=n+i;
        huffnode[x1].flag=1;
        huffnode[x2].flag=1;
        huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;
        huffnode[n+i].lchild=x1;
        huffnode[n+i].rchild=x2;
    }
    for(i=0;i<n;i++)
        {
            cd.start=n-1;
            c=i;
            p=huffnode[c].parent;
            while(p!=0)
            {
                if(huffnode[p].lchild==c)
                    cd.bit[cd.start]=0;
                else
                    cd.bit[cd.start]=1;
                cd.start--;
                c=p;
                p=huffnode[c].parent;
            }
            cout<<huffcode[i].leaf<<":";
            for(j=cd.start+1;j<n;j++)
            {
                huffcode[i].bit[j]=cd.bit[j];
                cout<<cd.bit[j];
            }
            cout<<endl;
            huffcode[i].start=cd.start;
    }
    delete[] huffcode;
    delete[] huffnode;
}
void main()
{
    string str;
    int i=0,j,n,m[100],h,k=0;
    char cha[100];
    cout<<"please input a string:"<<endl;
    cin>>str;
    n=str.length();
    cout<<"the total numbers of the str is : "<<n<<"個"<<endl;
    for(i=0;i<n;i++)
    {
        j=0;h=0;
        while(str[i]!=str[j])
            j++;
        if(j==i)
        {
        cha[k]=str[i];
        cout<<"char "<<cha[k]<<" appears ";
        }
        else
            continue;
        for(j=i;j<n;j++)
        {
            if(str[i]==str[j])
                h++;
        }
        cout<<h<<" times"<<endl;
        m[k]=h;
        k++;
    }
    cout<<"the huffmancode of every char is :"<<endl;
    huf(cha,m,k);
    
}