(4).txt

霍夫曼编码的C语言实现

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

  ouble orgpercent[256],percent[356]; 

  int p = 0;
  int f = 0;       

static struct TreeUnit  
    {
	double selfNum; 
	double lch;     
	double rch;     
	int faNum ;     
	int ord;        
	int origin;    
    } treeunit[512];


static struct Unitlong     
   {
	int r;         
	int q;          
   }unitlong[256];






void Hfuman( )   
{       
	    int h = 0;
	    int e;    
        int y;
        int j;
       	int w = 0;
    
		
search:	
		int l = 101,n = 100;
    	double m=percent[100];
        for(j = 0 ; j < 355 ; j ++)   
		{
			if(percent[j] < m && percent[j] != 0 )
			{
				m = percent[j];
				n = j;
			}
		}

		
		if(n >= 100)
		{   
			treeunit[p].selfNum = m;
			treeunit[p].rch = -1;
			treeunit[p].lch = -1;
	
			treeunit[p].origin = n - 100;
            unitlong[h].r = p;
			h++;
			p++;
			
		}
        
		double k = percent[101];
        for( j = 0; j < 355 ; j ++)    
		{
			
			if(j != n && percent[j] <  k && percent[j] != 0  )
			{ 
				 k = percent[j];
			     l = j;
			
			}
		}
	
		
		if(l>=100)
		{
			treeunit[p].selfNum = k;
			treeunit[p].rch = -1;
			treeunit[p].lch = -1;
		    treeunit[p].origin = l - 100;
			unitlong[h].r = p;
			h++;
			p++;
		}
		
		if(l>=100 && n >= 100)
		{
			if(n < l )
			{   
			   treeunit[p].lch = p - 2;
	     	   treeunit[p].rch = p - 1;
			   treeunit[p-1].ord = 0;
			   treeunit[p-2].ord = 1;
			
			}
		     else
			 {
                treeunit[p].lch = p - 1;
	     	    treeunit[p].rch = p - 2;
			    treeunit[p-1].ord = 1;
			    treeunit[p-2].ord = 0;
			 }
             treeunit[p].selfNum = treeunit[p-2].selfNum + treeunit[p-1].selfNum ; 
	         treeunit[p-1].faNum = p;
             treeunit[p-2].faNum = p;
   	         treeunit[p].origin = -1;	         
             percent[w] = treeunit[p].selfNum;  
        	 w++;
			 if(((1.0000 - treeunit[p].selfNum)) < 1e-10)   return;
			
		       p++;
			 
		}
		else if(l < 100 && n >= 100)
		{
			for(j = 0 ; j < 100 ; j++)
			{  
					if((percent[l]-treeunit[j].selfNum) < 1e-10)   
				    break;
			}
			if(j > 512)
			{
				printf("查找新建的结点频度位子出错 !\n");
				return;
			}
	    	e = j;
            treeunit[p].lch = p - 1;      //l < n ，n 一定小于l 项
	        treeunit[p].rch = e;
     		treeunit[e].ord = 1;
		    treeunit[p-1].ord = 0;
			 
             treeunit[p].selfNum = treeunit[e].selfNum + treeunit[p-1].selfNum ;  
			 treeunit[e].faNum = p;
             treeunit[p-1].faNum = p;
   	         treeunit[p].origin = -1;
	         percent[w] = treeunit[p].selfNum;
        	 w++; 
		     if((1.0000 - treeunit[p].selfNum)<1e-10)   return;
			 p++;
			
		}
		else if(l >= 100 && n < 100)
		{   		    
			for(j = 0 ; j <100 ; j++)
			{  
					if((percent[n]-treeunit[j].selfNum) < 1e-10)   
				    break;
			}
			if(j > 512)
			{
				printf("查找新建的结点频度位子出错 !\n");
				return;
			}
			e = j;
                                   
			   treeunit[p].lch = p-1;      //n < l ，l 一定小于n 项
	     	   treeunit[p].rch = e;
			   treeunit[e].ord = 1;
			   treeunit[p-1].ord = 0;
		
             treeunit[p].selfNum = (treeunit[e].selfNum + treeunit[p-1].selfNum ); 
		      treeunit[n].faNum = p;
             treeunit[p-1].faNum = p;
   	         treeunit[p].origin = -1;
	         percent[w] = treeunit[p].selfNum;  
        	 w++;
			 if((1.0000 - treeunit[p].selfNum)<1e-10) return;
		     p++;
			 
		}
		else if(l<100 && n < 100)
		{
			for(j = 0 ; j <100 ; j++)
			{  
					if(percent[l] == treeunit[j].selfNum)
				    break;
			}
			if(j > 512)
			{
				printf("查找新建的结点频度位子出错 !\n");
				return;
			}
			else
			e = j;
			j = 0;
			for(; j <100; j++)
			{  
					if((percent[n]-treeunit[j].selfNum) < 1e-10 )   
				    break;
			}
			if(j > 512)
			{
				printf("查找新建的结点频度位子出错 !\n");
				return;
			}
			else
			y = j;
            if(y < e )
			{   
			   treeunit[p].lch = y;
	     	   treeunit[p].rch = e;
			   treeunit[y].ord = 1;
			   treeunit[e].ord = 0;
			
			}
		    else
			 {
                treeunit[p].lch = e;
	     	    treeunit[p].rch = y;
				treeunit[e].ord = 1;
			   treeunit[y].ord = 0;
			 }
             treeunit[p].selfNum = treeunit[y].selfNum + treeunit[e].selfNum ;  
		     treeunit[y].faNum = p;
             treeunit[e].faNum = p;
   	         treeunit[p].origin = -1;
	         percent[w] = treeunit[p].selfNum;
        	 w++;
			 if((1.0000 - treeunit[p].selfNum)<1e-10)  return;
	         p++;
		}
		percent[l] = 1;
		percent[n] = 1;
goto search;


}



void Showord(int num )     
{ 

    int p = 0; 
	int i;
	int l ;   
    for( i =0 ; i < num ; i++ ) 
	{	
		l = 0;
        printf("\n频度%lf编码   : ",treeunit[unitlong[i].r].selfNum);  //  频度显示
		p = unitlong[i].r;
		while((1.0000-treeunit[p].selfNum) > 1e-10)
		{
		  
		  printf("%d",treeunit[p].ord);
		  p = treeunit[p].faNum;
		  l++;
		}//while
		printf("\n");  
        unitlong[i].q = l;
	}
			
		
	
	
	for(i=0;i < num;i++) 
		  printf("\n频度: %lf ,长度: %d \n",treeunit[unitlong[i].r].selfNum ,unitlong[i].q) ;

}

void Compute(double H,int num)       
{
	int n = 0;
	int j = 0;; 
	double everordlong = 0,result = 0;
	for(;j<num;j++)
	{
		n = unitlong[j].r;
		everordlong = everordlong + (treeunit[n].selfNum * double(unitlong[j].q));
	}
    result = (everordlong - H)/everordlong;
	printf("\n这%d条指令的信息冗余量为: %lf \n\n\n\n\n\n\n",num,result);


}




void  main()
{
	char sle;
	int num;      //指令个数
	double m = 0;
	int i = 0;
	   // 指令频度的数组
	for(i = 0 ;i <256; i++)
		orgpercent[i] = 0;
	for(i = 0 ;i <356; i++)
		percent[i] = 0;
hh:
	double n = 0;
	while(1){
	printf("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
    printf("                    计算指令冗余量                        \n" );
	printf("1. 进入请输入 M                      2. 退出请输入 N      \n " );
	printf("++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
    printf("\n");	
	scanf("%c", &sle);
	getchar();
	if(sle == 'N')
		return;
	else if(sle == 'M')
	{
		printf("\n请按顺序输入指令的频度，输完及退出按(1): \n");
	   for(i = 0; i < 256; i++)
	   {  
	   	if(i == 255 )
		    printf("最后一个: ");
		else
		{
			printf("%d: ",i+1);
		    scanf("%lf",&orgpercent[i]);   
		}
		if(orgpercent[i] == 1.0000000)
		{
		  orgpercent[i] = 0;
		  goto out; //推出输入系统
		}
	   }
	   
out :
	num = i;    //指令个数 
    for( i =0;i <= num ; i ++)
       n = n + orgpercent[i];
    if((n-1.0000000) > (1e-10) && (n-1.0000000) < (1e-10)  )
	 { 
		 printf("你的输入有误!");
		 goto hh;   
	 }

     for(i = 0;i <= num; i++)     
	 {   
		 if(orgpercent[i] >0)
		 m = m +  (-1) * orgpercent[i]*log(orgpercent[i])/log(2) ;

	 }
	 printf("\n\n指令的理想平均长度: %lf\n",m);
     for(i = 0; i <= num ; i++)    
	{ 
		 percent[100+i] = orgpercent[i];

	 }
     Hfuman();  
     Showord(num);          
     Compute(m,num);         
	} //else if
	else if(sle != 'Q' && sle != 'I')
	  printf(" 你的输入有误!!! \n\n\n\n");
	} //while
} //main