Huffman Codes

 题目：https://pintia.cn/problem-sets/16/problems/671

给定N个字符，每个字符有一个使用频率，要对每个字符进行编码，有M个学生对作业进行了提交，编程判断他们的答案是不是最优编码。我们知道，霍夫曼编码一定是最优的编码方案，但是题目告诉我们：一个最优的编码方案不一定由霍夫曼算法得出。在对每一位学生的答案进行检查时，正确答案一定符合以下两个要求：

1. 字符集的WPL与最优编码方案的WPL相等。
2. 任一字符的编码不是另一个字符的前缀。

所以我们要进行的任务是：用霍夫曼算法得到最优WPL；判断学生答案的WPL是否与最优WPL相等，以及是否是前缀码。

一.实现霍夫曼算法。

1.首先就是要建立一棵霍夫曼树。原始的结点集中保存每个字符的频率，每次选取两个值最小的结点进行合并，得到一个新的结点，该结点的权值等于两个子节点的频率之和，将这个新的结点加入结点集中去，重复上述步骤直到所有结点都被合并了。考虑到每次选取最小的结点这个特性，利用最小堆来实现结点集的存放。建立好最小堆后，每次弹出两个最小的结点（注意每弹出一个要调整最小堆），不断合并，形成一棵霍夫曼树。堆的插入操作是先定位到最后一个位置，再将要插入的值与祖先结点依次比较；删除操作是删除根，再将最后一个结点放到根的位置，再向下比较调整。

2.递归实现WPL计算。传入的参数有霍夫曼树T，和当前深度Depth。

二.判断答案

1.计算WPL值，即每个字符频率乘字符串长度，如果不相等后面的判断也不用做了。

2.根据字符串建树，如‘1’则向右，‘0’则向左。如果一个字符建立过程中经过了另一字符结点或在非叶子结点处就停止了，则不符合前缀码要求。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
using namespace std;
#define MAXALPHA 64
#define MAXSTU 1001

char Alpha[MAXALPHA];//字符表
int Freq[MAXALPHA];//频率表
string code[MAXSTU];

typedef struct TreeNode* Huffman;
struct TreeNode {
    int Weight;
    Huffman Left, Right;
};

typedef struct Heap* MinHeap;//最小堆
struct Heap {
    Huffman Data[MAXALPHA];
    int size ;
};


void Insert(MinHeap H, Huffman T) {
    int num = T->Weight;
    if (H->size==0) {
        H->Data[1] = T;
        H->size++;
        H->Data[0] = (Huffman)malloc(sizeof(struct TreeNode));
        H->Data[0]->Weight= -1;
        return;
    }
    H->size++;
    int i;
    for (i = H->size;H->Data[i / 2]->Weight> num;i /= 2)
        H->Data[i] = H->Data[i / 2];
    H->Data[i] = T;
    return;
}

Huffman Delete(MinHeap H) {
    if (H->size == 0)
        return NULL;
    Huffman ret = H->Data[1];
    int child, parent;
    Huffman X = H->Data[H->size--];
    for (parent = 1;parent * 2 <= H->size;parent = child) {
        child = parent * 2;
        if ((child != H->size) && (H->Data[child]->Weight > H->Data[child + 1]->Weight))
            child++;
        if (X->Weight < H->Data[child]->Weight)
            break;
        else
            H->Data[parent] = H->Data[child];
    }
    H->Data[parent] = X;
    return ret;
}

Huffman Build(MinHeap H) {
    int i;
    int count = H->size;
    Huffman T;
    for (i = 1;i < count;i++) {
        T = (Huffman)malloc(sizeof(struct TreeNode));
        T->Left = Delete(H);
        T->Right = Delete(H);
        T->Weight = T->Left->Weight + T->Right->Weight;
        Insert(H, T);
    }
    T = Delete(H);
    return T;
}

int Getanswer(Huffman T,int Depth) {
    if (!T->Left && !T->Right)
        return T->Weight * Depth;
    else
        return Getanswer(T->Left, Depth + 1) + Getanswer(T->Right, Depth + 1) ;
}

int Judge(Huffman T,string s) {
    int len = s.length();
    if (len != 0) {
        int i = 0;
        int error = 0;
        Huffman p,q;
        p = T;
        while (i < len - 1) {
            if (s[i] == '1') {
                if (p->Right) {
                    p = p->Right;
                    if (p->Weight) {
                        error = 1;
                        break;
                    }
                }
                else {
                    q = (Huffman)malloc(sizeof(struct TreeNode));
                    q->Left = q->Right = NULL;
                    q->Weight = 0;
                    p->Right = q;
                    p = q;
                }
            }
            else {
                if (p->Left) {
                    p = p->Left;
                    if (p->Weight) {
                        error = 1;
                        break;
                    }
                }
                else {
                    q = (Huffman)malloc(sizeof(struct TreeNode));
                    q->Left = q->Right = NULL;
                    q->Weight = 0;
                    p->Left = q;
                    p = q;
                }
            }
            i++;
        }
        if (!error) {
            if (s[i] == '1') {
                if (p->Right) {
                    error = 1;
                }
                else {
                    p->Right = (Huffman)malloc(sizeof(struct TreeNode));
                    p = p->Right;
                    p->Left = p->Right = NULL;
                    p->Weight = 1;
                }
            }
            else {
                if (p->Left) {
                    error = 1;
                }
                else {
                    p->Left = (Huffman)malloc(sizeof(struct TreeNode));
                    p = p->Left;
                    p->Left = p->Right = NULL;
                    p->Weight = 1;
                }
            }
        }
        return !error;
    }
    return 0;
}

int main() {
    int N;//要编码的字符个数
    scanf("%d", &N);
    int i, k;
    for (i = 1;i <= N;i++) {
        getchar();
        scanf("%c %d",&Alpha[i], &Freq[i]);
    }
    MinHeap H = (MinHeap)malloc(sizeof(struct Heap));
    H->size = 0;
    Huffman T;
    for (i = 1;i <= N;i++) {
        T = (Huffman)malloc(sizeof(struct TreeNode));
        T->Weight = Freq[i];
        T->Left = T->Right = NULL;
        Insert(H, T);
    }
    T = Build(H);
    int WPL = Getanswer(T,0);
    //printf("%d", WPL);
    int M;//要检查的学生数
    scanf("%d", &M);
    for (i = 1;i <= M;i++) {
        int WPLstu = 0;
        int flag = 0;
        for (k = 1;k <= N;k++) {
            getchar();
            cin >> Alpha[k] >> code[k];
            WPLstu += Freq[k] * code[k].length();
        }
        if (WPL == WPLstu) {
            Huffman T = (Huffman)malloc(sizeof(struct TreeNode));
            T->Left = T->Right = NULL;
            T->Weight = 0;
            for (k = 1;k <= N;k++) {
                if (!Judge(T,code[k])) {
                    flag = 1;
                    break;
                }
            }
            if (!flag) {
                printf("Yes
");
            }
            else
                printf("No
");
        }
        else
            printf("No
");
    }
    return 0;
}