霍夫曼树编码的实现

【 tulaoshi.com - 编程语言 】

#include stdio.h
#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;
}