huffman1.txt

本内容详细介绍huffman编码,并且有源程序.调试成功

#include "stdio.h"
#include "string.h"
#include "iostream.h"

#define maxvalue 1000
#define maxleaf 30
#define maxnode maxleaf*2-1
#define maxbit 30
typedef struct
{
	int weight;
	int parent;
	int lchild;
	int rchild;
}hnodetype;
typedef struct
{
	int bit[maxbit];
	int start;
}hcodetype;

char * getcode(char *s1,char *s2,char *s3);
char * getcode1(char *s1);
void huffmantree(char *s2,char s3[]);

 void main()
{
	char s1[maxleaf],s2[maxleaf];
	gets(s1);
	strcpy(s2,getcode(s1," ",""));
	//puts(s2);
	huffmantree(s1,getcode1(s2));
	//puts(s1);
}

 char * getcode(char *s1,char *s2,char *s3)
{
	char * p,*q,temp[128]="";
	p=s1;
	while((q=strstr(p,s2))!=NULL)
	{
		*q='\0';
		strcat(temp,p);
		strcat(temp,s3);
		p=q+strlen(s2);
	}
	strcat(temp,p);
	strcpy(s1,temp);

	return s1;
}

char * getcode1(char *s1)
{
	int m,i,j,temp1,k,t;
	t=0;
	i=0;
	m=strlen(s1);
	while(*(s1+i)!='\0')
	{
		temp1=s1[i];
		j=i+1;
		while(*(s1+j)!='\0')
		{
			if(temp1==*(s1+j))
			{
				k=j;
				while(*(s1+k)!='\0')
				{
					*(s1+k)=*(s1+k+1);
					k++;			
				}
					j--;	
			}
			j++;
		}
		i++;
	}
	puts(s1);
	return s1;	
}

/*
char * getcode1(char *s1)
{
	char s2[26],s5[26];
	char temp[200]="",*p,*q,*r,*s3="";
	int m,e,n=0;
	m=strlen(s1);
	while(m>0)
	{
		p=s1;
		s2[0]=s1[0];
		s2[1]='\0';
		r=s2;
		e=0;
		while((q=strstr(p,s2))!=NULL)
		{
			*q='\0';
			e++;
			strcat(temp,p);
			strcat(temp,s3);
			p=q+strlen(s2);
		}
		m-=e;
		strcat(s1,temp);
		strcpy(p,temp);
		s5[n]=s2[0];
		n++;
		strcpy(temp,"");

	}
//	puts(s5);
	s5[n]='\0';
	strcpy(s1,s5);

//	puts(s1);
	return s1;	
}*/

void huffmantree(char *s2,char s3[])
{
	hnodetype huffnode[maxnode];
	hcodetype huffcode[maxleaf],cd;
	int sum,i,j,n1,n2,x1,x2,p,k,c;
	char s5[maxleaf];
	char s1[26];
	int ww[26]={0},n=0;
	for(i=0;i<26;i++)
		s1[i]='a'+i;
	//puts(s2);
	//puts(s3);
	strcpy(s5,s2);
	sum=strlen(s2);
	printf("%d\n",sum);

	for(i=0;i<26;i++)
	{
		for(j=0;j<sum;j++)
			if(s2[j]==s1[i])
				ww[i]++;
	//	printf("%d",ww[i]);
	}		//í3???-′ú???D×?·?μ???êy

			n=strlen(s3);//????μ?′ú??
		//3?ê??ˉ?á11ì?
			for(i=0;i<2*n-1;i++)
			{
				huffnode[i].weight=0;//???ê
				huffnode[i].parent=-1;//±ê????
				huffnode[i].lchild=-1;//oó′ú????±ê??
				huffnode[i].rchild=-1;//oó′ú????±ê??
			}

			for(i=0;i<n;i++)
				for(j=0;j<26;j++)
					if(s3[i]==s1[j])
						huffnode[i].weight=ww[j];//ì?3??1?Toó×?·?3??????ê
	//code±à??1y3ì
	for(i=0;i<n-1;i++)
	{
		n1=n2=maxvalue;
		x1=x2=0;
		//?°?ò???ê?D×?D?μ?á???????￡?2￠???????áμ?????oí?μ
		for(j=0;j<n+i;j++)
		{
			if((huffnode[j].parent==-1) && (huffnode[j].weight<n1))
			{
				n2=n1;
				x2=x1;
				n1=huffnode[j].weight;
				x1=j;
			}
			else
			{
				if((huffnode[j].parent==-1) && (huffnode[j].weight<n2))
				{
					n2=huffnode[j].weight;
					x2=j;
				}
			}

		}

		huffnode[x1].parent=n+i;//???áμ?μ?????
		huffnode[x2].parent=n+i;
		huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;//???áμ?μ??μ
		huffnode[n+i].lchild=x1;//oó′úμ?????
		huffnode[n+i].rchild=x2;

	}
	//?¨á￠ê÷?áê?
	for(i=0;i<n;i++)
	{
		cd.start=n-1;
		c=i;
		p=huffnode[c].parent;
		while(p!=-1)
		{
			if(huffnode[p].lchild==c)
				cd.bit[cd.start]=0;
			else
				cd.bit[cd.start]=1;
			cd.start--;
			c=p;
			p=huffnode[c].parent;
		}
		for(j=cd.start+1;j<n;j++)
		{
			huffcode[i].bit[j]=cd.bit[j];
		//	cout<<huffcode[i].bit[j];
		}
			huffcode[i].start=cd.start;
	}


	for(k=0;k<sum;k++)
		for(i=0;i<n;i++)
			if(s2[k]==s3[i])
			{
				for(j=huffcode[i].start+1;j<n;j++)
					printf("%d",huffcode[i].bit[j]);
					printf(" ");
			}
			printf("\n");
}