霍夫曼树编码的实现

核心提示：#include <stdio.h>#include <stdlib.h>#include <string.h>#include <conio.h>typedef strUCt{unsigned int Weight;unsigned int Parent;unsigne

　　#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 Code\n");
　　for(i=0;i<Count;i++)
　　{
　　　　printf(" %c ",WhatLetter[i]);
　　　　printf("%d ",Weight[i]);

　　　　printf("%s\n",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]='\0';
　　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)
　　　　　　{
　　　　　　　 &