用Java写一个哈夫曼码的编/译码系统。
时间: 2023-06-26 16:09:37 浏览: 144
好的,下面是Java实现哈夫曼编/译码系统的代码示例:
```java
import java.util.PriorityQueue;
import java.util.Scanner;
public class HuffmanCode {
private static class Node implements Comparable<Node> {
char ch;
int freq;
Node left, right;
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
public boolean isLeaf() {
return left == null && right == null;
}
public int compareTo(Node that) {
return this.freq - that.freq;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入要编码的字符串:");
String input = scanner.nextLine();
int[] freq = new int[256];
for (int i = 0; i < input.length(); i++) {
freq[(int) input.charAt(i)]++;
}
Node root = buildHuffmanTree(freq);
String[] codeTable = buildCodeTable(root);
System.out.println("哈夫曼编码结果为:");
StringBuilder sb = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
sb.append(codeTable[(int) input.charAt(i)]);
}
System.out.println(sb.toString());
System.out.println("哈夫曼解码结果为:");
sb = new StringBuilder();
Node node = root;
for (int i = 0; i < sb.length(); i++) {
char c = sb.charAt(i);
if (c == '0') {
node = node.left;
} else {
node = node.right;
}
if (node.isLeaf()) {
sb.append(node.ch);
node = root;
}
}
System.out.println(sb.toString());
}
private static Node buildHuffmanTree(int[] freq) {
PriorityQueue<Node> pq = new PriorityQueue<>();
for (int i = 0; i < freq.length; i++) {
if (freq[i] > 0) {
pq.offer(new Node((char) i, freq[i], null, null));
}
}
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
pq.offer(new Node('\0', left.freq + right.freq, left, right));
}
return pq.poll();
}
private static String[] buildCodeTable(Node root) {
String[] codeTable = new String[256];
buildCodeTable(root, "", codeTable);
return codeTable;
}
private static void buildCodeTable(Node node, String code, String[] codeTable) {
if (node.isLeaf()) {
codeTable[node.ch] = code;
return;
}
buildCodeTable(node.left, code + "0", codeTable);
buildCodeTable(node.right, code + "1", codeTable);
}
}
```
该程序实现了以下功能:
1. 输入一个字符串,统计每个字符出现的频率;
2. 基于字符频率构建哈夫曼树;
3. 根据哈夫曼树生成每个字符的编码表;
4. 对输入字符串进行编码,输出编码结果;
5. 对编码结果进行解码,输出解码结果。
该程序的时间复杂度为 O(nlogn),其中n为字符串长度。
阅读全文