哈夫曼编码
数据结构上的代码实现。
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void Select(HuffmanTree &HT,int n,int &s1,int &s2)
{
for (int i = 0; i < n; i++)
{
if (HT[i].parent == 0)
{
s1=i;
break;
}
}
for (int i = 0; i <n; i++)
{
if ((HT[s1].weight > HT[i].weight) && (HT[i].parent == 0))
{
s1 = i;
}
}
for (int i = 0; i <n; i++)
{
if ((HT[i].parent == 0)&&i!=s1)
{
s2 = i;
break;
}
}
for (int i = 0; i <n; i++)
{
if ((HT[s2].weight > HT[i].weight) && (HT[i].parent == 0) && (i != s1))
{
s2 = i;
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int i,m,s1,s2,start;
char *cd;
unsigned int c, f;
if(n<=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=n;i++)
{
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=n+1;i<=m;i++)
{
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].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;
}
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);
}
int main()
{
int i,n;
int *w;
HuffmanTree HT;
HuffmanCode HC;
//汉字编码出了问题。。。。。。。
//printf("锟斤拷锟斤拷锟斤拷权值锟斤拷锟斤拷锟斤拷\n");
scanf("%d",&n);
w=(int *)malloc(n*sizeof(int));
//printf("锟斤拷锟斤拷锟斤拷权值锟斤拷\n");
for ( i=0;i<n;i++)
scanf("%d",&w[i]);
HC=(char **)malloc((n+1)*sizeof(char*));
HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));
HuffmanCoding(HT, HC, w, n);
for(i=1;i<n+1;i++)
{
puts(HC[i]);
free(HC[i]);
}
free(HC);
free(HT);
return 0;
}