題目很長，長的都讀不懂咋回事，不過很好理解，意思就是給你個字符串，讓你輸出用普通ASCII編碼和用huffman編碼分別占用的位數，然後輸出壓縮比；
第一次寫哈夫曼編碼，寫了半天，到最後還wa了好幾次，這個壓縮比的輸出格式太蛋疼了，他說保留一位小數，但是如果是x.0,則直接輸出x，這一天找了半天，最後試了好些格式才給試出來的。雖然題目沒有要求寫編碼和解碼，但是由於想練習下，我自己也給寫了出來；
大題思路是：首先找出每個字符出現的頻率（即次數），然後每個字符首先占一個節點，然後對所有節點取頻率最小的兩個，再構造一個節點為這兩個節點的父節點，其頻率為這個節點頻率之和，直到只剩下一個節點，此節點即為根節點，然後對各個節點進行編碼，跟節點沒有編碼，然後遞歸編碼，規則為：一個節點的左孩子的編碼為此節點的編碼加‘0’，右孩子的編碼為此節點的編碼+‘1’；直到沒有左右孩子為止；
然後求編碼長度的時候，對於所有的葉子節點，讓其編碼長度乘頻率，然後累加，就得到所有編碼的長度了。
參考代碼如下：
[cpp] #include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
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<lensource;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<lencode;)
{
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<Node> q;
while(!q.empty())
q.pop();
for(i=0;i<lentree;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);
/*
char code[10001];
codestr(s,code);
cout<<"編碼為:"<<endl;
cout<<code<<endl;
char str[10001];
decode(code,str);
cout<<"解碼後字符串為:"<<endl;
cout<<str<<endl;
*/
}
int main()
{
char c;
char cmp[6]={'E','N','D','\0'};
while(gets(s)&&strcmp(s,cmp)!=0)
{
lens=strlen(s);
lentree=0;
memset(flag,-1,sizeof(flag));
memset(a,0,sizeof(a));
for(int i=0;i<lens;i++)//構造所有葉子節點
{
if(flag[i]!=-1)
a[flag[i]].val++;
else
{
a[lentree].c=s[i];
a[lentree].val++;
for(int j=i+1;j<lens;j++)
if(s[j]==s[i])
flag[j]=lentree;
lentree++;
}
}
pcodelen=8*lens; //ASCII編碼長度就為字符串長度乘8
execute();
ans=(double)pcodelen/(double)nowcodelen;
cout<<pcodelen<<' ';
cout<<nowcodelen<<' ';
if((ans-floor(ans))<0.1) //如果ans小數點後一位為0，則輸出個整數
cout<<ans<<endl;
else
cout<<fixed<<setprecision(1)<<ans<<endl;
}
return 0;
}
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <cmath>
#include <cstdio>
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<lensource;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<lencode;)
{
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<Node> q;
while(!q.empty())
q.pop();
for(i=0;i<lentree;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);
/*
char code[10001];
codestr(s,code);
cout<<"編碼為:"<<endl;
cout<<code<<endl;
char str[10001];
decode(code,str);
cout<<"解碼後字符串為:"<<endl;
cout<<str<<endl;
*/
}
int main()
{
char c;
char cmp[6]={'E','N','D','\0'};
while(gets(s)&&strcmp(s,cmp)!=0)
{
lens=strlen(s);
lentree=0;
memset(flag,-1,sizeof(flag));
memset(a,0,sizeof(a));
for(int i=0;i<lens;i++)//構造所有葉子節點
{
if(flag[i]!=-1)
a[flag[i]].val++;
else
{
a[lentree].c=s[i];
a[lentree].val++;
for(int j=i+1;j<lens;j++)
if(s[j]==s[i])
flag[j]=lentree;
lentree++;
}
}
pcodelen=8*lens; //ASCII編碼長度就為字符串長度乘8
execute();
ans=(double)pcodelen/(double)nowcodelen;
cout<<pcodelen<<' ';
cout<<nowcodelen<<' ';
if((ans-floor(ans))<0.1) //如果ans小數點後一位為0，則輸出個整數
cout<<ans<<endl;
else
cout<<fixed<<setprecision(1)<<ans<<endl;
}
return 0;
}
