新建 文本文档.txt

实现哈弗曼

#include<iostream>
#include<string>
#include<fstream>
using namespace std;
const int INF=10000;
const int N=27;
 string s; //s为给出的字符集的字符串
typedef struct 
{
     int weight ;   // 结点的权值
     int parent,  lchild, rchild; 
}HTNode,  * HuffmanTree;   //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode ; //动态分配数组存储哈夫曼编码 

HuffmanTree  HT;
HuffmanCode HC;

void Select (HuffmanTree &HT,int n,  int &s1, int &s2)
{
	int temp1=INF;
	int temp2=INF;
	for(int i=1;i<=n;++i)
		if(HT[i].weight<temp1&& HT[i].parent==0) 
		{s1=i;temp1=HT[i].weight; }
	for( i=1;i<=n;++i)
		if(HT[i].weight<temp2&&(i!=s1)&& HT[i].parent==0) 
		{s2=i;temp2=HT[i].weight; } 
}

void HuffmanCoding( HuffmanTree &HT , HuffmanCode &HC, int *w,  int n) 
{  
 int  m=2*n-1; 
 HT= (HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
 if(!HT){cout<<"分配失败";exit(-1);}
 for( int i=1; i<=n; ++i) 
  {HT[i].weight = w[i];  HT[i].parent=0;  HT[i].lchild=0;  HT[i].rchild=0; }
  for( i=n+1 ; i<=m; ++i) 
 {HT[i].weight = 0; HT[i].parent=0; HT[i].lchild=0;HT[i].rchild=0; } 
  for( i=n+1; i<=m; i++)
  {//在HT[1..i-1]选择parent为0且weigHT最小的两个结点,其序号分别为s1和s2
  int s1,s2;
 Select(HT,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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));   
 if(!HC){cout<<"分配失败";exit(-1);}
 char* cd=(char *)malloc(n*sizeof(char ));   
cd[n-1]='\0' ;
for( i=1; i<=n; i++) 
{
    int  start=n-1; 
    int  f=HT[i].parent;
	 for(int c=i ; 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 Encoding(HuffmanCode &HC,string str)
{
 ofstream CodeFile("CodeFile.txt");
 int i=0;
 while(str[i]!='\0') 
 {
	 int j=0;  if(i%9==0)cout<<endl;
     while(str[i]!=s[j]&&s[j]!='\0') j++;
          printf("%-10s",HC[j+1]);
          CodeFile<<HC[j+1];
		  i++;
	}
cout<<endl;
}
 
void Decoding(HuffmanTree &HT,string str)
{
	ofstream TextFile("TextFile.txt");
	int i=0;
   while( str[i]!='\0')
  {
    int t=0;
   char *stemp=(char *)malloc(N*sizeof(char));
   int m=2*N-1;
   while(HT[m].lchild!=0&&HT[m].rchild!=0)
	{ 
		if(str[i]=='0')         {m=HT[m].lchild;stemp[t++]='0';}
        else if(str[i]=='1')  {m=HT[m].rchild;stemp[t++]='1';}
	    i++;
     }
	    stemp[t]='\0';
     	for(int j=1;j<=N;j++)
		    if (strcmp(HC[j],stemp)==0) {cout<<s[j-1];TextFile<<s[j-1];}
  }
cout<<endl<<endl;
}


void TreePrint(HuffmanTree HT,int m,int k)
{
	if(m==0) return;
	for(int n=0;n<k;n++)
		cout<<"____";
	cout<<HT[m].weight<<endl;
	TreePrint(HT,HT[m].lchild,k-1);
	TreePrint(HT,HT[m].rchild,k-1);
}



void Menu()
{//系统初始化
	cout<<"Init--I    Encode--E   Decode--D  Pintcode--P   Treeprint--T   Quit--Q"<<endl;
    cout<<"请输入命令：";
}//Initialization

void ReadCommand(char &cmd)
{
	//读入操作命令符显示键入操作符的提示信息
	do
	{cmd=getchar( );}
	while(!(cmd=='i' || cmd=='I' || cmd=='e' || cmd=='E' || cmd=='d'||
		       cmd=='D' ||cmd=='p'||cmd=='P'||cmd=='t'||cmd=='T'||cmd=='q'||cmd=='Q'));
}//ReadCommand

void Interpret(char cmd)
{
	//解释执行操作命令cmd
	switch(cmd)
	{
	case 'i': case'I': {ofstream hfmTree("hfmTree.txt");
		                     ifstream nstr("str.txt");
		                     ifstream nweight("weight.txt");
		                     int w[N+1];
						     getline(nstr,s,'\0');
						     cout<<"给出的字符集为:"<<s<<endl;
						     cout<<N<<"个字符的权值: "<<endl; 
						     for(int i=1;i<=N;i++)
						    { nweight>>w[i];   printf("%-5d",w[i]);  if(i%9==0)cout<<endl; }
                             cout<<endl;
                             HuffmanCoding( HT,HC,w, N) ;
							  for( i=1;i<2*N;i++)
							 {
								hfmTree<<HT[i].weight<<"   ";
								hfmTree<<HT[i].parent<<"   "; 
								hfmTree<<HT[i].lchild<<"   ";  
								hfmTree<<HT[i].rchild<<"   "<<endl;
                             }
							Menu();
							break;
			               }
	case 'e': case'E': {
							
							   ifstream hfmTree("hfmTree.txt");
							   ifstream ToBeTran("ToBeTran.txt");
							   string str;
							   getline(ToBeTran, str,'\0'); 
							   cout<<"要编码的字符串为:"<<str;
							   Encoding(HC,str);
                               cout<<endl;
							    Menu();
							    break;
			                }
	case'd':case'D':{ifstream CodeFile("CodeFile.txt");
		                    string str;
							getline(CodeFile,str,'\0');
							Decoding(HT,str); 
						    Menu( );
							break;
			               }
	case 'p':case'P': { ifstream CodeFile("CodeFile.txt");
		                      ofstream CodePrin("CodePrin.txt");
		                       string  code;
							  getline(CodeFile,code,'\0');
							  int i=0;
							  while(code[i]!='\0')
							  {
								cout<<code[i]; 
								if((i+1)%50==0) cout<<endl;
							    i++;
							  }
							   cout<<endl<<endl;
							   CodePrin<<code;
							  Menu();
							  break;}
	case 't':case 'T': {TreePrint(HT,2*N-1,15); Menu( );break;}
	}//swtich
}//Interpret

void main()
{
	Menu();
	char cmd;
	do
	{
		ReadCommand(cmd);//读入一个操作命令符
		Interpret(cmd); //解释执行操作命令符
	}
	while(cmd!='q'&&cmd!='Q');
}//main