huffman.c

多个Huffman编码、解码器的程序

#include"stdio.h"
#include"malloc.h"
#include"string.h"
#define MAX 100 //定义一个最大值
typedef struct
{
	int weight;
    int parent,lchild,rchild;
    char code;
}hufftree;//定义哈夫曼树的类型
typedef char * huffcode;
void select(hufftree *p,int j,int *s)//查找j以前的两个权值最小的元素
{
	int i,m,n,mid,t;                    
    hufftree *q;
    m=n=MAX;//m中存放最小,n的中存放次小的
    for(i=0,q=p;i<j;i++,q++)
       if(q->parent==0)
	   {  if(q->weight<m)
	   {     mid=m;  m=q->weight;  n=mid;
             t=*s; *s=i; *(s+1)=t;
	   }//若找到最小的则交换
          else if(q->weight<n)
          {      n=q->weight;  *(s+1)=i;}
	   }
}
void output(hufftree *ht,int n)//输出建好的哈夫曼树函数
{
	int m,i;
    hufftree *p;
    m=2*n-1;
    printf("建好的哈夫曼树为:\n");
    for(i=0,p=ht;i<m;i++,p++)
       printf("%c  %3d%3d%3d%3d\n",p->code,p->weight,p->parent,p->lchild,p->rchild);
}
void hcode(hufftree *ht,int *w,int n)//哈夫曼编码//
{
	int i,m,s[2]; 
    hufftree *p;
    m=2*n-1;
    for(i=0,p=ht;i<n;i++,p++,w++)
	{  p->weight=*w;
       p->parent=p->lchild=p->rchild=0;
	}
    for(;i<m;i++,p++)
       p->weight=p->parent=p->lchild=p->rchild=0;
    for(i=n;i<m;i++)
	{  select(ht,i,s);
       (ht+s[0])->parent=i;  (ht+s[1])->parent=i;
       (ht+i)->code='*',(ht+i)->lchild=s[0];  (ht+i)->rchild=s[1];
       (ht+i)->weight=(ht+s[0])->weight+(ht+s[1])->weight;
	}
}
void huffc(hufftree *ht,huffcode *hc,int n)
{   
	char *cd;
    int i,start,c,f;
    cd=(char*)malloc(n*sizeof(char));
    *(cd+n-1)='\0';
    for(i=0;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*sizeof(char));
       strcpy(*(hc+i),cd+start);
	}
    free(cd);
}
void change(hufftree *ht,huffcode *hc,int n)
{
	char c[10];
    int i,sign;
    huffcode *p;
    printf("如果想检验代码请输入1否则输入0\n");
    scanf("%d",&sign);
    getchar();
    while(sign)
	{   printf("请输入所要检验的代码\n");
        gets(c);
        for(i=0,p=hc;i<n;i++,p++)
           if(!strcmp(c,*p))  break;
        if(i>=n)  printf("此代码有误\n");
          else printf("此代码对应的字符为: %c\n",(ht+i)->code);
        printf("如果想继续检验代码请输入1否则输入0\n");
        scanf("%d",&sign);
        getchar();
	}
}

main()
{
	int n,m,i,*w,*p;
    hufftree *ht,*q;
    huffcode *hc,*r;
    printf("请输入字符的个数\n");
    scanf("%d",&n);
    getchar();
    m=2*n-1;
    w=(int*)malloc(m*sizeof(int)); 
    ht=(hufftree*)malloc(m*sizeof(hufftree));
    printf("请逐个输入每个字符及其权值\n\n\n");
    for(i=0,p=w,q=ht;i<n;i++,p++,q++)
	{   printf("请输入字符及其权值\n");
        q->code=getchar();
        scanf("%d",p);
        getchar();
	}
    hcode(ht,w,n);
    output(ht,n);
    hc=(huffcode*)malloc(m*sizeof(huffcode));
    huffc(ht,hc,n);
    printf("编码如下:\n");
    for(i=0,q=ht,r=hc;i<n;i++,q++,r++)
       printf("%c  %s\n",q->code,*r);
    change(ht,hc,n);
}