这篇博客是从旧博客 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;
}