哈夫曼樹編碼 代碼
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;
void Select(HuffmanTree HT,int n,int &first,int &second)
{
int min=100000;
for (int i=0;i<n;i++){
if(min>HT[i].weight&&HT[i].parent==0){
first=i;
min=HT[i].weight;
}
}
min=100000;
for (int i=0;i<n;i++)
{
if(min>HT[i].weight&&first!=i&&HT[i].parent==0){
second=i;
min=HT[i].weight;
}
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
if(n<1) return;
int m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for (int i=0;i<n;i++){
HT[i].weight=w[i];
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
for(int j=n;j<m+1;j++){
HT[j].weight=0;
HT[j].parent=HT[j].lchild=HT[j].rchild=0;
}
for(int i=n;i<m;i++){
int first,second;
Select(HT,i,first,second);
HT[i].lchild=first;
HT[i].rchild=second;
HT[first].parent=i;
HT[second].parent=i;
HT[i].weight=HT[first].weight+HT[second].weight;
printf("%d(%d,%d)\n",HT[i].weight,HT[first].weight,HT[second].weight);
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
char *cd=(char*)malloc(sizeof(char)*(n+1));
cd[n-1]='\0';
for(int i=0;i<n;i++)
{
int start=n-1;
for(int 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(sizeof(char)*(n-start));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
int main()
{
int w[100],n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&w[i]);
}
HuffmanCode HC;
HuffmanTree HT;
HuffmanCoding(HT,HC,w,n);
for(int i=0;i<n;i++)
{
printf("%s\n",HC[i]);
}
}