huff_vc.c

一份huff_tc.c

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define LEN sizeof(struct huffmantree)
#define NULL 0

struct huffmantree
{
	char c;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
};

int Select(struct huffmantree *HT,int n)
{
	int i,k;
	for(k=1;HT[k].parent!=0;k++);
	for(i=1;i<=n;i++)
	{
		if(HT[i].parent==0)
		{
			if(HT[k].weight>=HT[i].weight)k=i;
		}
	}
	return(k);
}

struct huffmantree *HuffmanCreat(char *c1,int *w,int n)
{
	struct huffmantree *p,*HT=NULL;
	int i,m,s1,s2;
	if(n<=1)return(HT);
	m=2*n-1;
	HT=(struct huffmantree *)malloc((m+1)*LEN);
	for(p=HT+1,i=1;i<=n;i++,p++,w++,c1++)
	{
		p->weight=*w;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
		p->c=*c1;
	}
	for(;i<=m;i++,p++)
	{
		p->weight=0;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}
	for(i=n+1;i<=m;i++)
	{
		s1=Select(HT,i-1);		
		HT[s1].parent=i;
		s2=Select(HT,i-1);
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	return(HT);
}

char **HuffmanCode(struct huffmantree *HT,int n)
{
	char *cd;
	char **HC;
	int i,start,f;
	unsigned c;
	HC=(char **)malloc(n*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);
	return(HC);
}

void CompileCode(struct huffmantree *HT,char **HC,char *s,int n)
{
	int i,j;
	printf("the compile code is :\n");
	for(j=0;s[j]!='\0';j++)
	{
		for(i=1;i<=n;i++)
		{
			if(HT[i].c==s[j])break;
		}
	    printf("%s",HC[i]);
	}
	return;
}

void CodeSolve(struct huffmantree *HT,char *code,int n)
{
	int i,j;
	printf("the solve code is :\n");
	for(j=0;code[j]!='\0';)
	{
		for(i=2*n-1;i>n;j++)
		{
			if(code[j]=='0')i=HT[i].lchild;
		    else if(code[j]=='1')i=HT[i].rchild;
		}
		printf("%c",HT[i].c);
	}
	return;
}

void main()
{
	struct huffmantree *HT;
	int i,n=0;
	int w[30];
	char **HC;
	char code[100],c[30],s[30];
	printf("input the original char :\n");
    gets(c);
	n=strlen(c);
	for(i=0;i<n;i++)
	{
		printf("input the weight of the %c :\n",c[i]);
		scanf("%d",&w[i]);
	}
	HT=HuffmanCreat(c,w,n);
	HC=HuffmanCode(HT,n);
    printf("input the original translation :\n");
	scanf("%s",s);
	CompileCode(HT,HC,s,n);
	printf("\n");
	printf("input the code :\n");
	scanf("%s",code);
	CodeSolve(HT,code,n);
	getchar();
	getchar();
}