本文主要是介绍杭电OJ 1053：Entropy，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个问题的主要难点是构建huffman树，在构建huffman树的过程中可以使用优先队列，另外在计算总的编码长度的时候用了树的遍历算法。需要注意的是如果出现的字符只有一种，这种情况要单独考虑。下面的代码还给出了指针优先队列的用法（指针优先队列和值优先队列的用法不太一样）。
C++代码：
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
const int N=10000;
class node{
public:node *left;node *right;char value;int weight;
};
class cmp{
public:bool operator()(const node *n1,const node *n2){return n1->weight>n2->weight;}
};
int inOrder(node *r,int level){int res=0;if(r==NULL)return 0;res=inOrder(r->left,level+1);if(r->value!='*')res+=r->weight*level;res+=inOrder(r->right,level+1);return res;
}
int main(){//freopen("1.txt","r",stdin);char arr[N];priority_queue<node*,vector<node*> ,cmp> Q;while(scanf("%s",arr)!=EOF){while(Q.empty()==false)Q.pop();if(strcmp("END",arr)==0)break;int len=strlen(arr);int fre[27]={0};for(int i=0;i<len;i++){if(arr[i]=='_')fre[26]++;elsefre[arr[i]-'A']++;}int type=0;for(int i=0;i<26;i++){if(fre[i]!=0){node *tmpNode=new node();tmpNode->left=NULL;tmpNode->right=NULL;tmpNode->value=i+'A';tmpNode->weight=fre[i];Q.push(tmpNode);type++;}}if(fre[26]!=0){node *tmpNode=new node();tmpNode->left=NULL;tmpNode->right=NULL;tmpNode->weight=fre[26];tmpNode->value='_';Q.push(tmpNode);type++;}if(type==1){printf("%d %d %.1f\n",len*8,len,len*8/(float)len);}else{while(Q.size()>1){node *t1=Q.top();Q.pop();node *t2=Q.top();Q.pop();node *t=new node();t->weight=t1->weight+t2->weight;t->left=t1;t->right=t2;t->value='*';Q.push(t);}node *root=Q.top();int res=inOrder(root,0);printf("%d %d %.1f\n",len*8,res,len*8/(float)res);}}return 0;
}这篇关于杭电OJ 1053：Entropy的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
