•输出每个字符、其对应的权值、以及对应的huffman编码。
•输出格式:字符---权值---编码
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct {
int weight;
char letter;
int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储Huffman树
typedef char **HuffmanCode; //动态分配数组存储Huffman编码
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{ //i表示字符数,s1,s2分别为最小和次小的权值
int j,k;
for(k=1;k<i;k++)
if(HT[k].parent==0)
{ s1=k; break; }
for(j=1;j<i;j++)
if(HT[j].parent==0)
{ if(HT[j].weight<HT[s1].weight)
s1=j;
}
for(k=1;k<=i;k++)
if(HT[k].parent==0&&k!=s1)
{ s2=k; break; }
for(j=1;j<i;j++)
if(HT[j].parent==0)
{
if(HT[j].weight<=HT[s2].weight&&j!=s2&&j!=s1)
s2=j;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *ch,int *w,int n)
{//ch代表输入的字符,w代表字符的权值,n表示字符的个数
int m,i,s1,s2,f,c,start=1;
HuffmanTree p;
char *cd;
if(n<=1) return;
m=2*n-1; //n个字符生成树有(2n-1)
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=1;i<n;++i,++ch,++p,++w)
{
p->parent=0; p->lchild=0; p->rchild=0; p->weight=*w; p->letter=*ch;
}
for(;i<=m;++i,++p)
{
(*p).weight=0; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;
}
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int i,f=0,k,w[100];
char ch,c[100];
cin>>ch;
while(ch!='#')
{
for(i=0;i<f;i++)
if(c[i]==ch)
{
w[i]++; break;
}
if(i==f)
{
c[f]=ch; w[f]=1; f++;
}
cin>>ch;
}
HuffmanCoding(HT,HC,c,w,i);
for(k=0;k<=i;k++)
{
cout<<HT[k].letter<<"---"<<HT[k].weight<<"---"<<HC[k]<<endl;
}
}
•输出格式:字符---权值---编码
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct {
int weight;
char letter;
int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储Huffman树
typedef char **HuffmanCode; //动态分配数组存储Huffman编码
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{ //i表示字符数,s1,s2分别为最小和次小的权值
int j,k;
for(k=1;k<i;k++)
if(HT[k].parent==0)
{ s1=k; break; }
for(j=1;j<i;j++)
if(HT[j].parent==0)
{ if(HT[j].weight<HT[s1].weight)
s1=j;
}
for(k=1;k<=i;k++)
if(HT[k].parent==0&&k!=s1)
{ s2=k; break; }
for(j=1;j<i;j++)
if(HT[j].parent==0)
{
if(HT[j].weight<=HT[s2].weight&&j!=s2&&j!=s1)
s2=j;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *ch,int *w,int n)
{//ch代表输入的字符,w代表字符的权值,n表示字符的个数
int m,i,s1,s2,f,c,start=1;
HuffmanTree p;
char *cd;
if(n<=1) return;
m=2*n-1; //n个字符生成树有(2n-1)
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=1;i<n;++i,++ch,++p,++w)
{
p->parent=0; p->lchild=0; p->rchild=0; p->weight=*w; p->letter=*ch;
}
for(;i<=m;++i,++p)
{
(*p).weight=0; (*p).parent=0; (*p).lchild=0; (*p).rchild=0;
}
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i;
HT[i].lchild=s1; HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
void main()
{
HuffmanTree HT;
HuffmanCode HC;
int i,f=0,k,w[100];
char ch,c[100];
cin>>ch;
while(ch!='#')
{
for(i=0;i<f;i++)
if(c[i]==ch)
{
w[i]++; break;
}
if(i==f)
{
c[f]=ch; w[f]=1; f++;
}
cin>>ch;
}
HuffmanCoding(HT,HC,c,w,i);
for(k=0;k<=i;k++)
{
cout<<HT[k].letter<<"---"<<HT[k].weight<<"---"<<HC[k]<<endl;
}
}