sdut 数据结构实验之二叉树六：哈夫曼编码

#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int main() { char s[10000]; while(scanf("%s",s)!=EOF) { priority_queue < int,vector<int>,greater<int> > Q;//利用优先队列，从小到大排序 int len=strlen(s); int i,max=0; int count[256]={0}; for(i=0;i<len;i++) { count[s[i]]++;//统计字符出现的频率，利用ASCII对应其数组的下标 if(s[i]>max) max=s[i];//找出频率最高的字符 } for(i=0;i<=max;i++) { if(count[i]!=0) Q.push(count[i]);//把字符出现的次数压入优先队列之中 } int sum=0; while(!Q.empty())//当队列不为空的时候弹出值 { int a=Q.top();//出第一个值 Q.pop(); if(!Q.empty()) { int b=Q.top();//出第二个值 Q.pop(); sum+=(a+b);//模拟构造赫夫曼树的过程，不过不理解如下面的例题所示。 Q.push(a+b); } } printf("%d %d %.1f\n",len*8,sum,len*8.0/sum); } return 0; }

例题：一组字符(a,b,c,d)在文中出现的次数分别为(7,6,3,5),字符＇d＇的哈夫曼编码的长度为？

首先构造huffman树 每一步都将所有数字排序 方法如下: 1: 3 5 6 7 2: 6 7 8 / \ 3 5 3: 8 13 / \ / \ 3 5 6 7 4: 21 / \ 8 13 / \ / \ 3 5 6 7 所以构造哈夫曼树如图 7 6 3 5 分别对应a b c d 如果左边为0 ,右边为 1 ,则他们编码分别为: a 11 b 10 c 00 d 01 长度为2