java的huffman实现的简单介绍

本文目录一览：

• 1、Java实现哈夫曼算法，运行出现问题，求帮助，在线等！！！
• 2、.’ title=’数据结构程序作业 Huffman编码 是java版的哈 求帮忙呀 ~>.’>数据结构程序作业 Huffman编码 是java版的哈 求帮忙呀 ~>.
• 3、用JAVA实现HUFFMAN算法 1 HUFFMAN算法原理 2 流程图 3 用JAVA语言编写代码
• 4、到底什么是哈夫曼树啊，求例子
• 5、Java中Huffman问题
• 6、用java实现哈夫曼编码

Java实现哈夫曼算法，运行出现问题，求帮助，在线等！！！

可以在Dog与Cat类中重写Animal中的animalDo方法，通过调用animalDo方法，

然后会自动根据不同的实例调用不同类中的方法（多态知识）。

.’>数据结构程序作业 Huffman编码 是java版的哈 求帮忙呀 ~>.

import java.util.Random;class HuffmanTree

{

Node[] nodes;

HuffmanTree(Node[] nodes) {

this.nodes = nodes;

}

public static Node buildTree(Node[] nodes, int end) {

sort(nodes,end); // 根据树的权值由小到大排序

// 取出取值最小的两棵树

Node first = nodes[0];

Node second = nodes[1];

int data = first.data + second.data;

nodes[0] = new Node(data, first, second); //把前两棵树结合为新的树放到第一位

if (end == 1)

{

return nodes[0];

} else

{

for (int i = 1; i end-1 ; i++)

{

nodes[i] = nodes[i + 1]; // 将原数组的第三个以后的树前移一位

}

int len = end – 1;

return buildTree(nodes, len);

}

}

public static void sort(Node[] nodes,int end) {

for (int i = 1; i end; i++)

{

for (int j = 0; j i; j++)

{

if (nodes[j].data nodes[i].data)

{

Node temp = nodes[j];

nodes[j] = nodes[i];

nodes[i] = temp;

}

}

}

}

static String code = “”; // 记录递归路径 static String data = “”;

static String str = “”;

public static void recurse(Node node) {

if (node.data != null)

{

str += ” ” + node.data;

}

if (node.left != null)

{

code += “0”;

recurse(node.left);

}

if (node.right != null)

{

code += “1”;

recurse(node.right);

}

if (node.right == null node.left == null) // 递归达到叶节点取出code

{

System.out.println(node.data + ” : ” + code);

}

if (code.length() = 1)

{

code = code.substring(0, code.length() – 1); // 去掉code最后一位

}

}

public static void main(String[] args) {

Node[] nodes = new Node[50]; // 免得插入这么多字母 我这里就不一一列举了 你只需改一下这个数组 里面装26个字母的权值， 如果要带字母就在Node加一个成员变量就可以了 for (int i =0;i50 ;i++ )

{

Random r = new Random();

int n = r.nextInt(26);

nodes[i]=new Node(n,null,null);

}

Node n = buildTree(nodes,49);

recurse(n);

System.out.println(“前序输出” + str);

}

}

class Node{

Integer data;

Node left;

Node right;

Node(Integer data, Node left, Node right) {

this.data = data;

this.left = left;

this.right = right;

}

}

用JAVA实现HUFFMAN算法 1 HUFFMAN算法原理 2 流程图 3 用JAVA语言编写代码

import java.util.*;

class HuffmanCode{

String name;

double weight;

int lc,rc,pa;

public HuffmanCode(){

name=””;

weight=0;

lc=-1;rc=-1;pa=-1;

}

}

public class Huffman {

HuffmanCode[] codes;

String[] huffstring;

StringBuffer buffer=new StringBuffer();

public Huffman(String s) {

for(int i=0;is.length();i++){

if(buffer.indexOf(s.substring(i,i+1))==-1){

buffer.append(s.charAt(i));

}

}

System.out.println(“字母：”+buffer);

huffstring=new String[buffer.length()];

codes=new HuffmanCode[2*buffer.length()-1];

for(int i=0;i2*buffer.length()-1;i++)

codes[i]=new HuffmanCode();

for(int i=0;ibuffer.length();i++){

codes[i].name=buffer.substring(i,i+1);

codes[i].weight=haveNum(buffer.charAt(i),s);

}

getHuffstring();

getCode(2*buffer.length()-2,huffstring,””);

//for(int i=0;icodes.length;i++){

// System.out.println(“”+i+”:”+codes[i].name+codes[i].weight+” “+codes[i].lc+” “+codes[i].rc+” “+codes[i].pa);

//}

for(int i=0;ihuffstring.length;i++){

System.out.println(codes[i].name+” code:”+huffstring[i]);

}

System.out.println(“编码：”+getHuffmanCode(s));

System.out.println(“平均码长为：”+getLength());

}

public double getLength(){

double n=0;

for(int i=0;ibuffer.length();i++){

n+=huffstring[i].length();

}

return n/buffer.length();

}

public String getHuffmanCode(String s){

StringBuffer buf=new StringBuffer();

for(int i=0;is.length();i++){

buf.append(getEachCode(s.substring(i,i+1)));

}

return buf.toString();

}

public String getEachCode(String name){

for(int i=0;ibuffer.length();i++){

if(name.equals(codes[i].name)){

return huffstring[i];

}

}

return “”;

}

public void getCode(int n,String[] thecodes,String thebuffer){

if(nthecodes.length){

thecodes[n]=thebuffer;

return;

}

getCode(codes[n].lc,thecodes,thebuffer+”0″);

getCode(codes[n].rc,thecodes,thebuffer+”1″);

}

public void getHuffstring(){

int[] twos={0,0};

for(int i=buffer.length();i2*buffer.length()-1;i++){

twos=findLastTwo(0,i);

codes[i].lc=twos[0];

codes[i].rc=twos[1];

codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;

}

}

public int[] findLastTwo(int start,int end){

double[] weights={1.0,1.0};

int[] t={-1,-1};

for(int i=start;iend;i++){

if(codes[i].pa!=-1)continue;

if(weights[0]codes[i].weight){

weights[0]=codes[i].weight;

t[1]=t[0];

t[0]=i;

}

else if(weights[1]codes[i].weight){

weights[1]=codes[i].weight;

t[1]=i;

}

}

codes[t[0]].pa=end;

codes[t[1]].pa=end;

return t;

}

public double haveNum(char c,String s){

double n=0;

for(int i=0;is.length();i++){

if(c==s.charAt(i))n++;

}

return n/s.length();

}

public static void main (String[] args) {

System.out.print(“输入编码字符串：”);

Scanner sr=new Scanner(System.in);

new Huffman(sr.nextLine());

}

}

到底什么是哈夫曼树啊，求例子

哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

例子：

1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

3、从森林中删除选取的两棵树，并将新树加入森林；

4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

扩展资料：

按照哈夫曼编码构思程序流程：

1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；

2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。

3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。

4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可

5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。

参考资料来源:百度百科——哈夫曼树

Java中Huffman问题

这题在实现层面变得和Huffman树没啥关系…

反复取取最小值，使值成为优先级..用优先队列最合适。。可自己把输入方式补上

import java.util.Arrays;

import java.util.PriorityQueue;

public class Test {

   public static void main(String[] args){      

      Integer[] a= {5, 3, 8, 2, 9};

      PriorityQueueInteger q=new PriorityQueueInteger(Arrays.asList(a));

      int cost=0;

      while(q.size()1){

         System.out.println(q); //可删

         int c=q.poll()+q.poll();

         q.offer(c); cost+=c;            

      }

      System.out.println(q); //可删

      System.out.println(cost);      

   }

}

[2, 3, 8, 5, 9]

[5, 5, 8, 9]

[8, 9, 10]

[10, 17]

[27]

59

用java实现哈夫曼编码

只要自己再加个类Tree就可以了。

代码如下：

public class Tree {

double lChild, rChild, parent;

public Tree (double lChild, double rChild, double parent) {

this.lChild = lChild;

this.rChild = rChild;

this.parent = parent;

}

public double getLchild() {

return lChild;

}

public void setLchild(double lChild) {

this.lChild = lChild;

}

public double getRchild() {

return rChild;

}

public void setRchild(double rChild) {

this.rChild = rChild;

}

public double getParents() {

return parent;

}

public void setParents(double root) {

this.parent = root;

}

}