huff_tc.c

一份huff_tc.c

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

struct huffmantree         /*huffman树结构体*/
{
	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)  /*构造哈夫曼树HT*/
{
	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);    /*开辟空间，0号空间不用*/
	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 *));  /*分配n个字符编码的头指针向量*/
	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));    /*为第i个字符编码分配空间*/
		strcpy(HC[i],&cd[start]);         /*从cd复制编码到HC*/
	}
	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++)  /*遇到0向左访问，遇到1向右访问*/
		{
			if(code[j]=='0')i=HT[i].lchild;
		    else if(code[j]=='1')i=HT[i].rchild;
		}
		printf("%c",HT[i].c);  /*输出最终找到结点的原码*/
	}
	return;
}


void Draw(char *m,int x,int y,char c,char *s)  /*画哈夫曼树*/
{
	char p[2];
	if(*m=='0')    /*画左子树*/
	{
		circle(x-50,y+50,20);
		line(x-10*sqrt(2),y+10*sqrt(2),x-50+10*sqrt(2),y+50-10*sqrt(2));
		Draw(m+1,x-50,y+50,c,s);
	}
	else if(*m=='1')   /*画右子树*/
	{
		circle(x+50,y+50,20);
		line(x+10*sqrt(2),y+10*sqrt(2),x+50-10*sqrt(2),y+50-10*sqrt(2));
		Draw(m+1,x+50,y+50,c,s);
	}
	else if(*m=='\0')   /*在相应结点圆的中心输出原码*/
	{
	    p[0]=c;
	    p[1]='\0';
	    outtextxy(x-4,y,p);
	    outtextxy(x-8,y+30,s);
	}
	return;
}

void main()
{
	int drive=DETECT,mode;
	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);  /*求每个字符哈夫曼编码*/
	for(i=1;i<=n;i++)printf("the code of %c is %s\n",HT[i].c,HC[i]);
    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);    /*解码*/
	getch();        
	{
		initgraph(&drive,&mode," ");/*转化为图形界面*/
		settextstyle(TRIPLEX_FONT,HORIZ_DIR,5);
		outtextxy(280,20,"Huffman Tree");
		circle(320,70,20);
		for(i=1;i<=n;i++)
		{
			Draw(HC[i],320,70,HT[i].c,HC[i]);
		}
		getch();
		closegraph();   /*关闭图形界面*/
	}
}