lala.c

这个程序主要实现对huffman编码的。huffman是数据结构的上机实验之一

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct{
  int weight;
  int parent,lchild,rchild;
  }HTNode,* HufumanTree;
typedef char * *HumanCode;

void Select(HTNode HT[],int k,int *s1,int *s2)
{ int i;
  for (i=1;i<=k && HT[i].parent!=0 ;i++);
  *s1=i;
  for (i=1;i<=k;i++)
    if (HT[i].parent==0 && HT[i].weight<HT[*s1].weight) *s1=i;
  for (i=1; i<=k ; i++)
    if (HT[i].parent==0 && i!=*s1) break;
  *s2=i;
  for (i=1;i<=k;i++)
    if ( HT[i].parent==0 && i!=*s1 && HT[i].weight<HT[*s2].weight) *s2=i;
}



main()
{
  int arra[26];
  float *w;
  FILE *fp;
  char letter,filename[40],*d,*cd;
  int n=0,m;
  int start,*y1,*y2,
      i,c,f,j,f1=1,f2=1,a,b;
  HufumanTree HT,p;
  HumanCode HC;
 y1=&a;
 y2=&b;

for(i=0;i<=25;i++)
  arra[i]=0;
printf("\nEnter a filename:");
  gets(filename);

if((fp=fopen(filename,"r"))==NULL)
    printf("Error opening ");
 else
    {
     while((letter=fgetc(fp))!=EOF)
      {if((letter<=122)&(letter>=97))
    arra[letter-97]++;}
   }

for(i=0;i<=25;i++)
{if(arra[i]!=0)
  n++;
 }
m=2*n-1;
w=(float *)malloc((n+1)*sizeof(float));
d=(char *)malloc((n+1)*sizeof(char));

for(i=0;i<=25;i++)
   if(arra[i]!=0)
      {
      d[f1]=i+97;
      w[f2]=arra[i];
      f1++;
      f2++;
      }
HT=(HufumanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,j=1;j<=n;++j)
{
p[j].weight=w[j];
p[j].parent=0;
p[j].lchild=0;
p[j].rchild=0;
}
for(;j<=m;++j)
{
p[j].weight=0;
p[j].parent=0;
p[j].lchild=0;
p[j].rchild=0;
}
for(i=n+1;i<=m;++i)
{
Select(HT,i-1,y1,y2);
HT[a].parent=i;HT[b].parent=i;
HT[i].lchild=a;HT[i].rchild=b;
HT[i].weight=HT[a].weight+HT[b].weight;
}
HC=(HumanCode)malloc((n+1)*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]);
}
free(cd);

printf("\ncharacter     weight                code\n");

for(i=1;i<=n;i++)
printf("%c%15f%20s\n",d[i],w[i],HC[i]);



fclose(fp);
}