霍夫曼树编码的实现

2019-11-17 05:35:57

字体：大中小

来源：转载

供稿：网友

　　#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)
            {
               &

上一篇：几个游戏代码(麻将原代码)

下一篇：集邮问题