1.txt

哈夫曼树的建立 哈夫曼树的建立 哈夫曼树的建立

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

#define LEN sizeof(struct HTnode)

int i,l,n,w=0,c,start,a1,a2,f;

struct HTnode {unsigned int weight;

       unsigned int parent,lchild,rchild;

      }*p,*HT;

typedef char **Huffmancode;

Huffmancode HC;

char *cd;

select()

{int k=1,j,flag=0;

 while((HT+k)->parent!=0) k++;

 for(j=k+1;j<=n;j++,flag=0)

  {if((HT+j)->parent!=0) flag=1;

   if((HT+j)->weight==0) flag=1;

   if(!flag) {if((HT+j)->weight<(HT+k)->weight) k=j;}

  }

 return(k);

}

void main()

{printf("\n赫夫曼树的建立:\n");

 printf("请输入权值(叶子)数目:");

 scanf("%d",&l);

 while(l<1) {printf("输入错误,请重新输入权值数目:"); scanf("%d",&l); }

 if(l==1) printf("\n只有一个权值,无须建立赫夫曼树!");

 else {n=2*l-1;

       HT=(struct HTnode*)malloc((n+1)*LEN);

       printf("请按对应顺序输入权值(输入一权值,键入一回车):\n");

       for(i=1,p=HT+1;i<=l;++i,++p)

{scanf("%d",&w);

 while(w<=0){printf("权值错,重新输入此权值:"); scanf("%d",&w);}

 p->weight=w; p->parent=0;

 p->lchild=0; p->rchild=0;

}

      for(i=l+1;i<=n;++i,++p)

       {p->weight=0; p->parent=0;

p->lchild=0;

       }

      for(i=l+1;i<=n;++i)

       {a1=select(); (HT+a1)->parent=i;

a2=select(); (HT+a2)->parent=i;

       (HT+i)->lchild=a1;

       (HT+i)->rchild=a2;

       (HT+i)->weight=(HT+a1)->weight+(HT+a2)->weight;

       }

     HC=(Huffmancode)malloc((l+1)*sizeof(char *));

     cd=(char *)malloc(l*sizeof(char));

     *(cd+(l-1))='\0';

     for(i=1;i<=l;++i)

      {start=l-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((l-start)*sizeof(char));

      strcpy(*(HC+i),(cd+start));

     }

    printf("\n对应的二进制赫夫曼编码为:\n");

    for(i=1;i<=l;++i)

      {printf("%s",*(HC+i));

       printf("   ");

      }

 }

}