haffman.cpp

对输入的字符串进行赫夫曼编码

#define MAXVALUE 1000
#define MAXLEAF 30
#define MAXNODE 59
#define MAXBIT 10
#define Maxsize 200
typedef unsigned char SString[Maxsize] ;
#include <stdio.h>

typedef struct
{
	char data;
	int Weight;
	int Flag;
	int Parent;
	int LChild;
	int RChild;
}hnodetype;

typedef struct
{
	int Bit[MAXBIT];
	int Start;
}hcodetype;


void CreatString(SString s)
{
	printf("\n请输入电文,以*结尾\n");
    scanf("%s",s); 
   
}

void CountString(SString s,int count[],char alph[])
{
	//int count[100];
	//char alph[100];
	int i,j,k;
	 i=0;j=0;k=0;
	for(i=0;i<100;i++)
		count[i]=0;
	for(i=0;i<100;i++)
		alph[i]='#';
    while(s[j]!='*'){
        for(j=0;s[j]!='*';j++){
			i=0;
            while(alph[i]!='#'&&alph[i]!=s[j])i++;
		    if(alph[i]='#'){
			     alph[i]=s[j];
		 	     count[i]=count[i]+1;
			}
			else if(alph[i]=s[j])
				count[i]=count[i]+1;
		}
	}
	printf("\n各字符频数统计\n");
	for(i=0;i<100&&alph[i]!='#';i++)
		printf("%c的权值为%d\n",alph[i],count[i]);
}
			



void TnitHaffman(hnodetype HuffNode[],hcodetype HuffCode[], int n,int count[],char alph[])
{
	int i;
    //for(j=0;alph[j]!='#';j++);
    for(i=0;i<2*n-1;i++)
	{
		HuffNode[i].Weight=0;
		HuffNode[i].Flag=0;
		HuffNode[i].Parent=0;
		HuffNode[i].LChild=-1;
		HuffNode[i].RChild=-1;
	}
	for(i=0;i<n;i++)
	{
		HuffNode[i].data=alph[i];
		HuffNode[i].Weight=count[i];
		/*getchar();
		printf("输入第%d个叶结点值:",i+1);
		scanf("%c",&HuffNode[i].data);
		printf("输入对应结点权值:");
		scanf("%d",&HuffNode[i].Weight);*/
	}
}

void OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
	int i,j;
	printf("%d个结点对应的编码为:\n",n);
	for(i=0;i<n;i++)
	{
		printf("%c------",HuffNode[i].data);
		for(j=HuffCode[i].Start+1;j<10;j++)
			printf("%d",HuffCode[i].Bit[j]);
		printf("\n");
	}
}


void Huffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
	int i,j,m1,m2,x1,x2,c,p;
	hcodetype cd;
	for(i=0;i<n-1;i++)
	{
		m1=m2=MAXVALUE;
		x1=x2=0;
		for(j=0;j<n+i;j++)
		{
			if(HuffNode[j].Weight<m1&&HuffNode[j].Flag==0)
			{
				m2=m1;
				x2=x1;
				m1=HuffNode[j].Weight;
				x1=j;
			}
			else if(HuffNode[j].Weight<m2&&HuffNode[j].Flag==0)
			{
				m2=HuffNode[j].Weight;
				x2=j;
			}
		}
		HuffNode[x1].Parent=n+i;
      	HuffNode[x2].Parent=n+i;
        HuffNode[x1].Flag=1;
        HuffNode[x2].Flag=1;
		HuffNode[n+i].Weight=HuffNode[x1].Weight+HuffNode[x2].Weight;
		HuffNode[n+i].LChild=x1;
		HuffNode[n+i].RChild=x2;
	}
	for(i=0;i<n;i++)
	{
		cd.Start=9;
		c=i;
		p=HuffNode[c].Parent;
		while(p!=0)
		{
			if(HuffNode[p].LChild==c)cd.Bit[cd.Start]=0;
			else if(HuffNode[p].RChild==c)cd.Bit[cd.Start]=1;
			cd.Start--;
			c=p;
			p=HuffNode[c].Parent;
		}
		for(j=cd.Start+1;j<10;j++)
		{
			HuffCode[i].Bit[j]=cd.Bit[j];
			HuffCode[i].Start=cd.Start;
		}
	}
}

/*void OutputHaffman(hnodetype HuffNode[],hcodetype HuffCode[],int n)
{
	int i,j;
	printf("%d个结点对应的编码为:\n",n);
	for(i=0;i<n;i++)
	{
		printf("%c------",HuffNode[i].data);
		for(j=HuffCode[i].Start+1;j<n;j++)
			printf("%d",HuffCode[i].Bit[j]);
		printf("\n");
	}
}

*/
void main()
{
	hnodetype  HuffNode[MAXNODE];
	hcodetype  HuffCode[MAXLEAF];
	SString S;
	int n;
	int count[100];
	char alph[100];
	CreatString(S);
	CountString(S,count,alph);
	for(n=0;alph[n]!='#';n++);
	TnitHaffman( HuffNode,HuffCode, n, count, alph);
	Huffman(HuffNode,HuffCode,n);
	OutputHaffman(HuffNode,HuffCode,n);

}