哈夫曼树编码译码作业.cpp

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

#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
struct nodeNum{                //定义一个结构为每个叶子节点所存储的数据（字符和它所对应的权值）
		char symbol;
		int frequency;
	    
};

struct BTreeNode{              //定义一个结构为树的节点
	nodeNum data;
	BTreeNode *left;
	BTreeNode *right;
};
   

//根据数组a中的n个值建立一棵哈夫曼树，返回树根指针
BTreeNode*CreateHuffman(nodeNum a[],int n)  
{
	BTreeNode **b,*q;        
	//动态分配一个由b指向的指针数组
	b=new BTreeNode*[n];
	int i,j;
	//初始化b指针数组，是每个指针元素指向a数组中对应的元素的结点
	for(i=0;i<n;i++){          
		b[i]=new BTreeNode;
		b[i]->data=a[i];
		b[i]->left=b[i]->right=NULL;
	}
	//进行n-1次循环建立哈夫曼树
	for(i=1;i<n;i++){
		//k1表示身临中具有最小权值的树的根结点的下标
		//k2表示身临中具有次最小权值的树的根结点的下标
		int k1=-1,k2;
		//k1初始指向森林中第一棵树，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.frequency<b[k1]->data.frequency) {k2=k1;k1=j;}
				else if(b[j]->data.frequency<b[k2]->data.frequency) k2=j;
			}
		}
		//由最小权值树和次最小权值树建立一棵新树，q指向树根节点
		q=new BTreeNode;
		q->data.frequency=b[k1]->data.frequency+b[k2]->data.frequency;
		q->left=b[k1];
		q->right=b[k2];
		//将指向新树的指针赋给b指针数组中k1位置，k2位置置为空
		b[k1]=q;
		b[k2]=NULL;
	}
	//删除动态建立的数组b
	delete []b;
	//返回整个哈夫曼树根指针
	return q;
}


//根据FBT指针所指向的哈夫曼树输出每个叶子的编码，len初值为0
void HuffManCoding(BTreeNode*FBT,int len)
{
	//静态数组用来存放编码，长度至少要等于哈夫曼树的深度减1
	static int a[15];
	if(FBT!=NULL){
		//访问到叶子结点时输出其保存在数组a中的0和1序列编码
		if(FBT->left==NULL&&FBT->right==NULL){
			cout<<"字符为："<<FBT->data.symbol<<"  权值为："<<FBT->data.frequency<<"  编码为:";
			for(int i=0;i<len;i++) cout<<a[i]<<" ";
			cout<<endl;

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

		}
		//访问到非叶子结点时分别向左、右子树递归调用，并分别把分支上的0，1编码保存到数组a的对应元素中，向下深入一层时len只增加1
		else{
			a[len]=0; HuffManCoding(FBT->left,len+1);
			a[len]=1; HuffManCoding(FBT->right,len+1);
		}
	}
}


//根据FBT指向的哈夫曼树将inputfile2.txt文件中的哈夫曼编码翻译成字符存入outputfile2.txt
void UnHuffManCoding(BTreeNode*FBT){
    //保存原树的根节点
	BTreeNode* FFBT=FBT;                 
	ifstream inn ("inputfile2.txt");
	ofstream off ("outputfile2.txt");
	char sign;
	inn.get(sign);
	//读取inputfile2.txt中的字符，遍历树寻找对应的叶子结点，找到后输出到outputfile2.txt文件
	while(!inn.eof()){	                  
		//如果读入的字符是0，则指向该结点的左孩子,同时判断是否是叶子结点，如果是则输出该节点所存放的字符，后恢复根节点的指向
		if(sign=='0'){
			FBT=FBT->left;
			if(FBT->left==NULL&&FBT->right==NULL){
				off<<FBT->data.symbol;
				FBT=FFBT;
			}
		}
		//如果读入的是1，则指向右孩子，其余功能同if
		else{
			FBT=FBT->right;
			if(FBT->left==NULL&&FBT->right==NULL){
				off<<FBT->data.symbol;
				FBT=FFBT;
			}
		}
		//读取下一个字符
		inn.get(sign);
	}
	inn.close();
	off.close();
}


//将建立的树清空，释放空间
void ClearBTree(BTreeNode*FBT)
{
	if(FBT!=NULL){
		ClearBTree(FBT->left);
		ClearBTree(FBT->right);
		delete FBT;
		FBT=NULL;
	}
}



void main()
{
//打开inputfile.txt文件读入字符同时统计每个字符出现的次数，保存在数组num中，而数组的下标+32对应着该字符的ASCII码值
ifstream input("inputfile1.txt");
	char ch;
	int num[100];
	int i=0,t=0;
	for(i=0;i<100;i++)
		num[i]=0;
	while(!input.eof()){
		input.get(ch);
		for(i=0;i<100;i++){
			if(ch==32+i)
				num[i]++;
		}
	}
	//统计出现频率不为0的字符的个数
	int NotEmpty=0;
	for(i=0;i<100;i++)
		if(num[i]!=0)
			NotEmpty++;

	i=0;
	int j=0;
    //将出现频率不为0的字符与它对应的字符打包成nodeNum型数组，a数组动态生成
	nodeNum*a=new nodeNum[NotEmpty];
	
	while(j<NotEmpty){
		while(i<100){
		if(num[i]!=0){
			a[j].symbol=32+i;
			a[j].frequency=num[i];
			i++; j++;
			continue;
		}
		i++;
		}
		
	}

	input.close();



BTreeNode*fbt=NULL;
//根据inputfile1.txt文件中个字符出现的频率创建一颗哈夫曼树，并返回树根指针
fbt=CreateHuffman(a,NotEmpty);
	
	//把字符编码，放到outputfile1.弹性体文件中
	HuffManCoding(fbt,0);
	//调用译码函数进行译码
   UnHuffManCoding(fbt);
   ClearBTree(fbt);
}