05-树9 Huffman Codes.c

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

#define MINH -1
#define MAXCODESIZE 63

typedef struct TreeNode *HuffmanTree;
struct TreeNode {
    int weight;
    HuffmanTree Left, Right;
};

typedef struct TreeNode *ElementType;
typedef struct HeapStruct *MinHeap;
struct HeapStruct {
    ElementType *Elements;
    int Size;
    int Capacity;
};

/* 堆的相关操作：开始 */
MinHeap CreateHeap( int MaxSize )
{
    MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));
    H->Elements = malloc((MaxSize + 1) * sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Elements[0] = (ElementType)malloc(sizeof(struct TreeNode));
    H->Elements[0]->weight = MINH;

    return H;
}

void DestoryHeap(MinHeap H)
{
    int i;
    if (!H) return;
    if (H->Elements) {
        for (i = 0; i < H->Size; ++i)
            free(H->Elements[i]);
        free(H->Elements);
    }
    free(H);
}

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

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

void Insert(MinHeap H, ElementType X)
{
    int i;
    if (IsFull(H)) return;
    i = ++H->Size;
    for (; H->Elements[i / 2]->weight > X->weight; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}

ElementType DeleteMin(MinHeap H)
{
    int Parent, Child;
    ElementType MinItem, X;
    if (IsEmpty(H)) return 0;

    MinItem = H->Elements[1];
    X = H->Elements[H->Size--];
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if ((Child != H->Size) && (H->Elements[Child]->weight > H->Elements[Child + 1]->weight))
            Child++;
        if (X->weight <= H->Elements[Child]->weight) break;
        else
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = X;
    return MinItem;
}

MinHeap BuildMinHeap(int *freq_arr,int n)
{
    int i;
    ElementType data;
    MinHeap H;
    H = CreateHeap(n);

    for (i = 0; i < H->Capacity; ++i) {
        data = (ElementType)malloc(sizeof(struct TreeNode));
        data->weight = freq_arr[i];
        data->Left = 0; data->Right = 0;
        Insert(H, data);
    }
    return H;
}
/* 堆的相关操作：结束 */

void DestoryCharFreq(int *freq_arr)
{
    if (!freq_arr) return;
    free(freq_arr);
}

void DestoryHuffmanTree(HuffmanTree HT)
{
    if (!HT) return;
    DestoryHuffmanTree(HT->Left);
    DestoryHuffmanTree(HT->Right);
    free(HT);
}

int *readPair(int n)
{
    int i; char c;
    int *freq_arr;
    freq_arr = malloc(n * sizeof(int));
    for (i = 0; i < n; ++i) {
        scanf(" %c %d", &c, &freq_arr[i]);
    }
    return freq_arr;
}

int HuffmanTreeWPL(int *freq_arr, int n)
{
    int i, wpl = 0;
    MinHeap H;
    HuffmanTree T;
    H = BuildMinHeap(freq_arr, n);  // 根据读入数据建立小顶堆
    for (i = 1; i < H->Capacity; ++i) {
        T = (HuffmanTree)malloc(sizeof(struct TreeNode));
        T->Left = DeleteMin(H);
        T->Right = DeleteMin(H);
        T->weight = T->Left->weight + T->Right->weight;
        Insert(H, T);
        wpl += T->weight;
    }
    T = DeleteMin(H);
    DestoryHeap(H);
    DestoryHuffmanTree(T);    // 销毁Huffman树所占空间
    return wpl;
}

void init_codeArr(char *code)   // 初始化code数组每个元素为\0
{
    int i;
    for (i = 0; i < MAXCODESIZE && code[i] != '\0'; ++i)
        code[i] = '\0';
}

HuffmanTree createTreeNode()
{
    HuffmanTree HT;
    HT = (HuffmanTree)malloc(sizeof(struct TreeNode));
    HT->weight = 1; HT->Left = 0; HT->Right = 0;
    return HT;
}

// 这里使用struct TreeNode结构体，其中的weight用来表示是否为本次code新添加结点，若是则为1，否则为0
HuffmanTree RecoverHFTreeByCode(HuffmanTree HT, char *code, int *flag, int *counter)
{
    int i;  HuffmanTree node;
    if (!HT) {
        HT = createTreeNode();
        ++(*counter);
    }
    for (i = 0, node = HT; code[i] != '\0';  ++i) {
        // 第一种情况：该结点不是新添加结点，并且没有左右孩子，即之前字符对应的子节点
        // 说明之前某字符编码是该编码的前缀码
        if (node->weight == 0 && !node->Left && !node->Right) {
            (*flag) = 0;
            break;
        }
        node->weight = 0;
        if (code[i] == '0') {   // 读到0向左孩子走一位
            if (!node->Left) {
                node->Left = createTreeNode();
                ++(*counter);
            }
            node = node->Left;
        } else {
            if (!node->Right) {
                node->Right = createTreeNode();
                ++(*counter);
            }
            node = node->Right;
        }
    }
    // 第二种情况：读完所有code后，该位置有孩子结点，说明该编码是之前某字符编码的前缀码
    if (node->Left || node->Right)
        (*flag) = 0;
    return HT;
}

void check_code(int *freq_arr, int n, int wpl)
{
    int i, sum_wpl, flag, counter; char c;
    HuffmanTree HT;
    char code[MAXCODESIZE] = "\0";
    sum_wpl = 0; flag = 1; counter = 0; HT = 0;
    for (i = 0; i < n; ++i) {
        init_codeArr(code);
        scanf("\n%c %s", &c, code);
        if (flag) { // 判断该次提交是否已经不正确了，如果还正确则继续处理
            sum_wpl += strlen(code) * freq_arr[i];
            HT = RecoverHFTreeByCode(HT, code, &flag, &counter);
        }
    }
    // 这里有三个判断条件
    // 1. 提交的总wpl与预设的完全相同
    // 2. 没有前缀码情况出现，此处用flag标识
    // 3. 没有度为1的结点，此处的counter表示生成的Huffman树结点数，如果正确应该等于2*n-1，n为叶节点个数，即所有字符数
    if (sum_wpl == wpl && flag && counter == 2 * n - 1)
        printf("Yes\n");
    else
        printf("No\n");
    DestoryHuffmanTree(HT);
}

int main()
{
    int n, m, i, wpl;
    int *freq_arr;
    scanf("%d\n", &n);

    freq_arr = readPair(n);     // 读入所有字符及其对应频率
    wpl = HuffmanTreeWPL(freq_arr, n);    // 根据读入字符及频率使用小顶堆建立Huffman树求得WPL值

    scanf("%d", &m);
    for (i = 0; i < m; ++i) {
        check_code(freq_arr, n, wpl);
    }

    DestoryCharFreq(freq_arr);

    return 0;
}