PTA-数据结构 Huffman Codes

刺骨的言语ヽ痛彻心扉 2022-05-04 09:27 239阅读 0赞

7-1 Huffman Codes （30 分）

In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a', 'x', 'u' and 'z' are 4, 2, 1 and 1, respectively. We may either encode the symbols as \{'a'=0, 'x'=10, 'u'=110, 'z'=111\}, or in another way as \{'a'=1, 'x'=01, 'u'=001, 'z'=000\}, both compress the string into 14 bits. Another set of code can be given as \{'a'=0, 'x'=11, 'u'=100, 'z'=101\}, but \{'a'=0, 'x'=01, 'u'=011, 'z'=001\} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not.

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives an integer N (2≤N≤63), then followed by a line that contains all the N distinct characters and their frequencies in the following format:

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

where `c[i]` is a character chosen from \{'0' - '9', 'a' - 'z', 'A' - 'Z', '\_'\}, and `f[i]` is the frequency of `c[i]` and is an integer no more than 1000. The next line gives a positive integer M (≤1000), then followed by M student submissions. Each student submission consists of N lines, each in the format:

c[i] code[i]

where `c[i]` is the `i`\-th character and `code[i]` is an non-empty string of no more than 63 '0's and '1's.

### Output Specification: ###

For each test case, print in each line either "Yes" if the student's submission is correct, or "No" if not.

Note: The optimal solution is not necessarily generated by Huffman algorithm. Any prefix code with code length being optimal is considered correct.

### Sample Input: ###

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

### Sample Output: ###

Yes
    Yes
    No
    No

思路:根据输入的权值创建Huffman树，求出WPL。当所输入编码的WPL与Huffman树的WPL相等，并为前缀码时，说明编码是正确的。

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <malloc.h>
    
    using namespace std;
    typedef int Status;
    typedef struct 
    {
        int weight;
        int parent,lchild,rchild;
    }HTNode,*HuffmanTree;
    typedef char** HuffmanCode;
    
    void Select(HuffmanTree HT,int end,int &s1,int &s2) //找出最小的两个数，将下标带回
    {
        int min1,min2;
        int i;
        s1 = end;
        s2 = s1;
        min1 = 2147483647;
        min2 = min1;
        for (i = 1; i <= end; i++)
        {
            if (!HT[i].parent)
            {
                if (HT[i].weight <= min1)
                {
                    min2 = min1;
                    s2 = s1;
                    min1 = HT[i].weight;
                    s1 = i;
                }
                else if (HT[i].weight <= min2)
                {
                    min2 = HT[i].weight;
                    s2 = i;
                }
            }
        }
    }
    void CreateHuffmanTree(HuffmanTree &HT,int *w,int n)  //创建哈夫曼树
    {
        if(n<=1)return ;
        int m = 2*n-1;
        HT = new HTNode[m+1];
        int i;
        HuffmanTree p;
        for(p = HT+1,i=1;i<=n;++i,++p,++w)  // 初始化，所有结点均没有双亲和孩子
        {
            p->weight = *w;
            p->parent = 0;
            p->lchild = 0;
            p->rchild = 0;
        }
        for(i=n+1;i<=m;++i,++p)
        {
            p->weight = 0;
            p->parent = 0;
            p->lchild = 0;
            p->rchild = 0;
        }
        for(i=n+1;i<=m;i++)
        {
            int s1,s2;
            Select(HT,i-1,s1,s2);
            HT[s1].parent = i;
            HT[s2].parent = i;
            HT[i].lchild = s1;
            HT[i].rchild = s2;
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    int WPL(HuffmanTree HT,int depth,int index)  //求WPL
    {
        if(!HT[index].lchild && !HT[index].rchild)
            return HT[index].weight * depth;
        return (WPL(HT,depth+1,HT[index].lchild) + WPL(HT,depth+1,HT[index].rchild));
    }
    bool isPrefix(char *a,char *b)  //判断是否为前缀码
    {
        int len = strlen(a)>strlen(b) ? strlen(b) : strlen(a);
        for(int i=0;i<len;i++)
        {
            if(a[i]!=b[i])
                return true;
        }
        return false;
    }
    int main()
    {
        char ch[100];
        int weight[100];
        int n;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>ch[i]>>weight[i];
        }
        HuffmanTree HT;
        CreateHuffmanTree(HT,weight,n);
        int m;
        cin>>m;
        while(m--)
        {
            char submission[100][100];
            for(int i=0;i<n;i++)
            {
                char tmp;
                scanf("%c",&tmp);
                getchar();
                scanf("%s",submission[i]);
                getchar();
            }
            int subWPL = 0;
            for(int i=0;i<n;i++)
            {
                subWPL += (strlen(submission[i])*weight[i]);
            }
            
            int flag = 1;
            for (int i = 0; i < n; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if(!isPrefix(submission[i],submission[j]))
                    {
                        flag = 0;
                        break;
                    }
                }
            }
            if(flag && (subWPL==WPL(HT,0,2*n-1)))
                cout<<"Yes"<<endl;
            else
                cout<<"No"<<endl;
        }
    
        return 0;
    }