huffman.cpp

实现了Huffman编码的过程。执行环境为 TC 3.0。

#include<stdio.h>
#include<alloc.h>
#include<string.h>
#include<conio.h>
#define	len	80
void select(struct hafuman *x,int *y1,int *y2,int str_length);
struct hafuman
{
	double  weigth;
	int  parent,lchild,rchild;
}htnode,*huffmantree;
void  main()
{
//----------Initialization.
again:  FILE    *f_str;
	char	*f_path;
	int	tree_point,el_number,s1,s2;
	int	i,j,*x,*y;
	int	str_length,str_length1,el_label=0,n4[70];
	double	a3[len],el_gailu[len];
	char	*cd,*hc,str_array[80],*str_element,ch_again;
	typedef char **huffmancode;
	struct	hafuman *huffman_tree,*p,pp[2*len-1];
	char	*str_exit={"System is trying to Quit...Byebye!"};
	printf("Please input the file PATH:");
	gets(f_path);
	f_str=fopen(f_path,"r");
	fgets(str_array,80,f_str);
	str_length=strlen(str_array);
	str_element[0]=str_array[0];
//----------Get the element of the string.
	for(i=1;i<str_length;i++)
	{
		for(j=0;j<=el_label;j++)
		if(str_element[j]==str_array[i])
			{goto loop;}
		str_element[++el_label]=str_array[i];
loop:		continue;
	}
//----------Get the number of each element.
	for(j=0;j<=el_label;j++)
	{
		n4[j]=0;
		for(i=0;i<str_length;i++)
		if(str_element[j]==str_array[i])
			{n4[j]=n4[j]+1;}
	}
//----------Some correlative informations.
	printf("The total character number of the string is: %d.\n",str_length);
	printf("The CODING string of the file is as follow:\n%s\n",str_array);
	for(i=0;i<=el_label;i++)
		{el_gailu[i]=double(n4[i])/double(str_length);}
//----------Set the Huffman tree.
	str_length1=el_number=el_label+1;
	tree_point=2*el_number-1;
	huffman_tree=(struct hafuman *)malloc((tree_point+1)*sizeof(struct hafuman));
	for(p=huffman_tree,i=1;i<=el_number;++i)
	{
		p[i].weigth=el_gailu[i-1];
		p[i].parent=p[i].lchild=p[i].rchild=0;
	}
	for(;i<=tree_point;++i)
		{p[i].weigth=p[i].parent=p[i].lchild=p[i].rchild=0;}
//----------Build the Huffman tree.
	for(i=1;i<=tree_point;i++)
		{pp[i].weigth=p[i].weigth;}
	for(i=el_number+1;i<=tree_point;i++)
	{
		select(&pp[1],&s1,&s2,str_length1);
		huffman_tree[s1].parent=i;
		huffman_tree[s2].parent=i;
		huffman_tree[i].lchild=s1;
		huffman_tree[i].rchild=s2;
		huffman_tree[i].weigth=huffman_tree[s1].weigth+huffman_tree[s2].weigth;
		pp[i]=huffman_tree[i];
		str_length1=str_length1+1;
	}
	cd=(char *)malloc(el_number*sizeof(char));
	cd[el_number-1]='\0';
//----------Get the Huffman codes and print the result.
	printf("Character--Probability--CodeLength--Codes");
	for(i=1;i<=el_number;i++)
	{
		int  start,c,f;
		start=el_number-1;
		for(c=i,f=huffman_tree[i].parent;f!=0;c=f,f=huffman_tree[f].parent)
		{
			if(huffman_tree[f].lchild==c)
				{cd[--start]='0';}
			else
				{cd[--start]='1';}
		}
		printf("\n    %c       %lf         %d       ",str_element[i-1],el_gailu[i-1],el_number-start-1);
		for(j=start;j<el_number;j++)
			{printf("%c",cd[j]);}
	}
	free(cd);
	printf("\nTry again now? (Enter to continue.Any key for quit.)...\n");
	ch_again=getch();
	if(ch_again==13)
		{printf("\n");goto again;}
	else
	{
		for(long i=0;i<7000000;i++)
			{if(i%200000==0)printf("%c",str_exit[i/200000]);}
		for(i=0;i<100000000;i++){;}
	}
}
void select(struct hafuman *pp,int *y1,int *y2,int str_length)
{
	double  tmp1,tmp2;
	int  tmp3,tmp4,i,j;
	tmp1=pp[0].weigth;
	tmp2=pp[1].weigth;
	tmp3=0;
	tmp4=1;
	for (i=1;i<str_length-1;i++)
	{
		if(pp[i+1].weigth<tmp1)
		{
			tmp1=pp[i+1].weigth;
			tmp3=i+2;
		}
	}
	for(i=1;i<str_length-1;i++)
	{
		if(pp[i+1].weigth<tmp2&&(i+2!=tmp3))
		{
			tmp2=pp[i+1].weigth;
			tmp4=i+2;
		}
	}
	if(tmp3==0)  tmp3=1;
	if(tmp4==1)  tmp4=2;
	if(pp[tmp3-1].weigth<pp[tmp4-1].weigth)
	{
		j=tmp3;
		tmp3=tmp4;
		tmp4=j;
	}
	*y1=tmp3;
	*y2=tmp4;
	pp[tmp3-1].weigth=30;
	pp[tmp4-1].weigth=40;
}