huffmantree.cpp

huffmantr

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LETTER {'\0',' ','A','B','C','D','E','F','G','H','I','J'\
,'K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'}
#define VALUE   {0,186,64,13,22,32,103,21,15,47,57,1,5,32,20,57\
,63,15,1,48,51,80,23,8,18,1,16,1}
#define N			27
#define MAXLENGTH	20
typedef struct HTreeNode{
	int	letter;
	int	weight,parent,lchild,rchild;
	}HTNode;//构造huffman树结点的存储结构


void Select(HTNode *Htree,int a,int *m1,int *m2)
{//Htree为一棵待建的huffman树，在Htree[1]----Htree[a]中选择
 //parent为0且weight最小的两个结点，序号分别为*m1,*m2
 int i,sum;
 *m1=1;
 while(Htree[*m1].parent)	//让*m1等于第一个parent为0的结点序号
	(*m1)++;
 *m2=*m1+1;
 while(Htree[*m2].parent)	//让*m2等于第二个parent为0的结点序号
	(*m2)++;
 for(i=*m2+1;i<=a;i++){
  if((!Htree[i].parent)&&(Htree[i].weight<Htree[*m1].weight))
		*m1=i;
  else if((!Htree[i].parent)&&(Htree[i].weight<Htree[*m2].weight))
		*m2=i;
	}//for,实现Htree[*m1].weight和Htree[*m2].weight最小
 if(Htree[*m1].weight>Htree[*m2].weight){
	sum=*m1;
	*m1=*m2;
	*m2=sum;
	}//if，确保Htree[*m1].weight<=Htree[*m2].weight
 }//Select


void HuffmanTreeing(HTNode *Htree,int k)
{//构造huffman树Htree,其叶子结点的权值已初始化
 int i,s1,s2;
 int *x1=&s1;
 int *x2=&s2;
 for(i=k+1;i<=2*k-1;i++){
	Select(Htree,i-1,x1,x2);		//调用Select
	Htree[s1].parent=i;
	Htree[s2].parent=i;
	Htree[i].lchild=s1;
	Htree[i].rchild=s2;
	Htree[i].weight=Htree[s1].weight+Htree[s2].weight;
	}//for,构造非叶子结点
}//HuffmanTreeing


void HuffmanCoding(HTNode *Htree,char **Hcode,int k,int *length)
{//利用已构造好的huffman树求出各个字符的huffman编码Hcode
 char *cd;
 int i,j,f,start;
 cd=(char *)malloc(k*sizeof(char));	//分配编码的工作空间
 if(!cd)
	printf("OVER FLOW!");
 cd[k-1]='\0';						//编码结束符
 for(i=1;i<=k;++i){					//逐个字符求huffman编码
	start=k-1;						//编码结束符位置
	for(j=i,f=Htree[i].parent;f!=0;j=f,f=Htree[f].parent){
		if(Htree[f].lchild==j)
			cd[--start]='0';
		else
			cd[--start]='1';
		}//for,从叶子到根逆向求huffman编码
	Hcode[i]=(char*)malloc((k-start)*sizeof(char));
									//为第i个字符分配空间
	length[i]=k-start;			//将第i个字符编码的长度(含字符串
									//结束符)存到length[i]
	strcpy(Hcode[i],&cd[start]);    //从cd复制编码到HC[i]
	}//for
 free(cd);							//释放工作空间
}//HuffmanCoding


void Letter_switch(HTNode *Htree,char **Hcode,int k,int *length)
{//由用户输入一个字符串，利用huffman树和huffman编码求该字符串
 //的编码
 char *ch;
 int j,i=-1;
 ch=(char *)malloc((MAXLENGTH*sizeof(char)));
									//动态分配储存字符串的数组
 if(!ch)
	printf("OVER FLOW!");
 printf("\n\n\nInput Your String:");
 do{i++;
	if(i%(MAXLENGTH+1)==MAXLENGTH){//空间不够则重新分配
	   ch=(char *)realloc(ch,(strlen(ch)+MAXLENGTH)*sizeof(char));										
	    if(!ch)
			printf("OVER FLOW!");
		}//外层if					     
	ch[i]=getchar();
	}while(*(ch+i)!='\n');//接收用户输入的字符串
 *(ch+i)='\0';			  //字符串结束符
 printf("It's Huffmancode is:");
 for(i=0;ch[i]!='\0';i++){//逐个打印出每个字符的编码
	 for(j=1;j<=k;j++){   //逐个查找huffman树叶子结点
		if(ch[i]==Htree[j].letter){//比较当前结点的letter值和ch[i]
			printf("%s",Hcode[j]);	//打印
			j=k+1;		//打印后利用更改循环变量直接退出内层循环
			}//if,相同则打印出该结点对应的huffman编码
		else if(j==k)	//若不同且已查找到最后一个字符，则报错	
			printf("\n  Your Letter is Wrong!");
		}//内层循环for
	}//外层循环for
 free(ch);				//释放存放字符串的空间
}//Letter_switch


void code_switch(HTNode *Htree,char **Hcode,int k,int *length)
{//用户输入一个“0”，“1”字符串作为huffman编码，利用huffman树和
 //huffman编码对其进行译码
 char *cc,*q,*pa;
 int lmax,lmin,j,i=-1,sum=0,tag;
 cc=(char *)malloc((MAXLENGTH*sizeof(char)));
								//动态分配储存字符串的数组
 if(!cc)
	printf("OVER FLOW!");			
 printf("\n\n\nInput Your Huffmancode:");
 do{i++;
	if(i%(MAXLENGTH+1)==MAXLENGTH){//空间不够则重新分配
	  cc=(char *)realloc(cc,(strlen(cc)+MAXLENGTH)*sizeof(char));
		if(!cc)
			printf("OVER FLOW!");
		}//外层if						
	cc[i]=getchar();
	sum++;			  //sum存输入字符长度(含字符串结束符)
	}while(*(cc+i)!='\n');//接收用户输入的字符串(huffman码)
 *(cc+i)='\0';			  //字符串结束符
 printf("It's Letter Code is:");
 lmin=lmax=length[1];
 for(i=2;i<=k;i++){
	if(length[i]<lmin)
		lmin=length[i];
	if(length[i]>lmax)
		lmax=length[i];
	}//for,求出huffman编码中各个字符编码的最大长度和最小长度
 q=pa=cc;
 tag=1;	    //最外层循环执行标志初始化
 while(tag){//对编码逐个进行译码
		for(i=lmin;i<=lmax;i++){//外层循环以编码长度(含字符串
								//结束符)为循环变量
			if(sum<i)
				break;			//sum为未译编码长度，若剩下的
								//未译编码长度小于当前的编码
								//长度，说明输入编码有错，退
								//出外层循环后报错
			for(j=1;j<=k;j++){	//逐个查找huffman树叶子结点
				if((length[j]==i)&&(strncmp(q,Hcode[j],i-1)==0)){
					//若当前叶子结点对应的huffman编码长度与i相等
					//，且其编码也与当前的q指针所指字符串的前i-1
					//相同，则打印该结点对应的字符
					printf("%c",Htree[j].letter);//打印
					q=q+i-1;		//q指向剩下的未译字符串					
					sum=sum-i+1;	//计算未译编码长度
					j=k+1;			//更改j，为了退出内层循环
					i=lmax+1;		//更改i，为了退出外层循环
					}//if
				}//内层循环for
			continue;//当前编码长度找不到对应字符的huffman编码
					 //，则编码长度加一，再查找一遍
			}//外层循环for
	if(*q=='\0')//若已译完字符串，最外层循环执行标志置“0”		
		tag=0;
	else if(pa==q){//检查q指针是否变化
		printf("\n  Your Code Error!");
		tag=0;
		}//else if,有两种情况执行这段代码：1，未译编码长度sum
		 //小于i，跳出外层循环后，显然pa==q，这时报错；   2，
		 //经过上面两重循环后，q指针未变化，说明找遍所有字符的
		 //huffman编码，仍然没有找到与待译字符串的前几个字符相
		 //匹配的，这时也应由此段代码报错
	else //q指针变化且未到字符串尾，将q重新赋给pa,继续最外层循环
		pa=q;
	}//最外层循环while
 printf("\n");
 free(cc);	 //释放存放字符串(编码)的空间
}//code_switch


void main()
{//利用宏中的数据建造huffman树、完成huffman编码，并将用户输入
 //的字符和编码进行编码与译码
 HTNode *HT,*p;
 int i,j,m,k;
 int *length;
 char letters[N+1]=LETTER;	//利用宏接收字符
 int values[N+1]=VALUE;		//利用宏接收字符的权值
 char **HC;				
 k=N;
 m = 2 * k - 1;
 HT=(HTNode *)malloc((m+1)*sizeof(HTNode));
					//分配指向huffman树的指针空间，0号单元未用
 if(!HT)
	printf("OVER FLOW!");									
 for(p=HT,i=0;i<=k;++i,++p){//初始化叶子结点
	(*p).letter=letters[i];
	(*p).weight=values[i];
	(*p).parent=0;
	(*p).lchild=0;
	(*p).rchild=0;
	}//for
 for(;i<=m;++i,++p){//初始化非叶子结点
	(*p).letter='\0';
	(*p).weight=0;
	(*p).parent=0;
	(*p).lchild=0;
	(*p).rchild=0;
	}//for
 HC=(char **)malloc((k+1)*sizeof(char *));
								//分配k个字符编码的头指针向量
 if(!HC)
	printf("OVER FLOW!");
 length=(int *)malloc((k+1)*sizeof(int));
							//分配储存k个字符编码长度的整型数组
 if(!length)
	printf("OVER FLOW!");
 HuffmanTreeing(HT,k);			//调用HuffmanTreeing
 HuffmanCoding(HT,HC,k,length);	//调用HuffmanCoding
 printf("Every Letter's Huffmancode are:");
 for(i=1;i<=k;i++){//打印出每个字符的huffman编码
	if((i-1)%3==0)
		printf("\n");
	printf("%c:%s",HT[i].letter,HC[i]);//打印
	for(j=1;j<=15-length[i];j++)    //为使输出上下对齐
		printf(" ");
	}//for
 Letter_switch(HT,HC,k,length);		//调用Letter_switch
 code_switch(HT,HC,k,length);		//调用code_switch
 free(HC);		//释放空间
 free(HT);		//释放空间
 free(length);	//释放空间
}//main