codestr(s,code);
cout<<"编码为:"<
decode(code,str);
cout<<"解码后字符串为:"<
}
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
if(flag[i]!=-1)
a[flag[i]].val++;
else
{
a[lentree].c=s[i];
a[lentree].val++;
for(int j=i+1;j
flag[j]=lentree;
lentree++;
}
}
pcodelen=8*lens; //ASCII编码长度就为字符串长度乘8
execute();
ans=(double)pcodelen/(double)nowcodelen;
cout<
cout<
cout<
return 0;
}
#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);
/*
char code[10001];
codestr(s,code);
cout<<"编码为:"<
decode(code,str);
cout<<"解码后字符串为:"<
}
int main()
{
char c;
char cmp[6]=