huffman.cpp

huffman编码实现

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <cmath>
#include <queue>

using namespace std;

struct HTNode
{
	int data;
	char ch;
	HTNode *lchild,*rchild,*parent;
};

struct List
{
	HTNode *d;
	List *link;
};

struct Code
{
        char ch;
        string str;
        Code *link;
};

int size;

HTNode* Min(List* &Head)
{//取链表中最小的那个元素，返回其地址，并在该链表中删去该元素。。。
	List *min,*temp,*cur,*c;
	min = temp = Head->link;
	c = cur = Head;
	while(temp != NULL)
	{
		if(temp->d->data < min->d->data)
		{
			min = temp;
			c = cur;
		}
		cur = temp;
		temp = temp->link;
	}
	c->link = min->link;
	return min->d;
}

void ReadIn(List* &Head)
{//数据的输入
	fstream fin("Data.in",ios::in);
	char ch;
	fin>>size;
	fin.get(ch);
	for(int i=0; i<size; i++)
	{
		List * temp = new List; 
		temp->d = new HTNode;//why?
		fin.get(temp->d->ch);
	//	temp->d->ch=ch;
	//	temp->d->data=d;
	//	fin>>temp->d->ch;
		fin>>temp->d->data;		
		fin.get(ch);//读入回车符。。。。。
	//	cout<<temp->d->ch<<' '<<temp->d->data<<endl;//exceed
		temp->d->lchild = temp->d->rchild = temp->d->parent = NULL;
		temp->link = Head->link;
		Head->link = temp;
	}
	fin.close();
	return ;
}

void CreateHT(HTNode* &HT, List* &Head)
{
	HTNode *first,*second;
//建树过程：
	int t((size-1)*2);
	while(t > 1)
	{
		first = Min(Head);
		t--;
		second = Min(Head);
 		t--;
		HTNode *temp = new HTNode;
		temp->data = first->data+second->data;
		temp->lchild = first;
		temp->rchild = second;
		first->parent = second->parent = temp;
		temp->parent = NULL;
		//插入新产生的节点
		List *n = new List;
		n->d = temp;
		n->link = Head->link;
		Head->link = n;
	}
	HT = Min(Head);
//	List * temp;
//	while(Head->link->link)
//	{	
//		temp = Head->link;
//		Head->link = temp->link;
//		delete temp;
//	}
//	Head->link = NULL;
}

void CreateHT(HTNode* & HT)
{//建立huffman树。。。。
	List *Node = new List;
	Node->link = NULL;
    ReadIn(Node);
	CreateHT(HT,Node);
}

//void PreOrder(fstream &out,HTNode* root,string str)//输出形式
string PreOrder(HTNode *root,Code* &code,string str,char &ch)
{
        string str1("");
        if( !root->rchild && !root->lchild )
        {
        //		out<<root->data<<' '<<str<<endl;
        		ch = root->ch;
				Code *temp = new Code;
                temp->ch = ch;
                temp->str =  str;
                temp->link = code->link;
                code->link = temp;
                return str;
        }
        if( root->lchild )
        {
                str1 = str+'0';
        //        PreOrder(out,root->lchild,str1);
                PreOrder(root->lchild,code,str1,ch);
        }
        if( root->rchild )
        {
                str1 = str+'1';
        //        PreOrder(out,root->rchild,str1);
                PreOrder(root->rchild,code,str1,ch);
        }
        return "";
}
void Coding(HTNode* root,Code* &code)
{//提取每个字符的huffman码。
 //       fstream fout("hfmtree.txt",ios::out);
 //       string str = "";
 //       PreOrder(fout,root,str);
 //       fout.close();

        char ch;
        string str;
        while((str = PreOrder(root,code,"",ch)) != "")
        {
                Code *temp = new Code;
                temp->ch = ch;
                temp->str =  str;
                temp->link = code->link;
                code->link = temp;
        }
}

string FindCode(char ch,Code * code)
{
        Code * cur = new Code;
        cur = code->link;
        while(ch != cur->ch && cur->link)
                cur = cur->link;
        return cur->str;
}

void Encoding(Code * code)
{//把正文编译成代码
        fstream fin("ToBeTran.txt",ios::in);
        fstream fout("CodeFile.txt",ios::out);
        char ch[80];
        while(fin.getline(ch,80))
                for(int i=0; ch[i]!='\0'; i++)
                        fout<<FindCode(ch[i],code);
        fin.close();
        fout.close();
        return ;
}


void Decoding(HTNode *HT)
{//把代码翻译成文本
        fstream fin("CodeFile.txt",ios::in);
        fstream fout("TextFile.txt",ios::out);
        char c;
        HTNode *cur = HT;
        while(fin>>c)
        {

                if( c == '0' )
                        cur = cur->lchild;
                else
                        cur = cur->rchild;
                 if( !cur->lchild && !cur->rchild )
                {
                        fout<<cur->ch;
                        cur = HT;
                }   
		}
        fin.close();
        fout.close();
}

void PrintC()
{
        fstream fin("CodeFile.txt",ios::in);
        fstream fout("CodePrin.txt",ios::out);
		cout<<"正文的代码如下：\n";
        int cnt(0);
        char ch;
        while(fin>>ch)
        {
                fout<<ch;
                cout<<ch;
                cnt++;
                if( cnt == 50 )
                {
                        fout<<endl;
                        cout<<endl;
                }
        }
		cout<<endl;
        fin.close();
        fout.close();
        return ;
}

//GetDepth(HT,0,depth);//调用方式
bool GetDepth(HTNode * root, int temp,int & depth)
{
	if( depth < temp )
		depth = temp;
	if( root && root->data != ' ')
	{
		GetDepth(root->lchild,temp+1,depth);
		GetDepth(root->rchild,temp+1,depth);
		return true;
	}
	return false;

}

void Print1(ostream cout,HTNode * tree)
{
	/*
	A tree with no children should be output as X.
	A tree with left and right subtrees L and R should 
	be output as (L')X(R'), where L' and R' are the 
	representations of L and R.
		If L is empty, just output X(R').
		If R is empty, just output (L')X.
	//*/
	if( tree->lchild ) 
	{
		cout<<'(';
		Print1(cout,tree->lchild);
		cout<<')';
	}
	cout<<tree->data;
	if( tree->rchild ) 
	{
		cout<<'(';
		Print1(cout,tree->rchild);
		cout<<')';
	}
}

void Print(ostream fout,HTNode* tree,int length)
{

//	fstream fout("treeprint.txt",ios::out);
//#define cout ffout
	if( tree->data == ' ' )
	{
		fout<<"NULL\n\n";
		return ;
	}

	int width = pow(2,length+1);
	queue<HTNode*>node;
	queue<int>npos;
//	queue<int>temp;
	
	fout<<setw(width-1)<<setfill(' ')<<tree->data<<endl;
	fout<<setw(width-1)<<setfill(' ')<<'|'<<endl;
	node.push(tree);
	npos.push(width);
	int n1(1),n2(0),d(0),tt(0);
	while(!node.empty())
	{
		HTNode *n = node.front();node.pop();
		int tpos = npos.front();npos.pop();
		n1--;
		if( n->lchild )
		{
			fout<<setw(tpos-pow(2,length-d)-tt-1)<<setfill(' ')<<' ';
			fout<<setw(pow(2,length-d)-1)<<setfill('_')<<'_';
			tt = tpos;
			node.push(n->lchild);
			npos.push(tpos-pow(2,length-d)+1);
			n2++;
		}
		if( n->rchild )
		{
		//	if( tpos != tt ) 
			fout<<setw(tpos-tt-1)<<setfill(' ')<<' ';
			fout<<setw(pow(2,length-d)-1)<<setfill('_')<<'_';
			tt = tpos+pow(2,length-d);
			node.push(n->rchild);
			npos.push(tt+1);
			n2++; 
		}
		if( !n1 )
		{
			d++;
			fout<<endl;
			n1 = n2; n2 = 0; tt = 0;
			vector<HTNode*>tn;
			vector<int>tp;
			int temp(0);
			while(!node.empty())
			{
				tn.push_back(node.front());node.pop();
				tp.push_back(npos.front());npos.pop();
			}
			for(int i=0; i<n1; i++)
			{
				fout<<setw(tp[i]-temp-1)<<setfill(' ')<<'|';
				temp = tp[i];
			}
			fout<<endl;
			temp = 0;
			for(i=0; i<n1; i++)
			{
				fout<<setw(tp[i]-temp-1)<<setfill(' ')<<tn[i]->data;
				temp = tp[i];
			}
			fout<<endl;
			for(i=0; i<n1; i++)
			{
				node.push(tn[i]);
				npos.push(tp[i]);
			}
		}
	}
}

void PrintTree(HTNode * HT)
{//打印huffman树。。。。。。。。
	fstream fout("TreePrint.txt",ios::out);
	int depth(0);
	GetDepth(HT,0,depth);
	fout<<"huffman树的结构如下："<<endl;
	fout<<"1.括号形式："<<endl;
	Print1(fout,HT);
	fout<<endl;
	cout<<"huffman树的结构如下："<<endl;
	Print1(cout,HT);
	cout<<endl;
	fout<<"2.树形形式："<<endl;
	Print(fout,HT,depth);
	cout<<"由于树形结构比较大，不能在屏幕上演示，存放在'TreePrint.txt'文件中!"<<endl;
}

int main()
{
	HTNode *HT;
	CreateHT(HT);
    Code *code = new Code;
    code->link = NULL;
    Coding(HT,code);//提取每个字符的huffman码。存放到链表code中
	Encoding(code);//把正文编译成代码
    Decoding(HT);//把代码翻译成文本
    PrintC();//打印代码文件
    PrintTree(HT);//树形输出huffman树。。。。。。
	return 0;
}