b.cpp

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

#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
#include<ctype.h>
struct nodeNum{
		char ii;
		int jj;
	
};
	char*cc;
struct BTreeNode{
	nodeNum data;
	BTreeNode *left;
	BTreeNode *right;
};



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);
		}
	}
}*/
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<<"的编码:";
				//FBT->data.cc=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];
					cc[i]=a[i];
				}
				
				//FBT->data.cc=b;


		//	delete b;
				
			
			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);
		}
	}
}

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

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

*/




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();

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


    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)
				out<<cc;
		 
	}
	out.close();



	/*ofstream output("outputfile1.txt");
		for(i=0;i<100;i++)
			if(num[i]!=0){
				output<<char(32+i)<<" "<<num[i]<<endl;
				t++;
			}
	output.close();
	cout<<t;*/


/*BTreeNode*fbt=NULL;
fbt=CreateHuffman(a,NotEmpty);
	cout<<WeightPathLength(fbt,0)<<endl;
	//	ofstream output("outputfile1.txt");
	HuffManCoding(fbt,0);
	//	output.close();
	ClearBTree(fbt);
*/
	
	
/*	int n,i;
	BTreeNode*fbt=NULL;
	cout<<"输入待构造的哈夫曼树中带权叶子的结点数n：";
	cin>>n;
	int*a=new int[n];
	cout<<"输入"<<n<<"个整数作为权值：";
	for(i=0;i<n;i++) cin>>a[i];
	fbt=CreateHuffman(a,n);
	cout<<"广义表形式的哈夫曼树：";
	cout<<"哈夫曼树的权数：";
	cout<<WeightPathLength(fbt,0)<<endl;
	cout<<"树中每个叶子的哈夫曼编码："<<endl;
	HuffManCoding(fbt,0);
	ClearBTree(fbt);*/
}
/*void main(){
	ifstream input("inputfile1.txt");
	char ii;
	int num[100];
	int i=0,t=0;
	for(i=0;i<100;i++)
		num[i]=0;
	while(!input.eof()){
		input.get(ii);
		for(i=0;i<100;i++){
			if(ii==32+i)
				num[i]++;
		}
	}
    struct nodeNum{
		char ii;
		int jj;
	}
	nodeNum a[100];
	for(i=0;i<100;i<++){
		a[i]->ii=32+i;
		a[i]->jj=num[i];
	}
	for(i=0;i<100;i++)
		cout<<a[i]->ii<<" "<<a[i]->jj<<endl;
	input.close();
	ofstream output("inputfile2.txt");
		for(i=0;i<100;i++)
			if(num[i]!=0){
				output<<char(32+i)<<" "<<num[i]<<endl;
				t++;
			}
	output.close();
	cout<<t;*/
	
	
	/*void main(){
	ifstream input("inputfile1.txt");
	char ii;
	int num[100];
	int i=0,t=0;
	for(i=0;i<100;i++)
		num[i]=0;
	while(!input.eof()){
		input.get(ii);
		for(i=0;i<100;i++){
			if(ii==32+i)
				num[i]++;
		}
	}
	int NotEmpty=0;
	for(i=0;i<100;i++)
		if(num[i]!=0)
			NotEmpty++;
	struct nodeNum{
		char ii;
		int jj;
	};
	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();
	ofstream output("outputfile1.txt");
		for(i=0;i<100;i++)
			if(num[i]!=0){
				output<<char(32+i)<<" "<<num[i]<<endl;
				t++;
			}
	output.close();
	cout<<t;
		
	
	
	
	
	//for(i=0;i<100;i++)
		//	cout<<num[i]<<" ";
}*/


	




/*	int*a=new int[t];
	for(i=0;i<n;i++) cin>>a[t];
		
	
}*/