huffman.cpp

赫夫曼编码。可以任意的设置字母和权值用于可以进行译码

#include<fstream>
#include<iostream>
using namespace std;
#define MAX_LEN 100
int n;
char st[MAX_LEN];
typedef struct
{ unsigned int weight;  
 unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
void intialhuffman(HuffmanTree &ht)
{
for(int i=1;i<2*n;i++)
{
   ht[i].weight=0;
   ht[i].parent=0;
   ht[i].lchild=0;
   ht[i].rchild=0;
}
}
/*void intialhuffmancode(HuffmanCode &hc);
{
int i;

}*/
void get_from_file(HuffmanCode &hc)      //读取文件ToBeTran的字符，并把它编码存入CodeFile
{   int i,m;
	char ch;
	ifstream infile("ToBeTran.txt",ios::in);
	if(!infile)
	{cerr<<"open ToBeTran.txt error!"<<endl;
	exit(1);    
}
	ofstream outfile("CodeFile.txt",ios::out);
if(!outfile)
{cerr<<"open CodeFile.txt error!"<<endl;
exit(1);
}
/*for(i=1;i<=n;i++)
hc[i]=(char *)malloc(n*sizeof(char));*/
while(infile.get(ch))
{   
	for(i=1;i<(n+1);i++)
	{
	if(st[i]==ch)
	break;
	}
	outfile<<hc[i];	
}
infile.close();
outfile.close();
} 


void translate(HuffmanCode &hc)     //从CodeFile中读取编码，并把译出结果存入TextFile中
{char ch,ct;
int i;
int j=0;
bool p=false;
char cr[20];
for(i=0;i<20;i++)
cr[i]=0;
//char *cd;
//cd=(char *)malloc(n*sizeof(char));
	ifstream infile("CodeFile.txt",ios::in);
if(!infile)
{cerr<<"open CodeFile.txt error!"<<endl;
exit(1);
}
ofstream outfile("TextFile.txt",ios::out);
if(!outfile)
{cerr<<"open TextFile.txt error!"<<endl;
exit(1);
}
while((ch=infile.get())!=EOF)
{
cr[j]=ch;
j++;
for(i=1;i<=n;i++)
{ 
if(strcmp(hc[i],cr)==0)
{
ct=st[i];
p=true;
outfile.put(ct);
}
}
if(p)
{
for(i=0;i<=j;i++)
cr[i]=0;
j=0;
p=false;
}
}
infile.close();
outfile.close();
}	
void save_hfmTree(HuffmanCode &hc)  //用c++写不成，改用c写
{//char ch;
	int i;
	char m;
	ofstream outfile("hfmTree.txt",ios::out);
if(!outfile)
{
	cerr<<"open hfmTree.txt error!"<<endl;
exit(1);
}
for(i=1;i<=n;i++)
outfile<<hc[i]<<endl;
outfile.close();
}


void get_hfmTree(HuffmanCode &hc)               //从hfmTree文件中读入已建立的hfmTree，用于译码。
{int i;
char cd[MAX_LEN];
//cd=(char *)malloc(n*sizeof(char));
	ifstream infile("hfmTree.txt",ios::in);
if(!infile)
{
cerr<<"open hfmTree.txt error!"<<endl;
exit(1);
}
for(i=1;i<=n;i++)
{
hc[i]=(char *)malloc(n*sizeof(char));
infile.getline(cd,MAX_LEN,'\n');
cd[strlen(cd)]=0;
strcpy(hc[i],cd);
}
}
void HuffmanCoding(HuffmanTree &ht,HuffmanCode &hc)
{if(n<=1) return;
int i,j,l,mk;
int s1=0;
int s2=1;
for(i=1;i<=n;i++)
mk=mk+ht[i].weight;
//for(p=ht,i=1;i<=n;++i,++p,++w)
/*p={*w,0,0,0};
for(;i<=m;++i,++p)
*p={0,0,0,0};*/
for(l=n+1;l<2*n;++l)
{   int total=mk+1;
		for(i=1;i<=l-1;i++)
	{
		if(ht[i].parent==0)
		{
	for(j=2;j<=l-1;j++)
	{   
		if((ht[j].parent==0)&&i!=j&&ht[i].weight+ht[j].weight<total)
	{
	total=ht[i].weight+ht[j].weight;
	s1=i;
	s2=j;
	}
	}
		}
	}
//select(ht,i,s1,s2);

ht[s1].parent=l;ht[s2].parent=l;
ht[l].lchild=s1;ht[i].rchild=s2;
ht[l].weight=ht[s1].weight+ht[s2].weight;
}
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{  int c,f,start;
	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]);
}
free(cd);
}
void pcodef()
{   int i;
    int j=0;
    int length;
	char ch;
	bool r=false;
	char a[MAX_LEN];
	ifstream infile("CodeFile.txt",ios::in);
	if(!infile)
	{cerr<<"open CodeFile.txt error!"<<endl;
	exit(1);
	}
	while((ch=infile.get())!=EOF)
	{
    a[j]=ch;
	cout<<a[j];
	j++;
	if(j%50==0) 
	{
		cout<<endl;
		r=true;
	}
	if(r)
	{
		for(i=0;i<j;i++)
			a[i]=0;
		r=false;
		j=0;
	}
	}
	infile.close();
	cout<<endl;
    ifstream infile1("TextFile.txt",ios::in);
	if(!infile1)
	{cerr<<"open TextFile.txt error!"<<endl;
	exit(1);
	}
	infile1.getline(a,MAX_LEN);
	length=strlen(a);
	for(i=0;i<length;i++)
	if(a[i]!=0)
	cout<<a[i];
	cout<<endl;
    infile1.close();
}
void huffman(HuffmanTree &ht,HuffmanCode &hc) 
{
char c;
int i,r,wei;
int nt;
cout<<"the number of char you want to enter,less than 100:"<<endl;
cin>>n;
nt=n+1;
int m=2*n-1;
ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
hc=(HuffmanCode)malloc((n+1)*sizeof(char *));
intialhuffman(ht);
cout<<"please enter the char one by one:"<<endl;
for(r=0;r<nt;r++)
{
c=cin.get();
st[r]=c;
}
cout<<"please enter the numbers:"<<endl;
for(i=1;i<=n;i++)
{
cin>>wei;
ht[i].weight=wei;
}
HuffmanCoding(ht,hc);
save_hfmTree(hc);
for(i=1;i<2*n;i++)
cout<<ht[i].weight<<"  "<<ht[i].parent<<"  "<<ht[i].lchild<<"  "<<ht[i].rchild<<endl;
for(i=1;i<=n;i++)
cout<<st[i]<<" "<<hc[i]<<endl;
}

void main()
{
bool s=true;
HuffmanTree ht;
HuffmanCode hc;
huffman(ht,hc);
int choice;
while(s)
{
cout<<"what do you want to do? 1.编码(字符在ToBeTran文本中输入) 2.译码(代码在CodeFile文本中输入)3.新建赫夫曼树 4.退出"<<endl;
cout<<"enter your choice(1-4):"<<endl;
cin>>choice;
switch(choice)
{
case 1:
       get_hfmTree(hc);
       get_from_file(hc);
	   translate(hc);
	   pcodef();
	   break;
case 2:get_hfmTree(hc);translate(hc);pcodef();break;
case 3:huffman(ht,hc);break;
case 4:s=false;break;
default:cout<<"you enter the wrong number,"<<endl<<"please enter the number(1-4):";break;
}
}
}