logo资料库

哈夫曼编码算法与分析(java实现).doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.10M 资料格式：doc 举报 版权申诉
第1页 / 共12页
第2页 / 共12页
第3页 / 共12页
第4页 / 共12页
第5页 / 共12页
第6页 / 共12页
第7页 / 共12页
第8页 / 共12页
资料共12页，剩余部分请下载后查看
    算 法 与 分 析 1. 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。给出文件中各个字符出 现的频率，求各个字符的哈夫曼编码方案。 2. 给定带权有向图 G =(V,E)，其中每条边的权是非负实数。另外，还给定 V 中的一个顶 点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上 各边权之和。 3. 设 G =(V,E)是无向连通带权图，即一个网络。E 中每条边(v,w)的权为 c[v][w]。如果 G 的子图 G’是一棵包含 G 的所有顶点的树，则称 G’为 G 的生成树。生成树上各边权的 总和称为该生成树的耗费。在 G 的所有生成树中，耗费最小的生成树称为 G 的最小生成 树。求 G 的最小生成树。 求解问题的算法原理： 1.最优装载哈夫曼编码 1.1 前缀码 对每一个字符规定一个 0,1 串作为其代码，并要求任一字符的代码都不是其它字符代码 的前缀，这种编码称为前缀码。 编码的前缀性质可以使译码方法非常简单。 表示最优前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有 2 个儿子结点。 平均码长定义为： )( )( T cdcf B(T)= Cc f(c):c 的码长，dt(c):c 的深度 使平均码长达到最小的前缀码编码方案称为给定编码字符集 C 的最优前缀码。 1.2 构造哈夫曼编码 哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为哈夫曼编码。 哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树 T。 算法以|C|个叶结点开始，执行|C|-1 次的“合并”运算后产生最终所要求的树 T。 编码字符集中每一字符 c 的频率是 f(c)。以 f 为键值的优先队列 Q 用在贪心选择时有 效地确定算法当前要合并的 2 棵具有最小频率的树。一旦 2 棵具有最小频率的树合并后，产 生一棵新的树，其频率为合并的 2 棵树的频率之和，并将新树插入优先队列 Q。经过 n-1 次 的合并后，优先队列中只剩下一棵树，即所要求的树 T。 可用最小堆实现优先队列 Q。 2.单源最短路径 Dijkstra 算法是解单源最短路径问题的贪心算法。 其基本思想是，设置顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集
    合 S 当且仅当从源到该顶点的最短路径长度已知。 初始时，S 中仅含有源。设 u 是 G 的某一个顶点，把从源到 u 且中间只经过 S 中顶点的 路称为从源到 u 的特殊路径，并用数组 dist 记录当前每个顶点所对应的最短特殊路径长度。 Dijkstra 算法每次从 V-S 中取出具有最短特殊路长度的顶点 u，将 u 添加到 S 中，同时对数 组 dist 作必要的修改。一旦 S 包含了所有 V 中顶点，dist 就记录了从源到所有其它顶点之 间的最短路径长度。 3.最小生成树 设 G=(V,E)是连通带权图，V={1,2,…,n}。 构造 G 的最小生成树的 Prim 算法的基本思想是：首先置 S={1}，然后，只要 S 是 V 的 真子集，就作如下的贪心选择：选取满足条件 i∈S，j∈V-S，且 c[i][j]最小的边，将顶点 j 添加到 S 中。这个过程一直进行到 S=V 时为止。 在这个过程中选取到的所有边恰好构成 G 的一棵最小生成树。 利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合 T 始终包含 G 的某棵 最小生成树中的边。因此，在算法结束时，T 中的所有边构成 G 的一棵最小生成树。 编程实现： 1.最优装载哈夫曼编码 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Huffman { private List nums; private List numsMo; private List trees; private String temp; public Huffman() { nums = new ArrayList(); numsMo = new ArrayList(); trees = new ArrayList(); temp=""; } public void addNums() {// 给定一组数 System.out.println("请输入一组数，中间用空格分隔："); Scanner sca = new Scanner(System.in);
    String str = sca.nextLine(); String[] strs = str.split(" "); for (int i = 0; i < strs.length; i++) { nums.add(Double.parseDouble(strs[i])); numsMo.add(Double.parseDouble(strs[i])); } } public void compareNum(List nums,List trees) {// 递 归算法 double[] min = new double[2]; if(nums.size()>1){ min = minTwo(nums); Tree t = new Tree(); nums.remove(Double.valueOf(min[0])); nums.remove(Double.valueOf(min[1])); nums.add(min[0]+min[1]); trees.add(t); compareNum(nums,trees); } } public void print(double num) {// 递归打印编码 for(Tree t : trees){ if(num == t.getRchild()){ temp = 1+temp; print(t.getParents()); break; }else if(num == t.getRchild()){ temp = 0+temp; print(t.getParents()); break; } } } public void write(double d){ temp =" ";
    System.out.print(d+" : "); System.out.print(d); System.out.print(temp); System.out.println("码长："+temp.length()); } public double[] minTwo(List nums) {// 在一组数中选则最小的 两个，按递增排序返回 Double temp = 0.0; for (int j = 0; j < 2; j++) { for (int i = 1; i < nums.size(); i++) { if (nums.get(i - 1) < nums.get(i)) { temp = nums.get(i); nums.set(i, nums.get(i - 1)); nums.set(i - 1, temp); } } } double[] n = {nums.get(nums.size()-1),nums.get(nums.size()-2)}; return n; } public void start(){ addNums(); compareNum(nums,trees); while(numsMo.size()>1){ double[] mins = minTwo(numsMo); if(mins[0]!=mins[1]){ numsMo.remove(Double.valueOf(mins[0])); write(mins[0]); } } if(!numsMo.isEmpty()){ write(numsMo.get(0)); }
    } public static void main(String[] args){ new Huffman().start(); } } 2.单源最短路径 public class Xl { []prev) {//单源最短路径问题的Dijkstra算法 int n=dist.length-1; if (v<1 || v>n) return; boolean[] s=new boolean[n+1]; //初始化 for (int i=1;i<=n;i++) { public static void dijkstra(int v,float[][] a,float[] dist,int dist[i]=a[v][i]; s[i]=false; if (dist[i]==Float.MAX_VALUE) prev[i]=0; else prev[i]=v; } dist[v]=0;s[v]=true; for (int i=1;i
    public static void main(String args[]) { float max=Float.MAX_VALUE; float[][] a=new float[][]{{0,0,0,0,0,0}, {0,max,10,max,15,50}, {0,max,max,30,max,max}, {0,max,max,max,max,10}, {0,max,max,5,max,25}, {0,max,max,max,max,max}}; int v=1; int n=5; float[] dist=new float[n+1]; int[] prev=new int[n+1]; dijkstra(v,a,dist,prev); for (int i=1;i<=n;i++) if (i!=v) System.out.println(v+"->"+i+" : "+dist[i]); } } 3.最小生成树 public class EdgeNode implements Comparable { float weight; int u,v; EdgeNode(int uu,int vv,float ww) { u=uu; v=vv; weight=ww; } public int compareTo(Object x) { double xw=((EdgeNode)x).weight; if (weight
    unionTree=new Tree[n+1]; root=new Tree[n+1]; for (int i=1;i<=n;i++) { unionTree[i]=new Tree(); unionTree[i].node=i; root[i]=unionTree[i]; } this.n=n; } public int find(int nodeindex) { if (nodeindex>n || nodeindex<1) return -1; Tree temp=unionTree[nodeindex]; while (temp.upper!=null) temp=temp.upper; return temp.node; } public void union(int a,int b) { Tree newtree=new Tree(); newtree.node=root[a].node; root[a].upper=newtree; root[a]=newtree; root[b].upper=newtree; root[b]=null; } } public class MinHeap { static Comparable[] heap; static int Len; public MinHeap() { heap=null; Len=0; } public MinHeap(int n) { heap=new Comparable[n]; Len=0; } /* 初始化堆结构 */ public void initialize(Comparable[] comp, int n) { if (heap==null || heap.length
    Len=n; for (int i=0;i0 && heap[j].compareTo(heap[j/2])==-1) { Comparable temp=heap[j]; heap[j]=heap[j/2]; heap[j/2]=temp; j=j/2; } } } /* 输出最小元素，并重建堆 */ public Comparable removeMin() { Comparable Min=heap[0]; heap[0]=heap[Len-1]; Len--; int j=0; while (j=Len)) // 如果heap[j*2]最小 Comparable temp=heap[j]; heap[j]=heap[j*2]; heap[j*2]=temp; j=j*2; } else if (j*2+1=0) // 如 果 && heap[j*2+1]最小 { { Comparable temp=heap[j]; heap[j]=heap[j*2+1]; heap[j*2+1]=temp; j=j*2+1; } else break;
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料