[求助]哈夫曼编码 JAVA语言版

各位大哥大姐，帮帮我啊，谢谢
yu_tingting213@126.com
----------------解决方案--------------------------------------------------------

给你转贴个！这种东西下次建议你去搜索下先！
package hartech.kids.huffman;

/**
* <p>Title: 哈夫曼编/译码器</p>
*
* <p>Description:
* 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
* 但是，这要求在发送端通过一个编码系统对待传数据预先编码，
* 在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），
* 每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个哈夫曼码的编／译码系统。
* </p>
*
* <p>Website: www.hartech.cn </p>
* <p>Page: http://www.hartech.cn/blog/blogview.asp?logID=87 </p>
* <p>Date: 2006-09-05 </p>
*/
public class Huffman {

class Elem {
char chara;
int weight;
int parent;
int lchild;
int rchild;
public Elem(char c, int w, int p, int l, int r) {
chara = c;
weight = w;
parent = p;
lchild = l;
rchild = r;
}
}

// 哈夫曼树
private Elem[] huffmanTree;
// 哈夫曼编码表
private String[] huffmanCode;
// 字符个数
int charNum;

// 给出 in 构造哈夫曼树 huffmanTree、哈夫曼编码表huffmanCode
// in 格式为{'字符1',对应权值,'字符2',对应权值, ...}
public Huffman(char[] in) {
if (in == null || in.length == 0 || in.length % 2 != 0) {
System.err.println("dd");
return;
}
charNum = in.length / 2;
// 0 单元不用，要用到 0 来标记是否有孩子、父亲
huffmanTree = new Elem[charNum * 2];
// 初始化
for (int i = 1; i < charNum + 1; i++) {
huffmanTree[i] = new Elem(in[ (i - 1) * 2], in[i * 2 - 1], 0, 0, 0);
}
for (int i = charNum + 1; i < charNum * 2; i++) {
huffmanTree[i] = new Elem( (char) 0, 0, 0, 0, 0);
}

// 构造哈夫曼树
huffmanTree[0] = new Elem( (char) 0, Integer.MAX_VALUE, 0, 0, 0);
int minNo1, minNo2;
for (int i = charNum + 1; i < charNum * 2; i++) {
// 找出weight最小且无父节点的两个
minNo1 = 0;
minNo2 = 0;
for (int j = 1; j < i; j++) {
if (huffmanTree[j].parent == 0) {
if (huffmanTree[j].weight < huffmanTree[minNo1].weight ||
huffmanTree[j].weight < huffmanTree[minNo2].weight) {
if (huffmanTree[minNo1].weight < huffmanTree[minNo2].weight) {
minNo2 = j;
}
else {
minNo1 = j;
}
}
}
}

huffmanTree[minNo1].parent = i;
huffmanTree[minNo2].parent = i;
// 保持叶子节点为父节点的左孩，如书上图6.26
if (minNo1 <= charNum) {
huffmanTree[i].lchild = minNo1;
huffmanTree[i].rchild = minNo2;
}
else {
huffmanTree[i].lchild = minNo2;
huffmanTree[i].rchild = minNo1;
}
huffmanTree[i].weight = huffmanTree[minNo1].weight +
huffmanTree[minNo2].weight;
}

// 求出每个字符编码，从叶子到根，保存至 huffmanCode
huffmanCode = new String[charNum + 1];
char[] temp = new char[charNum + 1];
int start, pa, ch;
for (int i = 1; i <= charNum; i++) {
start = charNum;
ch = i;
pa = huffmanTree[i].parent;
while (pa != 0) {
if (huffmanTree[pa].lchild == ch) {
temp[start] = '0';
}
else {
temp[start] = '1';
}
start--;
ch = pa;
pa = huffmanTree[pa].parent;
}
huffmanCode[i] = String.valueOf(temp, start + 1, charNum - start);
}
}

// 返回给定字符串的哈夫曼代码，对于本树中无记录的字符则直接插入到原对应位置
String toCodes(String in) {
StringBuffer out = new StringBuffer();
char c;
int j;
for (int i = 0; i < in.length(); i++) {
c = in.charAt(i);
j = 1;
while (huffmanTree[j].chara != c && j <= charNum) {
j++;
}
if (j <= charNum) {
out.append(huffmanCode[j]);
}
else {
out.append(c);
}
}
return out.toString();
}

// 对给定哈夫曼码译码，对于非 1、0 的字符直接插入到原对应位置
String toChars(String in) {
StringBuffer out = new StringBuffer();
// 指向树根
int point = charNum * 2 - 1;
char c;
for (int i = 0; i < in.length(); i++) {
c = in.charAt(i);
if (c == '0') {
point = huffmanTree[point].lchild;
}
else if (c == '1') {
point = huffmanTree[point].rchild;
}
else {
out.append(c);
continue;
}
// 为叶子
if (point <= charNum) {
out.append(huffmanTree[point].chara);
point = charNum * 2 - 1;
}
}
return out.toString();
}

// 打印哈夫曼树
public String printTree() {
StringBuffer out = new StringBuffer();
out.append("No.\t" + "Char\t" + "Weight\t" + "Parent\t" + "Lchild\t" +
"Rchild" + "\r\n\r\n");
for (int i = 1; i < charNum * 2; i++) {
out.append("[" + i + "]\t" + huffmanTree[i].chara + "\t" +
huffmanTree[i].weight + "\t" +
huffmanTree[i].parent + "\t" + huffmanTree[i].lchild + "\t" +
huffmanTree[i].rchild + "\r\n");
}
return out.toString();
}

// 打印出所有编码
public String printCodes() {
StringBuffer out = new StringBuffer();
int value = 0;
out.append("No.\t" + "Char\t" + "Code" + "\r\n\r\n");
for (int i = 1; i < charNum + 1; i++) {
out.append("[" + i + "]\t" + huffmanTree[i].chara + "\t" + huffmanCode[i] +
"\r\n");
value += huffmanCode[i].length() * huffmanTree[i].weight;
}
out.append("\r\n总带权路径长度为：\t" + value + "\r\n");
return out.toString();
}

public static void main(String[] args) {
// test：

// 词频表
char[] in = {
' ', 186, 'a', 64, 'b', 13, 'c', 22, 'd', 32, 'e', 103, 'f', 21, 'g',
15, 'h', 47, 'i', 57, 'j', 1, 'k', 5, 'l', 32, 'm', 20, 'n', 57, 'o',
63, 'p', 15, 'q', 1, 'r', 48, 's', 51, 't', 80, 'u', 23, 'v', 8, 'w',
18, 'x', 1, 'y', 16, 'z', 1};

Huffman huffman = new Huffman(in);
huffman.printTree();
huffman.printCodes();

// 编码：
// 输出：0010111010101101000010101110001000101111100011000111000010101101
// 000001110010100000001111011000110100100110010100010100
String code = huffman.toCodes("this program is my favorite");

// 译码：
// 输出：this program is my favorite
huffman.toChars(code);
}
}

----------------解决方案--------------------------------------------------------