huffman_code.cpp

数据结构试验。。。哈夫曼编码。。字符的编码与译码

#include<math.h>
#include<stdio.h>
#include<malloc.h>
#include<string.h>

#define null 0

typedef struct{
    char data;
	int weight;
 
    int parent,lchild,rchild;
}htNode,*HuffumanTree;

typedef char * *HuffmanCode;



void Select(HuffumanTree &ht,int m,int &s1,int &s2){
   
	//在ht[1....i-1]选择parent为，且weight的值最小的两个结点，序号分别为s1，s2
int min1,min2,i,j;
i=1;j=1;

 while(ht[i].parent!=0){ i++;}

  min1=i;

   for(i=min1;i<=m;i++){
	   
      if(ht[i].parent==0&&ht[i].weight<ht[min1].weight) min1=i;

}
   while(ht[j].parent!=0||j==min1){ j++;}

	min2=j;
	for(i=min2;i<=m;i++){
	   if (i==min1) {}
	  else 
	  {if(ht[i].parent==0&&ht[i].weight<ht[min2].weight) min2=i;}
	          
 }
s1=min1;
s2=min2;
}//end select();

void initialization(HuffumanTree &ht,HuffmanCode &hc,int *w,char *ch,int n){
	
	int m,s1,s2,f,c,start,i,j;
    char *cd;
     j=0;
	
	HuffumanTree p;
	if(n<1) return;
	m=2*n-1;
   ht=(HuffumanTree)malloc((m+1)*sizeof(htNode));//0号单元不用	
  p=ht--;
   
  for(i=1;i<=n;++i,++p,++w,++ch) //*p= {*ch,*w,0,0,0};
	
	{
	p->data=*ch;  
	p->weight=*w;
	p->parent=0;
	p->lchild=0;
	p->rchild=0;
	}
	
	

	for(;i<=m;++i,++p) //*p= {0,0,0,0};
	
	{
	
	p->data='#';	
	p->weight=0;
	p->parent=0;
	p->lchild=0;
	p->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].weight=ht[s1].weight+ht[s2].weight;
	}
  
hc=(HuffmanCode)malloc((n+1)*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]);
 
		  
		  printf("%c",ht[i].data);
		  printf("%s",hc[i]);
          printf(" ");
		 
  
  }
  free(cd);

printf("\n");
}//end initialization();


//字符编码	
void Encode(HuffumanTree &ht,HuffmanCode &hc,char *c){
	int j,i;


	printf("The code is:");
	
	for(j=0;c[j]!='\0';j++){
		for(i=0;i<=27;i++){
			if(ht[i].data==c[j])
			printf("%s",hc[i]);
		
		}

}

printf("\n");	

}//end Encode();


void Decode(HuffumanTree &ht,char *ch,int n){
//字符串译码	
HuffumanTree p;
int i;
p=&ht[2*n-1];//取得根结点地址
i=0;
while(ch[i]!='\0'){
	while(p->lchild!=0||p->rchild!=0){
		if(ch[i]=='0') p=&ht[p->lchild];
		else p=&ht[p->rchild];
i++;
	}
printf("%c",p->data);

p=&ht[2*n-1];
}
printf("\n");
}



void save(HuffumanTree ht,int n){
	FILE *fp;
	int i;
	if((fp=fopen("hfmTree.txt","w"))==null)
	{
		
		
		printf("can'not open the file");
         return;

	}


for(i=0;i<2*n-1;i++)
if(fwrite(&ht[i],sizeof(htNode),1,fp)!=1)
printf("file write error\n");
fclose(fp);
}

void main(){

    HuffumanTree h;
	HuffmanCode c;
    char cm[200];
	char t;;
	char cd[200];
	int i;
	i=0;
	
	
	char ch[27]={' ','A','B','C','D','E','F','G','H','I','j','K','L','M','N','O','P','Q','R','S',
	'T','U','V','W','X','Y','Z'};
	int	m[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};	
                                                               

    initialization(h,c,m,ch,27);
 
    
    save(h,27);
	
     printf("please input the string:");
    while((t=getchar())!='\n'){
		cm[i]=t;
		i++;
	}
	cm[i]='\0';
	Encode(h,c,cm);
       i=0;
    printf("please input the code:");

	while((t=getchar())!='\n'){
		cd[i]=t;
		i++;
	}
	cd[i]='\0';
	
	Decode(h,cd,27);

	printf("%d",h[53].weight);


}

	
	
	
	
	
	
	













	
	
	
	
	
	
	
	
	
	
	//	int m[4]={7,5,2,4};
    
	
//	initialization();