a.cpp

根据一段给定的文章构造哈夫曼树并对一段给出的代码译码成为一段文章

#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
//#include<ctype.h>
struct nodeNum{
		char ii;
		int jj;
	    //char *cc;    
};
	char **ss;
struct BTreeNode{
	nodeNum data;
	BTreeNode *left;
	BTreeNode *right;
};
   //nodeNum*a=new nodeNum[NotEmpty];


BTreeNode*CreateHuffman(nodeNum a[],int n)  //根据数组a中的n个值建立一棵哈夫曼树，返回树根指针
{
	BTreeNode **b,*q;
	b=new BTreeNode*[n];
	int i,j;
	for(i=0;i<n;i++){
		b[i]=new BTreeNode;
		b[i]->data=a[i];
		b[i]->left=b[i]->right=NULL;
	}
	for(i=1;i<n;i++){
		int k1=-1,k2;
		for(j=0;j<n;j++){
			if(b[j]!=NULL&&k1==-1){
				k1=j;
				continue;
			}
			if(b[j]!=NULL){
				k2=j;
				break;
			}
		}
		for(j=k2;j<n;j++){
			if(b[j]!=NULL){
				if(b[j]->data.jj<b[k1]->data.jj) {k2=k1;k1=j;}
				else if(b[j]->data.jj<b[k2]->data.jj) k2=j;
			}
		}
		q=new BTreeNode;
		q->data.jj=b[k1]->data.jj+b[k2]->data.jj;
		q->left=b[k1];
		q->right=b[k2];
		b[k1]=q;
		b[k2]=NULL;
	}
	delete []b;
	return q;
}

int WeightPathLength(BTreeNode*FBT,int len)  //根据FBT指针所指向的哈夫曼树求出带权路径长度，len初值为0
{
	if(FBT==NULL) return 0;
	else{
		if(FBT->left==NULL&&FBT->right==NULL){
			return FBT->data.jj*len;
		}
		else{
			return WeightPathLength(FBT->left,len+1)+
				WeightPathLength(FBT->right,len+1);
		}
	}
}

void HuffManCoding(BTreeNode*FBT,int len)
{
	static int a[15];
	if(FBT!=NULL){
		if(FBT->left==NULL&&FBT->right==NULL){
			cout<<"结点权值为"<<FBT->data.jj<<"字符为"<<FBT->data.ii<<"的编码:";
			for(int i=0;i<len;i++) cout<<a[i]<<" ";
			cout<<endl;

			ofstream output("outputfile1.txt",ios::ate);
		    
			output<<"结点权值为"<<FBT->data.jj<<"字符为"<<FBT->data.ii<<"的编码:";
			for( i=0;i<len;i++) output<<a[i]<<" ";
			output<<endl;
				output.close();
				

		}
		else{
			a[len]=0; HuffManCoding(FBT->left,len+1);
			a[len]=1; HuffManCoding(FBT->right,len+1);
		}
	}
}
//int q=0;
/*void HuffManCoding(BTreeNode*FBT,int len)
{
	static int a[10];
	
	if(FBT!=NULL){
		if(FBT->left==NULL&&FBT->right==NULL){
			cout<<"结点权值为"<<FBT->data.jj<<"字符为"<<FBT->data.ii<<"的编码:";
				
			*ss=new char[len];
				//char *b=new char[len];	
			//cc=new char[len];
			for(int i=0;i<len;i++){ 
					cout<<a[i]<<" ";
				//	(FBT->data.cc[i])=a[i];
				*ss[i]=char(a[i]+48);
				}
				
				//FBT->data.cc=b;


		//	delete b;
//				q++;
			
			cout<<endl;

			ofstream output("outputfile1.txt",ios::ate);
		    
			output<<"结点权值为"<<FBT->data.jj<<"字符为"<<FBT->data.ii<<"的编码:";
			for( i=0;i<len;i++) output<<a[i]<<" ";
			output<<endl;
				output.close();
				

		}
		else{
			a[len]=0; HuffManCoding(FBT->left,len+1);
			a[len]=1; HuffManCoding(FBT->right,len+1);
		}
	}
}*/

/*char* OUTPUT(BTreeNode*FBT,int len,char x)
{
	static int a[10];
	
	if(FBT!=NULL){
		if(FBT->left==NULL&&FBT->right==NULL){
			if(x==FBT->data.ii){
				(FBT->data.cc)=new char[len];
			for(int i=0;i<len;i++) 
				FBT->data.cc[i]=char(a[i]+48);
			FBT->data.cc[len]='\0';
				return FBT->data.cc;
			//	break;
				
			}
			
		
		}
		else{
			a[len]=0; OUTPUT(FBT->left,len+1,x);
			a[len]=1; OUTPUT(FBT->right,len+1,x);
		}
	}
}*/


void READ(BTreeNode*FBT){
	BTreeNode* FFBT=FBT;
	ifstream inn ("inputfile2.txt");
	ofstream off ("outputfile2.txt");
	char jjjj;
	inn.get(jjjj);
	while(!inn.eof()){	
		if(jjjj=='0'){
			FBT=FBT->left;
			if(FBT->left==NULL&&FBT->right==NULL){
				off<<FBT->data.ii;
				FBT=FFBT;
			}
		}
		else{
			FBT=FBT->right;
			if(FBT->left==NULL&&FBT->right==NULL){
				off<<FBT->data.ii;
				FBT=FFBT;
			}
		}
		inn.get(jjjj);
	}
	inn.close();
	off.close();
}



void ClearBTree(BTreeNode*FBT)
{
	if(FBT!=NULL){
		ClearBTree(FBT->left);
		ClearBTree(FBT->right);
		delete FBT;
		FBT=NULL;
	}
}



void main()
{

ifstream input("inputfile1.txt");
	char iii;
	int num[100];
	int i=0,t=0;
	for(i=0;i<100;i++)
		num[i]=0;
	while(!input.eof()){
		input.get(iii);
		for(i=0;i<100;i++){
			if(iii==32+i)
				num[i]++;
		}
	}
	int NotEmpty=0;
	for(i=0;i<100;i++)
		if(num[i]!=0)
			NotEmpty++;

	i=0;
	int j=0;
    nodeNum*a=new nodeNum[NotEmpty];
	
	while(j<NotEmpty){
		while(i<100){
		if(num[i]!=0){
			a[j].ii=32+i;
			a[j].jj=num[i];
			i++; j++;
			continue;
		}
		i++;
		}
		
	}
	for(j=0;j<NotEmpty;j++)
		cout<<a[j].ii<<" "<<a[j].jj<<endl;
	input.close();

ss=new char*[NotEmpty];

BTreeNode*fbt=NULL;
fbt=CreateHuffman(a,NotEmpty);
	cout<<WeightPathLength(fbt,0)<<endl;
	
	HuffManCoding(fbt,0);
	//	output.close();
//	ClearBTree(fbt);

//BTreeNode* x;
   /* ifstream in ("inputfile1.txt");
	ofstream out("outputfile2.txt",ios::ate);
	char jjj;
	while(!in.eof()){
		in.get(jjj);
				for(j=0;j<NotEmpty;j++)
			if(jjj==a[j].ii)
				for(i=0;i<10;i++)
				out<<ss[j];
		
	
		//	cout<<OUTPUT(fbt,0,jjj);

		 
	}
	out.close();*/
   READ(fbt);
}