huma1.c

这是一个霍夫曼编码程序

#include <stdio.h>
#include <stdlib.h>
#define n 100
#define max1 10000
#define m   2*n-1
typedef struct
{ int     wi;
  char  data;
  int   parent,lchild,rchild;

}huffm;
typedef struct
	{  char bits[n+1];
	   int  start;
	   char codetext;
	}codetype;
void huffmtree(huffm ht[m+1],int nn)
{
   int i,j,maxnumaddr1,maxnumaddr2;
   int w,maxnum1_w,maxnum2_w;
   
   for(i=1;i<=m;i++)
   {
	 ht[i].wi=0;
     ht[i].parent=0;
	 ht[i].lchild=ht[i].rchild=0;
   }

    for(i=1;i<=nn;i++)
	{
	 printf("请输入字符对应权值:\n");
      scanf("%d",&w);
	  ht[i].wi=w;
	  printf("%c 的权值:%d\n",ht[i].data,ht[i].wi);
	}
      getchar();//去掉回车符
	for(i=nn+1;i<=2*nn-1;i++)
	{
            maxnumaddr2=maxnumaddr1=0;
            maxnum1_w=maxnum2_w=max1;
	     for(j=1;j<i;j++)
		 { if(ht[j].parent==0)
		    if(ht[j].wi<maxnum1_w)
		       {
			      maxnum2_w=maxnum1_w;
		          maxnum1_w=ht[j].wi;
			      maxnumaddr2=maxnumaddr1;
	              maxnumaddr1=j;
		       }
		     else if(ht[j].wi<maxnum2_w)
		       {
				 maxnum2_w=ht[j].wi;
			     maxnumaddr2=j;
		       }
		 }
		 ht[maxnumaddr1].parent=ht[maxnumaddr2].parent=i;
		 ht[i].lchild=maxnumaddr1;
		 ht[i].rchild=maxnumaddr2;
		 ht[i].wi=ht[maxnumaddr1].wi+ht[maxnumaddr2].wi;
		
	}
for(i=1;i<=2*nn-1;i++)
printf("ht[%d].wi:%d\n",i,ht[i].wi);
}

/*/void huffmcode(codetype code[n+1])*/
void main()
{
	codetype code[n+1];
	int i,j,parentaddr,childaddr;
	char ch,test='y';
    int number;
    codetype codenode;

    huffm ht[m+1];
 while((test=='Y')||(test=='y')) 
 {
    i=0; 
	printf("请输入编码字符集:\n");
    ch=getchar();//读入第一个字符   
    while(ch!='\n')
	{    
		i++;
	    ht[i].data=code[i].codetext=ch;
		ch=getchar();

	}
	number=i;
 printf("编码字符数:number=%d\n",number); 
	     huffmtree(ht,number);
	     for(i=1;i<=number;i++)
		 {
	        codenode.codetext=code[i].codetext;
	        codenode.start=number+1;
	        childaddr=i;
	        parentaddr=ht[i].parent;
	        while(parentaddr!=0)
			{
		         codenode.start--;
	             if(ht[parentaddr].lchild==childaddr)
			         codenode.bits[codenode.start]='0';
				     
		         else codenode.bits[codenode.start]='1';
                      
		              childaddr=parentaddr;
		              parentaddr=ht[parentaddr].parent;

			}
            
	        code[i]=codenode;
		printf("编码结果为:%c\n",code[i].codetext);
		 
     for(j=code[i].start;j<=number;j++)
		 printf("%c",code[i].bits[j]);
	printf("\n");
 }
 printf("\n继续请按(Y|y) 退出请按(N|n)?");
           
	       test=getchar();
		   getchar();
 }
}