hafu-3.c

静态的哈夫曼编码

#include"stdio.h" 
#include"stdlib.h"
#include"string.h"

typedef char ElemType;
typedef struct
{ 
   ElemType elem;
   unsigned int m_weight; 
   unsigned int parent,lchild,rchild; 
}HTNode,*HuffmanTree;

typedef char** HuffmanCode; 
typedef int Status; 
typedef struct weight
{
  char elem; 
  unsigned int m_weight; 
}Weight; // save the information of the symbolizes; 

void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);

int main()
{ 
    HuffmanTree HT;
    HuffmanCode HC;
    Weight *w;
    FILE *src,*dest,*src1;
    char c;     // the symbolizes;
    int i,n=0,erro=1,len=0,marker=1;
    int wei;    // the weight of a element;
    w=(Weight *)malloc(256*sizeof(Weight));
    if(!(src = fopen("FILE.txt","r")))
	{
		printf("cannot open the source file! \n");
		return 0;
	}
    if(!(dest = fopen("CODE-U.txt","w")))
	{
        printf("cannot open the destination file! \n");
		return 0;
	}
	
    while((erro=fscanf(src,"%c",&c))!=EOF)
    {
         if(n==0)              ///first node
         {
            w[0].elem=c;
            w[0].m_weight=1;
            n++;
         }
         else
            if(n)
            {
                for(i=0;i<n;i++)
                    if(w[i].elem==c)
                    {
                        w[i].m_weight++;
                        break;
                    }
                    if(i==n)
                    {
                         w[++n].elem=c;
                         w[n].m_weight=1;
                    } //if

            }
            len++;
     }//while
     n--;
    HuffmanCoding(&HT,&HC,w,n);
    printf("\n");
    for(i=1;i<=n;i++)
        printf("the huffman code of %c is %s\n",HT[i].elem,HC[i]);

    src1 = fopen("FILE.txt","r");
    while((erro=fscanf(src1,"%c",&c))!=EOF)
    {
        for(i=0;i<len;i++)
        if(c==HT[i].elem)
        {
            fprintf(dest,"%s",HC[i]);
            break;
        }
    }
    printf("\nFILE.txt was encoded to FILE-U.txt by huffman codeing\n");
    fclose(src);fclose(src);
    fclose(dest);
    getch();
    return 1;

} 

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{ 
    int i,m,s1,s2,start,c,f;
    char *cd;
     HuffmanTree p;

    if(n<=1)
     return;

    m=2*n-1;
    (*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(i=1;i<=n;++i)
    {
        (*HT)[i].elem=w[i-1].elem;
        (*HT)[i].m_weight=w[i-1].m_weight;
        (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
    }

    for(;i<=m;++i)
    {
        (*HT)[i].elem='0';
        (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
    }

    for(i=n+1;i<=m;++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].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
    }

    (*HC)=(HuffmanCode)malloc(n*sizeof(char*));
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=1;i<=n;++i)
    {
        start=n-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((n-start)*sizeof(char));
        strcpy((*HC)[i],&cd[start]);
    }
} 

void Select(HuffmanTree HT,int n,int *s1,int *s2)
{ 
    int i;
    (*s1)=(*s2)=0;
    for(i=1;i<=n;i++)
    {
        if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
        {
            if(HT[i].m_weight<HT[(*s1)].m_weight)
            {
                (*s2)=(*s1);
                (*s1)=i;
            }
            else
                (*s2)=i;

        }

        if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
        {
            if((*s1)==0)
                (*s1)=i;
            else
                if((*s2)==0)
                {
                    if(HT[i].m_weight<HT[(*s1)].m_weight)
                        {
                            (*s2)=(*s1);
                            (*s1)=i;
                        }
                    else
                        (*s2)=i;
                } // end of else if
        } // end of if
    } // end of for

    if((*s1)>(*s2))
    {
        i=(*s1);
        (*s1)=(*s2);
        (*s2)=i;
    }
    return;
}