rar_file_with_haffman.h

哈夫曼编码在文件压缩中的应用。能用哈夫曼编码进行文件压缩~

#ifndef HAFUMAN_H
#define HAFUMAN_H
#include <iostream>
using namespace std;
int weight[256]={0};//用来存放这256个字符权值的数组.
const int MaxValue = 10000;//最大权值范围.
const int MaxBit =256;//最大位流符.
const int MaxN = 256;//最多字符数.
int N=0;//数来记录文件中出现的字符个数.
char char_a[256];//与权值对应的数组,用来存放字符.
struct HaffNode//以下为构构哈夫曼编码的过程.
{
    int weight;//权值.
    int flag;//标志符,用来观测此字符是否已纳入哈夫曼树中.
    int parent;
    int LeftChild;
    int RightChild;
};

struct Code
{
    int bit[MaxBit];//该点,对应的编码.
    int start;
    int weight;
};
int Find_usefull_Number(int weight[],int i)//用来从weight[]中找到权值不为0(即在文件中出现的字符).
{
    for(;i<256;i++)
    {
        if(weight[i]>0)
        {
            return i;
        }
    }
	
}
void Haffman(int weight[],int n,HaffNode haffTree[])//哈夫曼建码过程.
{
    int i,j,m1,m2,x1,x2,q=0,w=0;
    for(i=0;i<2*n-1;i++)
    {
        if(i<n)
        {
            q=Find_usefull_Number(weight,q);//一一找出weight[]中的正权值(即文件中出现了的字符..
            haffTree[i].weight=weight[q];//建立函数映射.存入字符.
            char_a[w++]=q;
            q++;
        }
        else
        {
            haffTree[i].weight=0;
        }
        haffTree[i].parent=0;
        haffTree[i].flag=0;
        haffTree[i].LeftChild=-1;
        haffTree[i].RightChild=-1;
    }
    for(i=0;i<n-1;i++)
    {
        m1=m2=MaxValue;
        x1=x2=0;
        for(j=0;j<n+i;j++)
        {
            if(haffTree[j].weight<m1&&haffTree[j].flag==0)
            {
                m2=m1;
                x2=x1;
                m1=haffTree[j].weight;
                x1=j;
            }
            else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
            {
                m2=haffTree[j].weight;
                x2=j;
            }
        }
        haffTree[x1].parent=n+i;
        haffTree[x2].parent=n+i;
		
        haffTree[x1].flag=1;
        haffTree[x2].flag=1;
		
        haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
		
        haffTree[n+i].LeftChild=x1;
        haffTree[n+i].RightChild=x2;
    }
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
{
    Code *cd =new Code;
    int child,parent;
    int i,j;
    for(i=0;i<n;i++)
    {
        cd->start=n-1;
        cd->weight=haffTree[i].weight;
        child=i;
        parent=haffTree[child].parent;
        while(parent!=0)
        {
            if(haffTree[parent].LeftChild==child)
            {
                cd->bit[cd->start]=0;
            }
            else
            {
                cd->bit[cd->start]=1;
            }
            cd->start--;
            child=parent;
            parent=haffTree[child].parent;
        }
        for(j=cd->start+1;j<n;j++)
        {
            haffCode[i].bit[j]=cd->bit[j];
        }
        haffCode[i].start=cd->start;
        haffCode[i].weight=cd->weight;
    }
}

void get_the_rar_file()
{
	//ifstream ifs("/home/fly_just_now/Desktop/text.txt")
	ifstream ifs("f1.txt");
	if(!ifs)
	{
		cerr << "open error!"<<endl;
	}
	
	//char Temp[4] ;
	//ifs.read(Temp,4);
	//cout << Temp <<endl;
	while (ifs.good())//读取文件中的字符,并计算它们出现的权值.
	{
		char ch = 0;
		ifs.get(ch);
		//cout<<ch;
		weight[ch]++;//计算.
	}
	
	int i;
	for(i=0;i<256;i++)//统计出现了多少种字符.
	{
		if(weight[i]!=0)
		{
			N++;
		}
		//屏幕输出.
		/*if(char(i)=='\n'&&weight[i]!=0)
		{
        cout<<"\\n"<<" "<<weight[i]<<endl;
        N++;
		}
		else if(i==0&&weight[i]!=0)
		{
        cout<<"0"<<" ";
        cout<<weight[i]<<endl;
        N++;
		}
		else if(char(i)==' '&&weight[i]!=0)
		{
        cout<<"_"<<" "<<weight[i]<<endl;
        N++;
		}
		else if(weight[i]!=0)
		{
        cout<<char(i)<<" "<<weight[i]<<endl;
        N++;
    }*/
	}
	ifs.close();
}
void save_the_rar_ya(HaffNode *myHaffTree,Code *myHaffCode)//将哈夫曼压缩后的存入文件.
{
    int Switch(char char_in_char_a);
    ofstream ofs("rubish.txt");
	if(!ofs)
	{
		cerr << "open error"<<endl;
	}
	
    int i,j,count;
    char ch = 0,C='N';
    for(i=0;i<N;i++)//存入编码类信息.
    {
        if(char_a[i]=='\n')//依次存入字符,字符权值,字符哈夫曼开始点,哈夫曼编码.
        {
			ofs<<"nn"<<C;
        }//其之中用N分割开来.
        else
        {
			ofs<<char_a[i]<<C;
			
        }
        for(j=myHaffCode[i].start+1;j<N;j++)
            ofs<<myHaffCode[i].bit[j];
        ofs<<endl;
    }
    ifstream ifs("f1.txt");
	//ifstream ifs("/home/fly_just_now/Desktop/text.txt");
	if(!ifs)
	{
		cerr << "open error!"<<endl;
	}
	ofs<<"::";
	while (ifs.good())
	{
		ifs.get(ch);//对原文件中的每一个字符用哈曼码存入新文件中.
		count=Switch(ch);
		for(j=myHaffCode[count].start+1;j<N;j++)
		{
            ofs<<myHaffCode[count].bit[j];
		}
	}
    ifs.close( );
	ofs.close( );
	ofstream New("rar_new_file.txt");
	if(!New)
	{
		cerr << "open error"<<endl;
	}
	ifstream rub("rubish.txt");
	if(!rub)
	{
		cerr << "open error"<<endl;
	}
	char ch1=0,ch2=0;
	while(rub.good())
	{
		ch2=ch1;
		rub.get(ch1);
		New<<ch1;
		if(ch1==':'&&ch2==':')
		{
			int count=0,sum=0;
			while(rub.good())
			{
				rub.get(ch1);
				sum=sum+(ch1-48)*pow(2,count);
				count++;
				if(count==8)
				{
					New<<char(sum);
					//cout<<char(sum);
					count=0;
					sum=0;
				}
			}
			if(sum!=0)
			{
				New<<char(sum);
				//cout<<char(sum);
			}
			break;
		}
	}
	New.close();
	rub.close();
    
}
int Switch(char char_in_char_a)//找到此字符的位置.根据与myHaffCode[]的对应关系,从而找到对应的哈夫码编码.
{
    int i;
    for(i=0;i<N;i++)
    {
        if(char_a[i]==char_in_char_a)
        {
            return i;
        }
    }
}
#endif