huffman_coding.cpp

霍夫曼信源编码的仿真

// Huffman信源编码源代码C语言

#include<stdio.h> 
#include<conio.h> 
#include<iostream.h> 
#include<string.h> 
#include<stdlib.h> 

#define MAXVALUE 10000 /*权值最大值*/ 
#define MAXLEAF 30 /*叶子最多个数*/ 
#define MAXNODE MAXLEAF*2-1 /* 结点数的个数*/ 
#define MAXBIT 50 /*编码的最大位数*/ 

typedef struct node /*结点类型定义*/ 
{ 
	char letter; 
	int weight; 
	int parent; 
	int lchild; 
	int rchild; 
}HNodeType; 

typedef struct /*编码类型定义*/ 
{ 
	char letter; 
	int bit[MAXBIT]; 
	int start; 
}HCodeType; 

typedef struct /*输入符号的类型*/ 
{ 
	char s; 
	int num; 
}lable; 

void HuffmanTree(HNodeType HuffNode[],int n,lable a[]) 
{ 
	int i,j,m1,m2,x1,x2,temp1; 
	char temp2; 
	for(i=0;i<2*n-1;i++) /*所有的结点初始化*/ 
	{ 
		HuffNode[i].letter=NULL; 
		HuffNode[i].weight=0; 
		HuffNode[i].parent=-1; 
		HuffNode[i].lchild=-1; 
		HuffNode[i].rchild=-1; 
	} 
	for(i=0;i<n-1;i++) 		
		for(j=i+1;j<n-1;j++) /*对输入字符按权值大小进行排序,从大到小*/ 
			if(a[j].num>a[i].num) 
			{ 
				temp1=a[i].num; 
				a[i].num=a[j].num; 
				a[j].num=temp1; 
				temp2=a[i].s; 
				a[i].s=a[j].s; 
				a[j].s=temp2; 
			} 
			for(i=0;i<n;i++) 
			{ 
				HuffNode[i].weight=a[i].num; 
				HuffNode[i].letter=a[i].s; 
			} 
			for(i=0;i<n-1;i++) /*构造huffman树*/ 
			{ 
				m1=m2=MAXVALUE; 
				x1=x2=0; 
				for(j=0;j<n+i;j++)/*寻找权值最小与次小的结点*/ 
				{ 
					if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) 
					{ 
						m2=m1; //m2是次小
						x2=x1; 
						m1=HuffNode[j].weight;// m1是最小
						x1=j; 
					} 
					else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2) 
					{ 
						m2=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; 
			} 
} 
void HuffmanCode(int n,lable a[])//n是不同的符号数 a[]为要编码的字符串
{ 
	HNodeType HuffNode[MAXNODE]; 
	HCodeType HuffCode[MAXLEAF],cd; 
	int i,j,c,p; 
	HuffmanTree(HuffNode,n,a); 
	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]; 
		HuffCode[i].start=cd.start; 
	} 
	for(i=0;i<n;i++) 
	{ 
		HuffCode[i].letter=HuffNode[i].letter; 
		printf(" %c ",HuffCode[i].letter); 

		for(j=HuffCode[i].start+1;j<n;j++) 
			printf("%d",HuffCode[i].bit[j]); 
		printf("\n"); 
	} 
} 

void main() 
{ 
	lable data[30]; //输入符号,其长度决定了叶子数
	char s[100],*p; 
	int i,count=0; 
	for(;;) 
	{ 
		cout<<" /*----------------------------------------------/"<<endl; 
		cout<<" / 求哈夫曼编码,直到输入为end结束! /"<<endl; 
		cout<<" /*----------------------------------------------/"<<endl; 
		printf(" Input some letters:"); 
		scanf("%s",&s); //input a string
		if(!strcmp(s,"end")) 
			exit(0); //0 indicate normal exit
		for(i=0;i<30;i++) 
		{ 
			data[i].s=NULL; 
			data[i].num=0; 
		} 
		p=s; 
		while(*p) /*计算字符个数与出现次数(即权值)*/ 
		{ 
			for(i=0;i<=count+1;i++) 
			{ 
				if(data[i].s==NULL) 
				{ 
					data[i].s=*p; 
					data[i].num++; 
					count++; //字符种类数
					break; 
				} 
				else if(data[i].s==*p) 
				{ 
					data[i].num++; 
					break; 
				} 
			} 
			p++; 
		} 
		printf("\n"); 
		printf(" different letters:%d\n",count); 

		for(i=0;i<count;i++) 
		{ 
			printf(" %c ",data[i].s); 
			printf("weight:%d",data[i].num); 
			printf("\n"); 
		} 
		HuffmanCode(count,data); 
		count=0; //继续编码，新的编码与之前的没有关系
	} 
	getch(); 
}