huffman.cpp

该程序是实现huffman编码的程序

#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
typedef struct
{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree; 
typedef char **HuffmanCode;
typedef char *CD;
void Select(HuffmanTree ,int ,int &,int &);
void YimaCopy(char [],int , CD ,int );
int main()
{
	char a;     
	char code1[5000];
	char code2[100];
	int i,m,k,j,p;
    cout<<"输入要编码的字符原文，以#结尾："<<endl;
	for(i=1;i<=4999;i++)
	{   
		a=getchar();
		if(a=='#') break;
		code1[i]=a;                            //code1用于存储原始输入符

	}
	code1[i]='\0';
	m=i-1;                          //m用于记录输入符的总个数
    j=1;
    for(i=1;i<=m;i++)
	{
		for(k=1;k<=j;k++)           //k用于对code2中已有代表符做遍历
		{
			if(code1[i]==code2[k]) {p=0;break;}         //code2用于存储原始输入符的代表符分类
			else {p=1;}
		}
		if(p==1) {code2[j]=code1[i];j++;}
	}
	code2[j]='\0';
	int n=j-1;                     //n用于记录代表符的总数
	int ww[100]={0};                         
	for(j=1;j<=n;j++)
	{
		for(i=1;i<=m;i++)
		{
		  if(code1[i]==code2[j])
			  ww[j]++;                       //ww用于记录不同代表符的权
		}
	}
    cout<<"代表符及其个数 "<<endl;	
    for(j=1;j<=n;j++)                          
	{
	cout<<code2[j]<<"  ";	//输出代表符
	}
   cout<<endl;

   for(j=1;j<=n;j++)
	{
	cout<<ww[j]<<"  ";	     //输出代表符对应相同字母的个数     
	}
    cout<<endl;


   int s1,s2,t;
   t=2*n-1;                                  //t用于记录二叉树的总结点数
   HuffmanTree HT; 
   HT=(HuffmanTree)malloc((t+1)*sizeof(HTNode));
   for(i=1;i<=n;++i)                           //树节点的初始化
   {                              
	HT[i].weight=ww[i];
    HT[i].parent=0;
    HT[i].lchild=0;
	HT[i].rchild=0;
   }
   for(i=n+1;i<=t;++i)                       //树节点的初始化
   {
	HT[i].weight=0;
    HT[i].parent=0;
    HT[i].lchild=0;
	HT[i].rchild=0;
   }
   cout<<"树构造之前： "<<endl;
   for(i=1;i<=t;i++)
	{
	cout<<"("<<i<<")"<<"  "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;	
	}

   
  for(i=n+1;i<=t;i++)                     //建哈夫曼树
   {   
	 
	   Select(HT,i-1,s1,s2);              //选择parent为0且weight最小的两个结点，其序号分别为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;
   }
   cout<<"树构造之后： "<<endl;
   for(i=1;i<=t;++i) 
   {
	cout<<"("<<i<<")"<<"  "<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
    }

   
   
   
   HuffmanCode HC; 
   HC=(HuffmanCode)malloc((n+1)*sizeof(char*));     
   CD cd;  
   cd=(CD)malloc(n*sizeof(char));
   cd[n-1]='\0';
   int c,start;
   int f;
   int hc[100];                                    //hc[i]用于记录该HC[i]中的字符数
   for(i=1;i<=n;++i)
   {   
	   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';                //cd用于记录编码
		   else cd[--start]='1';
	   }
	   HC[i]=(char*)malloc((n-start)*sizeof(char)); 
	   hc[i]=n-start;
	   for(j=0;j<=n-start-1;j++)
	   { 
		HC[i][j]=cd[j+start];                           //HC[i][]为不同的代表码的编码
	   }
	 }
   delete cd;
    
  
   
   for(j=1;j<=n;j++)
	   {
		  cout<<code2[j]<<"对应的编码是："<<HC[j]<<endl;
	   }
   cout<<"对应的全部编码文是："<<endl;
   for(i=1;i<=m;i++)                        //code1[]中所有元素输出编码
   {
	   for(j=1;j<=n;j++)
	   {
		   if(code1[i]==code2[j])
		    
			  cout<<HC[j];
	   }
   }
  cout<<endl;
 


  char aa; 	aa=getchar();     //注意该操作用以取得前面输入的回车符，将被后面的屏蔽掉，避免回车符进入译文中 
  char yima[5000];                 //由译码译成源码
    cout<<"根据代表符的编码输入编码文，仅包括1，0字符，以#结尾："<<endl;
    cout<<"编码文的输入要正确，否则译码将终止："<<endl;
	for(i=1;i<=4999;i++)
	{   
		aa=getchar();                        //译码的输入
		if(aa=='#') break;
		yima[i]=aa;                        
	}
	yima[i]='\0';
   cout<<"编码文的原文为："<<endl;
    int mm=i-1;
    j=1;
	CD ccdd;  
   while(j!=mm+1)                            
   {
	    for(i=1;i<=n;i++)
		{ 
		  ccdd=(CD)malloc(hc[i]*sizeof(char));
          YimaCopy(yima,j,ccdd,hc[i]);        //hc[i]用于记录该HC[i]中的字符数，将译码中的与HC[i]同长的部分提取给ccdd[]，以便与HC[i]比较
        
		  if(strcmp(ccdd,HC[i])==0){ cout<<code2[i];break;}  //利用已知编码对输入的译码进行匹配
		}
	
        j=j+hc[i]-1;         //j用于记录该译码应开始匹配的位置
   }
    cout<<endl;
	delete ccdd;
	delete HC,HT;
     return 0;
}

 void Select(HuffmanTree HT,int nn,int &s1,int &s2)
 {   
	 int i=1,j=1,k,l,r;
	 int a[100],b[100];
	 for(i=1;i<=nn;i++)
	 {
		 if(HT[i].parent==0)
		 { 
		  a[j]=i;                          //a[j]用于存储在HT中的序号
		  b[j]=HT[i].weight;                        //b[j]用于存储与序号对应的weight值
		  j++;
		 }
	}
	 --j;                             
     for( k=1;k<=j;k++)
	 {
	     r=0;
		 for(l=1;l<=j;l++)
		 {
			 if(b[k]<=b[l]){r++;}                    //r用于记录比较符合的个数，等于j时成功。
		}
		 if(r==j){s1=a[k];b[k]=b[1]+b[2];break;}  //注意是b[k],而不b[s1].求得最小weight值的序号,同时把
	 }                                 //其存的weight人为改大，在求第二最小weight值时直接求最小的即可                 
	for(k=1;k<=j;k++)
	 {
		 r=0;
		 for(l=1;l<=j;l++)
		 {
			 if(b[k]<=b[l]) {r++;}                 //同上
              
		 }
		 if(r==j){s2=a[k];break;}               //求得第二小weight值序号
	 }
 }
 
 

 
 void YimaCopy(char yima[],int j, CD ccdd,int hc)
 { 
	 
	  int k=0;
	for(k=0;k<=hc-2;k++)
	{   
		ccdd[k]=yima[k+j];                     //将译码中的与HC[i]同长的部分提取出来，以便与HC[i]比较
	}
	   ccdd[k]='\0';
 }