二叉树.c

按照data.txt格式输入权值＆字符名覆盖原data的内容,就可以使用程序对由这些字符组成的字符串进行编码了,结果将输出至code.txt中

# include <stdio.h>
# include <stdlib.h>
# include <string.h>

typedef struct  
{
  int wei;
   int par,lc,rc;
}HTnode,*Huffmantree; 
 /*定义树节点的结构,树存储在一个数组中,通过int型Lc,rc,par进行访问,wei为权值*/
typedef char * * Huffmancode;/*定义一个字符型指针数组,存储对应的字符编码*/
char fu[100];/*存储被编码字符的数组*/
char s[1000];/*存储接受编码的text*/
Huffmancode HC;
int small(Huffmantree HT,int i,int j)/*HT[i,j]中较小的,并返回位置i or j*/
{
  if (HT[i].wei>=HT[j].wei) return j;
  else return i;
}
void select(Huffmantree HT,int n,int *s1,int *s2) 
/*获得二叉树中par!=0的最小的两个权值,并返回其位置*/
{
   int a,b,c=1;
   for (b=1;b<=n;b++)
   {
	   if (HT[b].par==0) break;
   }/*遍历获得par!=0的第一个数的位置b*/
   for (a=b+1;a<=n;a++)
   {
	   if (HT[a].par==0)
	  b=small(HT,b,a);
	   
   }/*获得最小的权值,并将其位置返回给s1*/
   *s1=b;
 for (c=1;c<=n;c++)
   {
	   if (c==b) continue;
		    else if (HT[c].par==0) break;
   }
 if (c+1>n) *s2=c;
 else
    for (a=c+1;a<=n;a++)
	{  
		if (a!=b)
 		 {
                if   (HT[a].par==0)
				{  
		           c=small(HT,c,a);
				} 
		} ;  
	*s2=c;
	} /*获得第二小的数,并返回位置*/

} 
void Huffman(Huffmantree HT,Huffmancode HC,int *w,int n)
/*哈夫曼编码程序并将编码结果输出到"code.txt"*/
{
  int m,i,c,f,start,p,q;
  int s1,s2;
  FILE *fp1;  
  char *cd;
   char a;
 
  fp1=fopen("code.txt","w");  /*建立一个可写入的code.txt文件*/
  if (n<=1) return;
  m=2*n-1;
  HT=(Huffmantree)malloc((m+1)*sizeof(HTnode));
             /*申请2n个空间存放HT*/
  for (i=1;i<=n;++i) 
  {
     (HT+i)->wei=w[i-1];
	 (HT+i)->lc=0;
	 (HT+i)->par=0;
	 (HT+i)->rc=0;
	
  }           /*给前n个HT结构赋初值wei值为权值w[]数组中的数*/
  for (;i<=m;++i)  
   {  
	  (HT+i)->wei=0;
	 (HT+i)->lc=0;
	 (HT+i)->par=0;
	 (HT+i)->rc=0; 
  }         /*给后n个HT结构赋初值wei值为权值w[]数组中的数*/
  for (i=n+1;i<=m;++i)
	        /*将par!=0的权值最小的两个作为左右儿子,父节点为HT[n+i]*/
  {
    select(HT,i-1,&s1,&s2);/*选择权值最小的,用s1,s2返回其位置*/
	HT[s1].par=i;HT[s2].par=i;
	HT[i].lc=s1; HT[s2].rc=s2;
	HT[i].wei=HT[s1].wei+HT[s2].wei;
  } 
 HC=(Huffmancode)malloc((m+1)*sizeof(char*)); /*申请指针数组空间,用来接收并存放字符的编码*/
  cd=(char *)malloc(n*sizeof(char));/*申请一个字符指针,临时存放fu[i]的编码*/
  cd[n-1]='\0';
  for (i=1;i<=n;++i)
  
  {
    start=n-1;
	   for (c=i,f=HT[i].par;f!=0;c=f,f=HT[f].par)
		                      /*依次给编码数组赋值*/
	   {
	     if (HT[f].lc==c) cd[--start]='0';
		 else cd[--start]='1';
	   }
	   HC[i]=(char *)malloc((n-start)*sizeof(char));
	   strcpy(HC[i],&cd[start]);
  }
  free(cd); 
  for (i=1;i<=n;i++)         /*将字符编码数组输出至code.txt中*/
  {
	  fprintf(fp1,"  %c  code is  :   ",fu[i-1]);
      fprintf(fp1,"%s\n",HC[i]);
  }
     
  printf("input s : ");
   gets(s);                  /*获得编码文件*/
   q=0;
   fprintf(fp1,"%s:\n",s);   /*将编码的text输出至code.txt*/
while (s[q]!='\0')
{ 
   for (p=0;p<=n;p++)
   if (s[q]==fu[p]) break;  
  fprintf(fp1,"%s",HC[p+1]);  /*将text的编码输出至code.txt*/
  q++;
} 
fclose(fp1);
}
main()
{
  int *w,i=0,j,n;
  FILE *fp;  
  Huffmantree HT; 
  w=(int*)malloc(200*sizeof(int));  
  fp=fopen("data.txt","r");
do                           /*获得data.txt中的权值数据,存入int w[]中*/
{ 
  fscanf(fp,"%d",&j);  
  w[i]=j;
  i++;
} 
while (fgetc(fp)!='\n') ;
n=0;
do                          /*获得data.txt中的编码字符数据,存放如char fu[]中*/
{
fu[n++]=fgetc(fp); 
}
while (fgetc(fp)!='\n') ;
fclose(fp);
Huffman(HT,HC,w,i);        /*编码*/

}