Tanky WooRSS

HDU/HDOJ 1053 Entropy (Huffman树)

27 May 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

这两天把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代码:

#include 
#include 
#include 
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; iparent = &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; iflag = 1;
    return t;
}

int visit(int k)
{
    int sum = 0;
    Node *t = &Huffman;[0];
    int level;
    for(int i=0; iparent != NULL)
        {
            level ++;
            t = t->parent;
        }
        sum += level*Huffman[i].weight;

    }
    return sum;
}