huffman.cpp

Huffman编码与译码

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef struct {
	char letter;
	int  wt;
}hfm,*hfmlist;

//*************************全局变量************************************
unsigned int s1,s2,n;
char choose;
int DEPTH=0;
char a[20];

//***************Huffman树和Huffman编码的存储表示**********************
typedef struct{
	unsigned int weight;
	unsigned int code;
	unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;           //动态分配数组存储Huffman树
typedef char * *HuffmanCode;     //动态分配数组存储Huffman编码表

//***************************初始化Huffman树***************************
void select(HuffmanTree HT,int l){
	int a,b,c,j;
	s1=s2=1;
	a=b=1000;
	for(j=1;j<=l;j++){
		if(HT[j].code==0){
		  c=HT[j].weight;
		  if(c<a){b=a;a=c;s2=s1;s1=j;}
	      else if(c<b){b=c;s2=j;}
	    	 }//if
		}//for
	HT[s1].code=HT[s2].code=1;
	}//select

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, hfmlist HL,unsigned int n){
	//w存放n个权值（均>0），构造Huffman树HT,并求出n个字符的Huffman编码HC.
	unsigned int i,f,start,c,m;
    char*cd;
	    
	if (n<=1) return;
	m =2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
	for(i=1;i<=m;++i){HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=HT[i].code=0;}
    for(i=1;i<=n;++i)HT[i].weight=HL[i].wt;
	for (i=n+1;i<=m;++i){
		select(HT,i-1);
		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;
	}

	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd=(char*)malloc(n*sizeof(char));
	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));
		strcpy(HC[i],cd+start);
	}
	free(cd);
}

//*************************文件操作*****************************
void save (char *p){
      FILE *fp;
      int i;
      
      printf("input the name:");
      if((fp=fopen(gets(a),"w+"))==NULL){
		  printf("cannot open the file!\n");
	      exit(0);}//if
      for(i=0;p[i]!='\0';i++){
		  if(fwrite(p+i,sizeof(char),1,fp)!=1){//fwrite函数写数据块
			  printf("File write error!\n");exit(0);}//if
	  }//for
      fclose(fp);
}//save

//************************编码与译码操作**********************************
void Decoding(HuffmanTree HT,hfmlist HL,char*size,int n)//这个函数是用来译码的 
    {int i,j,k;
     char p[30];
	 printf("请输入需要译码的代码:");gets(p);//接受需要译码的字符串
	 i=2*n-1;
     k=0;
	 for(j=0;p[j]!='\0';j++){
		 if(p[j]=='0'){ if(HT[i].lchild!=0)i=HT[i].lchild;
						else{	size[k++]=HL[i].letter;
								i=2*n-1;
								j--;}
			 }
		 else{	if(HT[i].rchild!=0)i=HT[i].rchild;
				else{	size[k++]=HL[i].letter;
						i=2*n-1;
						j--;}
			 }
	 }//for
     if( p[j-1]=='0')size[k++]=HL[i].letter;
     else size[k++]=HL[i].letter;
     size[k]='\0';
  }//decoding
void Encoding(HuffmanCode HC,hfmlist HL,char *coding,int n){
	int i,j,t,k=0;
	char p[100];
	printf("请再次输入需要编码的文本:");
	gets(p);
	for(i=0;p[i]!='\0';i++){
	    if((p[i]>='a'&&p[i]<='z')||p[i]==' ')
		  for(j=1;j<=n;j++)
		    if(p[i]==HL[j].letter)
		      for(t=0;HC[j][t]!='\0';t++)
				coding[k++]=HC[j][t];
	     }//for
	coding[k]='\0';
}//encoding

//************************打印操作****************************
void Print(FILE *fp1,FILE *fp2){
	//将文件fp1中的代码以紧凑格式显示在终端上，每行50个代码
	//同时将此字符形式的编码文件写入文件fp2中
	char c[200];
	int i;
	fgets(c,200,fp1);
	for(i=0;c[i]=='0'||c[i]=='1';i++){
		printf("%c",c[i]);
		fprintf(fp2,"%c",c[i]);
		if((i+1)/50*50==(i+1)){
			printf("\n");
			fprintf(fp2,"\n");
		}
	}//for
	printf("\n");
}//Print

void PreOrderTraverse(HuffmanTree HT,int k,FILE *fp){
	//先序遍历并打印树，结果存放于fp中,k为根结点的下标
	int i;
	for(i=1;i<=DEPTH-1;i++)fprintf(fp,"         ");
	for(;i<=DEPTH;i++)fprintf(fp,"|------");
	fprintf(fp,"%d\n",HT[k].weight);
	if(HT[k].lchild!=0){
		DEPTH++;
		PreOrderTraverse(HT,HT[k].lchild,fp);
		DEPTH--;
	}
	if(HT[k].rchild!=0){
		DEPTH++;
		PreOrderTraverse(HT,HT[k].rchild,fp);
		DEPTH--;
	}
	if(HT[k].lchild==0&&HT[k].rchild==0)return;
	return;
} //PreOrderTraverse

void TreePrinting(HuffmanTree HT,int n,FILE *fp){
	//打印树HT，结果存于文件fp中，n为树的叶子结点数
	int i,k;
	for(i=1;i<=2*n;i++)if(HT[i].parent==0){k=i;break;}//寻找根结点
	PreOrderTraverse(HT,k,fp);
	return;
}//TreePrinting 

//**************************主函数*********************************
void main()
{
	FILE *fp1,*fp2,*fp3,*fp4,*fp5;
	HuffmanTree HT;
	HuffmanCode HC;
	hfmlist HL;
 
	unsigned int i,n;
    char  *b,c[100],cha,ch;

    b=(char *)malloc(100*sizeof(char));
	printf("请选择操作：\n");
	printf("i:初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
    printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n");b=(char *)malloc(100*sizeof(char));
	HL=(hfmlist)malloc(30*sizeof(hfm));//存储字符与权值，线性表长30
	printf("\n");
	printf("选择操作(i,e,d,p,t,q):");
	ch=getchar();
	getchar();
	printf("\n");
	do{
	  switch(ch){
		case 'i':printf("正在进行初始化……\n");
			     printf("输入字符长度：");
				 scanf("%d",&n);
				 getchar();
				 printf("\n");
				 HC=(HuffmanCode)malloc((n+1)*sizeof(char));
				 HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
				 for(i=1;i<=n;i++){
				     printf("请输入第%d个字符及权值(格式:字符 权值):",i);
					 scanf("%c %d",&(HL+i)->letter,&(HL+i)->wt);
					 getchar();					
				 }//for
                 if((fp5=fopen("hfmTree.txt","w"))==NULL){
					 printf("cannot open file!\n");
					 exit(0);
				 }//if
				 for(i=1;i<=n;i++){
					 fprintf(fp5,"第%d个字符及权值:\t\t\t",i);
					 fprintf(fp5,"%c %d\n",(HL+i)->letter,(HL+i)->wt);
				 }//for
				 fclose(fp5);
				 HuffmanCoding(HT,HC,HL,n);
				 printf("\n已经将Huffman树存入文件hfmTree.txt中\n\n");
				 printf("初始化完毕，请选择操作：\n");
	             printf("i:重新初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
                 printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n\n");
				 break;
		case 'e':
				 printf("请输入编码,以#结尾：");
				 if((fp2=fopen("ToBeTran.txt","w"))==NULL){
				         printf("cannot open file\n");exit(0);
				 }//if
				     cha=getchar();
	             while(cha!='#')
				 {
		              fputc(cha,fp2);
		              cha=getchar();
				 }//while
				 getchar();
	             fclose(fp2); 
				
				 printf("已经把编码存入文件ToBeTran.txt中\n\n");
				 Encoding(HC,HL,b,n);
                 printf("文本的哈夫曼编码是:"); 
				 printf("%s\n",b);
				 printf("下面进行保存:");
				 save(b);
				 printf("编码完毕，请选择操作：\n");
	             printf("i:重新初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
                 printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n");
				 break;
		case 'd':
			     Decoding(HT,HL,c,n);
				 printf("输入要译码的编码：");
				 printf("正在进行译码……\n");
				 printf("%s\n",c);
				 save(c);
				 printf("已经将结果存入文件%s中\n",a);
                 printf("译码完毕，请选择操作：\n");
	             printf("i:重新初始化(Initialization)\ne:编码(Encoding)\nd:译码(Decoding)\n");
                 printf("p:印代码文件(Print)\nt:印哈夫曼树(Tree printing)\nq:退出(Quit)\n");             
			     break;
		case 'p':
				 for(i=1;i<=n;i++)
					printf("字符:%c\t\t\t译码:%s\n",HL[i].letter,HC[i]);
				 if((fp1=fopen("CodePrin.txt","w"))==NULL){
		              printf("cannot open the file!\n");
	                  exit(0);
				 }//if
                 
				 if((fp4=fopen("CodeFile.txt","r"))==NULL){
					 printf("cannot open the file!\n");
					 exit(0);
				 }//if
                 Print(fp4,fp1);
				 printf("该代码文件已经存在并命名为CodePrin.txt\n");
			     fclose(fp4);
				 fclose(fp1);
				 break;
		case 't':printf("打印树存在于文件TreePrin中\n");
			     if((fp3=fopen("TreePrin.txt","w"))==NULL)
				 {printf("cannot open file\n");exit(0);}
			     TreePrinting(HT,n,fp3);
				 fclose(fp3);
			     break;
		case 'q':exit(0);break;
		default :exit(0);break;
	  }//switch
	  printf("\n请选择操作(i,e,d,p,t,q):");
	  ch=getchar();
	  getchar();
	}while(ch!='q');//do
}//main