huffmantree.cpp

huffman树的基本实现. 利用读取TXT文件统计产生huffman树,从而对TXT文件进行压缩和解压.

#include "HuffmanTree.h"
#include <fstream>
#include <iostream>
using namespace std;

const int MaxNum=120;
void Select(Node h[],int &i1,int &i2,int k)
{
	for(int i=0;i<k;i++)
	{
		if(h[i].parent<0)
		{
			i1=i;
			break;
		}
	}
	for(i=0;i<k;i++)
	{
		if(h[i].parent<0&&i1!=i)
		{
			i2=i;
			break;
		}
	}
	for(i=0;i<k;i++)
	{
		if(h[i].parent<0&&h[i1].weight>h[i].weight&&i2!=i)
		{
			i1=i;
		}
	}
	for(i=0;i<k;i++)
	{
		if(h[i].parent<0&&h[i2].weight>h[i].weight&&i1!=i)
		{
			i2=i;
		}
	}
}
HuffmanTree::HuffmanTree()
{
	for(int i=0;i<110;i++)
	{
		Huff[i].weight=0;
	}
	top=-1;
	for(i=0;i<20;i++)
	{
		stack[i]=-1;
	}
	n=0;
}
void HuffmanTree::Init()
{
	int i=0;
	int i1,i2;
	bool flag;
	char w[MaxNum];
	int m=0;
	ifstream ifile;
	ifile.open("sourcefile.txt",ios::in);
	if(!ifile)
	{
		cerr<<"Error while openin' file!\n";
		exit(1);
	}
	while(!ifile.eof())
	{
		ifile.get(w[m]);
		m++;
	}
	ifile.close();
	w[m-1]='\0';
	cout<<w<<endl;
	while(w[i])
	{
		flag=false;
		for(int j=0;j<n;j++)
		{
			if(Huff[j].character==w[i])
			{
				flag=true;
				Huff[j].weight++;
				break;
			}
		}
		if(flag==false)
		{
			Huff[n].character=w[i];
			Huff[n].weight++;
			n++;
		}
		i++;
	}
	for(int j=0;j<n*2-1;j++)
	{
		Huff[j].parent=-1;
		Huff[j].lchild=-1;
		Huff[j].rchild=-1;
	}
	for(int k=n;k<n*2-1;k++)
	{
		Select(Huff,i1,i2,k);
		Huff[k].lchild=i1;
		Huff[k].rchild=i2;
		Huff[i1].parent=Huff[i2].parent=k;
		Huff[k].weight=Huff[i1].weight+Huff[i2].weight;
		Huff[k].character='\0';
	}
}
void HuffmanTree::Encode(int root)
{
	if(Huff[root].character!='\0')
	{
		ofstream ofile;
		ofile.open("HuffCode.txt",ios::app);
		int i=0;
		ofile.put(Huff[root].character);
		while(stack[i]!=-1)
		{
			ofile<<stack[i];
			i++;
		}
		ofile<<'\n';
		ofile.close();
		return;
	}
	else
	{
		top++;
		stack[top]=0;
		Encode(Huff[root].lchild);
		stack[top]=1;
		Encode(Huff[root].rchild);
		stack[top]=-1;
		top--;
	}
}
void HuffmanTree::PrintHuffmanTreeCode()
{
	ifstream ifile;
	ifile.open("HuffCode.txt");
	char character[20];
	while(!ifile.eof())
	{
		ifile.getline(character,20,'\n');
		cout<<character<<endl;
	}
	ifile.close();
}
void HuffmanTree::Compress()
{
	char character;
	char temp;
	char s[10]={'\0'};
	ofstream ofile;
	ofile.open("CodeFile.txt",ios::app);
	ifstream ifile1;
	ifile1.open("sourcefile.txt");
	if(!ifile1)
	{
		cerr<<"Can't open file!\n";
		exit(1);
	}
	while(!ifile1.eof())
	{
		ifile1.get(character);
		ifstream ifile2;
		ifile2.open("HuffCode.txt");
		while(!ifile2.eof())
		{
			ifile2.get(temp);
			if(temp==character)
			{
				ifile2.getline(s,10,'\n');
				break;
			}
		}
		for(int i=0;s[i]!='\0';i++)
		{
			ofile.put(s[i]);
		}
		for(i=0;i<10;i++)
		{
			s[i]='\0';
		}
		ifile2.close();
	}
	ofile.close();
	ifile1.close();
}
void HuffmanTree::Decode()
{
	ifstream ifile;
	ifile.open("CodeFile.txt");
	ofstream ofile;
	ofile.open("TextFile.txt",ios::app);
	int root=n*2-2;
	char path;
	if(!ifile)
	{
		cerr<<"Erroe while opennin' the file!\n";
		exit(1);
	}
	while(!ifile.eof())
	{
		if(Huff[root].character!='\0')
		{
			ofile.put(Huff[root].character);
			root=n*2-2;
		}
		else
		{
			ifile.get(path);
			if(path=='0')
				root=Huff[root].lchild;
			else
				root=Huff[root].rchild;
		}
	}
	ifile.close();
	ofile.close();
}
void HuffmanTree::Print()
{
	ifstream ifile;
	ifile.open("CodeFile.txt");
	char character[50];
	while(!ifile.eof())
	{
		for(int i=0;i<50&&!ifile.eof();i++)
		{
			ifile.get(character[i]);
			cout<<character[i];
		}
		cout<<endl;
	}
	ifile.close();
}
void HuffmanTree::TreePrint()
{
	int front;
	int rear;
	int root=2*n-2;
	front=rear=0;
	int Q[100];
	if(Huff[root].lchild==0)return;
	Q[++rear]=root;
	int i=0;
	while(front!=rear)
	{
		root=Q[++front];
		cout<<Huff[root].character<<Huff[root].weight<<' ';
		if(Huff[root].lchild!=-1)Q[++rear]=Huff[root].lchild;
		if(Huff[root].rchild!=-1)Q[++rear]=Huff[root].rchild;
		i++;
		if(i%2==1)
			cout<<endl;
	}
}