064.哈夫曼编码

举报
C语言与CPP编程 发表于 2022/04/30 22:26:46 2022/04/30
【摘要】 #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; t...

      #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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。