数据结构与算法【Java】08---树结构的实际应用( 九 ) _生活百科

list = new ArrayList<>();//i 可以理解成就是索引,扫描 stringBuilderfor(inti = 0; i < stringBuilder.length(); ) {int count = 1; // 小的计数器boolean flag = true;Byte b = null;while(flag) {//1010100010111...//递增的取出 key 1(1，10,101...匹配)String key = stringBuilder.substring(i, i+count);//i 不动，让count移动，指定匹配到一个字符b = map.get(key);if(b == null) {//说明没有匹配到count++;}else {//匹配到flag = false;}}list.add(b);i += count;//i 直接移动到 count}//当for循环结束后，我们list中就存放了所有的字符"i like like like java do you like a java"//把list 中的数据放入到byte[] 并返回byte b[] = new byte[list.size()];for(int i = 0;i < b.length; i++) {b[i] = list.get(i);}return b;}//使用一个方法，将前面的方法封装起来，便于我们的调用/*** @param bytes 原始的字符串对应的字节数组* @return 是经过赫夫曼编码处理后的字节数组(压缩后的数组)*/private static byte[] huffmanZip(byte[] bytes){List<Node> nodes = getNodes(bytes);//根据nodes创建的赫夫曼树Node huffmanTreeRoot = createHuffmanTree(nodes);//生成对应的赫夫曼编码（根据赫夫曼树）Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);//根据生成的赫夫曼编码来对原始的字节数组进行压缩byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);return huffmanCodeBytes;}//编写一个方法，将字符串对应的byte[] 数组，通过生成的赫夫曼编码表，返回一个赫夫曼编码压缩后的byte[]/**** @param bytes 这是原始的字符串对应的 byte[]* @param huffmanCodes 生成的赫夫曼编码map* @return 返回赫夫曼编码处理后的 byte[]* 举例： String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();* 返回的是字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"* => 对应的 byte[] huffmanCodeBytes，即 8位对应一个 byte,放入到 huffmanCodeBytes* huffmanCodeBytes[0] =10101000(补码) => byte[推导10101000=> 10101000 - 1 => 10100111(反码)=> 11011000（原码）= -88 ]* huffmanCodeBytes[1] = -88*/private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {//1.利用 huffmanCodes 将bytes 转成赫夫曼编码对应的字符串StringBuilder stringBuilder = new StringBuilder();//遍历bytes 数组for(byte b: bytes) {stringBuilder.append(huffmanCodes.get(b));}//System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());//将 "1010100010111111110..." 转成 byte[]//统计返回byte[] huffmanCodeBytes 长度//一句话 int len = (stringBuilder.length() + 7) / 8;int len;if(stringBuilder.length() % 8 == 0) {len = stringBuilder.length() / 8;} else {len = stringBuilder.length() / 8 + 1;}//创建存储压缩后的 byte数组byte[] huffmanCodeBytes = new byte[len];int index = 0;//记录是第几个bytefor (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8String strByte;if(i+8 > stringBuilder.length()) {//不够8位strByte = stringBuilder.substring(i);}else{strByte = stringBuilder.substring(i, i + 8);}//将strByte 转成一个byte,放入到 huffmanCodeByteshuffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);index++;}return huffmanCodeBytes;}//生成赫夫曼树对应的赫夫曼编码//思路://1. 将赫夫曼编码表存放在 Map<Byte,String> 形式//生成的赫夫曼编码表{32（空格）=01, 97（a）=100, 100(...)=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();//2. 在生成赫夫曼编码表示，需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径static StringBuilder stringBuilder = new StringBuilder();//为了调用方便，我们重载 getCodesprivate static Map<Byte, String> getCodes(Node root) {if(root == null) {return null;}//处理root的左子树getCodes(root.left, "0", stringBuilder);//处理root的右子树getCodes(root.right, "1", stringBuilder);return huffmanCodes;}/*** 功能：将传入的node结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCodes集合* @param node传入结点* @param code路径：左子结点是 0, 右子结点 1* @param stringBuilder 用于拼接路径*/private static void getCodes(Node node,String code,StringBuilder stringBuilder){StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);//将code加入到 stringBuilder2 （拼接路径）stringBuilder2.append(code);if (node != null){//如果node等于空，不处理//判断当前node是叶子节点还是非叶子结点if (node.data =https://www.huyubaike.com/biancheng/= null){//非叶子节点//递归处理//向左递归getCodes(node.left,"0", stringBuilder2);//向右递归getCodes(node.right, "1", stringBuilder2);}else {//进入到这里说明是叶子节点，找到了最后huffmanCodes.put(node.data,stringBuilder2.toString());}}}//前序遍历的方法public static void preOrder(Node root){if (root != null){root.preOrder();}else {System.out.println("赫夫曼树为空");}}/**** @param bytes 接收字节数组* @return 返回的就是 List 形式[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],*/private static List<Node> getNodes(byte[] bytes){//1.创建一个ArrayListArrayList<Node> nodes = new ArrayList<>();//遍历bytes,存储每一个byte出现的次数=》map[key,value]HashMap<Byte,Integer> counts = new HashMap<>();for (byte b: bytes) {Integer count = counts.get(b);if (count == null){//Map还没有这个数据counts.put(b,1);}else {counts.put(b,count+1);}}//把每个键值对转成一个Node对象,并加入到nodes集合//遍历mapfor (Map.Entry<Byte,Integer> entry : counts.entrySet()){nodes.add(new Node(entry.getKey(), entry.getValue()));}return nodes;}//通过list创建应的赫夫曼树private static Node createHuffmanTree(List<Node> nodes){

数据结构与算法【Java】08---树结构的实际应用( 九 )

推荐阅读

巨蟹座跟处女座配吗

冷冻的面包吃的时候应该怎么处理冷冻的面包吃的时候应该怎么处理呢

这个肉是什么肉这个多肉是什么

良心建议，双子座如何过好单身生活

北京天马旅行社有限公司_工商信用信息_经营范围期限状态_法人_地址_注册资本_怎么样

冬至可不可以晒衣服冬至可以晒衣服吗

花高额费用存脐带血储存一般多少钱

粽子中腌肉方子肉粽子的肉怎么腌制

都江堰市2023年小升初入学指南都江堰市小升初招生网

冬枣一天吃几个比较好冬枣一天吃多少比较好

请使用微信内浏览器登录什么意思

淘宝技巧步骤如下，淘宝天猫运营流程及规划？

王者荣耀背景修改，王者荣耀实名制弄错了怎么修改？，

描写柳树的诗句碧玉妆成一树高万条垂下绿丝绦

雷颂德名字打分106分

国漫天官赐福让原著粉丝飘了，你认为是尬捧还是真的好看？

白牡丹多肉植物的种植方法

联想手机怎么使用手写输入法

双子座男神养成计划

宁夏理工学院2022年分省分专业招生计划(本科+专科）