#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,
/t/t char **WhatLetter,
/t/t int **Weight,int *Count);
void HuffmanCoding(HuffmanTree *HT,
/t/t HuffmanCode *HC,
/t/t int *Weight,
/t/t 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("");
OutputWeight(Data,strlen(Data),
/t/t &WhatLetter,
/t/t &Weight,
/t/t &Count);
HuffmanCoding(&HT,&HC,Weight,Count);
printf(" Letter Weight Code");
for(i=0;i<Count;i++)
{
/tprintf(" %c ",WhatLetter);
/tprintf("%d ",Weight);
/tprintf("%s",HC[i+1]);
}
printf("");
getch();
return 0;
}
void HuffmanCoding(HuffmanTree *HT,
/t/t HuffmanCode *HC,
/t/t int *Weight,
/t/t 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++)
{
/t(*HT).Parent=0;
/t(*HT).rChild=0;
/t(*HT).lChild=0;
/t(*HT).Weight=(*Weight);
/tWeight++;
}
for(i=Count+1;i<=TotalLength;i++)
{
/t(*HT).Weight=0;
/t(*HT).Parent=0;
/t(*HT).lChild=0;
/t(*HT).rChild=0;
}
/*///////////////////Create HuffmanTree////////////////*/
for(i=Count+1;i<=TotalLength;++i)
{
/tSelect((*HT),i-1,&s1,&s2);
(*HT)[s1].Parent=i;
(*HT)[s2].Parent=i;
(*HT).lChild=s1;
(*HT).rChild=s2;
(*HT).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)
{
/tstart=Count-1;
/tfor(c=i,f=(*HT).Parent;f!=0;c=f,f=(*HT)[f].Parent)
/t{
/t if((*HT)[f].lChild==c)
/t/tcd[--start]='0';
/t else
/t/tcd[--start]='1';
/t (*HC)=(char*)malloc((Count-start)*sizeof(char));
/t strcpy((*HC),&cd[start]);
/t}
}
}
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++)
{
/tif(HT.Parent==0)
/t{
/t if(temp1==0)
/t {
/t/ttemp1=HT.Weight;
/t/t(*s1)=i;
/t }
/t else
/t {
/t/tif(temp2==0)
/t/t{
/t/t temp2=HT.Weight;
/t/t (*s2)=i;
/t/t if(temp2<temp1)
/t/t {
/t/t/ttemp3=temp2;
/t/t/ttemp2=temp1;
/t/t/ttemp1=temp3;
/t/t/ttemp3=(*s2);
/t/t/t(*s2)=(*s1);
/t/t/t(*s1)=temp3;
/t/t }
/t/t}
/t/telse
/t/t{
/t/t if(HT.Weight<temp1)
/t/t {
/t/t/ttemp2=temp1;
/t/t/ttemp1=HT.Weight;
/t/t/t(*s2)=(*s1);
/t/t/t(*s1)=i;
/t/t }
/t/t if(HT.Weight>temp1&&HT.Weight<temp2)
/t/t {
/t/t/ttemp2=HT.Weight;
/t/t/t(*s2)=i;
/t/t }
/t/t}
/t }
/t}
}
}
int LookFor(char *str,char letter,int count)
{
int i;
for(i=0;i<count;i++)
{
/tif(str==letter) return i;
}
return -1;
}
void OutputWeight(char *Data,int Length,
/t/t char **WhatLetter,
/t/t 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;i<Length;i++)
{
/tif(i==0)
/t{
/t Letter[0]=Data;
/t LetterCount[0]=1;
/t AllCount++;
/t}
/telse
/t{
/t Index=LookFor(Letter,Data,AllCount);
/t if(Index==-1)
/t {
/t/tLetter[AllCount]=Data;
/t/tLetterCount[AllCount]=1;
/t/tAllCount++;
/t }
/t else
/t {
/t/tLetterCount[Index]++;
/t }
/t}
}
for(i=0;i<AllCount;i++)
{
/tSum=Sum+LetterCount;
}
(*Weight)=(int*)malloc(AllCount);
(*WhatLetter)=(char*)malloc(AllCount);
for(i=0;i<AllCount;i++)
{
/tPersent=(float)LetterCount/(float)Sum;
/t(*Weight)=(int)(1000*Persent);
/t(*WhatLetter)=Letter;
}
(*Count)=AllCount;
}
