PTA 6-8 哈夫曼编码 (25 分)

6-8 哈夫曼编码 (25 分)
给定一段文字，如果我们统计出字母出现的频率，是可以根据哈夫曼算法给出一套编码，使得用此编码压缩原文可以得到最短的编码总长。然而哈夫曼编码并不是唯一的。例如对字符串"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

结点的带权路径长度是指从根节点到该结点之间的路径长度与该结点上所带权值的乘积。

哈夫曼树的特点是带权路径长度最小，这也就意味着，无论你如何去搭建一棵哈夫曼树，它的带权路径永远相同。

所以我们只需要根据所给数据，搭建完哈夫曼树，计算出带权路径长度然后
计算出所给样例的带权路径长度是否相同，以及比较字母的前缀是否相等。

这里因为题目给的数据只有2~63个数据，不用担心超时，所以直接用了sort，但是最好还是换一种排序的方法，用c++中自带的vector，再加上用二分查找插入点，这样才会避免超时。

#include 
#include
using namespace std;
typedef struct tree* List;
struct tree
{
    List right,left;
    char value;
    int Data;
};
struct hfm
{
    char c;
    int code;
    List L;
};
typedef struct hfm hf;
bool cmp(hf a,hf b)
{
    return a.codeleft=s1.L;//一般情况下都是让小的在左边，大的在右边。
    L1->right=s2.L;
    s[cnt].code=s1.code+s2.code;然后再将s1.code+s2.code插入进数组中，参与下次排序。
    s[cnt].L=L1;
    cnt++;
}
int sum=0;
void find(List BF,int h)//就是不断递归找到结点离根节点的距离
{
    if(BF->left==NULL&&BF->right==NULL)//因为每一个带权结点都是叶子结点
    {
        sum=sum+BF->Data*h;
    }else if(BF->left==NULL)
    {
        find(BF->right,h+1);
    }else if(BF->right==NULL)
    {
        find(BF->left,h+1);
    }else
    {
        find(BF->left,h+1);
        find(BF->right,h+1);
    }
}
int main()
{
    int n,a[1000];
    cin>>n;
    cnt=n;
    int h=n;
    for(int i=0;i>s[i].c>>s[i].code;//先进行赋值
        a[i]=s[i].code;
        s[i].L=(List)malloc(sizeof(struct tree));//然后先给每一个数据创建一个链表为了之后方便
        s[i].L->value=s[i].c;
        s[i].L->Data=s[i].code;
        s[i].L->right=NULL;
        s[i].L->left=NULL;
    }
    sort(s,s+n,cmp);//因为题目给的数据比较少，所以这直接使用了sort。
    int x=2;
    while(n>=2)//如果数据少于2个，而最后剩下的就是我们需要的根
    {
        buildtree(s[x-2],s[x-1]);//建立哈夫曼树
        sort(s+x,s+cnt,cmp);//每次都得排一次序，因为每次都需要选取最小的两个权值。
        x=x+2;
        n--;
    }
    List p=s[cnt-1].L;//得到根节点。
    find(p,0);//开始计算带权路径长度
    int m;
    cin>>m;
    while(m--)
    {
        string s1[100];
        char ch;
        int sum1=0;
        for(int i=0;i>ch;
            cin>>s1[i];
            sum1=sum1+s1[i].length()*a[i];//计算带权路径长度
        }
        if(sum1!=sum)//如果不相等就直接输出No
        {
            cout<<"No"<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5690772.html