huffman.cpp

huffman编码的实现

#include<iostream>
using namespace std;

#define maxint 10000

typedef struct{
        unsigned int weight; 
        unsigned int parent,lchild,rchild;
}htnode,*htree;//动态分配数组存储赫夫曼树

typedef char * *hcode;//动态分配数组存储赫夫曼编码表 

void select_htree(htree ht,int t,int &s1,int &s2){
//查找哈夫曼树中权值最小s1和次小s2
	s1=0;s2=0;
	int n1,n2;
	n1=n2=maxint;
    int k;
    for(k=1;k<=t;k++){
		 if(ht[k].parent==0)
			 if(ht[k].weight<n1){
				 n2=n1;n1=ht[k].weight;
				 s2=s1;s1=k;
			 }
			 else if(ht[k].weight<n2){
				 n2=ht[k].weight;
				 s2=k;
			 }
	}
}

void initial_htree(htree &ht,int n){
//构造赫夫曼树ht
	if(n<=1) return  ;
	int m=2*n-1;
	ht=(htree)malloc((m+1)*sizeof(htnode));//0号单元未用
	int i;
	for(i=1;i<=n;++i){
		cout<<"请输入第"<<i<<"个节点权值:";
		cin>>ht[i].weight; 
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	} 
	for(;i<=m;++i){
		ht[i].weight=0;
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(i=n+1;i<=m;++i){
		//在ht中选择parent为0且weight最小的两个节点，其序号分别为s1.s2 
		int s1,s2;
		select_htree(ht,i-1,s1,s2);
		ht[s1].parent=i; ht[s2].parent=i;
		ht[i].lchild=s1; ht[i].rchild=s2;
		ht[i].weight=ht[s1].weight+ht[s2].weight;
	}
};

hcode encoding(htree ht,int n){
//进行赫夫曼译码 
	hcode hc=(hcode)malloc((n+1)*sizeof(char*));
	char *cd=(char*)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for(int i=1;i<=n;++i){
		int start=n-1;
		int c,f;
		for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)
			if(ht[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
			hc[i]=(char*)malloc((n-start)*sizeof(char));
			strcpy(hc[i],&cd[start]);
	}
	free(cd);
	return hc;
}

void print_htree(htree ht,int n){
//打印赫夫曼树 
	int m=2*n-1;
	for(int i=1;i<=m;++i){
		cout<<"第"<<i<<"个权值为:"<<ht[i].weight<<","<<"其父节点为:"
			<<ht[i].parent<<","<<"其左孩子为:"<<ht[i].lchild<<","
			<<"其右孩子为:"<<ht[i].rchild<<endl;
	}
}

void print_hcode(hcode hc,int n){
//打印赫夫曼编码 
	for(int i=1;i<=n;++i)
		cout<<"第"<<i<<"个权值编码为"<<hc[i]<<endl;
}

int root(htree ht,int n){
//求赫夫曼树根节点 
	int m=2*n-1;
	for(int i=1;i<=m;++i){
		if(ht[i].parent==0)
			return i;
	}
}


void decoding(htree ht,hcode hc,int n){
//对已存在的编码进行译码 
	int m=root(ht,n);
	for(int i=1;i<=n;++i){
		int q=m;
		for(char *p=hc[i];(*p)!='\0';++p){
			if(*p=='0')
				q=ht[q].lchild;
			else if(*p=='1')
				q=ht[q].rchild;}
		cout<<"第"<<i<<"个解码为："<<ht[q].weight<<endl;
	}
}

int main()
{
	int key;//控制操作 
	cout<<"请选择哈夫曼树操作:"<<endl;
	cout<<"1——初始化哈夫曼树"<<endl;
	cout<<"2——打印哈夫曼树并进行哈夫曼编码"<<endl;
	cout<<"3——打印哈夫曼编码"<<endl;
	cout<<"4——进行哈夫曼译码"<<endl;
	cout<<"5——退出"<<endl;
	do{
		htree ht;
		cin>>key;
		int n; 
		hcode hc;
		switch(key){
		case 1:cout<<"请输入叶子节点个数:";
			cin>>n;initial_htree(ht,n); break;
		case 2:cout<<"打印赫夫曼树:"<<endl<<endl;print_htree(ht,n);
			cout<<"赫夫曼编码完成！"<<endl;hc=encoding(ht,n); break;
		case 3:cout<<"打印赫夫曼编码:"<<endl;
			print_hcode(hc,n);break;
		case 4:cout<<"进行赫夫曼译码:"<<endl;
			decoding(ht,hc,n); break;
		default: break;
		}
		cout<<"请选择进一步操作"<<endl;
	}while(key!=5);
}