huffman.cpp

c++实现的哈夫曼编码

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define INT_MAX 10000
#define ENCODING_LENGTH 1000
typedef enum{none,left_child,right_child} Which;//标记是左孩子还是右孩子
typedef char Elemtype;
typedef struct TNode{
	Elemtype letter; 
	int weight;
	int parent;
	Which sigh;
	char *code;
}HTNode,*HuffmanTree;
int n;
char coding[50];//储存代码
char str[ENCODING_LENGTH];//保存要翻译的句子
void InitTreeNode(HuffmanTree &HT)		//初始前N个结点,后M-N个结点置空
{
	int i;int w;char c;
	int m=2*n-1;
	HuffmanTree p;
	HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
	printf("input %d database letter and weight",n);
	p=HT;
	getchar();
	for (i=1;i<=n;i++){
		scanf("%c%d",&c,&w);
		p->code='\0';
		p->letter=c;
		p->parent=0;
		p->sigh=none;
		p->weight=w;
		p++;
		getchar();
	}
	for (;i<=m;i++,p++){
		p->code='\0';
		p->letter=' ';
		p->parent=0;
		p->sigh=none;
		p->weight=0;
	}
}
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{			//在0~END之间,找出最小和次小的两个结点序号,返回S1,S2
	int i;
	int min1=INT_MAX;
	int min2;
	for (i=0;i<=end;i++){//找最小的结点序号
		if (HT[i].parent==0&&HT[i].weight<min1){ 
			*s1=i;
			min1=HT[i].weight;
		}
	}
	min2=INT_MAX;
	for(i=0;i<=end;i++){//找次小结点的序号
		if (HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight){
			*s2=i;
			min2=HT[i].weight;
		}
	}
}
void HuffmanTreeCreat(HuffmanTree &HT)  //建立HUFFMAN树
{	
	int i;int m=2*n-1;
	int s1,s2;
	for(i=n;i<m;i++){
		Select(HT,i-1,&s1,&s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[s1].sigh=left_child;
		HT[s2].sigh=right_child;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
}

void HuffmanTreeCode(HuffmanTree HT)  //HUFFMAN译码
{
	int i;
	char *temp;
	temp=(char *)malloc(n*sizeof(char));
	temp[n-1]='\0';
	int p;int s;
	for (i=0;i<n;i++){
		p=i;
		s=n-1;
		while (HT[p].parent!=0){//从结点回溯,左孩子为0,右孩子为1
			if (HT[p].sigh==left_child)
			temp[--s]='0';
			else if (HT[p].sigh==right_child)
			temp[--s]='1';
			p=HT[p].parent;
		}
		HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间
		strcpy(HT[i].code,temp+s);
		printf("%s\n",HT[i].code); 
	}
}
void GetCodingSen(char *sencence)    //输入要编码的句子
{
	int l;
	gets(sencence);
	l=strlen(sencence);
	sencence[l]='\0';
}
void HuffmanTreeEncoding(char sen[],HuffmanTree HT)    //将句子进行编码
{
	int i=0;int j;
	while(sen[i]!='\0'){
		for(j=0;j<n;j++){
			if (HT[j].letter==sen[i]) {//字母吻合则用代码取代
				strcat(coding,HT[j].code);
				break;
			}
		}
		i++;
		if (sen[i]==32) i++;
	}
	printf("\n%s",coding);
}
void HuffmanTreeDecoding(HuffmanTree HT,char code[]) //HUFFMAN译码过程,将代码翻译为句子
{
	char sen[100];
	char temp[50];
	char voidstr[]=" ";
	int i;int j;
	int t=0;int s=0;
	for(i=0;i<strlen(code);i++){
		temp[t++]=code[i];
		for(j=0;j<n;j++){
			if (strcmp(HT[j].code,temp)==0){//代码段吻合
				sen[s]=HT[j].letter;s++;
				strcpy(temp,voidstr);//将TEMP置空
				t=0;
				break;
			}
		}
	}
	printf("\n%s",sen);
}

void main(){ 
	HTNode hnode;
	HuffmanTree huff;
	huff=&hnode;
	printf("input the letter for coding number\n");
	scanf("%d",&n);
	InitTreeNode(huff);
	HuffmanTreeCreat(huff);
	HuffmanTreeCode(huff);
	GetCodingSen(str);
	HuffmanTreeEncoding(str,huff);
	HuffmanTreeDecoding(huff,coding);
}