huffman code.cpp

用哈夫曼算法创建huffman树

#include<stdio.h>
#include<string.h>
#define n 150
#define m 2*n-1
typedef struct{
	int weight;  //权值
	char letter;
	int lchild,rchild,parent;
}HTNode;
typedef HTNode HuffmanTree[m+1];  //0号单元不用
typedef struct{
	char ch;
	char bits[n+1];
	int len;
}CodeNode;
typedef CodeNode HuffmanCode[n];

void InputMessage(char str[]){
	char c;
	int i=0;
	printf("please input an array of message:\n");
	c=getchar();     //由于scanf中不能输入空格，所以将字符一个个的输入
	while(c!='\0'&&c!='\n'&&i<n){
		str[i]=c;
		i++;
		c=getchar();
	}
	str[i]='\0';
}

int Calculate(HuffmanTree HT,int count[],char str[]){
	char *p;
	int i,j,k;
	int temp[127]={0};    //临时存放ASC码值在32～126之间的常见字符的出现次数
	for(p=str;*p!='\0';p++)
	{     //统计各种字符的个数
		k=*p;
		temp[k]++;
	}
	for(i=32,j=0;i<=126;i++)
		if(temp[i]!=0){
			j++;
			HT[j].letter=i;
			count[j]=temp[i];
		}
	for(i=1;i<=j;i++)
		printf("字符 %c,次数为 %d\n",HT[i].letter,count[i]);
	return j;
}
				  
void Select(HuffmanTree HT,int k,int &s1,int &s2){
	int i,j;
	int min=65535;
	for(i=1;i<=k;i++)
		if(HT[i].weight<min && HT[i].parent==0)
		{   j=i;
		    min=HT[j].weight;
		}
	s1=j;
	min=65535;
	for(i=1;i<=k;i++)
		if(HT[i].weight<min && HT[i].parent==0 && i!=s1)
		{   j=i;
		    min=HT[j].weight;
		}
	s2=j;
}


void CHuffmanTree(HuffmanTree HT,HuffmanCode HC,int count[],char str[],int len){
	int i,s1,s2;
	for(i=1;i<=2*len-1;i++)
	{   
		HT[i].weight=0;
		HT[i].lchild=0;
	    HT[i].rchild=0;
		HT[i].parent=0;
	}
	for(i=1;i<=len;i++)
		HT[i].weight=count[i];
	for(i=len+1;i<=2*len-1;i++)
	{
		Select(HT,i-1,s1,s2);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s1;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
    for(i=0;i<len;i++)
		HC[i].ch=str[i];
	printf("\nhaffmantree created!\n");
}

void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int len){
	int c,p,i,start;
	char cd[n+1];
	cd[len]='\0';
    for(i=1;i<=len;i++)
	{
        start=len;
        c=i;
        while((p=HT[c].parent)>0)
		{	
			cd[--start]=(HT[p].lchild==c)?'0':'1';
			c=p;
			strcpy(HC[i].bits,&cd[start]);
		}
	}
    printf("\nhaffmancode has sucessfully done!\n");
    for(i=1;i<=len;i++)
		printf("%c的编码是：%s\n",HT[i].letter,HC[i].bits);
}

void main(){
	char str[n];
	int count[94];
	int len;
	HuffmanTree HT;
	HuffmanCode HC;
	InputMessage(str);
	len=Calculate(HT,count,str);
	CHuffmanTree(HT,HC,count,str,len);
	HuffmanCoding(HT,HC,len);
}