// 文件中有通过QT实现的界面
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HNode *Heap; /* 堆的类型定义 */
typedef struct SData myData;
typedef struct SData *HuffmanTree;
typedef struct Ans SAns;
struct Ans // 存储最终结果
{
    char ch; // 表示字符
    char *s; // 一个字符串, 表示结点的哈夫曼编码
};
struct SData // 哈夫曼树的结构
{
    int freq; // 结点元素出现的频率
    char ch; // 结点元素的字符
    HuffmanTree Left, Right; // 此哈夫曼结点的左子树和右子树
};
int i = 0; // 充当遍历哈夫曼树时对结果结构体数组ans赋值的下标
struct HNode // 堆的结构体
{
    myData *Data; // 存储元素的数组
    int Size;          // 堆中当前元素个数
    int Capacity;      // 堆的最大容量
};
typedef Heap MinHeap; // 最小堆

MinHeap CreateHeap(int MaxSize); // 创建最小堆
int IsFull(MinHeap H); // 判断最小堆是否已满
int Insert(MinHeap H, myData X); // 往最小堆中插入元素
int IsEmpty(MinHeap H); // 判断最小堆是否为空
myData DeleteMin(MinHeap H); // 删除最小堆顶的元素, 即最小元素(自定义'小')
char* MatchingString(char *s1, char *s2); // 连接不定长的字符串s1和s2, 返回新字符串
char* TraversalHT(myData *d, char *s, SAns *SAnsP); // 递归遍历哈弗曼树, 直到收录所有叶节点的数据
void InsertSort(SAns *ans, int N); // 插入排序
char* binarySearch(SAns *ans, char ch, int end); // 迭代实现的二分查找

int main()
{
    MinHeap heap = CreateHeap(100);
    char ch;
    int freq;
    printf("先输入数字代表权值(大于0)，再输入对应的字符，按Ctrl+Z结束\n");
    while (scanf("%d %c", &freq, &ch) != EOF)
    {
        myData temp = { freq, ch, NULL, NULL };
        Insert(heap, temp); // 将输入的数据放在结构体中, 插入到最小堆里
    }
    HuffmanTree T;
    const int size = heap->Size; // 定义const常量size为初始时刻堆的大小
    SAns *ans = (SAns*)malloc(sizeof(SAns)*size);
    // 通过连续两次取最小堆的堆顶元素, 且先取出的存放在左子树, 后取出的存放在右子树
    // 合成一颗二叉树, 再将其插入最小堆中
    // 反复进行此操作size-1次, 最终堆顶的元素就是我们所求的哈弗曼树
    // 这里说的堆顶并不是指heap->Data[0], 因为heap->Data[0]已用于放置哨兵
    for (int j = 1; j < size; j++)
    {
        T = (HuffmanTree)malloc(sizeof(myData));
        T->Left = (HuffmanTree)malloc(sizeof(myData));
        T->Right = (HuffmanTree)malloc(sizeof(myData));
        *T->Left = (DeleteMin(heap));
        *T->Right = (DeleteMin(heap));
        T->freq = T->Left->freq + T->Right->freq;
        Insert(heap, *T);
        // printf("%d\n", heap->Data[1].freq); // 输出总频率, 也可以说是权重, 检验结果是否正确
    }
    TraversalHT(&heap->Data[1], "", ans); // 遍历哈弗曼树, 将结果放在ans结构体数组中

//    for (int k = 0; k < size; k++) // 检验
//    {
//        printf("%c   %s\n", ans[k].ch, ans[k].s);
//    }
//    printf("**********************\n");

    InsertSort(ans, size); // 对ans数组进行插入排序, 元素的大小取决于字符ch的大小

//    for (int k = 0; k < size; k++) // 检验排序的结果
//    {
//        printf("%c   %s\n", ans[k].ch, ans[k].s);
//    }

    printf("输入需要翻译的字符串：");
    char str[100]; // 开一个足够大的字符数组, 用于存放需要翻译的字符串
    while (scanf("%s", str) != EOF)
    {
        for (int w = 0; w < strlen(str); w++)
        {
            // 遍历str, 通过二分查找, 找到与字符对应的哈夫曼编码
            printf("%s", binarySearch(ans, str[w], size - 1));
        }
        printf("\n");
        printf("输入需要翻译的字符串：");
    }

    return 0;
}

char* binarySearch(SAns *ans, char ch, int end)
{
    // 经典的二分查找, 算法详细过程省略...
    int mid;
    int beg = 0;
    while (end >= beg)
    {
        mid = (beg + end) / 2;
        if (ans[mid].ch > ch)
            beg = mid + 1;
        else if (ans[mid].ch < ch)
            end = mid - 1;
        else
            return ans[mid].s;
    }
    return NULL; // 消除warning
}

void InsertSort(SAns *ans, int N)
{
    // 经典的插入排序, 算法详细过程省略...
    for (int p = 1; p < N; p++)
    {
        SAns temp = ans[p];
        int i;
        for (i = p; i > 0 && ((int)ans[i - 1].ch < (int)temp.ch); i--)
            ans[i] = ans[i - 1];
        ans[i] = temp;
    }
}

char* MatchingString(char *s1, char *s2)
{
    // 由于本程序采用C语言编写, 没有内置string类, 且需要连接不定长的字符串s1和s2
    // 故先申请一块动态内存, 用于存放结果t
    // 先将不定长的s1复制到t中, 之后直接通过strcat()函数把s2接在t后面,返回t
    char *t = (char*)malloc(strlen(s1) + strlen(s2) + 1);
    if (t == NULL)
        exit(1);
    strcpy(t, s1);
    strcat(t, s2);
    return t;
}

char* TraversalHT(myData *d, char *s, SAns *SAnsP)
{
    // 接收参数 d, s, SAnsP,
    // d代表哈弗曼树结构, s用于存放遍历到此节点时的哈夫曼编码,
    // SAnsP用于存放通过遍历得到的叶节点的字符和哈夫曼编码所构成的结果
    if (d->Left) // 若d存在左子树, 则继续遍历其左子树, 并且在字符串s后面拼接上字符串"0"
        TraversalHT(d->Left, MatchingString(s, "0"), SAnsP);
    else
    {
        // 不存在左子树, 则必定不存在右子树, 此时只需保存结果, 接着就可以返回NULL结束这次递归
        SAns temp = { d->ch, s };
        SAnsP[i] = temp;
        printf("编码:   %c  %s\n", d->ch, s);
        i++; // 结果数组下标+1
        return NULL;
    }
    if (d->Right) // 若d存在右子树, 则继续遍历其右子树, 并且在字符串s后面拼接上字符串"1"
        TraversalHT(d->Right, MatchingString(s, "1"), SAnsP);
    return NULL; // 消除warning
}

MinHeap CreateHeap(int MaxSize)
{
    // 创建容量为MaxSize的空的最小堆
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Data = (myData *)malloc((MaxSize + 1) * sizeof(myData));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0].freq = -1; // 定义"哨兵"为小于堆中所有可能元素的值， 这里可以是-1
    //有了哨兵就不必在后续的遍历中的for循环判断条件中加入(...&&i>1)，可有效提高效率
    return H;
}

int IsFull(MinHeap H)
{
    return (H->Size == H->Capacity);
}

int Insert(MinHeap H, myData X)
{
    // 将元素X插入最小堆H，其中H->Data[0]已经定义为哨兵
    int i;
    if (IsFull(H))
    {
        printf("最小堆已满\n");
        return 0;
    }
    i = ++H->Size; // i指向插入后堆中的最后一个元素的位置
    for (; H->Data[i / 2].freq > X.freq; i /= 2)
        H->Data[i] = H->Data[i / 2]; // 上滤X，最终i就是X的下标
    H->Data[i] = X; // 将X插入
    return 1;
}

int IsEmpty(MinHeap H)
{
    return (H->Size == 0);
}

myData DeleteMin(MinHeap H)
{
    // 从最小堆H中取出键值为最小的元素，并删除一个结点
    int Parent, Child;
    myData MinItem, X;

    if (IsEmpty(H))
    {
        printf("最小堆已为空\n");
        X.freq = -1;
        return X; //-1表示删除元素失败
    }

    MinItem = H->Data[1]; // 取出根结点存放的最小值
    // 用最小堆中最后一个元素从根结点开始向上过滤下层结点
    X = H->Data[H->Size--]; // 同时减小当前堆的规模
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child)
    {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Data[Child].freq > H->Data[Child + 1].freq))
            Child++;  // Child指向左右子结点的较小者
        if (X.freq <= H->Data[Child].freq)
            break; // 找到了合适位置
        else  // 下滤X
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = X;

    return MinItem;
}