haffmantree.cpp

哈弗曼编码

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
typedef struct{
	int weight;
	int lchild;
	int rchild;
}HTNode;
typedef struct{
	HTNode * HTree;
	int root;   //根结点的位置
}HuffmanTree;



int SelectMin(HuffmanTree HT,int* visit,int num){
	//在数组HT.HTree的前num个元素中选择weight最小的，返回数组序号
	//visit=1时表示不可选，=0时表示可选
	int min=0;
	while(visit[min])min++;
	for(int i=min;i<num;i++)
		if((HT.HTree[i].weight<HT.HTree[min].weight) && (visit[i]==0))   min=i; 
    visit[min]=1;
	return min;                                    
}

void CreateHuffmanTree(HuffmanTree HT,int* w,int n){
	//对N个字符建立Huffman树，w[]记录字符相应的权重
	int m,min1,min2,* visit;   HTNode* p;                   
	m=2*n-1;  visit=new int[m];   p=HT.HTree;
    for(int i=0;i<n;i++,p++){
		p->weight=w[i];   p->lchild=-1; p->rchild=-1; visit[i]=0;
	}
	for(;i<m;i++,p++){
		p->weight=0;     p->lchild=-1; p->rchild=-1; visit[i]=0;
	}
	for(i=n,p=HT.HTree+n;i<m;i++,p++){
		min1=SelectMin(HT,visit,i);
		min2=SelectMin(HT,visit,i);
		p->weight=HT.HTree[min1].weight+HT.HTree[min2].weight;
		p->lchild=min1;  p->rchild=min2;
	}
	HT.root=m-1;                                    
}

void Coding(HuffmanTree T,int i,int *codes,int code){
	if(i==-1)  return;
	if((T.HTree[i].lchild==-1) && (T.HTree[i].rchild==-1)){
		codes[i]=code; return;
	}
	
	code=code<<1; 
	Coding(T,T.HTree[i].lchild,codes,code);
	code+=1;  
	Coding(T,T.HTree[i].rchild,codes,code);
	code=code>>1; 
}

void HuffmanCoding(HuffmanTree T,int *codes){
	int code=1;     
	Coding(T,T.root,codes,code);
}

char *IntToTwice(int n){
	int num=n;
	int count=0;
	while(num/=2) count++;
	char *s=new char[count+1];
	s[count]='\0';
	num=n%int(pow(2,count));
	int j=0;
	while(j<count){
		s[count-j-1]=num%2+'0';
		num/=2;
		j++;
	}
	return s;
}

void SaveZifuCode(char *filename,char *zifu,int *codes,int n){
	FILE *fp;
	if((fp=fopen(filename,"w"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
	for(int i=0;i<n;i++){
		fputc(zifu[i],fp);
		fputs("--",fp);
		fputs(IntToTwice(codes[i]),fp);
		fputc('\n',fp);
	}
}


void InorderTraverse(HuffmanTree HT,int i,int *inorder,int *j){
	if(i==-1) return;
	if((HT.HTree[i].lchild==-1) && (HT.HTree[i].rchild==-1)){
		inorder[(*j)++]=i;  return;
	}
	InorderTraverse(HT,HT.HTree[i].lchild,inorder,j);
	inorder[(*j)++]=i;
	InorderTraverse(HT,HT.HTree[i].rchild,inorder,j);
}


void InorderTraverseTree(HuffmanTree HT,int *inorder){
	int i=0;
	int *j=&i;
    InorderTraverse(HT,HT.root,inorder,j);
}

void FloorTraverse(HuffmanTree HT,int *floor){
	int front,rear,t;
	front=rear=0;
	floor[front]=HT.root;
	while(front<=rear){
		t=floor[front];
		if(HT.HTree[t].lchild!=-1)  floor[++rear]=HT.HTree[t].lchild;
	    if(HT.HTree[t].rchild!=-1)  floor[++rear]=HT.HTree[t].rchild;
		front++;
	}
}

void TreePrint(HuffmanTree HT,int m,char *zifu,char sign){
	char *allzifu=new char[m];
	int *inorder=new int[m];
	int *floor=new int[m];
	for(int i=0;i<(m+1)/2;i++)  allzifu[i]=zifu[i];
	while(i<m){ 
		allzifu[i]=sign;  i++;
	}
	InorderTraverseTree(HT,inorder);
	FloorTraverse(HT,floor);
	i=0; int k,t;
	cout<<"HuffmanTree is as followed:"<<endl;
	while(i<m){
		k=0;
		for(int j=0;j<m;j++){
			if(floor[i]==inorder[j]){
				for(t=k;t<j;t++) cout<<' ';
				cout<<allzifu[floor[i]];
				k=j+1; i++;
			}
		}
		cout<<endl;
	}
}

void InputTextFile(char *filename){
	FILE *fp;
    if((fp=fopen(filename,"w"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
	char c;
	cout<<"Please input the text:"<<endl;
	while((c=getchar())!='#')fputc(c,fp);
	fputc('#',fp);
	fclose(fp);
}

void TransTextToCode(char *textfile,char *codefile,int *codes,char *zifu){
    FILE *fp1,*fp2;
    if((fp1=fopen(textfile,"r"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
    if((fp2=fopen(codefile,"w"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
	int j;char c=fgetc(fp1);
	while(c!='#'){
		 j=0;
	    while(zifu[j]!=c) j++;
	    fputs(IntToTwice(codes[j]),fp2);
		c=fgetc(fp1); 
	}
	fputc('#',fp2);
    fclose(fp1);  fclose(fp2);
}

void CodePrint(char *codefile,char *stdcodefile){
	//把编码文件转化为每行50个的标准编码文件
    FILE *fp1,*fp2;
    if((fp1=fopen(codefile,"r"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
    if((fp2=fopen(stdcodefile,"w"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
	char c=fgetc(fp1);
    int i;
	cout<<"The codes are:"<<endl;
	while(c!='#'){
		i=0;
	    while(i<50 && c!='#'){
            fputc(c,fp2); i++; cout<<c;c=fgetc(fp1);
		}
		fputc('\n',fp2); cout<<endl;
	}
    fclose(fp1);fclose(fp2);
}

int Match(int m,int *codes,int n){
	//匹配编码与字符，成功返回字符序号，反之返回-1
	for(int i=0;i<n;i++)
		if(m==codes[i]) return i;
    return -1;
}

void TransCodeToText(char *codefile,char *textfile,int *codes,int n,char *zifu){
    FILE *fp1,*fp2;
    if((fp1=fopen(codefile,"r"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
    if((fp2=fopen(textfile,"w"))==NULL){
		cout<<"Can't open the file!"<<endl;
		exit(0);
	}
    char c=fgetc(fp1);  int num=1; int i;
	while(c!='#'){
		num=2*num+(c-'0');
		if((i=Match(num,codes,n))!=-1){
			fputc(zifu[i],fp2); num=1;
		}
		c=fgetc(fp1);
	}
	fputc('#',fp2);
	fclose(fp1); fclose(fp2);
}






void main(){
	int n,* w,*codes; HuffmanTree HT; char * zifu;
	cout<<"Please input the number of chars:"<<endl;
	cin>>n;     
	codes=new int[n];
	w=new int[n];
	zifu=new char[n];
    HT.root=2*n-2;
    HT.HTree=new HTNode[2*n-1];
	cout<<"Please input chars:"<<endl;
    for(int i=0;i<n;i++) cin>>zifu[i];
	cout<<"Please input the weights of chars:"<<endl;
	for(i=0;i<n;i++) cin>>w[i];


	CreateHuffmanTree(HT,w,n);
    
    HuffmanCoding(HT,codes);

    SaveZifuCode("HfmTree.txt",zifu,codes,n);

    TreePrint(HT,2*n-1,zifu,'*');

	InputTextFile("ToBeTrans.txt");
	
	TransTextToCode("ToBeTrans.txt","CodeFile.txt",codes,zifu);
	
	CodePrint("CodeFile.txt","CodePrin.txt");
    
	TransCodeToText("CodeFile.txt","TextFile.txt",codes,n,zifu);
}