huffman_alpha.cpp

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

//1.输入英文字母序列文件，编码输出二进制文件
//2.输入二进制文件，解码输出英文字母序列文件
#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;

	string source;
	int freq[256];	//字频表
	string hc[256];	//huffman编码表，词典
	void traverse(string code,BinaryTree *node);	//遍历huffman树，内部递归函数，只被build调用
public:
	void build(string s);		//从纯英文String生成Huffman树
	string code();				//以字符串形式返回Huffman编码
	string decode(string s);	//解码
}ht;
////////////////////////////////////
//test driver
////////////////////////////////////
void main()
{
	string userInput;
	cin>>userInput;
	ht.build(userInput);
	cout<<"huffman编码："<<ht.code()<<endl;
	cout<<"反向验证(解码)："<<ht.decode(ht.code())<<endl;
	if (ht.decode(ht.code())==userInput) cout<<"与用户输入一致，验证通过。"<<endl;
	else cout<<"与用户输入不一致，验证失败。"<<endl;
	cout<<"理论最大压缩比：1:"<<double(ht.code().length())/8*double(userInput.length())<<endl;
}

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

void HuffmanTree::build(string s)
{
	source=s;
	int i,charnum;
	for (i=0;i<256;i++) freq[i]=0;				//初始化字频表
	for (i=0;i<s.length();i++) freq[s[i]]++;	//统计字频
	//test cout
	cout<<"字频表初始化完成"<<endl;
	for (i=0;i<256;i++) if (freq[i]) cout<<"F("<<char(i)<<")="<<freq[i]<<endl;
	//--------
	//建立树结点链
	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;
	//test cout
	cout<<"结点链建立完成\n";
	cout<<"Charnum="<<charnum<<endl;
	ncp=nchead;
	while (ncp=ncp->right) cout<<ncp->t->c<<" = "<<ncp->t->f<<endl;
	cout<<"开始构造huffman树"<<endl;
	//---------
	//构造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;
		//test cout
		cout<<"第"<<i<<"次循环开始"<<endl;
		cout<<"min1="<<min1->t->f<<endl;
		cout<<"min2="<<min2->t->f<<endl;
		//--------
		//利用两个最小结点生成树
		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;
		//test cout
		cout<<"第"<<i<<"次循环结束，当前结点链："<<endl;
		ncp=nchead;
		while (ncp=ncp->right) cout<<ncp->t->f<<endl;	
		//-------
	}
	root=temp;		//huffman树生成完毕
	//test cout
	cout<<"huffman树建立完毕，根结点:"<<root->f<<endl;
	cout<<"遍历huffman树开始"<<endl;
	//---------
	//先序遍历huffman树，建立huffman编码表
	for (i=0;i<256;i++) hc[i]="";		//初始化huffman编码表
	traverse("",root);
}

void HuffmanTree::traverse(string code,BinaryTree *node)
{
	//test cout
	cout<<"Traverse: "<<code<<" / ";
	if (node->c) cout<<node->c; else cout<<"^";
	cout<<" / "<<node->f<<endl;
	//---------
	if (node->c) hc[node->c]=code;
	else 
	{
		traverse(code+"0",node->lchild);
		traverse(code+"1",node->rchild);
	}
}

string HuffmanTree::code()
{
	int i;
	string temps;
	temps="";
	for (i=0;i<source.length();i++)
		temps+=hc[source[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;
		else btp=btp->rchild;
		if (btp->c) {temps=temps+btp->c; btp=root;}
	}
	return temps;
}