题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1053
分析：这道题目是一道很典型的哈夫曼树问题，哈夫曼树（见百度百科）总之一句话，主要作用就是用来解决压缩编码问题，相信学过离散数学的同学都应该学过这个神奇的数据结构。
（1）建立哈夫曼树节点结构体
typedef struct Huffman_trie { int deep;//深度 int freq;//频度（即哈夫曼树中的权重） Huffman_trie *left,*right; //优先权队列中用于排序比较的方法，不懂的建议先学一学优先权队列 friend bool operator<(Huffman_trie a,Huffman_trie b) return a.freq>b.freq; }Huffman_trie;
（2）首先我们把读入的字符串进行预处理，按照字符分别放入对应的节点中，同时记录其出现频率，count_num记录字符出现次数，同时放入哈夫曼节点中
len = strlen(str); str[len]='!'; sort(str,str+len); count_num=1; index=0; for(int i=1;i<=len;i++) { if(str[i]!=str[i-1]) { trie[index++].freq=count_num; count_num=1; }else count_num++; }
（3）用一个优先权队列存储节点，每次取出频率最小的两个节点，合并节点并把其合并后的节点放入优先权队列中，一直合并到队列中只剩下最后一个节点，把其作为根节点。（这正是哈夫曼树建立的关键，这个地方一定要理解）
root = (Huffman_trie*)malloc(sizeof(Huffman_trie)); for(int i=0;i<index;i++) pq.push(trie[i]); while(pq.size()>1) { Huffman_trie *h1 = (Huffman_trie*)malloc(sizeof(Huffman_trie)); *h1 = pq.top(); pq.pop(); Huffman_trie *h2 = (Huffman_trie*)malloc(sizeof(Huffman_trie)); *h2 = pq.top(); pq.pop(); Huffman_trie h3; h3.left=h1; h3.right=h2; h3.freq=h1->freq+h2->freq; pq.push(h3); } *root = pq.top();
（4）哈夫曼树建立完之后就是求其编码长度的问题了，这时候就是遍历该树的问题了，方法有很多，可以深度遍历，也可以广度遍历。这里采用广度遍历，同时借助于一个queue进行的。
queue<Huffman_trie>q; q.push(*root); while(!q.empty()) { Huffman_trie ht=q.front(); q.pop(); if(ht.left!=NULL) { ht.left->deep=ht.deep+1; q.push(*ht.left); } if(ht.right!=NULL) { ht.right->deep=ht.deep+1; q.push(*ht.right); } if(!ht.left&&!ht.right) sum+=ht.deep*ht.freq; }
（5）剩下的就很简单了，不做过多的赘述。
整个题的全部代码
#include <iostream> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef struct Huffman_trie { int deep;//深度 int freq;//频度（即哈夫曼树中的权重） Huffman_trie *left,*right; //优先权队列中用于排序比较的方法，不懂的建议先学一学优先权队列 friend bool operator<(Huffman_trie a,Huffman_trie b) return a.freq>b.freq; }Huffman_trie; Huffman_trie trie[300];//哈夫曼树节点 Huffman_trie *root; int len,count_num,index,sum; priority_queue<Huffman_trie> pq; void huffman() { sum=0; root = (Huffman_trie*)malloc(sizeof(Huffman_trie)); for(int i=0;i<index;i++) pq.push(trie[i]); while(pq.size()>1) { Huffman_trie *h1 = (Huffman_trie*)malloc(sizeof(Huffman_trie)); *h1 = pq.top(); pq.pop(); Huffman_trie *h2 = (Huffman_trie*)malloc(sizeof(Huffman_trie)); *h2 = pq.top(); pq.pop(); Huffman_trie h3; h3.left=h1; h3.right=h2; h3.freq=h1->freq+h2->freq; pq.push(h3); } *root = pq.top(); pq.pop(); root->deep=0; queue<Huffman_trie>q; q.push(*root); while(!q.empty()) { Huffman_trie ht=q.front(); q.pop(); if(ht.left!=NULL) { ht.left->deep=ht.deep+1; q.push(*ht.left); } if(ht.right!=NULL) { ht.right->deep=ht.deep+1; q.push(*ht.right); } if(!ht.left&&!ht.right) sum+=ht.deep*ht.freq; } } int main() { char str[1000]; while(scanf("%s",str)!=EOF&&strcmp(str,"END")!=0) { len = strlen(str); str[len]='!'; sort(str,str+len); count_num=1; index=0; for(int i=1;i<=len;i++) { if(str[i]!=str[i-1]) { trie[index++].freq=count_num; count_num=1; }else count_num++; } if(index==1) printf("%d %d 8.0\n",len*8,len); else { huffman(); printf("%d %d %.1lf\n",len*8,sum,len*8*1.0/sum); } } return 0; }
本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2012/11/14/2769367.html ，如需转载请自行联系原作者
