今天给大家分享的是由图老师小编精心为您推荐的霍夫曼树编码的实现，喜欢的朋友可以分享一下，也算是给小编一份支持，大家都不容易啊!
【 tulaoshi.com - 编程语言 】
#include stdio.h（本文来源于图老师网站，更多请访问http://www.tulaoshi.com/bianchengyuyan/）
#include stdlib.h
#include string.h
#include conio.h
typedef struct
{
unsigned int Weight;
unsigned int Parent;
unsigned int lChild;
unsigned int rChild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
int LookFor(char *str,char letter,int count);
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count);
void HuffmanCoding(HuffmanTree *HT,
HuffmanCode *HC,
int *Weight,
int Count);
void Select(HuffmanTree HT,int Count,int *s1,int *s2);
int main()
{
HuffmanTree HT;
HuffmanCode HC;
char Data[100];
char *WhatLetter;
int *Weight;
int Count;
int i;
printf("Please input the line:");
/* Example: aaaaaaaaaaaaaabcccccc*/
scanf("%s",Data);
printf("n");
OutputWeight(Data,strlen(Data),
&WhatLetter,
&Weight,
&Count);
HuffmanCoding(&HT,&HC,Weight,Count);
printf(" Letter Weight Coden");
for(i=0;iCount;i++)
{
printf(" %c ",WhatLetter[i]);
printf("%d ",Weight[i]);
printf("%sn",HC[i+1]);
}
printf("n");
getch();
return 0;
}
void HuffmanCoding(HuffmanTree *HT,
HuffmanCode *HC,
int *Weight,
int Count)
{
int i;
int s1,s2;
int TotalLength;
HuffmanTree p;
char* cd;
unsigned int c;
unsigned int f;
int start;
if(Count=1) return;
TotalLength=Count*2-1;
(*HT)=(HuffmanTree)malloc((TotalLength+1)*sizeof(HTNode));
p=((*HT)++);
for(i=1;i=Count;i++)
{
(*HT)[i].Parent=0;
(*HT)[i].rChild=0;
(*HT)[i].lChild=0;
(*HT)[i].Weight=(*Weight);
Weight++;
}
for(i=Count+1;i=TotalLength;i++)
{
(*HT)[i].Weight=0;
(*HT)[i].Parent=0;
(*HT)[i].lChild=0;
(*HT)[i].rChild=0;
}
/*///////////////////Create HuffmanTree////////////////*/
for(i=Count+1;i=TotalLength;++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;
}
/*///////////////////Output Huffman Code///////////////*/
(*HC)=(HuffmanCode)malloc((Count+1)*sizeof(char*));
cd=(char*)malloc(Count*sizeof(char));
cd[Count-1]=' ';
for(i=1;i=Count;++i)
{
start=Count-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((Count-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
}
}
}
void Select(HuffmanTree HT,int Count,int *s1,int *s2)
/*/(*s1) is smallest,(*s2) is smaller.*/
{
int i;
unsigned int temp1=0;
unsigned int temp2=0;
unsigned int temp3;
for(i=1;i=Count;i++)
{
if(HT[i].Parent==0)
{
if(temp1==0)
{
temp1=HT[i].Weight;
(*s1)=i;
}
else
{
if(temp2==0)
{
temp2=HT[i].Weight;
(*s2)=i;
if(temp2temp1)
{
temp3=temp2;
temp2=temp1;
temp1=temp3;
temp3=(*s2);
(*s2)=(*s1);
(*s1)=temp3;
}
}
else
{
if(HT[i].Weighttemp1)
{
temp2=temp1;
temp1=HT[i].Weight;
(*s2)=(*s1);
(*s1)=i;
}
if(HT[i].Weighttemp1&&HT[i].Weighttemp2)
{
temp2=HT[i].Weight;
(*s2)=i;
}
}
}
}
}
}
int LookFor(char *str,char letter,int count)
{
int i;
for(i=0;icount;i++)
{
if(str[i]==letter) return i;
}
return -1;
}
void OutputWeight(char *Data,int Length,
char **WhatLetter,
int **Weight,int *Count)
{
int i;
char* Letter=(char*)malloc(Length);
int* LetterCount=(int *)malloc(Length);
int AllCount=0;
int Index;
int Sum=0;
float Persent=0;
for(i=0;iLength;i++)
{
if(i==0)
{
Letter[0]=Data[i];
LetterCount[0]=1;
AllCount++;
}
else
{
Index=LookFor(Letter,Data[i],AllCount);
if(Index==-1)
{
Letter[AllCount]=Data[i];
LetterCount[AllCount]=1;
AllCount++;
}
else
{
LetterCount[Index]++;
}
}
}
for(i=0;iAllCount;i++)
{
Sum=Sum+LetterCount[i];
}
(*Weight)=(int*)malloc(AllCount);
(*WhatLetter)=(char*)malloc(AllCount);
for(i=0;iAllCount;i++)
{
Persent=(float)LetterCount[i]/(float)Sum;
(*Weight)[i]=(int)(1000*Persent);
(*WhatLetter)[i]=Letter[i];
}
(*Count)=AllCount;
}
来源:http://www.tulaoshi.com/n/20160219/1614954.html
