HDU/HDOJ 1053 Entropy (Huffman树)

昨晚做了一晚上,可是状态不好,今天下午去踢了会球,发挥的不错,晚上做题心情也好,哈哈,终于搞定了。

这两天把Huffman看了好几遍,看到了三种方法来处理Huffman这个数据结构:

1.STL中的priority_queue

2.链表表示Huffman Node的parent, lchild, rchild.

3.数组表示Huffman Node的parent, lchild, rchild.

关于数组控制Huffman结构的,我在http://www.cppleyuan.com/viewthread.php?tid=713 写过,

另外,关于优先级队列的,我会在总结算法导论之贪心算法中讲出。

这里我用的是最普遍的链表形式。

这里有一点不好控制:

如何找出当前最小的两个结点?

我给Huffman Node中增加了一个控制变量flag,默认为-1,表示未被适用,如果选出此点,则将flag设置为1,表示此结点已经是某一个子树的结点,这样,就不会再重复使用该点。

另外,注意Huffman树的叶结点有N个,则总结点数是2*N-1个,

所以我设置一个数组保存Huffman Node,则0~N-1为叶结点,2*N-2是根结点。这样一直从每个叶结点返回到根结点,求出当前叶结点的层数。

另外还有一点要注意:单独考虑只有

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <string>
#include <iostream>
#include <iomanip>
const int INF = 999999;
using namespace std;
 
typedef struct Node{
    int flag;   // 记录是否被用过
    int weight;
    //int level;
    char data;
    Node *lchild, *rchild, *parent;
}Node;
 
Node Huffman[1000];
 
int rec[27];
string ss;
Node *s1, *s2;
 
 
Node *select(int k);
int visit(int k);
int main()
{
    //freopen("input.txt", "r", stdin);
    while(cin >> ss && ss!="END")
    {
        // 初始化
        memset(rec, 0, sizeof(rec));
        int k = 0;  // 计数,Huffman Node的个数
        for(int i=0; i<1000; ++i)
        {
            Huffman[i].data = '#';
            Huffman[i].flag = -1;
            Huffman[i].lchild = Huffman[i].rchild = Huffman[i].parent = NULL;
            Huffman[i].weight = 0;
        }
        // 输入
        for(int i=0; i<ss.size(); ++i)
            if(ss[i] == '_')
                rec[26]++;
            else
                rec[ss[i]-'A']++;
 
 
        for(int i=0; i<27; ++i)
            if(rec[i])
            {
                if(i == 26)
                    Huffman[k].data = '_';
                else
                    Huffman[k].data = i+'A';
                //Huffman[k].flag = -1;
                Huffman[k].weight = rec[i];
                //Huffman[k].lchild = Huffman[k].rchild = Huffman[k].parent = NULL;
                ++k;
            }
        if(k == 1)
        {
            cout << ss.size()*8 << " " << ss.size() << " 8.0\n";
            continue;
        }
 
        //cout << "k = " << k << endl;
        // 生成其他结点
        for(int i=k; i<=2*k-2; ++i)
        {
            s1 = select(i);
            s2 = select(i);
            Huffman[i].lchild = s1;
            Huffman[i].rchild = s2;
            Huffman[i].parent = NULL;//
            Huffman[i].flag = -1;//
            Huffman[i].weight = s1->weight + s2->weight;
            Huffman[i].data = '#';
            //cout << "Node " << k << ": " << Huffman[i].data << " " << Huffman[i].weight << endl;
            s1->parent = &Huffman[i];
            s2->parent = &Huffman[i];
        }
 
        int len1 = 8 * ss.size();
        int len2 = visit(k);
        cout << len1 << " " << len2 << " " << setiosflags( ios::fixed | ios::showpoint) << setprecision(1) << (double)len1/len2 << endl;
 
 
    }
}
 
Node *select(int k)
{
    Node *t = &Huffman[0];
    int _max = INF;
    for(int i=0; i<k; ++i)
    {
        if(Huffman[i].flag == -1 && Huffman[i].weight < _max)
        {
            _max = Huffman[i].weight;
            t = &Huffman[i];
        }
    }
    t->flag = 1;
    return t;
}
 
int visit(int k)
{
    int sum = 0;
    Node *t = &Huffman[0];
    int level;
    for(int i=0; i<k; ++i)
    {
        level = 0;
        t = &Huffman[i];
        while(t->parent != NULL)
        {
            level ++;
            t = t->parent;
        }
        sum += level*Huffman[i].weight;
 
    }
    return sum;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注