xinyunbianma.cpp

这是哈弗曼吗的编码与译码程序,下载之后用visual c++ 打开

//产生哈夫曼编码的代码:
#include"stdio.h"
#include"stdlib.h"
#include"string.h"

typedef char ElemType;
typedef struct{
   ElemType elem;
   unsigned int m_weight;
   unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char** HuffmanCode; 
typedef int Status; 
typedef struct weight{
   char elem;
   unsigned int m_weight;
}Weight;
HuffmanTree HT;
HuffmanCode HC;
Weight *w;

int pianyi;
char *coder;
char string[10000];
int l_pianyi;
char l_string[15000];


void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int); 




void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n){
   int i,m,s1,s2,start,c,f;
   char *cd;
  
   if(n<=1)
        return;

   m=2*n-1;
   (*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
   for(i=1;i<=n;++i){
      (*HT)[i].elem=w[i-1].elem;
      (*HT)[i].m_weight=w[i-1].m_weight;
      (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
   }

   for(;i<=m;++i){
      (*HT)[i].elem='0';
      (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
   }

   for(i=n+1;i<=m;++i){
      Select(*HT,i-1,&s1,&s2);
      (*HT)[s1].parent=i;(*HT)[s2].parent=i;
      (*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
      (*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
   }

   (*HC)=(HuffmanCode)malloc(n*sizeof(char*));
    cd=(char *)malloc(n*sizeof(char));
    cd[n-1]='\0';
    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';
          else cd[--start]='1';
       }

      (*HC)[i]=(char *)malloc((n-start)*sizeof(char));
      strcpy((*HC)[i],&cd[start]);
    }
}

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

        }

       if(((*s1)==0||(*s2)==0)&&HT[i].parent==0){
           if((*s1)==0) (*s1)=i;
           else if((*s2)==0){
                   if(HT[i].m_weight<HT[(*s1)].m_weight){
                     (*s2)=(*s1);
                     (*s1)=i;
                   }
                   else (*s2)=i;
           } // end of else if
       } // end of if

     } // end of for

     if((*s1)>(*s2)){
        i=(*s1);
        (*s1)=(*s2);
        (*s2)=i;
     }

     return;

}




void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n){

     int i;
     printf("\n序号---节点----权---哈弗曼编码\n");
     for(i=1;i<=n;i++)
        printf(" %d\t%c\t%d\t%s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);

}
/*******************************************************************************/
                      // 编码
/*******************************************************************************/
void coding(int m)//对字符进行编码
{
 int n,i,j;
 char *p;
 printf("请输入字符串：\n");
 scanf("%s",string);
 n=strlen(string);
 for(i=1,p=string;i<=n;i++,p++)
 {
  for(j=1;j<=m;j++)
	  if(HT[j].elem==*p){
	    
        strcpy(&coder[pianyi],HC[j]);
		pianyi+=strlen(HC[j]);
	  }
 }
 printf("%s",coder);
 printf("\n");
}

/*******************************************************************************/
                      // 译码
/*******************************************************************************/
void yima(int m)
{
 int c;
 char *p;
 for(p=coder,c=2*m-1;*p!='\0';p++)
 {
     if(*p=='0')
	 {
      c=HT[c].lchild;
      if(HT[c].lchild==0&&HT[c].rchild==0) 
	  {
	   l_string[l_pianyi]=HT[c].elem;
	   l_pianyi++;
       printf("%c",HT[c].elem);
       c=2*m-1;
       continue;
	  }
	 }
     if(*p=='1')
	 {
        c=HT[c].rchild;
        if(HT[c].lchild==0&&HT[c].rchild==0) 
		{
			 l_string[l_pianyi]=HT[c].elem;
	   l_pianyi++;
        printf("%c",HT[c].elem);
        c=2*m-1;
        continue;
		}
	 }
   }
    l_string[l_pianyi]='\0';
    printf("\n");
}

void main(void){
    
    char c; // the symbolizes;
    int i,n; // the number of elements;
    int wei; // the weight of a element;
    pianyi=0;
	l_pianyi=0;
	coder=(char *)malloc(50000*sizeof(char));
    printf("输入哈弗曼树的叶子节点个数:" );
    scanf("%d",&n);
    w=(Weight *)malloc(n*sizeof(Weight));
    for(i=0;i<n;i++){
        printf("输入叶子节点的字符和权值:");
        scanf("%1s%d",&c,&wei);//1s为字符串长度为1
        w[i].elem=c;
        w[i].m_weight=wei;
    }

    HuffmanCoding(&HT,&HC,w,n);
    OutputHuffmanCode(HT,HC,n);
    coding(n);
	yima(n);


}