网站建设浦东,网站排名监控工具,做胃镜多少钱那好天津津门网站a,wordpress本地优化加速版题目#xff1a; 哈夫曼编码大全 描述#xff1a; 关于哈夫曼树的建立#xff0c;编码#xff0c;解码。
输入 第一行输入数字N#xff0c;代表总共有多少个字符以及权值 第二第三行分别是一行字符串#xff0c;以及每个字符对应的权值 接下来输入一个数M#xff0c;表…题目 哈夫曼编码大全 描述 关于哈夫曼树的建立编码解码。
输入 第一行输入数字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();}}
}
