使用java设计一个简单的哈夫曼编码/译码系统,系统应具有如下功能: 1、接收原始数据。 从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树(输出哈弗曼树的存储结构的终态)。 2、编码 利用已建好的哈弗曼树,对输入的正文进行编码,存储编码结果。 3、译码 利用编码后的结果进行译码,存储译码结果。 4、打印编码规则 即字符与编码的一一对应关系。 5、打印哈夫曼树 将已创建的哈弗曼树输出到显示器上。
时间: 2024-02-25 12:58:10 浏览: 78
好的,以下是一个简单的哈夫曼编码/译码系统的 Java 实现。代码中有注释说明每个方法的功能,您可以根据自己的需要进行修改和优化。
```java
import java.util.*;
public class HuffmanCode {
private static Map<Character, String> codeTable = new HashMap<>(); // 储存字符与编码的映射表
private static Node root = null; // 哈夫曼树的根节点
// 定义哈夫曼树的节点类
private static class Node implements Comparable<Node> {
int weight;
Node left, right;
public Node(int weight) {
this.weight = weight;
}
public Node(int weight, Node left, Node right) {
this.weight = weight;
this.left = left;
this.right = right;
}
// 根据节点的权值进行排序
public int compareTo(Node o) {
return this.weight - o.weight;
}
}
// 读取输入的字符集大小n,以及n个字符和n个权值,建立哈夫曼树
private static void buildHuffmanTree(Scanner scanner) {
int n = scanner.nextInt();
PriorityQueue<Node> pq = new PriorityQueue<>();
// 将字符和权值分别加入优先队列中
for (int i = 0; i < n; i++) {
char c = scanner.next().charAt(0);
int weight = scanner.nextInt();
pq.add(new Node(weight));
}
// 通过优先队列构建哈夫曼树
while (pq.size() > 1) {
Node left = pq.poll();
Node right = pq.poll();
Node parent = new Node(left.weight + right.weight, left, right);
pq.add(parent);
}
root = pq.poll();
}
// 递归地遍历哈夫曼树,生成字符和编码的映射表
private static void generateCodeTable(Node node, String code) {
if (node.left == null && node.right == null) {
codeTable.put((char) node.weight, code);
} else {
generateCodeTable(node.left, code + "0");
generateCodeTable(node.right, code + "1");
}
}
// 利用已建好的哈夫曼树,对输入的正文进行编码,存储编码结果
private static String encode(String text) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < text.length(); i++) {
char c = text.charAt(i);
sb.append(codeTable.get(c));
}
return sb.toString();
}
// 利用编码后的结果进行译码,存储译码结果
private static String decode(String encodedText) {
StringBuilder sb = new StringBuilder();
Node node = root;
for (int i = 0; i < encodedText.length(); i++) {
char c = encodedText.charAt(i);
if (c == '0') {
node = node.left;
} else {
node = node.right;
}
if (node.left == null && node.right == null) {
sb.append((char) node.weight);
node = root;
}
}
return sb.toString();
}
// 打印编码规则,即字符与编码的一一对应关系
private static void printCodeTable() {
for (Map.Entry<Character, String> entry : codeTable.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
}
// 打印哈夫曼树
private static void printHuffmanTree(Node node, int depth) {
if (node == null) {
return;
}
printHuffmanTree(node.right, depth + 1);
for (int i = 0; i < depth; i++) {
System.out.print(" ");
}
if (node.left != null || node.right != null) {
System.out.println(node.weight + "*");
} else {
System.out.println(node.weight);
}
printHuffmanTree(node.left, depth + 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
buildHuffmanTree(scanner);
generateCodeTable(root, "");
printCodeTable();
printHuffmanTree(root, 0);
String text = "hello world";
String encodedText = encode(text);
System.out.println(encodedText);
String decodedText = decode(encodedText);
System.out.println(decodedText);
}
}
```
阅读全文