main.cpp

是一个用哈夫曼树生成哈夫曼编码的程序

//	char ch;  int result;
//	cout<<"hello!";
	CharSet HCS;
	long int n;
	char *filenam1="ToBeTran.txt";
	char *filenam2="CodeFile.txt";

	if(HT==NULL){             //如果哈夫曼树不再内存中,就从文件中读入

	   n=CountHTNodefromFile();//将要为哈夫曼树分配空间的数
	   
	   HT=(HuffmanTree)malloc(n*sizeof(HTNode));//分配空间 // AllotSpacetoHT(HT,m);//
	   if(HT==NULL) return OVERFLOW;
     //用AllotSpacetoHT反而不好用!!!!!!!!!!!!!!!!!!!!!!!!!1
	   ReadHTfromFile(HT,2*charsetsize);//从文件中读入哈夫曼树//
		//PrintHuffmantree(HT,2*charsetsize-1);
		
	}//if

	//--------------------------------------------------------------
	//试验田
	GetHCSFromHT(HT,HCS,charsetsize);
	for(int i=1;i<=charsetsize;i++){
		cout<<HCS.CSElem[i].ch<<"   "<<HCS.CSElem[i].weight<<endl;
	
	}//for
	cout<<endl;
	QuickSort(&HCS,1,charsetsize);
	for(int j=1;j<=charsetsize;j++){
		cout<<HCS.CSElem[j].ch<<"   "<<HCS.CSElem[j].weight<<endl;
	
	}//for
	cout<<endl;







   //---------------------------------------------------------------

	CreateHuffmanCode(HT,HC,charsetsize); //对字符集中的所有字符生成哈夫曼编码并存入HC中
	//\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\


	result=DealFileNotExistorEmpty(filenam1);
	if(result==IWWY){//如果ToBeTran.txt不存在则建立,内容为空则
		//    cout<<"hello";                                     //等待用户向ToBeTran.txt中装入内容
		
		printf("请在%s中装入要编码的内容I will wait for you!\n",filenam1);
		printf("装入完成后按<c>继续进行编码,按<q>退出\n");
		while(cin>>ch&&ch!='c'){
			if(ch=='q') return EXIT;
		}//while    		      //循环等待
	}//if
  //||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

	Translating(filenam1,filenam2,HT,HC);
	return OK;
}//Encoding
*/




int Encoding(HuffmanTree &HT,HuffmanCode &HC){
	//开始编码HuffmanTree &HT,HuffmanCode &HC
  //  HuffmanTree HT=NULL;HuffmanCode HC;
//	char ch;  int result;
//	cout<<"hello!";
	long int n;
	char *filenam1="ToBeTran.txt";
	char *filenam2="CodeFile.txt";

	if(HT==NULL){             //如果哈夫曼树不再内存中,就从文件中读入

	   n=CountHTNodefromFile();//将要为哈夫曼树分配空间的数
	   
	   HT=(HuffmanTree)malloc(n*sizeof(HTNode));//分配空间 // AllotSpacetoHT(HT,m);//
	   if(HT==NULL) return OVERFLOW;
     //用AllotSpacetoHT反而不好用!!!!!!!!!!!!!!!!!!!!!!!!!1
	   ReadHTfromFile(HT,2*charsetsize);//从文件中读入哈夫曼树//
	  // PrintHuffmantree(HT,charsetsize);
		//PrintHuffmantree(HT,2*charsetsize-1);
	}//if
	if(HC.hc==NULL&&HC.hclen==NULL)            
	CreateHuffmanCode(HT,HC,charsetsize); //对字符集中的所有字符生成哈夫曼编码并存入HC中

//	//||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
//
//
//	result=DealFileNotExistorEmpty(filenam1);
//	if(result==IWWY){//如果ToBeTran.txt不存在则建立,内容为空则
//		//    cout<<"hello";                                     //等待用户向ToBeTran.txt中装入内容
//		
//		printf("请在%s中装入要编码的内容I will wait for you!\n",filenam1);
//		printf("装入完成后按<c>继续进行编码,按<q>退出\n");
//		while(cin>>ch&&ch!='c'){
//			if(ch=='q') return EXIT;
//		}//while    		      //循环等待
//	}//if
//  //||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

	Translating(filenam1,filenam2,HT,HC);
	return OK;
}//Encoding


long int CountHTNodefromFile(){
	FILE *fp;int n;
	fp=fopen("hfmTree.dat","rb+");
	if(!fp) {
		cout<<"Open hfmTree.dat error!";
		return OPENFLERR;
	
	}//if
	fseek(fp,0,SEEK_END);
    n=ftell(fp);
	fclose(fp);
	
	return (n/sizeof(HTNode));
}

	
	////////////////////////////////////////////////////////
	/*
	//从hfmTree.dat文件中读取哈夫曼结点以计算charsetsize
	FILE *fp;HuffmanTree p;int i;
	fp=fopen("hfmTree.dat","rb");
	if(!fp) {
		cout<<"Open hfmTree.dat error!";
		return OPENFLERR;
	
	}//if
	for(i=0;feof(fp)!=EOF;++i){
	p=(HuffmanTree)malloc(sizeof(HTNode));
	if(!p) return ERROR;
	
	fread(p,sizeof(HTNode),1,fp);
	
	}//for
	charsetsize=i/2;
	free(p);
	fclose(fp);
	return OK;
	*/
//////////////////////////////////////////////////////////
void DestroyHuffmanTree(HuffmanTree &HT){
	free(HT);
}//DestroyHuffmanTree
void DestroyCharSet(CharSet &HCS){
	free(HCS.CSElem);
}//DestroyCharSet
int GetHCSFromHT(const HuffmanTree &HT,CharSet &HCS,int size){
	//从哈夫曼树中筛选出每个字符及其权之，建成哈夫曼字符集
	//size为字符集的大小
    CharSetElem* p=NULL;int i;
	p=(CharSetElem*)malloc(size*sizeof(CharSetElem));//0号未用
	if(p==NULL){
		return	OVERFLOW;
	}//if
	HCS.CSElem=p;
	HCS.Size=size;
	for(i=1;i<=size;++i){
		HCS.CSElem[i].ch=HT[i].hfch;
		HCS.CSElem[i].weight=HT[i].weight;	
	}//for
	return OK;
}// GetHCSFromHT

int QuickSort(CharSet* pHCS,int start,int end){
	//对HCS进行快速排序，按降序排
	//注意是在HCS.CSElem[start-end]之间排
	int n;
	if(end-start<1) return OK;               //比较一下if(end-start<=1) return OK;结果很大不同
	                                         //解释:a[n-1,n]此时end-start=1,满足条件就return了
	                                         //然而其实还需一次快速排序，例如a[n-1]=5,a[n]=6,
	                                         //注意是按降序排列的
    n=Partition(pHCS,start,end);   //一次划分
	QuickSort(pHCS,start,n-1);
	QuickSort(pHCS,n+1,end);
	return OK;
}//QSort

int Partition(CharSet* pHCS,int low,int high){
	int piovity;//枢轴
	
	CharSetElem temp=pHCS->CSElem[low];
	piovity=pHCS->CSElem[low].weight;
	//low=1;high=HCS->Size;
	while(low<high){
		while((low<high)&&(pHCS->CSElem[high].weight<=piovity)) --high;
		pHCS->CSElem[low]=pHCS->CSElem[high];
		while((low<high)&&(pHCS->CSElem[low].weight>=piovity)) ++low;
		pHCS->CSElem[high]=pHCS->CSElem[low];
		}//while
	pHCS->CSElem[low]=temp;
	return low;
}//Partition

int ReadyForDecoding(HuffmanTree &HT,HuffmanCode &HC,CharSet &HCS){
	//从文件读入哈夫曼树，并生成哈夫曼编码及其字符集(按权值降序排列)
	//总之此函数是先做好解码的准备工作
	long int n;int i;CharSetElem* p;
	if(HT==NULL){             //如果哈夫曼树不再内存中,就从文件中读入
	   n=CountHTNodefromFile();//将要为哈夫曼树分配空间的数 
	   HT=(HuffmanTree)malloc(n*sizeof(HTNode));//分配空间 // AllotSpacetoHT(HT,m);//
	   if(HT==NULL) return OVERFLOW;
	   ReadHTfromFile(HT,2*charsetsize);        //从文件中读入哈夫曼树//                     |哈夫曼树与哈夫曼    
	   CreateHuffmanCode(HT,HC,charsetsize);     //对字符集中的所有字符生成哈夫曼编码并存入HC|编码共存亡


	   	///////////////////////////////////////////////////////for test
//	PrintHuffmantree(HT,2*charsetsize-1);       //for test
	///////////////////////////////////////////////////////for test


	}//if

	if((HCS.CSElem==NULL)&&(HCS.Size==0)){
		//如果没有建立字符集，则建立
		p=(CharSetElem*)malloc((charsetsize+1)*sizeof(CharSetElem));//0号未用
		if(p==NULL){
		return	OVERFLOW;
		}//if
		HCS.CSElem=p;
		HCS.Size=charsetsize;
		for(i=1;i<=charsetsize;++i){
			HCS.CSElem[i].ch=HT[i].hfch;
			HCS.CSElem[i].weight=HT[i].weight;		
		}//for
		/*
	//////////////////////////////////////////////////////////////for test
	for(int j=1;j<=charsetsize;j++){
		cout<<HCS.CSElem[j].ch<<"   "<<HCS.CSElem[j].weight<<endl;
	
	}//for
	cout<<endl;
	/////////////////////////////////////////////////////////////for test
	*/
	}//if



	QuickSort(&HCS,1,charsetsize);      //对字符集进行快速排序,以降序排列

	/*
	///////////////////////////////////////////////////////////////////for test
	for(int k=1;k<=charsetsize;k++){
		cout<<HCS.CSElem[k].ch<<"   "<<HCS.CSElem[k].weight<<endl;
	
	}//for
	cout<<endl;
	///////////////////////////////////////////////////////////////////for test
	*/

	return OK;
}//ReadyForDecoding
int HuffmanCodeMaxLen(const HuffmanCode &HC,int n){
	//找出哈夫曼编码的最大长度并作为返回值返回
	//n为哈夫曼编码的个数
	int i,max=HC.hclen[1];  //把第一个假设为最大长度
	for(i=1;i<=n;++i){
		if(max<HC.hclen[i]) max=HC.hclen[i];	
	}//for
	return max;
}//HuffmanCodeMaxLen
void ReadCharsFromFile(int count,char *dest,FILE *fp){
	//count 为要从文件中读的字符个数
	//dest  是目的缓冲区，存放字符
	//fp 为已打开的文件指针
	int i;char ch;
	for(i=0;i<count;++i){
		ch=fgetc(fp);
		if(ch==EOF)
			break;
		dest[i]=ch;
	}//for
	dest[i]='\0';

}//ReadCharsFromFile
bool CompareStrings(char * str1,char *str2){  //test ok
	//str1--code 缓冲区中的
	//str2--哈夫曼编码
	//此函数是专门为此程序定制的,str2的长度小于等于str1
	int i;
	for(i=0;str2[i]!='\0';++i){
		if((str1[i]-str2[i])!=0)
			break;	
	}//for
	if(str2[i]!='\0') return false;        //str1与str2不相等
	                                       //从str1的开始到str2的等长度,str1与str2不相等
	return true;                           //相等
}//CompareStrings
int WriteStringtoFile(char *filename,char *strWritten,char *openmode){//test OK
	//把字符串strWritten写入文件filename以openmode方式
	FILE *fp=NULL;
	fp=fopen(filename,openmode);
	if(fp==NULL){
		printf("Open file %s error!",filename);
		return (OVERFLOW);
	}//if
	fprintf(fp,"%s",strWritten);
	fclose(fp);
	return OK;
}//WriteChartoFile
int Decoding(const HuffmanTree &HT,const HuffmanCode &HC,const CharSet &HCS){
	//开始解码
	int maxlen,i,pos,count=0;char *code=NULL;         //code 为从文件读入的字符缓冲区
	int fpPos=0;
    int filesize;
	FILE *fp=NULL; 
	char strWritten[SWAPSIZE];                       //此为译出的编码的暂存区，当暂存区满后，
	                                                 //写入文件
	maxlen=HuffmanCodeMaxLen(HC,charsetsize);
	code=(char *)malloc((maxlen+1)*sizeof(char)); //code长度为maxlen+1因为还有'\0'
	if(code==NULL){
		return OVERFLOW;
	}//if
	CreateNewFile("TextFile.txt");               //生成文件TextFile.txt
	fp=fopen("CodeFile.txt","r");
	if(!fp) {
		cout<<"Open CodeFile.txt error!";
		return OPENFLERR;	
	}//if
	////测出CodeFile.txt文件的大小
	fseek(fp,0,SEEK_END);   
	filesize=ftell(fp);
	rewind(fp);



	////
	//正式开始译码
	for(;fpPos<=filesize;){
		//文件没读到尾循环
		ReadCharsFromFile(maxlen,code,fp);
		for(i=1;i<=charsetsize;++i){
			//先试权值最大的,即出现可能性大的
			pos=Locate(HCS.CSElem[i].ch,HT,1,charsetsize);      //pos是权值最大的字符在HT中的下标
			if(CompareStrings(code,HC.hc[pos])==true){
				break;                                       //如果译码成功			
			}//if
		}//for(i=1;i<=charsetsize;++i)
		if(count==(SWAPSIZE-1)){                       //暂存区已满，写入文件，count归零
			 strWritten[count]='\0';
			 WriteStringtoFile("TextFile.txt",strWritten,"a+");
			 count=0;
		}//if(count==SWAPSIZE-1)

		strWritten[count++]=HCS.CSElem[i].ch;            //把译码写入暂存区
		fpPos+=HC.hclen[pos];
		rewind(fp);                 //文件内部指针恢复初始状态
		fseek(fp,fpPos,SEEK_SET);                        //移动到fpPos的位置
		                                                 //在它前面的都已经译码完成

//	fseek(fp,-(maxlen-HC.hclen[pos]-1),SEEK_CUR);      //向前移动maxlen-HC.hclen[pos]-1
		                                                   //个指针
	}//for(;feof(fp)!=EOF;) 
//要是暂存区中恰巧满了，并且已经解码完毕，则暂存区中无内容，count=0
	if(count!=0) strWritten[count]='\0';     //由于在上面的for循环中暂存区还没有满，
	                                         //就已经译完码了，暂存区中还有译码,
	                                         //所以在解码函数结束之前应写入文件
	                                          
	WriteStringtoFile("TextFile.txt",strWritten,"a+"); 
	//要是去掉上面这两句就会译码不全。


	fclose(fp);           //关闭文件
	return OK;

}//Decoding 
int PrintCode(){
 //将CodeFile.txt文件中的代码以每行50个的形式显示，并把此种形式的代码写入文件CodePrin.txt
	char print[SIZEALINE+1];long int filend;
//	print[SIZEALINE]='\n';
    print[SIZEALINE]='\0';
	FILE *fp=NULL;
	fp=fopen("CodeFile.txt","r");
	if(fp==NULL){
		cout<<"Open CodeFile.txt "<<endl;
		return OPENFLERR;
	}//if
    CreateNewFile("CodePrin.txt");       //生成文件CodePrin.txt
	fseek(fp,0,SEEK_END);
	filend=ftell(fp);                  //得到文件尾位置
	rewind(fp);                        //恢复文件初始状态
	do{
	ReadCharsFromFile(SIZEALINE,print,fp);
	WriteStringtoFile("CodePrin.txt",print,"a");        //50一行写入文件
    WriteStringtoFile("CodePrin.txt","\n","a");         //换行
	printf("%s",print);
	cout<<endl;                       //换行
	}while(ftell(fp)!=filend);         //判断是否到文件末尾
	fclose(fp);
	return OK;
}//Print
/*
void PrintHuffmantree(HuffmanTree HT,int n){
	//屏幕输出哈夫曼树
	//n为哈夫曼树的结点数
	if(HT){//如果哈夫曼树在内存中则print
	int i;HuffmanTree p;
	p=HT+1;

	for(i=1;i<n;i++,++p){
		if(i<=charsetsize)             //(n+1)/2)
			cout<<p->hfch;
		cout<<"\t"<<p->weight<<"\t"<<p->lchild<<"\t"<<p->rchild<<"\t"<<p->parent<<endl;
	
	}//for
	}//if
}//PrintHuffmantree
*/
////////////////////////
void PrintHuffmantree(HuffmanTree HT,int n){
	//屏幕输出哈夫曼树
	//n为哈夫曼树的结点数
	if(HT){//如果哈夫曼树在内存中则print
		HuffmanTree p=HT;
		CreateNewFile("TreePrint.txt");
		FILE *fp=NULL;
		fp=fopen("TreePrint.txt","a");
		PreOrderHuffmanTree(p,n-1,fp);
		fclose(fp);

	}//if
}//PrintHuffmantree
int PreOrderHuffmanTree(HuffmanTree p,int m,FILE *fp){
	//先根遍历HuffmanTree
	//p指向哈夫曼树的根结点
	//以嵌套方式输出HuffmanTree
  //  if(m==0) return OK;     //遇到叶子结点返回
	cout<<p[m].weight;fprintf(fp,"%d",p[m].weight);
	if((p[m].lchild==0)&&(p[m].rchild==0))
		return OK;
	cout<<"(";	fputc('(',fp);
	PreOrderHuffmanTree(p,p[m].lchild,fp);
    cout<<",";	fputc(',',fp);
	if(p[m].rchild!=0) 
		PreOrderHuffmanTree(p,p[m].rchild,fp);
	cout<<")";	fputc(')',fp);
	return OK;
}//PreOrderHuffmanTree