main.cpp

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

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

#include<iostream.h>
#include<malloc.h>
#define ERROR -2
#define OVERFLOW -1
#define OPENFLERR -3
#define OK 1
#define NOTEXIST -4
#define IWWY -6
#define EXIT 0          //正常退出
#define SWAPSIZE 21     //暂存区大小
#define SIZEALINE 50
typedef struct CharSetElem{
	int weight;
	char ch;
}CharSetElem;
typedef struct CharSetType{
	CharSetElem * CSElem;
	int Size;   //字符集大小为Size，而分配的空间+1
}CharSet; 
typedef struct HTNode{
	char hfch;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef struct HuffmanCode{
	char** hc;
	int * hclen;
}HuffmanCode;                   //动态分配哈夫曼编码
///////////////Inilization's functions///////////////////
int BuildCharSet(CharSet &HCS);    //
int CreateHuffmanTree(HuffmanTree &HT,const CharSet &HCS);    //
void SelectTwoMin(const HuffmanTree HT,int n,unsigned int &s1,unsigned int &s2);//
int WriteHTtoFile(const HuffmanTree &HT,int n);   //
void Inilization(CharSet &HCS,HuffmanTree &HT);
///////////////Encoding sections//////////////////////////////////
int CreateHuffmanCode(const HuffmanTree &HT,HuffmanCode &HC,int n);
int Locate(char ch,const HuffmanTree &HT,int start,int end);
int CreateNewFile(char *filename);
int Translating(char *filenam1,char *filenam2,const HuffmanTree &HT,const HuffmanCode &HC);
int WriteStringToFile(char *strWritten,char *filename);
//int AllotSpacetoHT(HuffmanTree HT,int size); 
int ReadHTfromFile(HuffmanTree &HT,int n); 
///int Encoding(); 
int Encoding(HuffmanTree &HT,HuffmanCode &HC);//int Encoding(HuffmanTree &HT,HuffmanCode &HC); //int Encoding(HuffmanTree &HT,HuffmanCode &HC);
//int DealFileNotExistorEmpty(char *filename);
long int CountHTNodefromFile();
//////////////////Decoding Sections//////////////////////////
int GetHCSFromHT(const HuffmanTree &HT,CharSet &HCS,int size);    //测试时用的
int Partition(CharSet *pHCS,int low,int high);
int QuickSort(CharSet *pHCS,int start,int end);
int ReadyForDecoding(HuffmanTree &HT,HuffmanCode &HC,CharSet &HCS);
//int ReadyForDecoding(HuffmanTree &HT,HuffmanCode &HC,CharSet *HCS);
int HuffmanCodeMaxLen(const HuffmanCode &HC,int n);
void ReadCharsFromFile(int count,char *dest,FILE *fp);
bool CompareStrings(char * str1,char *str2);
int WriteStringtoFile(char *filename,char *strWritten,char *openmode);
int Decoding(const HuffmanTree &HT,const HuffmanCode &HC,const CharSet &HCS);
///////////////////Print Sections///////////////////////////
int PrintCode();
void PrintHuffmantree(HuffmanTree HT,int n);
int PreOrderHuffmanTree(HuffmanTree p,int m,FILE *fp);





void DestroyHuffmanTree(HuffmanTree &HT);
void DestroyCharSet(CharSet &HCS);

int charsetsize;
//HuffmanCode HC;
//HuffmanTree HT;
//CharSet HCS;
int main(){
	char ch;/*long int n;
	n=CountHTNodefromFile();
	charsetsize=n/2;*/
		
	HuffmanTree HT=NULL;   //初始化HT
	HuffmanCode HC;
	HC.hc=NULL;HC.hclen=NULL; //初始化HC
	CharSet HCS;//CharSet HCS;
	HCS.Size=0;HCS.CSElem=NULL;//对哈夫曼字符集初始化
	cout<<"<q>--quit  <I>--Inilization  <E>--Encoding  <D>--Decoding  <P>--Print  <T>--Tree"<<endl;
	while(cin>>ch&&ch!='q'){
		switch(ch){
		case 'I':
			Inilization(HCS,HT);
			break;
		case 'E':       
			long int n;
			n=CountHTNodefromFile();
			charsetsize=n/2;               //计算出字符集的大小
		//	cout<<"charsetsize"<<charsetsize;
	    //   cout<<"HTNode size!"<<n<<endl;
			Encoding(HT,HC);//Encoding();
			cout<<"请到CodeFile.txt中查看编码!"<<endl;
			break;
		case 'D':
			long int m;
			m=CountHTNodefromFile();
			charsetsize=m/2; //计算出字符集的大小
			ReadyForDecoding(HT,HC,HCS); //做好解码的准备工作
			Decoding(HT,HC,HCS);      //解码
			cout<<endl;			
			break;
		case 'P':
			PrintCode();			     
			break;
		case 'T':
			PrintHuffmantree(HT,charsetsize*2);
			cout<<endl;
			break;
		default:break;			

		}//switch
	cout<<"<q>--quit  <I>--Inilization  <E>--Encoding  <D>--Decoding  <P>--Print  <T>--Tree"<<endl;
	}//while
	if(HT!=NULL) DestroyHuffmanTree(HT);
//	DestroyCharSet(HCS);

	/*
	CharSet HCS;int i;HuffmanTree HT,p,HT2;
	HCS.CSElem=NULL;
	HCS.Size=0;
	BuildCharSet(HCS);
	for(i=1;i<=HCS.Size;i++){
		printf("%c %d\n",HCS.CSElem[i].ch,HCS.CSElem[i].weight);
	}
	CreateHuffmanTree(HT,HCS);
	p=HT+1;

	for(i=1;i<=2*HCS.Size-1;i++,++p){
		if(i<=HCS.Size)
			cout<<p->hfch;
		cout<<"\t"<<p->weight<<"\t"<<p->lchild<<"\t"<<p->rchild<<"\t"<<p->parent<<endl;
	
	}//for
	WriteHTtoFile(HT,2*HCS.Size);

	HT2=(HuffmanTree)malloc((2*HCS.Size)*sizeof(HTNode));
	ReadHTfromFile(HT2,2*HCS.Size);
	p=HT2+1;
	for(i=1;i<=2*HCS.Size-1;i++,++p){
		if(i<=HCS.Size)
			cout<<p->hfch;
		cout<<"\t"<<p->weight<<"\t"<<p->lchild<<"\t"<<p->rchild<<"\t"<<p->parent<<endl;
	
	}//for

	

*/

return true;
}//main
int BuildCharSet(CharSet &HCS){
	//建立哈夫曼字符集
	//HCS为哈夫曼字符集
	int n,k,i;
	char e,yorn;
	CharSetElem * p;
	printf("请输入哈夫曼字符集的大小:");
	scanf("%d",&n); 
	if(n<=1)
		return ERROR;
	charsetsize=n;        //charsetsize是全局变量
	p=(CharSetElem*)malloc((n+1)*sizeof(CharSetElem));//0号未用 
	printf("hello");
	if(!p) return OVERFLOW;
	HCS.CSElem=p;
	HCS.Size=n;
   // printf("hello");
	cout<<"请问你所要输入的字符集中是否存在空格(y/n):";
	cin>>yorn;
	if(yorn=='y'){
		cout<<"请输入空格的权值:";
	    cin>>HCS.CSElem[1].weight;
		HCS.CSElem[1].ch=' ';
		cout<<"在后面就不要输入空格和它的权值了!"<<endl;

		for(i=2;i<=n;++i){
			cout<<"请输入字符集的第"<<i<<"个字符及其权值:";
	        cin>>e>>k;
		    HCS.CSElem[i].weight=k;
		    HCS.CSElem[i].ch=e;	
		}//for
	}//if
	else if(yorn=='n')
	{
		for(i=1;i<=n;++i){
			cout<<"请输入字符集的第"<<i<<"个字符及其权值:";
	        cin>>e>>k;
		    HCS.CSElem[i].weight=k;
		    HCS.CSElem[i].ch=e;
		}//for
	}//else

	return OK;
}// BuildCharSet
int CreateHuffmanTree(HuffmanTree &HT,const CharSet &HCS){
	//构造哈夫曼树
	unsigned int s1,s2;
	int m,n,i,j;
	HuffmanTree p;
	//CharSetElem *q;
	n=HCS.Size; m=2*n-1;  //注意n是字符集中字符个数  m是将要构造的哈夫曼树的结点个数
	p=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	if(!p) return OVERFLOW;
	HT=p;
	for(p=HT+1,i=1;i<=n;++i,++p){   //初始化哈夫曼树 0号单元不用管,没用
		p->hfch=HCS.CSElem[i].ch;
		p->weight=HCS.CSElem[i].weight;
		p->parent=0;p->lchild=0;p->rchild=0;	
	}//for
	for(;i<=m;++i,++p){                                //从n+1到m的哈夫曼字符不用管,在程序中没用到
		p->parent=0;p->lchild=0;p->rchild=0;p->weight=0;
	}//for
	//开始建立哈夫曼树
	for(j=n+1;j<=m;++j){
		SelectTwoMin(HT,j-1,s1,s2);//选择两个最小的结点，S1为最小的S2为次小的下标
		HT[s1].parent=j;HT[s2].parent=j;
		HT[j].lchild=s1;HT[j].rchild=s2;
		HT[j].weight=HT[s1].weight+HT[s2].weight;
	}//for
	return OK;
}//CreateHuffmanTree
void SelectTwoMin(const HuffmanTree HT,int n,unsigned int &s1,unsigned int &s2){
	//在HT[1'''n]中选择两个最小权值的结点并且是没有双亲的结点，
	//再把结点的下标赋给S1与S2
	//w1,w2分别为最小的权值，次小的权值
	int i;
	unsigned int w1=65535,w2=65535;          //把w1和w2，设为机内最大数(int类型的)
	for(i=1;i<=n;++i){
		if(HT[i].parent==0)              //经过一趟循环选择最小与次小的
			if(HT[i].weight<w1){
				w2=w1;
				s2=s1;
				w1=HT[i].weight;
				s1=i;			
			}//内if
			else if(HT[i].weight<w2){
				w2=HT[i].weight;
				s2=i;
			}//else if
	}//for
}//SelectTwoMin
int WriteHTtoFile(const HuffmanTree &HT,int n){
	//哈夫曼树写入文件hfmTree.dat中，包括0号单元
	//n为结点的个数加1即(2*字符集大小)
	FILE *fp;
//	int i;
	fp=fopen("hfmTree.dat","wb+");
	if(!fp){
		cout<<"Open file error!";
		return OPENFLERR;//exit(1);	
	}//if
	fwrite(HT,sizeof(HTNode),n,fp);

//	for(i=1;i<=n;++i){
//		fwrite(HT,sizeof(HTNode),1,fp);
//	}//for
	fclose(fp);
	return OK;
}//WriteHTtoFile


void Inilization(CharSet &HCS,HuffmanTree &HT){
	//创建哈夫曼字符集并且生成哈夫曼树并把哈夫曼树写入文件
	 //HuffmanTree HT,HT2;

	BuildCharSet(HCS);
	CreateHuffmanTree(HT,HCS);
	//PrintHuffmantree(HT,2*charsetsize-1);
	WriteHTtoFile(HT,2*HCS.Size);//WriteHTtoFile(HT,2*charsetsize);
	//AllotSpacetoHT(HT2,(2*charsetsize));
	//ReadHTfromFile(HT2,(2*charsetsize));
    //PrintHuffmantree(HT2,2*charsetsize-1);
}//Inilization


////////////////////////////////
//编码部分
int CreateHuffmanCode(const HuffmanTree &HT,HuffmanCode &HC,int n){
	//n为字符集大小
	char **hc=NULL;char *code=NULL,*p=NULL;
	int *hclen=NULL;unsigned int c,f;int i,start;
	hc=(char **)malloc((n+1)*sizeof(char *));//同HT一样0号单元未用
	if(!hc){
		cout<<"分配空间失败!"<<endl;
		return OVERFLOW;	
	}//if
	HC.hc=hc;
	hclen=(int *)malloc((n+1)*sizeof(int));//同HT,HC一样0号单元未用
	if(!hclen){
		cout<<"分配空间失败!"<<endl;
		return OVERFLOW;
	}//if
	HC.hclen=hclen;
	code=(char *)malloc(n*sizeof(char));   //编码的工作空间
	if(!code){
		cout<<"分配空间失败!"<<endl;
		return OVERFLOW;	
	}//if
	code[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) code[--start]='0';//从叶子结点到根逆向求编码
			else code[--start]='1';
			}//内for
		p=(char *)malloc((n-start)*sizeof(char));
		if(!p){
			cout<<"分配空间失败!"<<endl;
		    return OVERFLOW;
		}//if
		HC.hc[i]=p;HC.hclen[i]=n-start-1;       //以空间换时间,
		                                        // 因为在后面的译码的时候用到编码的字符串的长度,
		                                        //要是每个字符的译码都再去strlen就不值了
		strcpy(HC.hc[i],&code[start]);  //在start处开始copy
			
	}//外for
	free(code); //释放编码的工作空间
	return OK;

}//CreateHuffmanCode
int Translating(char *filenam1,char *filenam2,const HuffmanTree &HT,const HuffmanCode &HC){
	//filenam1是存放被编码的源文件
	//filenam2是存放编码的文件
	//假设filenam1是按要求建好，并且里面有要编码的内容的
	FILE *fp1,*fp2;char ch;int i;
	char *strCode;
	fp1=fopen(filenam1,"r");            //以只读方式打开文件
	fp2=fopen(filenam2,"w+");            //以写方式打开文件，是为了清空文件
	if(fp1==NULL){
		printf("Open file %s error!",filenam1);
		return OPENFLERR;
	}//if
	if(fp2==NULL){
		printf("Open file %s error!",filenam1);
		return OPENFLERR;
	}//if
	fclose(fp2);                    //关闭文件filenam2
	for(ch=fgetc(fp1);ch!=EOF;ch=fgetc(fp1)){
	//	cout<<ch<<endl;
		i=Locate(ch,HT,1,charsetsize); //在HT[1---charsetsize]中找到字符ch的下标
	//	cout<<"hello"<<i;
		strCode=HC.hc[i]; //取得字符的编码
//		printf("%s",strCode);
		
	//	WriteStringToFile(strCode,filenam2);
//cout<<strCode<<" ";
	WriteStringtoFile(filenam2,strCode,"a");//把字符的编码写入文件filenam2
	}//for
	fclose(fp1);
	return OK;
}//Translate
int CreateNewFile(char *filename){
	FILE *fp;
	fp=fopen(filename,"w+");
	if(!fp){
		cout<<"Create new file error!"<<endl;
		return OPENFLERR;
	}//if
	fclose(fp);
	return OK;
}//CreateNewFile
int Locate(char ch,const HuffmanTree &HT,int start,int end){
	//ch 为要搜索的字符 在HT[start...end]之间搜索
	//找到返回下标，没找到返回NOTEXIST
	int i;
	for(i=start;i<=end;++i)
		if(ch==HT[i].hfch) 
			return i;
	return NOTEXIST;
}//Locate
int WriteStringToFile(char *strWritten,char *filename){
	//把字符串strWritten追加如文件filename
	FILE *fp;
	fp=fopen(filename,"a");//以追加方式打开文件
	if(!fp){
		cout<<"Open file error!"<<endl;
		return OPENFLERR;	
	}//if
	fprintf(fp,"%s",strWritten);
	fclose(fp);
	return OK;
}//WriteStringToFile
//////////////////////////////////////////////////////////////////////
///就因为这个函数，花了偶六个小时!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
/////////////////////////////////////////////////////////|||||||||||||
//int AllotSpacetoHT(HuffmanTree HT,int size){//allot 英文意思是分配
//	//对哈夫曼树分配空间
//	HuffmanTree p;
//	p=(HuffmanTree)malloc(size*sizeof(HTNode));
//	if(!p){
//		return OVERFLOW;
//	}//if
//	HT=p;
//	return OK;
//}//AllotSpacetoHT
////////////////////////////////////////////////////////||||||||||||||||

int ReadHTfromFile(HuffmanTree &HT,int n){
	//从hfmTree.dat文件中读取哈夫曼树入HT所指空间
	//n为要读入的HTNode的个数包括未用的0号单元
	FILE *fp;
	fp=fopen("hfmTree.dat","rb+");
	if(!fp) {
		cout<<"Open hfmTree.dat error!";
		return OPENFLERR;
	
	}//if
	fread(HT,sizeof(HTNode),n,fp);
	fclose(fp);
	return OK;
}//ReadHTfromFile

//////////////////////////////////////////////////
//这个函数可是花了好长时间幺
/*int DealFileNotExistorEmpty(char *filename){
	//处理文件不存在,或是为空文件的情况
	FILE *fp=NULL;long int  size;                        //char ch;
	fp=fopen(filename,"r"); //以读写方式打开文件,即是若文件不存在则创建,存在则打开
	if(fp==NULL){
		fclose(fp);
		fp=fopen(filename,"w+");
		fclose(fp);
		printf("%s中无内容,请装入后再编码!",filename);
		return IWWY;
	}//if
	fseek(fp,0,SEEK_END);    
	size=ftell(fp);              //计算文件的大小,来判断文件是否为空
	if(size==0){
			rewind(fp);
			fclose(fp);
			return IWWY;
	}

	if(feof(fp)==EOF){               //检查文件是否为空
		printf("%s中无内容,请装入后再编码!",filename);
		fclose(fp);
		
		return IWWY;
		
	}//if

	fclose(fp);
	return OK;
}//DealFileNotExistorEmpty
*/
/*
////////////////////////////////
int Encoding(HuffmanTree HT,HuffmanCode &HC){
	//开始编码HuffmanTree &HT,HuffmanCode &HC
  //  HuffmanTree HT=NULL;HuffmanCode HC;