霍夫曼算法代码java 编程实现霍夫曼编码

求高手写个关于哈夫曼编码的算法

恩，楼主这个题目相当复杂啊

创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站建设、网站制作、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的青山湖网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

首先读文件，按字符读。一个一个读，统计所有出现字符的频数。

记录到一个链表里吧

第二步，建树。霍夫曼树……复杂程度可想而知。

Huffman 算法

思想： 权大的外结点靠近根， 权小的远离根。

算法： 从m个权值中找出两个最小值W1，W2构成

w

w1 w2 W=W1+W2表通过该结点的频度。

依次往上找……

估计你的100个字符的短文，出现的字符数量估计平均有20个左右，建的树的高度就12就算低的。

3 按结点到跟的距离编码，从左到右编码为0 1 0 1依次进行……

生成霍夫曼编码

把每个字幕的二进制编码记录，打出，这就是密码表

然后对原来的文件进行打印，碰到相应的字母打印出相应的密码（二进制啊，汗……）

估计只有拿到密码才能看明白那一串的01！！

如果某一电文出现的字符为D={M，S，T，A，Q， K} ， 每个字符出现的频率为W={10，29，4，8，15，7}，

则用改算法生成的密码为：

S：0 A：100 M：101 Q：111

T：1100 K：1101

100 1100 101 0 111 0 1101 0 0 密文的含义是：

A T M S Q S K S S

用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;

}

}

JAVA和数据结构大虾们帮下忙： 输入一段文字，该程序可以统计出每个字符出现的次数并对字符进行哈夫曼编码

写给你了，请发JAVA版块

package other;

import java.io.Serializable;

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.LinkedList;

import java.util.List;

import java.util.Map;

/**

* 定义了一种接口，要进行编码的最小单元类必需实现些接口

*

*/

interface CombinableT extends ComparableT {

T combinate(T a, T b);

}

/**

*

* the huffman tree Class 哈夫曼树，包括当前节点数据信息，左节点，右节点信息。

*/

class HuffmanTreeT extends CombinableT implements

ComparableHuffmanTreeT {

/** the root of huffman tree */

private T root;

/** the left node of huffman tree */

private HuffmanTreeT left;

/** the right node of huffman tree */

private HuffmanTreeT right;

/** 哈夫曼编码字符串，如:0000110 */

private String huffmanCodeString = "";

/** 是否对最终生成的哈夫曼进行过编码操作 */

private static boolean isSettedHuffmanCoderString = false;

public T getRoot() {

return root;

}

public void setRoot(T root) {

this.root = root;

}

public HuffmanTreeT getLeft() {

return left;

}

public void setLeft(HuffmanTreeT left) {

this.left = left;

}

public HuffmanTreeT getRight() {

return right;

}

public void setRight(HuffmanTreeT right) {

this.right = right;

}

/**

*

* 重写此方法用于递归合并节点后进行排序操作

*

*/

public int compareTo(HuffmanTreeT o) {

return o.getRoot().compareTo(this.getRoot());

}

public String toString() {

return "the root:" + this.getRoot() + "\r\nthe left:" + this.getLeft()

+ "\r\nthe right:" + this.getRight();

}

/**

*

* 对最终生成的树进行哈夫曼编码，使每个叶子节点生成01的路径编码

*

*/

private void setHuffmanCoderString() {

HuffmanTreeT left = this.getLeft();

// 如果有左节点则在路径中追加"0"

if (left != null) {

left.huffmanCodeString = this.huffmanCodeString + "0";

left.setHuffmanCoderString();// 递归编码

}

HuffmanTreeT right = this.getRight();

// 如果有右节点则在路径中追加"1"

if (right != null) {

right.huffmanCodeString = this.huffmanCodeString + "1";

right.setHuffmanCoderString();// 递归编码

}

}

public void printHuffmanCoderString() {

// 打印最终生成树的哈夫曼编码前要进行编码操作，

// 且此操作只执行一次，所以用全局标识变量判断

if (!HuffmanTree.isSettedHuffmanCoderString) {

this.setHuffmanCoderString();

HuffmanTree.isSettedHuffmanCoderString = true;// 标识已执行过编码

}

// 如果是叶子节点（即要编码的单元），则打印出编码信息，如果是非叶子结点（中间临时生成的节点），则不打印

if (this.left == null this.right == null)

System.out.println("the " + this.getRoot() + " huffmanCoder:"

+ this.huffmanCodeString);

if (this.left != null)

this.left.printHuffmanCoderString();// 递归打印

if (this.right != null)

this.right.printHuffmanCoderString();// 递归打印

}

}

/**

*

* 用类用于生成一个哈夫曼树

*/

class HuffmanTreeFactoryT extends CombinableT {

/** 初始时一个list列表当作要编码的单元类的容器 */

private ListHuffmanTreeT HuffmanTreeCollection;

/**

*

* @param unitClasses

* 待编码的单元类集合

*

*/

public HuffmanTreeFactory(ListT unitClasses) {

if (unitClasses == null || unitClasses.size() == 0)

throw new IllegalArgumentException(

"the unit classes collection can't be empty");

HuffmanTreeCollection = new LinkedListHuffmanTreeT();

// 初始化哈夫曼集合容器

for (T unitClass : unitClasses) {

HuffmanTreeT huffmanTree = new HuffmanTreeT();

huffmanTree.setRoot(unitClass);

huffmanTree.setLeft(null);

huffmanTree.setLeft(null);

HuffmanTreeCollection.add(huffmanTree);

}

Collections.sort(HuffmanTreeCollection);

}

/**

* 将待编码的哈夫曼集合处理成只含有一个元素的集合，则这最后一个元素 即为最终生成的哈夫曼树

*/

private void generateHuffmanTree() {

while (true) {

if (HuffmanTreeCollection == null

|| HuffmanTreeCollection.size() = 1)

break;

// 处理之前一定要重新排序，这是哈夫曼编码的关键原理

Collections.sort(HuffmanTreeCollection);

HuffmanTreeT huffmanTreeOne = HuffmanTreeCollection.remove(0);

HuffmanTreeT huffmanTreeTwo = HuffmanTreeCollection.remove(0);

HuffmanTreeT huffmanTreeNew = new HuffmanTreeT();

// 将集合中前面两个元素合并成一个元素插到集合中去

// 并将第一个元素和第二个元素分别作为新元素的左，右节点

huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().combinate(

huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));

huffmanTreeNew.setLeft(huffmanTreeOne);

huffmanTreeNew.setRight(huffmanTreeTwo);

HuffmanTreeCollection.add(huffmanTreeNew);

}

}

/**

*

*

*

* @return 生成最终的哈夫曼树

*

*/

public HuffmanTreeT getHuffmanTree() {

generateHuffmanTree();

return this.HuffmanTreeCollection.get(0);

}

}

/**

* 自定义一个用于测试的单元类

*/

class UnitClass implements Serializable, CombinableUnitClass {

/** 出现概率数据 */

private int rate;

public UnitClass(int rate) {

this.rate = rate;

}

public int getRate() {

return rate;

}

public void setRate(int rate) {

this.rate = rate;

}

/**

* implements thid compartTo() in order to sort the

*

* collection stored from unitclass

*/

public int compareTo(UnitClass o) {

return o.getRate() this.rate ? 1 : o.getRate() this.rate ? -1 : 0;

}

public String toString() {

return "the rate is:" + rate;

}

/**

*

* 重写此方法用于哈夫曼编码时可以合并两个分支点信息

*

*/

public UnitClass combinate(UnitClass a, UnitClass b) {

if (a == null || b == null)

return null;

return new UnitClass(a.getRate() + b.getRate());

}

}

public class Test {

public static int counter(String s, char c) {

int count = 0;

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

if (s.charAt(i) == c) {

count++;

}

}

return count;

}

public static void main(String[] args) {

String str = "你好呵呵123abbeab啊";

ListUnitClass l = new ArrayListUnitClass();

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

char c = str.charAt(i);

System.out.println(c + "出现了" + counter(str, c) + "次");

l.add(new UnitClass(c));

}

HuffmanTreeFactoryUnitClass factory = new HuffmanTreeFactoryUnitClass(

l);

factory.getHuffmanTree().printHuffmanCoderString();

}

}