#include <iostream>
using namespace std;
#if !defined(_HUFFMANTREE_H_)
#define _HUFFMANTREE_H_
/*
 * 哈夫曼樹結構
 */
class HuffmanTree
{
public:
  unsigned int Weight;
  unsigned int Parent;
  unsigned int lChild;
  unsigned int rChild;
};
typedef char **HuffmanCode;
/*
 * 從結點集合中選出權值最小的兩個結點
 * 將值分別賦給s1和s2
 */
void Select(HuffmanTree* HT,int Count,int *s1,int *s2)
{
  unsigned int temp1=0;
  unsigned int temp2=0;
  unsigned int temp3;
  for(int i=1;i<=Count;i++)
  {
    if(HT[i].Parent==0)
    {
      if(temp1==0)
      {
        temp1=HT[i].Weight;
        (*s1)=i;
      }
      else
      {
        if(temp2==0)
        {
          temp2=HT[i].Weight;
          (*s2)=i;
          if(temp2<temp1)
          {
            temp3=temp2;
            temp2=temp1;
            temp1=temp3;
            temp3=(*s2);
            (*s2)=(*s1);
            (*s1)=temp3;
          }
        }
        else
        {
          if(HT[i].Weight<temp1)
          {
            temp2=temp1;
            temp1=HT[i].Weight;
            (*s2)=(*s1);
            (*s1)=i;
          }
          if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
          {
            temp2=HT[i].Weight;
            (*s2)=i;
          }
        }
      }
    }
  }
}
/*
 * 霍夫曼編碼函數
 */
void HuffmanCoding(HuffmanTree * HT,
          HuffmanCode * HC,
          int *Weight,
          int Count)
{
  int i;
  int s1,s2;
  int TotalLength;
  char* cd;
  unsigned int c;
  unsigned int f;
  int start;
  if(Count<=1) return;
  TotalLength=Count*2-1;
  HT = new HuffmanTree[(TotalLength+1)*sizeof(HuffmanTree)];
  for(i=1;i<=Count;i++)
  {
    HT[i].Parent=0;
    HT[i].rChild=0;
    HT[i].lChild=0;
    HT[i].Weight=(*Weight);
    Weight++;
  }
  for(i=Count+1;i<=TotalLength;i++)
  {
    HT[i].Weight=0;
    HT[i].Parent=0;
    HT[i].lChild=0;
    HT[i].rChild=0;
  }
  //建造哈夫曼樹
  for(i=Count+1;i<=TotalLength;++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)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
  cd = new char[Count*sizeof(char)];
  cd[Count-1]='\0';
  for(i=1;i<=Count;++i)
  {
    start=Count-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 [(Count-start)*sizeof(char)];
      strcpy((*HC)[i], &cd[start]);
    }
  }
  delete [] HT;
  delete [] cd;
}
/*
 * 在字符串中查找某個字符
 * 如果找到，則返回其位置
 */
int LookFor(char *str, char letter, int count)
{
  int i;
  for(i=0;i<count;i++)
  {
    if(str[i]==letter) return i;
  }
  return -1;
}
void OutputWeight(char *Data,int Length,
         char **WhatLetter,
         int **Weight,int *Count)
{
  int i;
  char* Letter = new char[Length];
  int* LetterCount = new int[Length];
  int AllCount=0;
  int Index;
  int Sum=0;
  float Persent=0;
  for(i=0;i<Length;i++)
  {
    if(i==0)
    {
      Letter[0]=Data[i];
      LetterCount[0]=1;
      AllCount++;
    }
    else
    {
      Index=LookFor(Letter,Data[i],AllCount);
      if(Index==-1)
      {
        Letter[AllCount]=Data[i];
        LetterCount[AllCount]=1;
        AllCount++;
      }
      else
      {
        LetterCount[Index]++;
      }
    }
  }
  for(i=0;i<AllCount;i++)
  {
    Sum=Sum+LetterCount[i];
  }
  (*Weight) = new int[AllCount];
  (*WhatLetter) = new char[AllCount];
  for(i=0;i<AllCount;i++)
  {
    Persent=(float)LetterCount[i]/(float)Sum;
    (*Weight)[i]=(int)(1000*Persent);
    (*WhatLetter)[i]=Letter[i];
  }
  (*Count)=AllCount;
  delete [] Letter;
  delete [] LetterCount;
}
#endif
void main()
{
  HuffmanTree * HT = NULL;
  HuffmanCode HC;
  char Data[100];
  char *WhatLetter;
  int *Weight;
  int Count;
  cout<<"請輸入一行文本數據:"<<endl;
  cin>>Data;
  cout<<endl;
  OutputWeight(Data,strlen(Data),
    &WhatLetter,
    &Weight,
    &Count);
  HuffmanCoding(HT, &HC, Weight, Count);
  cout<<"字符 出現頻率 編碼結果"<<endl;
  for(int i = 0; i<Count; i++)
  {
    cout<<WhatLetter[i]<<"   ";
    cout<<Weight[i]/1000.0<<"%\t";
    cout<<HC[i+1]<<endl;
  }
  cout<<endl;
}