首页 > C/C++语言 > C/C++数据结构 > 霍夫曼树编码的实现
2006
06-05

霍夫曼树编码的实现

C/C++数据结构留下评论

#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,
                    Huffma nCode *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);
        printf(“%d “,Weight);
        printf(“%s\n “,HC[i+1]);
    }
    printf(“\n”);
    getch();
    return 0;
}

void HuffmanCoding(HuffmanTree *HT,
                    Huffma nCode *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((TotalLeng th+1)*sizeof(HTNode));

    p=((*HT)++);
    for(i=1;i<=Count;i++)
    {
        (*HT).Parent=0;
        (*HT).rChild=0;
        (*HT).lChild=0;
        (*HT).Weight=(*Weight);
        Weight++;
    }
    for(i=Count+1;i<=TotalLength;i++)
    {
        (*HT).Weight=0;
        (*HT).Parent=0;
        (*HT).lChild=0;
        (*HT).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).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]=’\0′;
    for(i=1;i<=Count;++i)
    {
        start=Count- 1;
        for(c=i,f=(* HT).Parent;f!=0;c=f,f=(*HT)[f].Parent)
        {
             if((*HT)[f].lChild==c)
                 cd [--start]=’0′;
             else
                 cd [--start]=’1′;
             (*HC)=(char*)malloc((Count-start)*sizeof(char));
             strcpy((*HC),&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.Parent==0)
        {
             if(temp1==0)
             {
                 temp1=HT .Weight;
                 (*s1)=i;
             }
             else
             {
                 if(temp2==0)
                  {
                      temp2=HT.Weight;
                      (*s2)=i;
                      if(temp2<temp1)
                      {
                          temp3=temp2;
                          temp2=temp1;
                          temp1=temp3;

                          temp3=(*s2);
                          (*s2)=(*s1);
                          (*s1)=temp3;
                      }
                  }
                  else
                  {
                      if(HT.Weight<temp1)
                      {
                          temp2=temp1;
                          temp1=HT .Weight;

                          (*s2)=(*s1);
                          (*s1)=i;
                      }
                      if(HT.Weight>temp1&&HT.Weight<temp2)
                      {
                           temp2=HT.Weight;
                           (*s2)=i;
                      }
                  }
             }
        }
    }
}

int LookFor(char *str,char letter,int count)
{
    int i;
    for(i=0;i<count;i++)
    {
        if(str==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;i<Length;i++)
    {
        if(i==0)
        {
             Letter[0]=Data;
             LetterCount[0]=1;
             AllCount++;
        }
        else
        {
             Index=LookFor(Letter,Data ,AllCount);
             if(Index==-1)
             {
                  Letter[AllCount]=Data;
                  LetterCount[AllCount]=1;
                  AllCount++;
             }
             else
             {
                  LetterCount[Index]++;
             }
        }
    }
    for(i=0;i<AllCount;i++)
    {
        Sum=Sum+Lett erCount;
    }
    (*Weight)=(int*)malloc(AllCount);
    (*WhatLetter)=(char*)malloc(AllCount );

    for(i=0;i<AllCount;i++)
    {
        Persent=(flo at)LetterCount/(float)Sum;
        (*Weight)=(int)(1000*Persent);
        (*WhatLetter )=Letter;
    }
    (*Count)=AllCount;
}

>> 本文固定链接: http://www.vcgood.com/archives/778

>> 转载请注明: 2006年06月05日 于 C语言帝国 发表


您可能还会对这些文章感兴趣！

留下一个回复