编码_译码.cpp

这是哈夫曼编码译码的vc程序

#include<fstream.h>
#include<stdlib.h>
#include<string.h>
#define MaxSize  1000 
int m,n;//n为字符表中字符的个数
struct node{
	char ch;
	int  weight;
	node *next;
};
struct HTNode{
	 int weight;
	 int parent,lchild,rchild;
};
/////////////////////////////////////////////////
class HuffmanATree{
private:
	HTNode *HT;//哈夫曼树
	char **HC;//字母表代码
	char *LetterList;//字母表
	int  *LetterWeight;//字母权重
public:
	HuffmanATree(){};
	int NodeWeight();
	int Select(int,int*,int*);
	HuffmanCoding();//取得字母表的哈夫曼编码
	Translation(); //将原文译为代码 
	Retranslation(); //将代码译为文字
    ~HuffmanATree(){};
};
/////////////////////////////////////////////////
int HuffmanATree::NodeWeight()
{//统计权重；
	char str[100];
	cout<<"请输入将要译码的原文:"<<endl;
	cin.getline(str,100);	
    cout<<"<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>"<<endl;
    cout<<"原文是:"<<endl;
	cout<<str<<endl;
	ofstream outfile("f1.txt");
	if(!outfile)
	{cerr<<"open error!"<<endl; exit(1);}
	outfile<<str<<" ";	
	outfile.close();
	cout<<"原文已经存放入文件f1中!"<<endl;	
	node *NH,*p1,*p2,*q1;char*s;
    p1=NH=new node;
	for( s=str,m=1;*s!='\0';s++,m++)
	{		
		p2=new node;
		p2->ch=*s;p2->weight=1;p1->next=p2;
		p1->next=p2;p1=p2;p2->next=NULL;
	}
	for(p1=NH->next;p1!=NULL;p1=p1->next)
		for(q1=p1,p2=p1->next;p2!=NULL;p2=p2->next)
			if(p2->ch==p1->ch)
			{
				q1->next=p2->next;
				p1->weight++;
			}
			else q1=p2;
	 n=0;int i=0;
	for(p1=NH->next;p1!=NULL;p1=p1->next)
	{   //输出字符表和字符对应的权重;
		//cout<<p1->ch<<" "<<p1->weight<<endl;
		n++;
	}
	//cout<<n<<endl;
	LetterList=new char[n];
	LetterWeight=new int[n];
	for(p1=NH->next,i=0;p1!=NULL;p1=p1->next,i++)
	{
		*(LetterList+i)=p1->ch;
		*(LetterWeight+i)=p1->weight;
		//cout<<i<<" "<<*(LetterList+i);
	}
    /*for(i=0;i<n;i++)
		cout<<" "<<*(LetterList+i);//字符表被意外改变		
	cout<<endl;
	*/
	return 0;
}

HuffmanATree::Select(int k,int *s1,int *s2)
{
	int i,j;
	if(k<2) return -1;
	*s1=*s2=0;
	for(j=1;j<=k;j++)
	{
		if(HT[j].parent!=0) continue;
		if(*s1==0) *s1=j;
		else {*s2=j;break;}
	}
	if(*s1==0||*s2==0) return -1;
	if(HT[*s1].weight>HT[*s2].weight)
	{
		i=*s1;*s1=*s2;*s2=i;
	}
	for(i=j+1;i<=k;i++)
	{
		if(HT[i].parent!=0) continue;
		if(HT[i].weight<HT[*s1].weight)
		{
			*s2=*s1;*s1=i;
		}
		else
			if(HT[i].weight<HT[*s2].weight)
				*s2=i;
	}
	return 0;
}
HuffmanATree::HuffmanCoding()
{//取得字母表的哈夫曼编码
	if(n<=1) 
	{cout<<"error";exit(1);}
	int m=n+n-1;
	HT=new HTNode[MaxSize];//这里能否用动态
    HTNode *p;int i;
	for(p=HT+1,i=1;i<=n+1;i++,++p,++LetterWeight)		
	{p->weight=*LetterWeight;p->parent=p->lchild=p->rchild=0;}
	for(;i<=m+1;i++,++p)    
	{p->weight=0;p->parent=p->lchild=p->rchild=0;}
	//以上为初始化HT
	for(i=n+1;i<=m;++i){
		int s1,s2; 
		Select(i-1,&s1,&s2);
		HT[s1].parent=i;HT[s2].parent=i;
		HT[i].lchild=s1;HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
		HT[i].parent=0;
	}//以上为构造HT的终态
///////////////////////////////////////////////////////////
/*输出Huffman树结构	
    for(i=1;i<=n+n-1;i++)
		cout<<i<<" "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
*/
////////////////////////////////////////////////////////////
	HC=new char*[n+1];
	char *cd=new char[n];
	cd[n-1]='\0';
	for(i=1;i<=n;++i){
		int start =n-1;int c,f;
		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]=new char;
			strcpy(HC[i],&cd[start]);//将地址存入HC[i]
	}
	delete []cd;//以上为从树叶到根逆向得到编码
	/*
	for(i=1;i<=n;i++)
		cout<<" "<<*(HC+i);//输出哈夫曼编码;    
	cout<<endl;
	*/
}
////////////////////////////////////////////
HuffmanATree::Translation()
{//将原文译为代码
	int i,j;
	char ch;
	ifstream infile("f1.txt");//f1中为原文
	if(!infile)
	{cerr<<"open error!"<<endl; exit(1);}
	ofstream outfile("f2.txt");//f2存放代码
	if(!outfile)
	{cerr<<"open error!"<<endl; exit(1);}
/*	for(i=1;i<n;i++)
		cout<<" "<<*(LetterList+i-1);//字符表被意外改变
*/
	cout<<"原文翻译为："<<endl;//以下翻译有问题！
	for(i=1;i<m;i++)
	{
		infile.get(ch);
		//cout<<" "<<ch;			
		for( j=1;j<=n;j++)
		{
			if(*(LetterList+j-1)==ch)
			{
				//cout<<" "<<*(LetterList+j-1);
				outfile<<*(HC+j);
				cout<<*(HC+j);
				break;
			}
		}		
	}
	cout<<endl;
	infile.close();
	outfile.close();
	cout<<"翻译所得代码已存入文件f2中"<<endl;
	cout<<"<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>"<<endl;	
}
HuffmanATree::Retranslation()
{//将代码译为文字
	char *code=new char;
	ifstream infile("f2.txt");
	if(!infile)
	{cerr<<"open error!"<<endl; exit(1);}
	int i=0;
	infile>>code;
	infile.close();
	//cout<<code<<endl;
	cout<<"将代码译回文字为:"<<endl;
	ofstream outfile("f3.txt");//f2存放代码
	if(!outfile)
	{cerr<<"open error!"<<endl; exit(1);}
	for(i=n+n-1;*code!='\0';code++)
	{
		if(*code=='0')
			i=HT[i].lchild;
        else
			i=HT[i].rchild;
		if(HT[i].lchild==0&&HT[i].rchild==0)
		{
			outfile<<*(LetterList+i-1);
			cout<<*(LetterList+i-1);
			i=n+n-1;
		}
	}
    outfile.close();
	cout<<endl<<"已经存入文件f3中"<<endl;
	cout<<"<<<<<<<<<<<<<<<>>>>>>>>>>>>>>>>"<<endl;
}

int main()
{
	HuffmanATree h_tr;
	h_tr.NodeWeight();
	h_tr.HuffmanCoding();
	h_tr.Translation();
	h_tr.Retranslation();
	return 0;
}