huffman.cpp

Huffman编码

#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cmath>
using namespace std;
#include "Huffman.h"

void Initialize(wElem w[],int n)
{
     char* FileName=new char[128]; // 存放文件名的工作空间
 T:  cout<<"The source file stores in which file?"<<endl<<"Please input the file name(such as sourcefile.txt):"<<endl;
     cin>>FileName;
     ifstream hufInPut(FileName,ios::in);
	 
     if(!hufInPut)
	 {
		 cerr<<"file can not be opened"<<endl;
		 goto T;
	 }
     else
	 {
		 int hufNum=0;//统计字符个数的计数器。
		 char huff[1000];// 存放输入的字符串。
		 int i=0,t=1;
         hufInPut.getline(huff,1000); // 读入字符集大小 n 到 hufNum
		 while(huff[i]!='\0')
		 {
             hufNum++;
			 i++;
		 }
         cout<<"total number of char:"<<hufNum<<endl;
		 cout<<huff<<endl;
	     hufInPut.close();
	     char *s=huff;
	     int ch[256]={0};//统计各个字符的权值
	     while(*s!='\0')
		 {
		    ch[*s]++;
		    s++;
		 }
	     for(i=0;i<256;i++)
		 {
		     if(ch[i]!=0)
			 {	 
				 w[n].weight=ch[i];
                 w[n].ch=char(i);//将读入字符及其权值存入存储读取字符及权值的数组中。
		         n++;
				 cout<<setw(2)<<char(i)<<setw(8)<<"的频度是:"<<setiosflags(ios::left)<<setw(4)<<ch[i];
				 if(++t==5)
				 {
					 cout<<endl;
					 t=1;
				 }
			 }
		 }
	 }
}

void HuffmanBuilding(element huffTree[],wElem w[],int n)
{
	for(int i=0;i<2*n-1;i++)
	{
		huffTree[i].parent=-1;
        huffTree[i].lchild=-1;
		huffTree[i].rchild=-1;
	}
	for(i=0;i<n;i++)
		huffTree[i].weight=w[i].weight;
	for(int k=n;k<2*n-1;k++)
	{
		int i1,i2;
		i1=i2=0;
		int j=0;
		int m0,n0;
		m0=n0=0;
		for(i=0;i<k;i++)
		{	
			if(huffTree[i].parent==-1)
			{
				if(m0<n0)
				{
					int p=m0;
					m0=n0;
					n0=p;
					int q=i1;
					i1=i2;
					i2=q;
				}
				if(j==0)
				{
					m0=huffTree[i].weight;
					i1=i;
				}
				if(j==1)
				{
					n0=huffTree[i].weight;
					i2=i;
				}
				 else 
				 {
					 if(m0==n0&&huffTree[i].weight<n0)
					 {
                        n0=huffTree[i].weight;
					    i2=i;
					 }
				      else if(m0>n0&&huffTree[i].weight<=n0)
					  {
					     m0=n0;
					     n0=huffTree[i].weight;
					     i1=i2;
					     i2=i;
					  }
				       else if(m0>n0&&huffTree[i].weight<m0&&huffTree[i].weight>n0)
					   {
						   m0=huffTree[i].weight;
						   i1=i;
					   }
					   
				 }
				 j++;
			}
		}
	    huffTree[i1].parent =k;   // 标记 parent 
		huffTree[i1].ch=w[i1].ch;
        huffTree[i2].parent =k;   // 标记 parent
		huffTree[i2].ch=w[i2].ch;
        huffTree[k].lchild =i1;   // 标记左孩子
        huffTree[k].rchild =i2;   // 标记右孩子
        huffTree[k].weight =huffTree[i1].weight+huffTree[i2].weight; // 新结点的权值
		huffTree[k].ch=w[k].ch;
	}
	cout<<"每个结点的权重："<<endl;
	for(i=0;i<2*n-1;i++)
         cout<<huffTree[i].weight<<" ";
	 cout<<endl<<"每个结点的父结点："<<endl;;
	for(i=0;i<2*n-1;i++)
         cout<<huffTree[i].parent<<" ";
	cout<<endl<<"哈夫曼树建立成功"<<endl;
}
//**************************************************
// 哈夫曼编码函数的实现
//**************************************************
void HuffmanCoding(element huffTree[],HuffmanCode Hucode[],wElem w[],char b[],int n)
{
     char* cd=new char[n];         // 分配求编码的工作空间
     cd[n-1]='\0';               // 编码结束符
     int c=0;
     int f=0;
     for(int i=0;i<n;i++)       // 逐个字符求赫夫曼编码
	 {
         int start=n-1;            // 编码结束符位置
         for(c=i,f=huffTree[i].parent;f!=-1;c=f,f=huffTree[f].parent ) // 从叶子到根逆向求编码
		 {
             if(huffTree[f].lchild==c)
			 { 
                cd[--start]='0'; 
			 } 
               else 
			   { 
                  cd[--start]='1';
			   }
		}
        Hucode[i].ch = w[i].ch ;    // 复制字符
	    Hucode[i].hufCh = (char*)malloc((n-start)*sizeof(char)); // 为第 i 个字符编码分配空间
        strcpy(Hucode[i].hufCh,&cd[start]);              // 从 cd 复制编码到 Hucode
	 }
	 ofstream outfile("HuffCode.txt");
     if (outfile.fail())
         cerr<<"error"<<endl;
	 //写入列名称
	 outfile<<"字符\t"<<"数组编号\t"<<"权值\t"<<"编码"<<endl;
	 //保存信息到文件
	 for (i=0;i<n;i++)
	 {
		 outfile<<Hucode[i].ch<<"\t"<<i<<"\t"<<"\t"<<huffTree[i].weight<<"\t"<<Hucode[i].hufCh<<endl;
	 }
	 cout<<"各字符编码已成功写入HuffCode.txt中！"<<endl;
	 outfile.close();
         
     ifstream hufInPut2("Sourcefile.txt",ios::in);
	 char a;
	 i=0;
	 int j=0;
	 while(!hufInPut2.eof())
	 {
		i=0;
		hufInPut2.read(&a,sizeof(char));
		while(Hucode[i].hufCh)
		{		 
           if(Hucode[i].ch==a)
		   {
			   if(j==0)
				  strcpy(b,Hucode[i].hufCh);
				 else
					strcat(b,Hucode[i].hufCh);
				j++;
				break;
			}
			i++;
		}		
	}
	 cout<<"哈夫曼编码已成功写入Sourcefile.txt中！"<<endl;
}

//********************************************************************
// DeCoding的译码实现
//*******************************************************************
void Decode(element huffTree[],wElem w[],int n)
{
    int i=0,k=0;
    int j=2*n-2;      //表示从根结点开始往下搜索
    char* Code1;
 
    ifstream f1("CodeFile.txt");          //利用已建好的哈夫曼树进行译码
    if(f1.fail())         //文件打开失败
	{
          cout<<"请先编码！\n";
          return;
	}
    cout<<"经译码,原内容为:"<<endl;
    char ch;
    while(f1.get(ch))            
	{
        k++;                     //计算CodeFile.txt中代码长度
	}
    f1.close();  
 
    Code1=new char[k+1];
    ifstream f2("CodeFile.txt");
    k=0;
    while(f2.get(ch))
	{
       Code1[k]=ch;          //读取文件内容
       k++;
	}
    f2.close();                
    Code1[k-1]='\0';         //结束标志符
    if(huffTree==NULL)         //还未建哈夫曼树
	{
         cout<<"树尚不存在，请先编码!\n";
         return;
	}
    ofstream fo("TextFile.txt");         //将字符形式的编码文件写入文件TextFile.txt中
    while(Code1[i]!='\0')
	{
        if(Code1[i]=='0')
            j=huffTree[j].lchild;          //往左走
         else
            j=huffTree[j].rchild;         //往右走
         if(huffTree[j].rchild==-1)   //到达叶子结点
		 {
              cout<<w[j].ch;         //输出叶子结点对应的字符
			  fo<<w[j].ch;        //存入文件
              j=2*n-2;             //表示重新从根结点开始往下搜索        
		 }
         i++;
	}
    fo.close();
 
    cout<<"\n译码成功且已存到文件TextFile.txt中！\n";
}//Decode
void Printcode(char b[])
{
   cout<<"输出代码文件："<<endl;
   ofstream codefile("CodeFile.txt");
   codefile<<b;
   codefile.close();
   int j=0;
   while(b[j]=='0'||b[j]=='1')
   {
	  cout<<b[j];
	  j++;
	  if(j%50==0)
	  cout<<endl;
	}
    cout<<endl;
}

//////////////////////////////////////////////////////////////////////////////
//印哈夫曼树函数
//函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上

void TreePrinting(element huffTree[],int n)//中序遍历树来打印
{
	cout<<"series"<<"  "<<"character"<<"  "<<"lchild"<<"    "<<"rchild"<<"   "<<"parent"<<endl;
	for(int i=0;i<2*n-1;i++)
	{
		cout<<setw(2)<<i<<"         "<<setw(1)<<huffTree[i].ch<<"           "<<setw(2)<<huffTree[i].lchild<<"        "<<setw(2)
			<<huffTree[i].rchild<<"       "<<setw(2)<<huffTree[i].parent<<endl;
	}
}