题目很长，长的都读不懂咋回事，不过很好理解，意思就是给你个字符串，让你输出用普通ASCII编码和用huffman编码分别占用的位数，然后输出压缩比；
第一次写哈夫曼编码，写了半天，到最后还wa了好几次，这个压缩比的输出格式太蛋疼了，他说保留一位小数，但是如果是x.0,则直接输出x，这一天找了半天，最后试了好些格式才给试出来的。虽然题目没有要求写编码和解码，但是由于想练习下，我自己也给写了出来；
大题思路是：首先找出每个字符出现的频率（即次数），然后每个字符首先占一个节点，然后对所有节点取频率最小的两个，再构造一个节点为这两个节点的父节点，其频率为这个节点频率之和，直到只剩下一个节点，此节点即为根节点，然后对各个节点进行编码，跟节点没有编码，然后递归编码，规则为：一个节点的左孩子的编码为此节点的编码加‘0’，右孩子的编码为此节点的编码+‘1’；直到没有左右孩子为止；
然后求编码长度的时候，对于所有的叶子节点，让其编码长度乘频率，然后累加，就得到所有编码的长度了。
参考代码如下：
[cpp] #include
#include
#include
#include
#include
#include
#include
using namespace std;
struct Node
{
int val; //记录节点的频率
char c; //节点机率的字符，中间节点的c值均设为0；
int len; //编码的长度；
char code[31]; //编码；
int num; //记录在数组中的位置，存属为了操作方便，完全可以没有；
int lchild; //左孩子的下标 若没有 为-1；
int rchild; //右孩子的下标，若没有，为-1；
int parent; //父亲节点的下标，若没有，为-1；
};
bool operator <(const Node &a,const Node &b) //考虑到用到优先队列取最小和次小，所有重载下<号
{
return a.val>b.val;
}
Node a[201];
int lens; //字符串长度
int lentree; //数的节点的个数；
char s[10001]; //读入的字符串
int flag[10001]; //用来判断字符串的某一位的字符之前有没有出现过
int pcodelen,nowcodelen; //分别表示用ASCII编码和用huffman编码的长度
double ans; //压缩比
void codenode(int k) //对各个节点进行编码；
{
if(a[k].lchild!=-1)
{
strcpy(a[a[k].lchild].code,a[k].code);
a[a[k].lchild].code[a[k].len]='0';
a[a[k].lchild].len=a[k].len+1;
codenode(a[k].lchild);
}
if(a[k].rchild!=-1)
{
strcpy(a[a[k].rchild].code,a[k].code);
a[a[k].rchild].code[a[k].len]='1';
a[a[k].rchild].len=a[k].len+1;
codenode(a[k].rchild);
}
if(a[k].lchild==-1&&a[k].rchild==-1)
{
nowcodelen+=a[k].val*a[k].len; //如果为叶子几点则令nowcodelen的值增加此节点编码长度的值
}
}
void codestr(char *source,char *code) //对字符串进行编码
{
int i;
int j;
int lencode=0;
int lensource=strlen(source);
for(i=0;i
for(j=0;j<(lentree+1)/2;j++)
{
if(a[j].c==source[i])
{
strcpy(code+lencode,a[j].code);
lencode+=a[j].len;
}
}
}
code[lencode]=0;
}
void decode(char *code,char *str)//解码
{
int i;
int lenstr=0;
int lencode=strlen(code);
for(i=0;i
int t=lentree-1;
while(a[t].lchild!=-1||a[t].rchild!=-1)
{
if(code[i]=='0')
{
t=a[t].lchild;
i++;
}
else
{
t=a[t].rchild;
i++;
}
}
str[lenstr++]=a[t].c;
}
str[lenstr]=0;
}
void execute()
{
if(lentree==1)
{
nowcodelen=a[lentree-1].val;
return ;
}
int i;
priority_queue
while(!q.empty())
q.pop();
for(i=0;i
a[i].rchild=a[i].lchild=-1;
a[i].num=i;
q.push(a[i]);
}
while(q.size()!=1)//构造最优二叉树
{
Node x1=q.top();
q.pop();
Node x2=q.top();
q.pop();
a[lentree].val=x1.val+x2.val;
a[lentree].rchild=x1.num;
a[lentree].lchild=x2.num;
a[lentree].num=lentree;
q.push(a[lentree]);
lentree++;
}
a[lentree].len=0; //先令根节点的编码长度为0；
nowcodelen=0;
codenode(lentree-1);
/*