热门标签 | 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 }

贪心算法 哈夫曼树编码


推荐阅读
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 本文探讨了一种常见的C++面试题目——实现自己的String类。通过此过程,不仅能够检验开发者对C++基础知识的掌握程度,还能加深对其高级特性的理解。文章详细介绍了如何实现基本的功能,如构造函数、析构函数、拷贝构造函数及赋值运算符重载等。 ... [详细]
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 我的读书清单(持续更新)201705311.《一千零一夜》2006(四五年级)2.《中华上下五千年》2008(初一)3.《鲁滨孙漂流记》2008(初二)4.《钢铁是怎样炼成的》20 ... [详细]
  • 本文介绍了如何在AngularJS应用中使用ng-repeat指令创建可单独点击选中的列表项,并详细描述了实现这一功能的具体步骤和代码示例。 ... [详细]
  • 在项目冲刺的最后一天,团队专注于软件用户界面的细节优化,包括调整控件布局和字体设置,以确保界面的简洁性和用户友好性。 ... [详细]
  • JavaScript 页面卸载事件详解 (onunload)
    当用户从页面离开时(如关闭页面或刷新页面),会触发 onunload 事件,此时可以执行预设的脚本。需要注意的是,不同的浏览器对 onunload 事件的支持程度可能有所不同。 ... [详细]
  • 探索Java 11中的ZGC垃圾收集器
    Java 11引入了一种新的垃圾收集器——ZGC,由Oracle公司研发,旨在支持TB级别的内存容量,并保证极低的暂停时间。本文将探讨ZGC的开发背景、技术特点及其潜在的应用前景。 ... [详细]
  • 本文介绍了如何通过安装 sqlacodegen 和 pymysql 来根据现有的 MySQL 数据库自动生成 ORM 的模型文件(model.py)。此方法适用于需要快速搭建项目模型层的情况。 ... [详细]
  • 本文探讨了程序员这一职业的本质,认为他们是专注于问题解决的专业人士。文章深入分析了他们的日常工作状态、个人品质以及面对挑战时的态度,强调了编程不仅是一项技术活动,更是个人成长和精神修炼的过程。 ... [详细]
  • 本文介绍了SIP(Session Initiation Protocol,会话发起协议)的基本概念、功能、消息格式及其实现机制。SIP是一种在IP网络上用于建立、管理和终止多媒体通信会话的应用层协议。 ... [详细]
  • 在日常生活中,支付宝已成为不可或缺的支付工具之一。本文将详细介绍如何通过支付宝实现免费提现,帮助用户更好地管理个人财务,避免不必要的手续费支出。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
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社区 版权所有