当前位置：首页 > news >正文

第八题、哈夫曼编码大全

news 2025/8/26 23:47:59

题目：哈夫曼编码大全
描述：
关于哈夫曼树的建立，编码，解码。

输入
第一行输入数字N，代表总共有多少个字符以及权值
第二第三行分别是一行字符串，以及每个字符对应的权值
接下来输入一个数M，表示接下来有M行字符串，要求你对每个字符串进行编码
再输入一个数X，表示接下来有X行编码，要求你对每行编码进行解码

输出
第一行输出所有节点的权重
接下来输出N行，每行以 “a:001”的格式输出每个字符对应的编码
接着输出M行，对输入的字符串的编码结果
最后，输出X行的解码结果
输入样例

6
abcdef
50 10 5 5 20 10
2
abcdef
defabaabbc
2
011001100100110110101101100
1100011000110101100101100

输出样例

50 10 5 5 20 10 10 20 30 50 100
a:0
b:100
c:1100
d:1101
e:111
f:101
010011001101111101
11011111010100001001001100
accbdfadb
cacadacfb

参考：
本题代码请删除所有中文（包括注释），否则编译错误，无法通过

import java.util.*;public class Main {private static class Node{int value, lchild, rchild, parent;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();String str = sc.next();Node[] hfm = new Node[2 * n - 1];for (int i = 0; i < n; i++) {hfm[i] = new Node();hfm[i].value = sc.nextInt();}for (int i = 0; i < n - 1; i++) {// l1 记录最小叶节点下标，l2 记录次小叶节点下标int l1 = -1, l2 = -1;for (int j = 0; j < n + i; j++) {if (hfm[j].parent == 0 && (l1 == -1 || hfm[j].value < hfm[l1].value)) {l2 = l1;l1 = j;} else if (hfm[j].parent == 0 && (l2 == -1 || hfm[j].value < hfm[l2].value)) {l2 = j;}}hfm[n + i] = new Node();hfm[n + i].value = hfm[l1].value + hfm[l2].value;hfm[n + i].lchild = l1;hfm[n + i].rchild = l2;hfm[l1].parent = hfm[l2].parent = n + i;}// 输出所有节点权重for (int i = 0; i < 2 * n - 1; i++) {System.out.print(hfm[i].value + " ");}System.out.println();// 对每个字符编码String[] code = new String[n];for (int i = 0; i < n; i++) {StringBuilder sb = new StringBuilder();int child = i, parent = hfm[i].parent;while (parent != 0) {if (hfm[parent].lchild == child) {sb.append('0');} else {sb.append('1');}child = parent;parent = hfm[parent].parent;}code[i] = String.valueOf(sb.reverse());}// 输出字符的编码for (int i = 0; i < n; i++) {System.out.println(str.charAt(i) + ":" + code[i]);}// 对字符串编码int m = sc.nextInt();for (int i = 0; i < m; i++) {String s = sc.next();for (int j = 0; j < s.length(); j++) {int id = str.indexOf(s.charAt(j));System.out.print(code[id]);}System.out.println();}// 对字符串解码int x = sc.nextInt();for (int i = 0; i < x; i++) {String s = sc.next();int now = 0;while (now < s.length()) {for (int j = 0; j < n; j++) {int idx = s.indexOf(code[j], now);if (idx == now) {now += code[j].length();System.out.print(str.charAt(j));break;}}}System.out.println();}}
}