关于Huffman Codes的一道题

Z时代
2024-01-10
分类：IT

题目描述

图片描述

题目来源及自己的思路

PTA - 中国大学MOOC-陈越、何钦铭-数据结构-2018秋
建树算最坏情况下的WPL值，然后根据输入建树，检查值是否在叶节点上，以及最终WPL值是否超过最坏情况。

相关代码

// 请把代码文本粘贴到下方（请勿用图片代替代码）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode *HuffmanTree;
struct TreeNode {
    HuffmanTree Left, Right;
    int Weight;
    char Data;
};
typedef struct HeapNode *MinHeap;
struct HeapNode {
    HuffmanTree data[64];
    int size;
};
MinHeap ini_a_heap(int num) {
    MinHeap the;
    the = malloc(sizeof(struct HeapNode));
    the -> size = num;
    char ch;
    int we;
    for (int i = 0; i < num; i++) {
        scanf(" %c %d", &ch, &we);
        the->data[i] = malloc(sizeof(struct TreeNode));
        the->data[i]->Data = ch;
        the->data[i]->Weight = we;
        the->data[i]->Left = NULL;
        the->data[i]->Right = NULL;
    }
    return the;
}
HuffmanTree ini_tree() {
    HuffmanTree this;
    this = malloc(sizeof(struct TreeNode));
    this->Left = NULL;
    this->Right = NULL;
    return this;
}
int is_a_huff(MinHeap heap, int num, int best_wpl) {
    char ch, code[num], j;
    HuffmanTree tree, this;
    tree = ini_tree();
    int wpl = 0, res = 1;
    for (int i = 0; i < num; i++) {
        int dep = 0;
        scanf(" %c %s", &ch, code);
        if (strlen(code) > num - 1)
            res = 0;
        printf("%d %d\n",strlen(code), num - 1);
        this = tree;
        if (res)
        for (j = 0; j < strlen(code) - 1; j++) {
            dep++;
            switch (code[j]) {
            case '0':
                if (this->Left == NULL) {
                    this->Left = ini_tree();
                }
                this = this->Left;
                break;
            case '1':
                if (this->Right == NULL) {
                    this->Right = ini_tree();
                }
                this = this->Right;
                break;
            }
        }
        if (res)
        switch (code[j]) {
        case '0':
            if (this->Left == NULL)
                this->Left = heap->data[i];
            else
                res = 0;
            break;
        case '1':
            if (this->Right == NULL)
                this->Right = heap->data[i];
            else
                res = 0;
            break;
        }
        wpl += heap->data[i]->Weight * (dep+1);
    }
    if (wpl <= best_wpl && res) return 1;
    return 0;
}
int com(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}
int WPL(MinHeap heap, int num) {
    int i, weight[num], depth = 0, res = 0;
    for (i = 0; i < num; i++)
        weight[i] = heap->data[i]->Weight;
    qsort(weight, num, sizeof(int), com);
    for (i = 0; i < num - 2; i++)
        res += (++depth) * weight[i];
    res += (++depth) * weight[i++];
    res += depth * weight[i];
    return res;
}
int main(int argc, char **argv) {
    int N, wpl;
    scanf("%d", &N);
    MinHeap heap;
    heap = ini_a_heap(N);
    wpl = WPL(heap, N);
    int time;
    scanf("%d", &time);
    for (int i = 0; i < time; i++) {
        if (is_a_huff(heap, N, wpl)) puts("Yes");
        else puts("No");
    }
    return 0;
}