huffman_final.cpp

二叉树的实验报告 源码以及运行结果的说明

#include <iostream>
#include <string>
#include <fstream>
using namespace std;
////////////////////////////////////
//the declaration of HuffmanTree
////////////////////////////////////
class HuffmanTree
{
private:
	struct BinaryTree		//二叉树结点
	{
		int f;	//字频
		char c;	//字符
		BinaryTree *parent,*lchild,*rchild;
	}*root,*btp;
	
	struct NodeChain		//结点钩子，指向待编码结点
	{
		BinaryTree *t;		
		NodeChain *left, *right;
	}*nchead,*ncp;

	int freq[256];	//字频表
	string hc[256];	//huffman编码表，词典
	bool hc_exist[256];
	void traverse(string code,BinaryTree *node);	//遍历huffman树，内部递归函数，只被build调用
	void destorytree(BinaryTree *node);		//清除huffman树，内部递归函数
public:
	void build(string s);		//从纯英文String生成Huffman树
	void clear();				//清空所有数据
	string code(string s);		//以字符串形式返回Huffman编码
	string decode(string s);	//解码
	string dict(char s);		//返回对应字符的字典
	int save(string path);		//保存huffman树和编码表到文件
	int load(string path);		//从文件中读取huffman树和编码表
}ht;
////////////////////////////////////
//test driver
////////////////////////////////////
void main()
{
	int i;
	char buf[255]="";
	string path;
	//test1.初始化
	cout<<"test1.初始化  从终端读入一段英文字符，统计每个字符出现的频率，建立赫夫曼树，并将该树存入某文件\n";
	cout<<"请输入一段英文：";
	cin.getline(buf,255,'\n');
	string userInput(buf);
	ht.build(userInput);
	cout<<"huffman编码："<<ht.code(userInput)<<endl;

	//test2.编码
	cout<<"\ntest2.编码  利用建好的赫夫曼树对各字符进行编码，用列表的形式显示在屏幕上，并将编码结果存入另一文件中"<<endl;
	cout<<"huffman字典：\n";
	for (i=0;i<256;i++) if (ht.dict(i)!="") cout<<" ["<<char(i)<<"] "<<ht.dict(i)<<endl;
	cout<<"请输入欲保存的文件名(不含扩展名)：";
	cin>>path;
	path=path+".htc";
	ht.save(path);

	//test3.解码
	cout<<"\ntest3.解码  利用保存的赫夫曼编码，对任意输入的0，1序列能正确解码"<<endl;
	if (ht.load(path)) cout<<"文件读取成功.\n"; else cout<<"文件读取失败.\n";
	cout<<"请输入任意二进制字符串：";
	cin>>userInput;
	cout<<"解码结果："<<ht.decode(userInput)<<endl;
}

////////////////////////////////////
//the implemetation of HuffmanTree
////////////////////////////////////

void HuffmanTree::build(string s)
{
	int i,charnum;
	for (i=0;i<256;i++) freq[i]=0;				//初始化字频表
	for (i=0;i<s.length();i++) freq[s[i]]++;	//统计字频
	//建立树结点链
	nchead=new NodeChain;
	nchead->left=NULL;
	nchead->t=NULL;
	ncp=nchead;
	charnum=0;
	for (i=0;i<255;i++) if (freq[i])
	{
		charnum++;
		btp=new BinaryTree;	//新建树结点
		btp->f=freq[i];
		btp->c=i;
		btp->parent=btp->lchild=btp->rchild=NULL;
		ncp->right=new NodeChain;		//新建钩子结点
		ncp->right->t=btp;
		ncp->right->left=ncp;
		ncp=ncp->right;
	}
	ncp->right=NULL;
	//构造huffman树
	NodeChain *min1,*min2,*p;	//最小结点为min1，次小结点为min2
	BinaryTree *temp;
	for (i=0;i<charnum-1;i++)
	{
		//找到两个最小的结点
		min1=min2=NULL;		
		p=nchead;
		while (p=p->right)	if ((min1==NULL)||(p->t->f < min1->t->f)) min1=p;
		p=nchead;
		while (p=p->right)	if ((p!=min1)&&((min2==NULL)||(p->t->f < min2->t->f))) min2=p;
		//利用两个最小结点生成树
		temp=new BinaryTree;		//新建父结点,连结两子结点
		temp->c=0;
		temp->f=min1->t->f + min2->t->f;
		temp->lchild=min1->t;
		temp->rchild=min2->t;
		min1->t->parent=min2->t->parent=temp;
		min1->t=temp;		//将min1改为指向生成的新结点
		if (min2->right) {min2->right->left=min2->left; min2->left->right=min2->right;}	//删除min2结点
		else min2->left->right=NULL;
		delete min2;
	}
	root=temp;		//huffman树生成完毕
	//先序遍历huffman树，建立huffman编码表
	for (i=0;i<256;i++) hc_exist[i]=false;		//初始化huffman编码表
	traverse("",root);
}

void HuffmanTree::traverse(string code,BinaryTree *node)
{
	if (node->c) 
	{
		hc_exist[node->c]=true;
		hc[node->c]=code;
	}
	else 
	{
		traverse(code+"0",node->lchild);
		traverse(code+"1",node->rchild);
	}
}

string HuffmanTree::code(string s)
{
	int i;
	string temps;
	temps="";
	for (i=0;i<s.length();i++)
		temps+=hc[s[i]];
	return temps;
}

string HuffmanTree::decode(string s)
{
	int i;
	string temps="";
	btp=root;
	for (i=0;i<s.length();i++)
	{
		if (s[i]=='0') btp=btp->lchild;
		if (s[i]=='1') btp=btp->rchild;
		if (btp->c) {temps=temps+btp->c; btp=root;}
	}
	return temps;
}

string HuffmanTree::dict(char s)
{
	if (hc_exist[s]) return hc[s];
	else return "";
}

int HuffmanTree::save(string path)
{
	ofstream outfile(path.data());
	if (outfile.is_open())
	{
		outfile.clear();
		int i;
		for (i=0;i<256;i++)
			if (hc_exist[i]) outfile<<char(i)<<endl<<hc[i]<<endl;
		outfile.close();
		return 1;
	}
	else return 0;
}
void HuffmanTree::clear()
{
	destorytree(root);
	root=NULL;
	ncp=nchead;
	while (ncp=ncp->right) delete ncp->left;
	nchead=NULL;
	int i;
	for (i=0;i<256;i++)
	{
		hc_exist[i]=false;
		freq[i]=0;
	}
}
void HuffmanTree::destorytree(BinaryTree *node)
{
	if (node)
	{
		destorytree(node->lchild);
		destorytree(node->rchild);
		delete node;
	}
}
int HuffmanTree::load(string path)
{
	ifstream infile(path.data());
	if (infile.is_open())
	{
		int i;
		char a;
		string temps;
		clear();	//初始化对象
		if (root) delete root;	//删除旧的头结点
		root=new BinaryTree;	//新建头结点
		root->c=0;
		root->lchild=root->rchild=NULL;
		while (!infile.eof())	//读入字典并生成huffman树
		{
			getline(infile,temps);
			a=temps[0];
			if (hc_exist[a]) break;
			hc_exist[a]=true;
			getline(infile,hc[a]);
			btp=root;
			for (i=0;i<hc[a].length();i++)	//根据读入的字典条目创建当前结点
				if (hc[a][i]=='0') 
				{
					if (btp->lchild) btp=btp->lchild;	//如果存在左子树则访问
					else		//不存在则建立
					{
						btp->lchild=new BinaryTree;
						btp->lchild->c=0;
						btp->lchild->f=0;
						btp->lchild->lchild=NULL;
						btp->lchild->rchild=NULL;
						btp->lchild->parent=btp;
						btp=btp->lchild;
					}
				}
				else
				{
					if (btp->rchild) btp=btp->rchild;	//如果存在右子树则访问
					else		//不存在则建立
					{
						btp->rchild=new BinaryTree;
						btp->rchild->c=0;
						btp->rchild->f=0;
						btp->rchild->lchild=NULL;
						btp->rchild->rchild=NULL;
						btp->rchild->parent=btp;
						btp=btp->rchild;
					}
				}
			btp->c=a;
		}
		return 1;
	}
	else return 0;
}