首页 > 代码库 > Hdu 1053 Entropy
Hdu 1053 Entropy
Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=1053
一道关于huffman树的题目。刚开始把各种字符看作一个结点，而这么一个结点同时也是一棵树。将这个字符出现的次数作为value。每次取出两个值最小的树，合并为一棵树，然后将这棵树再与其他结点放在一起排序。反复此步骤，直至只剩一棵树。那么，这棵树极为huffman树。
最初想用优先队列排序，取出最小的两颗树，合并为一棵树后放回的策略。但可惜对c++内存方面理解不深透，怎么也做不出这棵树。
最后只能用笨办法，建立一个数组，不断的排序取出最小的数。让后放回，再排序的策略。
虽然过了，但感觉对huffman树的理解还是有很多不够，还需努力。
/** Author : Emerald Date : 29.Jan 2015 Aim : Hdu 1053 */#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <string>using namespace std;typedef struct Node{ int value , depth; // value 表示出现的次数 ， depth 表示此结点位于第几层，也就是深度 struct Node *left, *right;}Node;// 用于 qsort() 函数int cmp( const void *a, const void *b ) { return (*(Node*)a).value - (*(Node*)b).value;}// 定义一个结点数组来保存一棵树.因为最多可能有27个字符，所以27×27的大小比较保险const int MAXN = 27*27;Node node[ MAXN ];int ans;void getEn( Node* t );// 建立huffuman树Node* buildTree( string in ) { int i, length = in.length(); // 初始化，没有这一步会影响答案 for( i=0; i<length*length && i<MAXN; i++ ) { node[i].value = http://www.mamicode.com/node[i].depth = 0;"%d %d %.1lf\n", in.length()*8 ,ans , ( in.length()*8.0) / ans*1.0 ); } return 0;}
Hdu 1053 Entropy
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。