频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
poj 1521 Entropy huffman(哈夫曼)编码
2013-06-03 10:56:36           
收藏   我要投稿

题目很长,长的都读不懂咋回事,不过很好理解,意思就是给你个字符串,让你输出用普通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;
}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 哈夫曼 编码
上一篇:一种可靠的 DLL 接口实现方案
下一篇:POJ 1704(Georgia and Bob-Nim博弈)
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站