<!--[if !supportLists]-->一、<!--[endif]-->什么是链表?
链表是使用指针进行连接的一种数据结构,他可以提供比数组更加灵活的数据存储。
认识一下链表之前,先知道节点。
Class Node { Object data;/用于存储数据; Node next;//指向下一个的指针 }
一、哈夫曼编码
以哈夫曼树─即最优二叉树,路径长度最小的二叉树,经常应用于数据压缩。在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称“熵编码法”),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。这种方法是由Huffman发展起来的。例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。
二、首先,需要一个Class LinkNode;结点类,用于保存节点的数据以及前一个与后一个节点的指针,这在C++中称之为指针,但是Java中是没有指针这个概念的。不过不妨碍理解。建立了一个结点类后,作为他的基础。代码如下:
public class HMF { private LinkNode [] nodes; public HMF(int[] data){ nodes = new LinkNode[data.length]; for(int i=0;i<data.length;i++){ nodes[i]=new LinkNode(); nodes[i].data=data[i]; } } //对节点排序 private void sort(LinkNode [] nodes){ int a= nodes.length; for(int i=0;i<a;i++){ for(int j=0;j<a-i-1;j++){ if(nodes[j].data > nodes[j+1].data){ //交换的不是数据,而是对象本身的位置 LinkNode x =nodes[j]; nodes[j]=nodes[j+1]; nodes[j+1]=x; } } } } //创建哈夫曼树 private LinkNode creatTree(){ LinkNode [] nodes=this.nodes;//临时变量 while(nodes.length>1){ sort(nodes); LinkNode lk0=nodes[0]; LinkNode lk1=nodes[1]; //去最小的两个 LinkNode lkn =new LinkNode(); lkn.data=lk0.data+lk1.data; lkn.left=lk0; lkn.right=lk1; //新建一个小一个单位的数组 LinkNode [] nodes2= new LinkNode[nodes.length-1]; for(int i=2;i<nodes.length;i++){ nodes2[i-2] =nodes[i]; } nodes2[nodes.length-2]=lkn; nodes=nodes2; } return nodes[0]; } // public void Code(){ LinkNode root = this.creatTree(); printTree(root," "); } public void printTree(LinkNode lk,String code){ if(lk!=null){ if(lk.left == null && lk.right == null) System.out.println(lk.data+"的编码是"+code); printTree(lk.left,code+"0"); printTree(lk.right,code+"1"); } } public static void main(String [] args){ int [] test = { 3,5,1,6,2,7} ; HMF hum = new HMF(test); hum.Code(); } }
相关推荐
理解二叉树线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系。二叉树的线索化过程是基于对二叉树进行遍历,而线索二叉树上的线索又为相应的遍历提供了方便
C语言实现的哈夫曼树
c++写的哈夫曼树,用了链表建树,用了stl的优先队列
很好的哈夫曼树基本操作!
图+查找+排序+循环链表+循环链表+数组+广义表+二叉树与树的转换+哈夫曼树
(1) 读入一个 ASCII 文件,统计文档中字符出现的频度,构造哈夫曼树; (2) 在构造好的哈夫曼树中对每个字符进行 Huffman 编码; (3) 要求打印出原始数据、每个字符对应的Huffman 编码和总编码长度。
建立一棵二叉链表树,分别输出此先根、中根和后根遍历序列 将上题编程,实现哈夫曼树的构建和哈夫曼编码的设计
1. 将提供的字符串(自定义字符串)进行排序,获取...5. 直到链表中只剩一个节点时,将此节点赋给哈夫曼树头; 6. 利用创建的哈夫曼树得到编码; 用递归得到叶子节点,由叶子节点追溯到根节点,得到编码后反转顺序;
用c ++建立非链表哈夫曼树 并用哈夫曼树进行编码 和译码
2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3.掌握哈夫曼树与哈夫曼码的基本操作。 二、设计内容和要求 1.输入一个文本,统计各字符出现的频度,输出结果 2.使用二叉链表或三叉链表作存贮结构,构造哈夫曼树 3...
数据结构实验报告 ―― 实验五 简单哈夫曼编/译码的设计与实现 本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在 ... 二、【数据结构设计】 1、构造哈夫曼树时使用静态链表作为哈夫曼树的
构造哈夫曼树时使用静态链表作为哈夫曼树的存储。求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值...
做课设的时候发现网上资料没有用三叉链表动态实现赫夫曼树译码器的资料,自己写了一份,方便大家学习,完全由个人创作。
C代码的哈夫曼树带权值结算 代码可运行结构清晰
2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3.掌握哈夫曼树与哈夫曼码的基本操作。 二、设计内容和要求 1.输入一个文本,统计各字符出现的频度,输出结果 2.使用二叉链表或三叉链表作存贮结构,构造哈夫曼树 3...
编码:利用建立好的哈夫曼树对源文件进行编码,实现 文件压缩,然后将结果以文件形式保存,如编码文件 codefile。 d.译码:利用建立好的哈夫曼树对 codefile 中的代码进行译 码。结果存入译码文件 decofile 中。 e...
实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划)视频
该资源包括了数据结构的课程设计,哈夫曼树的建立,采用链表形式,方便了学生的作业及课程设计
链表HuffmanTree.rar是一个计算机专业源码资料包,包含了用于构建哈夫曼树的链表结构及其相关操作的源代码。哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树,广泛应用于数据压缩和编码领域。这个资料包...