热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

贪心算法哈夫曼树编码

1#include2#include3#defineN50叶子结点数4#defineM2*N-1树中结点总数5typedefstruct6{7
  1 #include 
  2 #include <string.h>
  3 #define N 50        //叶子结点数
  4 #define M 2*N-1        //树中结点总数
  5 typedef struct
  6 {
  7     char data[5];    //结点值
  8     int weight;        //权重
  9     int parent;        //双亲结点
 10     int lchild;        //左孩子结点
 11     int rchild;        //右孩子结点
 12 } HTNode;
 13 typedef struct
 14 {
 15     char cd[N];        //存放哈夫曼码
 16     int start;
 17 } HCode;
 18 void CreateHT(HTNode ht[],int n)  //由ht的叶子结点构造完整的哈夫曼树
 19 {
 20     int i,k,lnode,rnode;
 21     int min1,min2;
 22     for (i=0;i<2*n-1;i++)            //所有结点的相关域置初值-1
 23         ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
 24     for (i=n;i<2*n-1;i++)            //构造哈夫曼树的分支结点
 25     {
 26         min1=min2=32767;            //lnode和rnode为最小权重的两个结点位置
 27         lnode=rnode=-1;
 28         for (k=0;k<=i-1;k++)        //查找最小和次小的结点
 29             if (ht[k].parent==-1)    //只在尚未构造二叉树的结点中查找
 30             {
 31                 if (ht[k].weight<min1)
 32                 {
 33                     min2=min1;rnode=lnode;
 34                     min1=ht[k].weight;lnode=k;
 35                 }
 36                 else if (ht[k].weight<min2)
 37                 {
 38                     min2=ht[k].weight;rnode=k;
 39                 }
 40             }
 41         ht[lnode].parent=i;ht[rnode].parent=i;    //合并两个最小和次小的结点
 42         ht[i].weight=ht[lnode].weight+ht[rnode].weight;
 43         ht[i].lchild=lnode;ht[i].rchild=rnode;
 44     }
 45 }
 46 void CreateHCode(HTNode ht[],HCode hcd[],int n)    //由哈夫曼树ht构造哈夫曼编码hcd
 47 {
 48     int i,f,c;
 49     HCode hc;
 50     for (i=0;i//根据哈夫曼树构造所有叶子结点的哈夫曼编码
 51     {
 52         hc.start=n;c=i;
 53         f=ht[i].parent;
 54         while (f!=-1)    //循环直到树根结点
 55         {
 56             if (ht[f].lchild==c)    //处理左孩子结点
 57                 hc.cd[hc.start--]=0;
 58             else                    //处理右孩子结点
 59                 hc.cd[hc.start--]=1;
 60             c=f;f=ht[f].parent;
 61         }
 62         hc.start++;        //start指向哈夫曼编码最开始字符
 63         hcd[i]=hc;
 64     }
 65 }
 66 void DispHCode(HTNode ht[],HCode hcd[],int n)    //输出哈夫曼编码
 67 {
 68     int i,k;
 69     int sum=0,m=0,j;
 70     printf("输出哈夫曼编码:\n"); 
 71     for (i=0;i)
 72     {
 73         j=0;
 74         printf("      %s:\t",ht[i].data);
 75         for (k=hcd[i].start;k<=n;k++)
 76         {
 77             printf("%c",hcd[i].cd[k]);
 78             j++;
 79         }
 80         m+=ht[i].weight;
 81         sum+=ht[i].weight*j;
 82         printf("\n");
 83     }
 84     printf("平均长度=%g\n",1.0*sum/m);
 85 }
 86 int main()
 87 {
 88     int n=6,i;
 89     char *str[]={"a","b","c","d","e","f"};
 90     int fnum[]={45,13,12,16,9,5};
 91     HTNode ht[M];
 92     HCode hcd[N];
 93     for (i=0;i)
 94     {
 95         strcpy(ht[i].data,str[i]);
 96         ht[i].weight=fnum[i];
 97     }
 98     CreateHT(ht,n);
 99     CreateHCode(ht,hcd,n);
100     DispHCode(ht,hcd,n);
101     return 1;
102 }

贪心算法 哈夫曼树编码


推荐阅读
  • 单链表的高效遍历及性能优化策略
    本文探讨了单链表的高效遍历方法及其性能优化策略。在单链表的数据结构中,插入操作的时间复杂度为O(n),而遍历操作的时间复杂度为O(n^2)。通过在 `LinkList.h` 和 `main.cpp` 文件中对单链表进行封装,我们实现了创建和销毁功能的优化,提高了单链表的使用效率。此外,文章还介绍了几种常见的优化技术,如缓存节点指针和批量处理,以进一步提升遍历性能。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • 本文详细介绍了使用 Python 进行 MySQL 和 Redis 数据库操作的实战技巧。首先,针对 MySQL 数据库,通过 `pymysql` 模块展示了如何连接和操作数据库,包括建立连接、执行查询和更新等常见操作。接着,文章深入探讨了 Redis 的基本命令和高级功能,如键值存储、列表操作和事务处理。此外,还提供了多个实际案例,帮助读者更好地理解和应用这些技术。 ... [详细]
  • 本文探讨了如何有效地构建和优化微信公众平台账号,涵盖了用户信息管理、内容创作与发布、互动策略及数据分析等方面。通过合理设置用户信息字段,如用户名、昵称、密码、真实姓名和性别等,确保账号的安全性和用户体验。同时,文章还介绍了如何利用微信公众平台的各项功能,提升用户参与度和品牌影响力。 ... [详细]
  • 并发编程入门:初探多任务处理技术
    并发编程入门:探索多任务处理技术并发编程是指在单个处理器上高效地管理多个任务的执行过程。其核心在于通过合理分配和协调任务,提高系统的整体性能。主要应用场景包括:1) 将复杂任务分解为多个子任务,并分配给不同的线程,实现并行处理;2) 通过同步机制确保线程间协调一致,避免资源竞争和数据不一致问题。此外,理解并发编程还涉及锁机制、线程池和异步编程等关键技术。 ... [详细]
  • 在 POJ1651 的乘法谜题挑战中,如果选手按相反顺序选择卡片,即先选 50,再选 20,最后选 1,则最终得分会有所不同。题目要求输入的第一行包含... 改写后的摘要:在 POJ1651 的乘法谜题挑战中,如果选手按照逆序选取卡片,例如依次选择 50、20 和 1,最终的得分将发生变化。题目首先要求输入的第一行包括... ... [详细]
  • 资源管理器的基础架构包括三个核心组件:1)资源池,用于将CPU和内存等资源分配给不同的容器;2)负载组,负责承载任务并将其分配到相应的资源池;3)分类函数,用于将不同的会话映射到合适的负载组。该系统提供了两种主要的资源管理策略。 ... [详细]
  • 在探讨Hibernate框架的高级特性时,缓存机制和懒加载策略是提升数据操作效率的关键要素。缓存策略能够显著减少数据库访问次数,从而提高应用性能,特别是在处理频繁访问的数据时。Hibernate提供了多层次的缓存支持,包括一级缓存和二级缓存,以满足不同场景下的需求。懒加载策略则通过按需加载关联对象,进一步优化了资源利用和响应时间。本文将深入分析这些机制的实现原理及其最佳实践。 ... [详细]
  • 作为软件工程专业的学生,我深知课堂上教师讲解速度之快,很多时候需要课后自行消化和巩固。因此,撰写这篇Java Web开发入门教程,旨在帮助初学者更好地理解和掌握基础知识。通过详细记录学习过程,希望能为更多像我一样在基础方面还有待提升的学员提供有益的参考。 ... [详细]
  • ButterKnife 是一款用于 Android 开发的注解库,主要用于简化视图和事件绑定。本文详细介绍了 ButterKnife 的基础用法,包括如何通过注解实现字段和方法的绑定,以及在实际项目中的应用示例。此外,文章还提到了截至 2016 年 4 月 29 日,ButterKnife 的最新版本为 8.0.1,为开发者提供了最新的功能和性能优化。 ... [详细]
  • DRF框架中Serializer反序列化验证机制详解:深入探讨Validators的应用与优化
    在DRF框架的反序列化验证机制中,除了基本的字段类型和长度校验外,还常常需要进行更为复杂的条件限制校验。通过引入`validators`模块,可以实现自定义校验逻辑,如唯一字段校验等。本文将详细探讨`validators`的使用方法及其优化策略,帮助开发者更好地理解和应用这一重要功能。 ... [详细]
  • 如何高效利用Hackbar插件提升网页调试效率
    通过合理利用Hackbar插件,可以显著提升网页调试的效率。本文介绍了如何获取并使用未包含收费功能的2.1.3版本,以确保在不升级到最新2.2.2版本的情况下,依然能够高效进行网页调试。此外,文章还提供了详细的使用技巧和常见问题解决方案,帮助开发者更好地掌握这一工具。 ... [详细]
  • 题目探讨了在无向图中求解点连通数的问题,具体涉及UVA1660和POJ1966两个经典问题。通过最小割算法的应用,分析了如何高效地确定网络中的关键节点和路径,为电缆电视网络的优化设计提供了理论支持。该研究不仅验证了最小割算法的有效性,还为进一步探索复杂网络的连通性和鲁棒性奠定了基础。 ... [详细]
  • AngularJS 进阶指南:第三部分深入解析
    在本文中,我们将深入探讨 AngularJS 的指令模型,特别是 `ng-model` 指令。`ng-model` 指令用于将 HTML 元素与应用程序数据进行双向绑定,支持多种数据类型验证,如数字、电子邮件地址和必填项检查。此外,我们还将介绍如何利用该指令优化表单验证和数据处理流程,提升开发效率和用户体验。 ... [详细]
  • 在使用 SQL Server 时,连接故障是用户最常见的问题之一。通常,连接 SQL Server 的方法有两种:一种是通过 SQL Server 自带的客户端工具,例如 SQL Server Management Studio;另一种是通过第三方应用程序或开发工具进行连接。本文将详细分析导致连接故障的常见原因,并提供相应的解决策略,帮助用户有效排除连接问题。 ... [详细]
author-avatar
Quan
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有