huffman.cpp

本内容详细介绍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);
	//puts(s1);
	strcpy(s2,getcode(s1," ",""));

	huffmantree(s1,getcode1(s2));
}

 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)
{
	char s2[2],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(s3);
		}
		m-=e;
		strcpy(s1,temp);
		strcpy(p,temp);
		s5[n]=s2[0];
		n++;
		strcpy(temp," ");

	}
	s5[n]='\0';
	strcpy(s1,s5);
	return s1;	
}
void huffmantree(char *s2,char s3[])
{
	hnodetype huffnode[maxnode];
	hcodetype huffcode[maxbit],cd;
	int sum,i,j,n1,n2,x1,x2,p,k,c;
	char s5[maxleaf];
	char s1[26];
	int ww[26],n=0;
	for(i=0;i<26;i++)
	{
		s1[i]=97+i;
		ww[i]=0;
	}
	strcpy(s5,s2);
	sum=strlen(s2);
	for(i=0;i<26;i++)
		for(j=0;j<sum;j++)
			if(s2[j]==s1[i])
				ww[i]++;
			n=strlen(s3);
			for(i=0;i<2*n-1;i++)
			{
				huffnode[i].weight=0;
				huffnode[i].parent=-1;
				huffnode[i].lchild=-1;
				huffnode[i].rchild=-1;
			}
			for(i=0;i<n;i++)
				for(j=0;j<26;j++)
					if(s3[i]==s1[j])
						huffnode[i].weight=ww[j];

	//code
	for(i=0;i<n-1;i++)
	{
		n1=n2=maxvalue;
		x1=x2=0;
		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;
		huffnode[n+i].rchild=x2;

	}
	cout<<x2;
	
}


/*#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(s1);
	//strcpy(s2,getcode(s1,ss1,ss2));
//	huffmantree(s1,getcode1(s2));
}

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);
	puts(s1);
	return s1;
}
*/