main.cpp

哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <iomanip>

using namespace std;


typedef char ElemType; 

typedef struct 
{ 
	ElemType elem; 
	unsigned int m_weight; 
	unsigned int parent,lchild,rchild;   // the weight of the node
}HTNode,*HuffmanTree; 
double lenSource,lenCode;
typedef struct weight 
{ 
	char elem; 
	unsigned int m_weight; 
}Weight; // save the information of the symbolizes;

typedef char** HuffmanCode;

typedef struct dtree
{
	ElemType elem;
	dtree* Left,*Right;
} DecodeTree;     

map<char, int>  m_Weight;
map<char,char*> m_table;
string fileName;
int Count;

void		HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);	 //create huffman code
void		Select(HuffmanTree,int,int *,int *);						 //select two node which has lowest weight
void		OutputHuffmanCode(HuffmanTree,HuffmanCode,int);				 //
void		CreateHuffmantable(HuffmanTree,HuffmanCode,int);			 //
void		EncodeFile(void);					
void		ReadFile(void);												 //read input file
int			GetChoice(void);			
DecodeTree* ReadTable(void);											 //read huffman table create huffman tree (for decode)
void		DecodeFile(DecodeTree* const Root);	
void		DeleteTree(DecodeTree* root);								 //release memory				

int main(void) 
{ 
    cout<<"********************************************************************\n"
        <<"*****        A program of huffman code.                       ******\n"
        <<"*****           author: xiangxijia                            ******\n"
        <<"*****           Date  : 2008-11-12                            ******\n"    
        <<"********************************************************************\n";                                                                            
    int choice;
    while(choice = GetChoice()){
		if(choice == 1 ){
			HuffmanTree HT; 
			HuffmanCode HC; 
			Weight *w; 
			char c; // the symbolizes; 
			int i,n; // the number of elements; 
			int wei; // the weight of a element; 
			ReadFile();
			n = Count;
			i = 0;
			w=(Weight *)malloc(n*sizeof(Weight));
			map<char,int>::iterator it;
			it = m_Weight.begin();
			while(it != m_Weight.end())
			{
				w[i].elem = it->first;
				w[i].m_weight = it->second;
				i++;
				it++;           
			} 
			
			HuffmanCoding(&HT,&HC,w,n); 
			CreateHuffmantable(HT,HC,n);
			OutputHuffmanCode(HT,HC,n); 
			EncodeFile();
			cout<<"The compress rate is(%): "<<(double)(lenCode*100/lenSource)<<endl;
			free(w);
			free(HT);
			free(HC);
			m_Weight.clear();
			
		}
		else if(choice == 2 )
		{
			DecodeTree * const Root =  ReadTable();
			DecodeFile(Root);
			DeleteTree(Root);
		}
		else if(choice == 0)
		{
			return 1;
		}
	}
	//	system("pause");
	//	return 1; 
	
} 



void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n) 
{ 
	int i,m,s1,s2,start,c,f; 
	char *cd; 
	HuffmanTree p; 
	if(n<=1) 
		return; 
	
	m=2*n-1; 
	(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
	for(i=1;i<=n;++i) 
	{ 
		(*HT)[i].elem=w[i-1].elem; 
		(*HT)[i].m_weight=w[i-1].m_weight; 
		(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
	} 
	
	for(;i<=m;++i) 
	{ 
		(*HT)[i].elem='0'; 
		(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
	} 
	
	for(i=n+1;i<=m;++i) 
	{ 
		Select(*HT,i-1,&s1,&s2); 
		(*HT)[s1].parent=i;(*HT)[s2].parent=i; 
		(*HT)[i].lchild=s1;(*HT)[i].rchild=s2; 
		(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight; 
	} 
	
	(*HC)=(HuffmanCode)malloc(n*sizeof(char*)); 
	cd=(char *)malloc(n*sizeof(char)); 
	cd[n-1]='\0'; 
	for(i=1;i<=n;++i) 
	{ 
		start=n-1; 
		for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent) 
		{ 
			if((*HT)[f].lchild==c) cd[--start]='0'; 
			else cd[--start]='1'; 
		} 
		
		(*HC)[i]=(char *)malloc((n-start)*sizeof(char)); 
		strcpy((*HC)[i],&cd[start]); 
	} 
} 


void Select(HuffmanTree HT,int n,int *s1,int *s2) 
{ 
	int i; 
	(*s1)=(*s2)=0; 
	for(i=1;i<=n;i++) 
	{ 
		if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0) 
		{ 
			if(HT[i].m_weight<HT[(*s1)].m_weight) 
			{ 
				(*s2)=(*s1); 
				(*s1)=i; 
			} 
			else (*s2)=i; 
			
		} 
		
		if(((*s1)==0||(*s2)==0)&&HT[i].parent==0) 
		{ 
			if((*s1)==0) (*s1)=i; 
			else if((*s2)==0) 
			{ 
				if(HT[i].m_weight<HT[(*s1)].m_weight) 
				{ 
					(*s2)=(*s1); 
					(*s1)=i; 
				} 
				else (*s2)=i; 
			} // end of else if 
		} // end of if 
	} // end of for 
	
	if((*s1)>(*s2)) 
	{ 
		i=(*s1); 
		(*s1)=(*s2); 
		(*s2)=i; 
	} 
	return; 
} 


void CreateHuffmantable(HuffmanTree HT,HuffmanCode HC,int n)
{
	ofstream out("table.txt");
	for(int i= 1;i<=n;i++)
	{
		m_table[HT[i].elem] = HC[i];
		out<<HT[i].elem<<" "<<HC[i]<<endl;
	}
	out.close();
	
}

void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) 
{ 
	int i; 
	cout<<"\nElement---Weight---Huffman code:\n"; 
	for(i=1;i<=n;i++) 
		cout<<HT[i].elem<<setw(5)<<HT[i].m_weight<<"     "<<HC[i]<<endl;
	
		/*
		cout<<"+++++++++++++++++++++++++++++++++++++++++++++++++++++++\n";
		map<char,char*>::iterator it;
		it = m_table.begin();
		while(it != m_table.end())
		{
		cout<<it->first<<" :"<<it->second<<endl;
		it++;
		}	                  
		
	*/
	
}

void EncodeFile(void)
{
	ofstream out("out.txt");
	ifstream in(fileName.c_str());
	cout<<"\nThe File afther Encode:\n";
	string strLine;
	while(getline(in,strLine))
	{
		for(int i=0;i<strLine.length();i++)
        {
            if(strLine[i] == ' '){
				cout<<m_table['$'];
				out<<m_table['$'];
				lenCode += strlen(m_table['$']);
            }
            else
            {
				cout<<m_table[strLine[i]];
				out<<m_table[strLine[i]];
				lenCode += strlen(m_table[strLine[i]]);
			}
			
        }
		cout<<m_table['#'];
		out<<m_table['#'];
		lenCode += strlen(m_table['#']);
		
	}
	cout<<endl;
	out<<endl;
	in.close();
	out.close();     
}

void ReadFile(void)
{
	
	cout<<"input the file Name:\n";
	cin>>fileName;
	
	ifstream in;
	in.open(fileName.c_str(),ios_base::in);
	while(!in.is_open())
	{
		cout<<"File not Exist,please input the file name again!:\n";
		cin>>fileName;
		in.open(fileName.c_str(),ios_base::in);
	}
	
	
	m_Weight.clear();
	Count = 0;
	
	string strLine;
	while(getline(in,strLine))
	{
		for(int i=0;i<strLine.length();i++)
        {
            lenSource += 8;
            if(strLine[i] == ' ')
				m_Weight['$']++;
            else
				m_Weight[strLine[i]]++;
        }
        lenSource += 8;
		m_Weight['#']++;   //'#' stand for Endl
		
	}
	
	map<char,int>::iterator it;
	it = m_Weight.begin();
	while(it != m_Weight.end())
	{
		//	cout<<it->first<<":"<<it->second<<endl;
		it++;
		Count++;
	}
	in.close();
	
}
int GetChoice(void)
{
	cout<<"@input your choice 1 for Encode, 2 for Decode, 0 for Exit:\n";
	int i;
	cin>>i;
	return i;
}
DecodeTree* ReadTable() 	/*read table & create huffman tree*/
{
	
	cout<<"input the file Name(huffman Table):\n";
	cin>>fileName;
	ifstream in;
	in.open(fileName.c_str(),ios_base::in);
	while(!in.is_open())
	{
		cout<<"File not Exist,please input the file name again!:\n";
		cin>>fileName;
		in.open(fileName.c_str(),ios_base::in);
	}
	char ch;
	string strCode;
    DecodeTree* const Root = new DecodeTree;
	Root->Left = NULL;
	Root->Right = NULL;
	Root->elem = '@';
	while(in>>ch>>strCode)
	{
		//cout<<ch<<":"<<strCode<<endl;
		DecodeTree * father = Root;
		int i=0;
		for(;i<strCode.length()-1;i++)
        {
			if(strCode[i] == '0')
			{
				if(father->Left == NULL)
				{
					DecodeTree* node = new DecodeTree;
					node->Left = NULL;
					node->Right = NULL;
					node->elem = '@';
					father->Left = node;
					father = node;
				}
				else
				{
					father = father->Left;
				}
			}
			else if(strCode[i] == '1')
			{
				if(father->Right == NULL)
				{
					DecodeTree* node = new DecodeTree;
					node->Left = NULL;
					node->Right = NULL;
					node->elem = '@';
					father->Right = node;
					father = node;
				}
				else
				{
					father = father->Right;
				}
			}
			
        }
        if(strCode[i] == '0')
        {
            if(father->Left == NULL)
            {
				DecodeTree* node = new DecodeTree;
				node->Left = NULL;
				node->Right = NULL;
				node->elem = ch;
				father->Left = node;
				father = node;               
            }
            else
            {
                father->Left->elem = ch;
            }
        }
        else if(strCode[i] == '1')
        {
			if(father->Right == NULL)
            {
				DecodeTree* node = new DecodeTree;
				node->Left = NULL;
				node->Right = NULL;
				node->elem = ch;
				father->Right = node;
				father = node;               
            }
            else
            {
                father->Right->elem = ch;
            }
        }
		
	}
	
	
    cout<<"Read table & create decode tree finished!\n";
    in.close();
    return Root;
	
}


void DecodeFile(DecodeTree* const Root)
{
    cout<<"input the file Name(File to Decode):\n";
	cin>>fileName;
	ifstream in;
	ofstream out("DecodedFile.txt");
	in.open(fileName.c_str(),ios_base::in);
	while(!in.is_open())
	{
		cout<<"File not Exist,please input the file name again!:\n";
		cin>>fileName;
		in.open(fileName.c_str(),ios_base::in);
	}
	char ch;
	DecodeTree * father = Root;
	while(in>>ch)
    {
		if(ch == '0')
		{
			
			father = father->Left;
			if((father->Left == NULL)&&(father->Right == NULL))
			{
				if(father->elem == '#')
				{
					cout<<"\n";
					out<<"\n";
				}
				else if(father->elem == '$')
				{
					cout<<" ";
					out<<" ";
				}
				else
				{
					cout<<father->elem;
					out<<father->elem;
				}
                father = Root;
			}
		}
		else if(ch == '1')
		{
			father = father->Right;
			if((father->Left == NULL)&&(father->Right == NULL))
			{
                if(father->elem == '#')
				{
					cout<<"\n";
					out<<"\n";
				}
				else if(father->elem == '$')
				{
					cout<<" ";
					out<<" ";
				}
				else
				{
					cout<<father->elem;
					out<<father->elem;
				}
				father = Root;
			}
		}
    }
	in.close();
	out.close();
	
}
void DeleteTree(DecodeTree* root)
{

	if(root->Left == NULL && root->Right == NULL)
	{
		delete root;
		root = NULL;
		return;
	}
	if(root->Left != NULL)
		DeleteTree(root->Left);
	if(root->Right != NULL)
		DeleteTree(root->Right);
	delete root;
	root = NULL;
}