huffman.cpp

huffam编码的C语言举例

#include<iostream>
using namespace std;

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


typedef struct{
	char data;
	int weight;
	int parent,lchild, rchild;
}HTNode,*HuffmanTree;        //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表


void Select(HuffmanTree HT,int n,int &a,int &b){
	//比较数组HT，得到两个未选的最小的数a和b
	int k,min1=32767,min2=32767;
	a=b=-1;
	for(k=1;k<=n;k++){
		if(HT[k].parent==0){
			if(HT[k].weight<min1){
				min2=min1;
				b=a;
				min1=HT[k].weight;
				a=k;
			}
			else if(HT[k].weight<min2){
				min2=HT[k].weight;
				b=k;
			}
		}//if
	}//for
}//Select

void Huff_coding(HuffmanTree &HT,HuffmanCode &HC,char *w,char *z,int n){
	//huffman编码
	int m,i,s1,s2,c,start,f;
	char* cd;
	HuffmanTree p;

	if(n<=1)return;
	m=2*n-1;

	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未使用
	if(!HT){
		cout<<"HT分配不成功！！！"<<endl;
		exit(0);
	}

	for(p=HT,i=1;i<=n;++i,++w,++z){
		p[i].data=*z;
		p[i].weight=*w;
		p[i].parent=0;
		p[i].lchild=0;
		p[i].rchild=0;
	}//for
	for(;i<=m;++i){
		p[i].data=48;
		p[i].weight=0;
		p[i].parent=0;
		p[i].lchild=0;
		p[i].rchild=0;
	}//for
	for(i=n+1;i<=m;++i){     //建立哈夫曼树
		Select(HT,i-1,s1,s2);//调用比较函数，找到两个最小的结点，其序号分别是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;
	}//for
	//从叶子到根逆向求每个字符的哈夫曼编码

	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量
	if(!HC){
		cout<<"HC分配不成功！！！"<<endl;
		exit(0);
	}
	cd=(char*)malloc(n*sizeof(char));            //分配求编码的工作空间
	if(!cd){
		cout<<"cd分配不成功！！！"<<endl;
		exit(0);
	}

	cd[n-1]='\0';                                //编码结束符
	for(i=1;i<=n;++i){                           //逐个字符求哈夫曼编码
		start=n-1;                               //编码结束符位置
		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));//为第i个字符编码分配空间
		if(!HC[i]){
			cout<<"HC[i]分配不成功！！！"<<endl;
			exit(0);
		}
		
		strcpy(HC[i],&cd[start]);                //从cd复制编码(串)到HC
	}//for
	free(cd);                                   //释放工作区间
}//Huff_coding

void HuffmandeCoding(HuffmanTree HT,int n){
	//从根向叶子求huffman译码
	int m,i,ch;
	m=2*n-1;
	i=m;
	while ((ch=getchar())!='\n'){
		if(ch=='0'||ch=='1'){
		    if (i<=n){ 
			    cout<<HT[i].data;   
			    i=m;
		    }//if
		    if (ch=='0') i=HT[i].lchild;
		    else i=HT[i].rchild;
		}
		else cout<<"输入错误,不能进行编码"<<endl;
	}//while
	cout<<HT[i].data;
}// HuffmandeCoding


void In_C(void){
	//从终端读入字符
    int i(0),j(0),k(1);
	char ch;
	char c[100]={0};
	char w[100]={0};
	char *p;

	HuffmanTree HT;
	HuffmanCode HC;
    
	cout<<"                     请输入字符串!!!"<<endl
		<<"               请键入回车键后再输入EOF结束!!!"<<endl<<endl;

	while((ch=getchar())!=EOF){
		//求得不同的字符数组*c及其权值*w

		p=strchr(c,ch);
		if(p!=NULL) ++w[p-c];

		else{
			c[i]=ch;
			w[i]=1;
			i++;
		}
	}//while
	cout<<endl;
	
	--i;     //去掉回车字符
	Huff_coding(HT,HC,w,c,i);
	cout<<"huffman树为:"<<endl;
	for(;k<=2*i-1;k++){
		//显示huffman树

		cout<<HT[k].data<<"\t"<<HT[k].weight<<
			"\t"<<HT[k].parent<<"\t"<<HT[k].lchild<<"\t"<<HT[k].rchild<<endl;
	}

	cout<<endl<<"huffman编码为:"<<endl;

	for(j=1;j<=i;j++){
		//显示huffman编码

	    cout<<c[j-1]<<"\t";
	    for(k=0;*(*(HC+j)+k)!='\0';k++){
	    cout<<*(*(HC+j)+k);
	    }//for

	    cout<<endl;
	}//for

	//输入字符依据现有编码进行译码
	cout<<"请输入字符进行译码:"<<endl;
	HuffmandeCoding(HT,i);
	cout<<endl;

}//In_C


void File_C(void){
	//对文件进行编码

	FILE *fp1,*fp2,*fp3,*fp4;
	char ch,*c1,*p,*p1;
	int a(0),k(1),i(0),j;

	char c[32767]={0};
	char w[32767]={0};

	HuffmanTree HT;
	HuffmanCode HC;

	c1=c;

	//读取ToBeTran文件求字符串*c及其权值*w

	if ((fp1=fopen("ToBeTran.txt","r"))==NULL){
		cout<<"ToBeTran文件不能打开!!!"<<endl;
	}
	else{
		ch=fgetc(fp1);
		while(ch!=EOF){
		
			p=strchr(c,ch);
			if(p!=NULL) ++w[p-c];

		    else{ 
			   c[i]=ch;
			   w[i]=1;
			   i++;
		    }
			ch=fgetc(fp1);
		}//while
	}//else


	Huff_coding(HT,HC,w,c,i);
	cout<<"huffman树为:"<<endl;
	for(;k<=2*i-1;k++){
		//显示huffman树

		cout<<HT[k].data<<"\t"<<HT[k].weight<<
			"\t"<<HT[k].parent<<"\t"<<HT[k].lchild<<"\t"<<HT[k].rchild<<endl;
	}

	cout<<endl<<"huffman编码为:"<<endl;

	if ((fp2=fopen("CodeFile.txt","w"))==NULL){
		cout<<"CodeFile文件不能打开!!!"<<endl;
	}
	

	for(j=1;j<=i;++j){
		//把编码写入CodeFile文件中，并显示出来

	    cout<<c[j-1]<<"\t";
		fprintf(fp2,"%c\t",c[j-1]);
	    for(k=0;*(*(HC+j)+k)!='\0';k++){
	    cout<<*(*(HC+j)+k);
		fprintf(fp2,"%c",*(*(HC+j)+k));
	    }//for

        fprintf(fp2,"\n");
	    cout<<endl;
	}//for

	fclose(fp2);   //关闭CodeFile文件
	fclose(fp1);   //关闭ToBeTran文件


	//再次打开ToBeTran文件将编码写入文件CodePrint中

	if ((fp1=fopen("ToBeTran.txt","r"))==NULL){
		cout<<"ToBeTran文件不能打开!!!"<<endl;
	}

	if ((fp3=fopen("CodePrint.txt","w"))==NULL){
		cout<<"CodePrint文件不能打开!!!"<<endl;
	}

	else{
		ch=fgetc(fp1);
		while(ch!=EOF){
		
			p1=strchr(c,ch);

	        for(k=0;HC[p1-c1+1][k]!='\0';k++){
		        fprintf(fp3,"%c",HC[p1-c1+1][k]);
				a++;
				if(a%50==0)          //编码文件50个字符一行
			    fprintf(fp3,"%c",'\n');
                
	        }//for
            
			

			ch=fgetc(fp1);
		}

	}

    fclose(fp1);   //再次关闭ToBeTran文件
	fclose(fp3);   //关闭CodePrint文件

	//再次打开CodePrint文件进行译码
	int m,i1,ch1;
	m=2*i-1;
	i1=m;
	char ch2;

	fp3=fopen("CodePrint.txt","r");

	if ((fp4=fopen("TextFile.txt","w"))==NULL){
		cout<<"TextFile文件不能打开!!!"<<endl;
	}
	else{
		ch1=fgetc(fp3);
		int k3(1); 
	    while (ch1!=EOF){
		
		    if (i1<=i){ 
			    fprintf(fp4,"%c",HT[i1].data);   
			    i1=m;
			}//if
		    if (ch1=='0') i1=HT[i1].lchild;
		    else i1=HT[i1].rchild;

			
			if(k3%50==0) ch2=fgetc(fp3);    //从CodePrint文件中每读取50个字符后忽略掉换行字符
				
            k3++;
			ch1=fgetc(fp3);

	    }//while
	    fprintf(fp4,"%c",HT[i1].data);
	}

    fclose(fp3);   //关闭CodePrint文件
	fclose(fp4);   //关闭TextFile文件



}//File_C



void main()
{   
	int n;

    cout<<"********************************************************"<<endl;
	cout<<"****************     请选择编码内容     ****************"<<endl;
	cout<<"****************       1  终端输入      ****************"<<endl;
	cout<<"****************       2  文件编码      ****************"<<endl;
	cout<<"****************       3  退出程序      ****************"<<endl;
	cout<<"********************************************************"<<endl;

    scanf("%d",&n);
	while(n!=3){
		switch(n){
			case 1:
				getchar();
				In_C();
				break;

			case 2:
				cout<<endl;
				File_C();
			
			default:
				cout<<endl<<endl<<"                     请重新选择:"<<endl<<endl;
		}

    	cout<<"********************************************************"<<endl;
	    cout<<"****************     请选择编码内容     ****************"<<endl;
	    cout<<"****************       1  终端输入      ****************"<<endl;
	    cout<<"****************       2  文件编码      ****************"<<endl;
	    cout<<"****************       3  退出程序      ****************"<<endl;
	    cout<<"********************************************************"<<endl;

		scanf("%d",&n);
	}//while

	_getch();
}