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;

}

}