#include <stdio.h>
#include <string.h>
#define MaxString 50
#define n 50
#define M 2*n-1

struct         /*定義結構體數組*/
{
    char letter;
    int num,weight,parent,Lchild,Rchild;
}Node[M+1],*node1,*node2;    /* 定義一個結構體數組,及兩個指向結構體類型的指針 */

struct
{
    char letter;
    char code[20];
}Code[n];                    /* 定義結構體數組用來存放每個字母的哈夫曼編碼 */

char String[50];             /* 定義一個字符串數組存儲輸入的字符串,用來轉換完整編碼使用 */

void Init(void)   /*初始化結構體數組*/
{
    int i = 1;
    node1 = &Node[1];       /* 初始化結構體指針 */
    node2 = &Node[2];
    for ( ; i < M+1; i++)             /* 初始化結構體中元素 */
    {
        Node[i].num = i;
        Node[i].letter = '0';
        Node[i].weight = 1;
        Node[i].parent = 0;
        Node[i].Lchild = 0;
        Node[i].Rchild = 0;
    }
}
    
int collect()      /*統計字符串輸入到結構體數組中*/
{
    char ch[MaxString];
    int i = 0,j,k = 0;
    printf("please Input The String:");
    gets(ch);                                 /* 讀入字符串 */
    for (i = 0;i<strlen(ch);i++)              /* 將字符串保存至String中 */
     String[i] = ch[i];
    for (i = 0; i < strlen(ch) ; i++)
     {
         j = 0;
        while ( ch[i] != Node[j+1].letter && j != k)        /*將字母統計存入表中*/
               { j++;}
        if ( ch[i] == Node[j+1].letter )
            (Node[j+1].weight)++;
         else
            {
                 Node[j+1].letter = ch[i];                   /* 與前面的均不相等則在最后寫入 */
                 k++;
             }
     }
     return k;
}


select(int k)                   /*在權值中選擇最小的兩個*/
{
    int i = 0,j = 0,length;
    length = k;
    while (node1->parent != 0)                              /* 初始化node1準備判斷 */
         node1 = &Node[++i];
    while (node2->parent != 0)                              /* 初始化node2準備判斷 */
      if (node1 != &Node[++j])
         node2 = &Node[j];
    
     for ( i = 1; i < length;i++)                                                           /* 通過兩次找最小的,找出兩個最小值 */
       if ( node1->weight > Node[i].weight && node2 != &Node[i] && Node[i].parent==0)
          node1 = &Node[i];
     for ( j =1; j < length; j++)
       if (node2->weight > Node[j].weight && node1 != &Node[j] && Node[j].parent==0)
          node2 = &Node[j];
}


CrateHuffmanTree(int k)           /*創建哈弗曼樹*/
{
    int i = 1;
    int length = k;
    for (i = length+1; i<= 2*length -1;i++)
    {
        select(length);
        Node[i].weight = node1->weight + node2->weight;
        Node[i].parent = 0;
        node1->parent = node2->parent = i;
        Node[i].Lchild = node1->num;
        Node[i].Rchild = node2->num;
    }
}


/*創建哈弗曼編碼*/
CraHufCode(int k)                            /*對單個字符進行編碼*/
{
    int length = k,i = 1,j = 1,m;
    char code[20];                                /* 定義臨時用來存儲反編碼的字符串數組 */
    for (i = 1;i <= length; i++ )                  /*只對葉子結點編碼*/
     {
         j = 0;
         node1 = &Node[i];                         /*初始化指針*/
         while(node1->parent != 0)
         {
           if( Node[node1->parent].Lchild == node1->num)         /* 構建反編碼 */
            code[j] = '0';
            else code[j] = '1';
            node1 = &Node[node1->parent];
            j++;
          }
          Code[i].letter = Node[i].letter;
            m = 0;
         while (j != 0)                                       /* 將編碼存儲到Code中 */
              {
                   Code[i].code[m] = code[j-1];
                 j--;                                         /* code從后往前移動 */
                 m++;                                         /* M從前往后 */

             }


      }
}
/*創建對應單詞的哈弗曼編碼*/
CrateCode(int k)
{
    int i=0,j=1,length = k;
    char FCode[100];
    for (i=0;i<50;i++)
      FCode[i]=0;
      if(length == 1)
          printf("0");
    else
{ for ( i = 0;i < strlen(String);i++)
        for (j = 1; j <= length; j++)
          if (String[i] == Node[j].letter)           /* 進行字母匹配 */
              strcat(FCode,Code[j].code);            /* 將編碼追加寫入Fcode */

    printf("The HuffmanCode of your String is :\n");

     puts(FCode);   }                               /* 輸出完整的哈弗曼編碼 */

    

}


DeCode(int k,char FCode[])        /*對輸入的哈弗曼編碼進行譯碼*/
{
    int length = k,i=0,j=0;
    if ( length == 1)
     for (j=0;j<Node[1].weight;j++)
        printf("%c",Node[1].letter);
else
{   while(i < strlen(FCode))
   {
      node1 = &Node[2*length-1];
      while(node1->Lchild != 0)
      {
        if(FCode[i] == '0')
         node1 = &Node[node1->Lchild];
         else
           node1 = &Node[node1->Rchild];
           i++;
      }
      putchar(Node[node1->num].letter);

}
}
}



    
int main(void)
{
    int length,i;
    char FCode[100];
    Init();
    length = collect();
    CrateHuffmanTree(length);
    CraHufCode(length);
    CrateCode(length);
    printf("please Input The Huffman Code:");
    gets(FCode);
    DeCode(length,FCode);
    getch();

}