#include <iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<iomanip>
#pragma warning(disable : 4996) 

using namespace std;

typedef struct
{
    int weight;
    int parent, lchild, rchild;
} htnode, * huffmantree;

typedef char** huffmancode;
typedef char* huffmancoder;

void select(huffmantree ht, int i, int& s1, int& s2)
{
    int w1 = 0, w2 = 0;
    for (int j = 1; j <= i; j++)
    {
        if (ht[j].parent == 0)
        {
            if (w1 == 0)
            {
                w1 = ht[j].weight;
                s1 = j;
            }
            else if (w2 == 0)
            {
                w2 = ht[j].weight;
                s2 = j;
                if (w1 > w2)
                {
                    int t = w1;
                    w1 = w2;
                    w2 = t;
                    t = s1;
                    s1 = s2;
                    s2 = t;
                }

            }
            else if (ht[j].weight < w2)
            {
                if (ht[j].weight < w1)
                {
                    w2 = w1;
                    s2 = s1;
                    w1 = ht[j].weight;
                    s1 = j;
                }
                else
                {
                    w2 = ht[j].weight;
                    s2 = j;
                }
            }
        }

    }
    if (s1 > s2)
    {
        int t = s1;
        s1 = s2;
        s2 = t;
    }
}

void puttree(huffmantree ht, int n)
{

    for (int i = 1; i <= n; i++)
    {
        cout << setw(8) << ht[i].weight
            << setw(8) << ht[i].parent
            << setw(8) << ht[i].lchild
            << setw(8) << ht[i].rchild << endl;
    }
    cout << "--------------------------------" << endl;
}
void putcode(huffmancode hc, int n)
{
    cout << "Huffman tree编码：" << endl;
    for (int i = 1; i <= n; i++)
    {
        cout << i << "   " << hc[i] << endl;
    }
    cout << "--------------------------------" << endl;
}

void huffmancoding(huffmantree& ht, huffmancode& hc, int* w, int n)
{
    if (n <= 1)
        return;
    int m = 2 * n - 1;
    ht = new htnode[m + 1];
    huffmantree p = ht;
    int i = 1;
    for (; i <= n; i++, w++)
    {
        p[i].weight = *w;
        p[i].parent = 0;
        p[i].lchild = 0;
        p[i].rchild = 0;
    }

    for (; i <= m; i++)
    {
        p[i].weight = 0;
        p[i].parent = 0;
        p[i].lchild = 0;
        p[i].rchild = 0;
    }

    cout << "Huffman tree的存储格式(初始状态）：" << endl;
    puttree(ht, m);

    for (int i = n + 1; i <= m; i++)
    {
        int s1, s2;
        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;
    }

    cout << "Huffman tree的存储格式（终止状态） ：" << endl;
    puttree(ht, m);

    hc = new huffmancoder[n + 1];
    char* cd = new char[n];
    cd[n - 1] = '\0';
    for (int i = 1; i <= n; i++)
    {
        int start = n - 1;
        int f = ht[i].parent;
        for (int c = i; 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;

    putcode(hc, n);

}

void codemodal(huffmantree ht, char* code, int m)
{
    int ch = m, j = 0;
    int quan[100], xun[100];
    for (int i = 0; code[i] != '\0'; i++)
    {

        if (ht[ch].lchild == 0 && ht[ch].rchild == 0)
        {
            quan[j] = ht[ch].weight;
            xun[j] = ch;
            j++;
            ch = m;
            i--;
        }
        else if (code[i] == '0')
            ch = ht[ch].lchild;
        else
            ch = ht[ch].rchild;
    }
    int i = 0;
    cout << "解码后对应的序号：" << endl;
    while (i < j)
    {
        cout << xun[i] << " ";
        i++;
    }
    cout << endl;
    cout << "解码后对应的权值：" << endl;
    i = 0;
    while (i < j)
    {
        cout << quan[i] << " ";
        i++;
    }
}

int main()
{
    huffmantree ht;
    huffmancode hc;
    int* w;
    int n;
    cout << "请输入Huffman tree的大小：" << endl;
    cin >> n;
    w = new int[n + 1];
    cout << "请输入Huffman tree的权值：" << endl;

    int i = n;
    int* p = w;
    while (i--)
    {
        cin >> *p;
        p++;
    }

    huffmancoding(ht, hc, w, n);

    char* code;
    int l;
    cout << "请输入01编码的长度：" << endl;
    cin >> l;
    w = new int[l + 1];
    cout << "请输入01编码集：" << endl;
    i = 0;
    code = new char[l + 1];
    char* q = code;
    while (i != l)
    {
        cin >> q[i];
        i++;
    }
    q[i] = '\0';
    codemodal(ht, code, 2 * n - 1);

    return 0;
}