#include <iostream>
#include <cmath>
#include <cstring>
#define N 128
using namespace std;

struct HuffmanNode
{
    int weight;
    int parent;
    int lchild;
    int rchild;
    char ch;
};

HuffmanNode HT[300];  //存儲huffman樹
char HC[N][100];  //存儲huffman編碼
int fre[N];    //fre[]中存放對應字母的次數
char le[N];    //le數組存儲文章中出現的字母
int m, sum, total = 0;  //m為huffman數的結點總數，total為字符種類數, sum為文章中字符的總個數


//初始化字母出現頻率數組f[]
void InitFre()
{
    int i;

    for (i = 0; i < N; i++)
    fre[i] = 0;
}
//讀入文件，計算字母出現個數和頻率
void OpenFile()
{
    char ch;
    int i;

    freopen("Huffman.txt", "rb", stdin);
    while (scanf("%c", &ch) != EOF)   //讀入并計算字母個數
    {
        for (i = 0; i < total; i++) //判斷字母是否已經出現過
        {
            if (ch == le[i])    //字母已經出現過，頻數加一
            {
                fre[i]++;
                break;
            }
        }
        if (i == total)     //字母未出現過
        {
            fre[total]++;
            le[total++] = ch;
        }
    }
}
//函數功能：選擇兩個權值最小的結點
void Select(int &p1, int &p2, int n)
{
    int i, j;
    for (i = 1; i <= n; i++)    //p1初始化
    {
        if (HT[i].parent == -1)
        {
            p1 = i;
            break;
        }
    }
    for (j = i + 1; j <= n; j++)    //p2初始化
    {
        if (HT[j].parent == -1)
        {
            p2 = j;
            break;
        }
    }
    for (i = 1; i <= n; i++)    //選擇一個權值最小的給p1
        if ((HT[p1].weight > HT[i].weight) && (HT[i].parent == -1) && (p2 != i))    p1 = i;
    for (j = 1; j <= n; j++)    //選擇剩下權值最小的給p2
        if ((HT[p2].weight > HT[j].weight) && (HT[j].parent == -1) && (p1 != j))    p2 = j;
}
//存儲各個字符對應的huffman編碼
void Encoding()
{
    int c, p, i;    //c 和p 分別指示T 中孩子和雙親的位置
    char cd[total + 1];    //臨時存放編碼
    int start;     //指示編碼在cd中的位置
    cd[total] = '\0';    //編碼結束符
    for (i = 1; i <= total; i++)    //依次求葉子HT[i]的編碼
    {
        start = total;  //編碼起始位置的初值
        c = i;  //從葉子HT[i]開始上溯
        while ((p = HT[c].parent) != -1)    //p指向的點不是根結點
        {
            cd[--start] = (HT[p]. lchild == c)? '0' : '1';  //若HT[c]是HT[p]的左孩子，則生成代碼0，否則生成代碼1
            c = p; //繼續上溯
        }
        strcpy(HC[i], &cd[start]);  //將編碼復制到編碼表HC中
        printf("%c(%d): %s\n", HT[i].ch, fre[i - 1], HC[i]);    //輸出編碼表
    }
}
//將字母頻數作為權值建立huffman樹
void HuffmanCoding()
{
    int i, p1, p2;
    m = 2 * total - 1;
    for (i = 1; i <= total; i++)  //HT初始化
    {
        HT[i].weight = fre[i - 1];
        HT[i].parent = -1;
        HT[i].lchild = -1;
        HT[i].rchild = -1;
        HT[i].ch = le[i - 1];
    }
    for (i = total + 1; i <= m; i++)  //HT初始化
    {
        HT[i].weight = 0;
        HT[i].parent = -1;
        HT[i].lchild = -1;
        HT[i].rchild = -1;
        HT[i].ch = 0;
    }
    if(total == 1)  //如果只有一個字符，不需要建立huffman樹
    {
        HC[1][0] = '0';
        HC[1][1] = '\0';
        printf("%c(%d): %s\n", HT[1].ch, fre[0], HC[1]);    //輸出編碼表
        return;
    }
    for (i = total + 1; i <= m; i++)   // 建立huffman樹
    {
        Select(p1, p2, i - 1);  //選擇兩個最小的權值
        HT[p1].parent = i;
        HT[p2].parent = i;
        HT[i].lchild = p1;
        HT[i].rchild = p2;
        HT[i].weight = HT[p1].weight + HT[p2].weight;
    }
    Encoding(); //存儲各個字符對應的huffman編碼
}
//將文章按照huffman編碼壓縮
void EssayTranslate()
{
    freopen("Huffman.txt", "rb", stdin);
    freopen("Encode.txt", "wb", stdout);
    char ch;    //存放文章中的字符
    char te = 0;    //存放轉換后的字符
    int temp = 7;   //指示壓縮過的huffman編碼長度
    sum = 1;    //文章中出現過的字符個數
    while (scanf("%c", &ch) != EOF)   //將Huffman.txt中的字母編碼輸出到Huffman.txt中
    {
        int i;
        for (i = 1; i <= total; i++)    //查找字符的huffman編碼
        {
            if (ch == HT[i].ch)
                break;
        }
        int len = strlen(HC[i]);
        int j;
        for (j = 0; j < len; j++)   //將huffman編碼壓縮為一個字符儲存
        {
            if (HC[i][j] == '1')
                te = te | (1 << temp);
            temp--;
            if (temp == -1)  //八位huffman編碼壓縮為一個字符后輸出
            {
                printf("%c", te);
                te = 0;
                temp = 7;
            }
        }
        sum++;
    }
    if (temp != 7)  printf("%c", te);//如果最后的剩余編碼不足八位，輸出
}
//將壓縮后的文章解壓
void EssayDecode()
{
    freopen("Encode.txt", "rb", stdin);
    freopen("Decode.txt", "wb", stdout);
    char ch;    //指示壓縮文章中的字符
    char str[100];  //指示壓縮文章中字符對應的huffman編碼
    int flag = 1;   //指示已經轉換完的字符個數
    int pos = m, j = 0; //pos指示結點位置，j指示str中0、1的位置
    while (scanf("%c", &ch) != EOF)
    {
        int i;
        for (i = 7; i >= 0; i--)    //依次轉換壓縮后字符所代表的huffman編碼
        {
            if (ch & (1 << i))  //對應編碼為1，pos指向結點的右子樹
            {
                str[j++] = '1';
                pos = HT[pos].rchild;
            }
            else    //對應編碼為零，pos指向結點的左子樹
            {
                str[j++] = '0';
                pos = HT[pos].lchild;
            }
            if (HT[pos].lchild == -1 || pos == -1)   //如果已經到了huffman樹葉子的位置，輸出所代表的字符
            {
                str[j] = '\0';
                j = 0;
                int p;
                for(p = 1; p <= total; p++) //找到編碼str對應的字符輸出
                {
                    if(!strcmp(str, HC[p]))
                        break;
                }
                printf("%c", HT[p].ch);
                pos = m;
                flag++;
                if(flag == sum)  return;    //如果已經轉換了所有的字符，結束
            }
        }
    }
}

int main()
{
    InitFre();  //字母出現頻率數組fre初始化
    OpenFile();    //讀入文件，計算字母出現個數和頻率
    HuffmanCoding();    //將字母頻數作為權值建立huffman樹
    EssayTranslate();    //將文章按照huffman編碼壓縮
    EssayDecode();   //將壓縮后的文章解壓
    return 0;
}