064.哈夫曼编码

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      #define MAX 1000
     
    
   

    

     

    
    

     

      #define MAXSYMBS 30
     
    
   

    

     

    
    

     

      #define MAXNODE 59
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
  int weight;
     
    
   

    

     

    
    

     
  int flag;
     
    
   

    

     

    
    

     
  int parent;
     
    
   

    

     

    
    

     
  int lchild;
     
    
   

    

     

    
    

     
  int rchild;
     
    
   

    

     

    
    

     

      }huffnode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
  int bits[MAXSYMBS];
     
    
   

    

     

    
    

     
  int start;
     
    
   

    

     

    
    

     

      }huffcode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	huffnode huff_node[MAXNODE];
     
    
   

    

     

    
    

     

          huffcode huff_code[MAXSYMBS],cd;
     
    
   

    

     

    
    

     
    int i,j,m1,m2,x1,x2,n,c,p;
     
    
   

    

     

    
    

     

      /* char symbs[MAXSYMBS],symb; */
     
    
   

    

     

    
    

     
    /*数组huff_node初始化*/
     
    
   

    

     

    
    

     
    clrscr();
     
    
   

    

     

    
    

     
	printf("please input the leaf num of tree:\n");
     
    
   

    

     

    
    

     
    scanf("%d",&n);
     
    
   

    

     

    
    

     
    for(i=0;i<2*n-1;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		huff_node[i].weight=0;
     
    
   

    

     

    
    

     

              huff_node[i].parent=0;
     
    
   

    

     

    
    

     

      		huff_node[i].flag=0;
     
    
   

    

     

    
    

     

      		huff_node[i].lchild=-1;
     
    
   

    

     

    
    

     

              huff_node[i].rchild=-1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	printf("please input the weight of every leaf\n");
     
    
   

    

     

    
    

     
    for(i=0;i<n;i++)
     
    
   

    

     

    
    

     
        scanf("%d",&huff_node[i].weight);
     
    
   

    

     

    
    

     

      /*构造哈夫曼树*/
     
    
   

    

     

    
    

     
    for(i=0;i<n-1;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

              m1=m2=MAX;
     
    
   

    

     

    
    

     

              x1=x2=0;
     
    
   

    

     

    
    

     
        for(j=0;j<n+i;j++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
            if (huff_node[j].weight<m1&&huff_node[j].flag==0)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

      			    m2=m1;
     
    
   

    

     

    
    

     

                      x2=x1;
     
    
   

    

     

    
    

     

                      m1=huff_node[j].weight;
     
    
   

    

     

    
    

     

                      x1=j;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
            else if (huff_node[j].weight<m2&&huff_node[j].flag==0)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

      			    m2=huff_node[j].weight;
     
    
   

    

     

    
    

     

                      x2=j;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

              huff_node[x1].parent=n+i;    /*将找出的两棵子树合并为一棵子树*/
     
    
   

    

     

    
    

     

              huff_node[x2].parent=n+i;
     
    
   

    

     

    
    

     

              huff_node[x1].flag=1;
     
    
   

    

     

    
    

     

              huff_node[x2].flag=1;
     
    
   

    

     

    
    

     

              huff_node[n+i].weight=huff_node[x1].weight+huff_node[x2].weight;
     
    
   

    

     

    
    

     

              huff_node[n+i].lchild=x1;
     
    
   

    

     

    
    

     

              huff_node[n+i].rchild=x2;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      /*求字符的哈夫曼编码*/
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    for(i=0;i<n;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		cd.start=n;
     
    
   

    

     

    
    

     

              c=i;
     
    
   

    

     

    
    

     

              p=huff_node[c].parent;
     
    
   

    

     

    
    

     
        while(p!=0)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if(huff_node[p].lchild==c)
     
    
   

    

     

    
    

     
            
     
    
   

    

     

    
    

     

      				cd.bits[cd.start]=0;
     
    
   

    

     

    
    

     
            else
     
    
   

    

     

    
    

     

      				cd.bits[cd.start]=1;
     
    
   

    

     

    
    

     

                  cd.start=cd.start-1;
     
    
   

    

     

    
    

     

                  c=p;
     
    
   

    

     

    
    

     

                  p=huff_node[p].parent;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      		cd.start++;
     
    
   

    

     

    
    

     
        for(j=cd.start;j<=n;j++)
     
    
   

    

     

    
    

     

      			huff_code[i].bits[j]=cd.bits[j];
     
    
   

    

     

    
    

     

              huff_code[i].start=cd.start;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
        /*输出字符的哈夫曼编码*/
     
    
   

    

     

    
    

     
    puts("The Hafman code are:");    
     
    
   

    

     

    
    

     
    for(i=0;i<n;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		for(j=huff_code[i].start;j<=n;j++)
     
    
   

    

     

    
    

     
			printf("%10d",huff_code[i].bits[j]);
     
    
   

    

     

    
    

     
        printf("\n");                                                                                                                                                                                                                                                                                                                                                                                                                                      
     
    
   

    

     

    
    

     
		
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	puts("Press any key to quit...");
     
    
   

    

     

    
    

     
	getch();
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：程序员编程指南，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_41055260/article/details/124495723