test.cpp

霍夫曼的文件编码源代码

#include<iostream>
#include<fstream>
#include <string>
#include "minheap.h"
#include "binarytree.h"
#include "huffman.h"

template <class T>
BinaryTree<int> HuffmanTree(T a[], int n)
{//根据权重a[1：n]构造霍夫曼树
	//创建一个单节点数的数组
	Huffman<T> *w=new Huffman<T> [n+1];
	BinaryTree<int> z,zero;
	for(int i=1;i<=n;i++)
	{
		z.MakeTree(i,zero,zero);
		w[i].weight=a[i];
		w[i].tree=z;
	}

	//把数组变成一个最小堆
	MinHeap <Huffman<T> >H(1);
	H.Initialize(w,n,n);

	//将堆中的树不断合并
	Huffman<T> x,y;
	for(i=1;i<n;i++)
	{
		H.DeleteMin(x);
		H.DeleteMin(y);
		z.MakeTree(0,x.tree,y.tree);
		x.weight += y.weight;x.tree=z;
		H.Insert(x);
	}
	H.DeleteMin(x);//最后的树
	H.Deactivate();
	delete [] w;
	return x.tree;
}

void count(string file,int ch[])
{
	ifstream fin(file.c_str());
	if(!fin)
	{
		cerr<<"can not open"<<file<<endl;
		exit(1);
	}
	for(int i=1;i<110;i++)
		ch[i]=0;
	char k;
	while(!fin.eof())
	{
		fin.read(&k,1);
		ch[int(k)]++;
	}
}


void Code(BinaryTree<int> c, int ch[])
{
	BinaryTreeNode<int> *t = c.root;
	int l = 0;//计数器
	char *code = new char [c.Height()];//创建一个字符数组，记录每个节点的值，左节点为0，右节点为1
	while(t) //从根节点到外节点从左到右遍历整个树，得到其霍夫曼编码
	{
		if(t->LeftChild)//遍历左子树
		{
			t = t->LeftChild;
			code[l] = '0';
			l++;
			//找到外节点
			if(t->LeftChild && t->LeftChild->data)
			{//先得出左孩子编码
				code[l] = '0';
				int m = t->LeftChild->data;
				//输出其编码
				if( m == 10 )
					cout << '\\' << "n\t" << ch[m] << "\t";
				else
					cout << char(m) << " \t" << ch[m] << "\t";
				for(int i = 0; i <= l; i++)
					cout << code[i];
				cout << endl;
				//将该节点及其data域置0
				t->LeftChild->data = 0;
				t->LeftChild = 0;
				t = c.root;//返回根节点重新遍历
				l = 0;
			}
			else if(!t->LeftChild && t->RightChild && t->RightChild->data)
			{//如果右孩子是外节点，得出右孩子编码
				code[l] = '1';
				int m = t->RightChild->data;
				if( m == 10 )
					cout << '\\' << "n\t" << ch[m] << "\t";
				else
					cout << char(m) << "\t" << ch[m] << "\t";
				for(int i = 0; i <= l; i++)
					cout << code[i];
				cout << endl;
				t->RightChild->data = 0;
				t->RightChild = 0;
				t = c.root;
				l = 0;
			}
		}
		else if(!t->LeftChild && t->RightChild)//遍历右子树
		{
			t = t->RightChild;
			code[l] = '1';
			l++;
			if(t->LeftChild && t->LeftChild->data)
			{
				code[l] = '0';
				int m = t->LeftChild->data;
				if( m == 10 )
					cout << '\\' 
					<< "n\t" << ch[m] << "\t";
				else
					cout << char(m) << "\t" << ch[m] << "\t";
				for(int i = 0; i <= l; i++)
					cout << code[i];
				cout << endl;
				t->LeftChild->data = 0;
				t->LeftChild = 0;
				t = c.root;
				l = 0;
			}
			else if(!t->LeftChild && t->RightChild && t->RightChild->data)
			{
				code[l] = '1';
				int m = t->RightChild->data;
				if( m == 10 )
					cout << '\\' << "n\t" << ch[m] << "\t";
				else
					cout << char(m) << " \t" << ch[m] << "\t";
				for(int i = 0; i <= l; i++)
					cout << code[i];
				cout << endl;
				t->RightChild->data = 0;
				t->RightChild = 0;
				t = c.root;
				l = 0;
			}
		}
		else//根节点左右子树全置空
			break;
		if(t->LeftChild && !t->LeftChild->LeftChild && !t->LeftChild->RightChild)
		{//左子树置0
			t->LeftChild = 0;
			t = c.root;
			l = 0;
		}
		else if(!t->LeftChild && t->RightChild && !t->RightChild->LeftChild && !t->RightChild->RightChild)
		{//右子树置0
			t->RightChild = 0;
			t = c.root;
			l = 0;
		}
	}
	c.Delete();//删除该树/**/
}

void main()
{
int ch[110];
	count("binarytree.txt",ch);
	BinaryTree<int> c =	HuffmanTree(ch, 110);
	cout << "Char " << "cout  " << "Code\t" << endl;
	Code(c,ch);	/**/
}