7-2 哈夫曼编码

给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"aaaxuaxz"，容易得到字母 'a'、'x'、'u'、'z' 的出现频率对应为 4、2、1、1。我们可以设计编码 {'a'=0, 'x'=10, 'u'=110, 'z'=111}，也可以用另一套 {'a'=1, 'x'=01, 'u'=001, 'z'=000}，还可以用 {'a'=0, 'x'=11, 'u'=100, 'z'=101}，三套编码都可以把原文压缩到 14 个字节。但是 {'a'=0, 'x'=01, 'u'=011, 'z'=001} 就不是哈夫曼编码，因为用这套编码压缩得到 00001011001001 后，解码的结果不唯一，"aaaxuaxz" 和 "aazuaxax" 都可以对应解码的结果。本题就请你判断任一套编码是否哈夫曼编码。

输入格式：

首先第一行给出一个正整数 N（2≤N≤63），随后第二行给出 N 个不重复的字符及其出现频率，格式如下：

c[1] f[1] c[2] f[2] ... c[N] f[N]

其中c[i]是集合{'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}中的字符；f[i]是c[i]的出现频率，为不超过 1000 的整数。再下一行给出一个正整数 M（≤1000），随后是 M 套待检的编码。每套编码占 N 行，格式为：

c[i] code[i]

其中c[i]是第i个字符；code[i]是不超过63个'0'和'1'的非空字符串。

输出格式：

对每套待检编码，如果是正确的哈夫曼编码，就在一行中输出"Yes"，否则输出"No"。

注意：最优编码并不一定通过哈夫曼算法得到。任何能压缩到最优长度的前缀编码都应被判为正确。

输入样例：

7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11

输出样例：

Yes
Yes
No
No

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxN 1001
#define MinH -10001
#define ERROR 0

typedef enum
{
    false,
    true
} bool;
typedef int ElementType;
typedef struct Node *Heap;
struct Node
{
    ElementType *Data;
    int Size;
    int Capacity;
} H;

struct Huff
{
    char code[200];
    int Code_Len;
};
typedef struct Huff Hfm_Code;
typedef struct Huff *Hfm_Code_p;

typedef struct TNode *Position;
typedef Position Tree;
struct TNode
{
    ElementType Flag;
    Tree l;
    Tree r;
};

void Create(int N)
{
    H.Size = 0;
    H.Data = (ElementType *)malloc((N + 1) * sizeof(ElementType));
    H.Data[0] = MinH;
    H.Capacity = N;
}

bool Full(Heap H)
{
    return (H->Size == H->Capacity);
}

void Insert(ElementType X)
{
    if (Full(&H))
        return;

    int i;
    for (i = ++H.Size; H.Data[i / 2] > X; i /= 2)
        H.Data[i] = H.Data[i / 2];

    H.Data[i] = X;
}

ElementType Delete(void)
{
    if (H.Size == 0)
        return ERROR;

    ElementType temp, min;
    min = H.Data[1];
    temp = H.Data[H.Size--];
    int Parent, Child;
    for (Parent = 1; Parent * 2 <= H.Size; Parent = Child)
    {
        Child = Parent * 2;
        if ((Child != H.Size) && (H.Data[Child] > H.Data[Child + 1]))
        {
            Child++;
        }
        if (temp <= H.Data[Child])
            break;
        else
            H.Data[Parent] = H.Data[Child];
    }
    H.Data[Parent] = temp;
    return min;
}

int Get_WPL(int N, int *c)
{
    int count = 0;
    Create(N);
    for (count; count < N; count++)
    {
        char ch;
        int temp;
        scanf(" %c", &ch);
        scanf("%d", &temp);
        c[count] = temp;
        Insert(temp);
    }
    int WPL = 0;
    while (H.Size >= 2)
    {
        int a = 0, b = 0, sum = 0;
        a = Delete();
        b = Delete();
        sum = a + b;
        WPL += sum;
        Insert(sum);
    }
    return WPL;
}

bool Get_Check_Len(int WPL, Hfm_Code_p Code, int *c, int N)
{
    bool flag = true;

    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        char ch;
        scanf("%c ", &ch);
        gets(Code[i].code);
        if (flag)
        {
            Code[i].Code_Len = strlen(Code[i].code);
            if (Code[i].Code_Len > N - 1)
                flag = false;
            sum += (Code[i].Code_Len * c[i]);
        }
    }
    if (sum == WPL && flag)
        flag = true;
    else
        flag = false;
    return flag;
}

bool Check_Tree(Hfm_Code_p Code, int N)
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j)
                continue;
            if (strncmp(Code[i].code, Code[j].code, Code[i].Code_Len) == 0)
                return false;
        }
    }
    return true;
}

int main(void)
{
    int N;
    scanf("%d", &N);
    int *c = (int *)malloc(N * sizeof(int));
    int WPL = Get_WPL(N, c);
    int M;
    scanf("%d", &M);
    getchar();

    while (M--)
    {
        Hfm_Code_p Code;
        Code = (Hfm_Code_p)malloc(N * sizeof(Hfm_Code));
        bool flag_L = Get_Check_Len(WPL, Code, c, N);
        if (!flag_L)
        {
            printf("No\n");
            continue;
        }

        bool flag_T = Check_Tree(Code, N);
        if (flag_L && flag_T)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}