数据结构和算法笔记.rar

package cn.Huffman; import java.io.UnsupportedEncodingException; import java.util.*; public class helloTree { public static void main(String[] args) throws UnsupportedEncodingException { String str = "I like like like java do you like a java"; byte[] huffman = HuffmanCodes.HuffmanZip(str); System.out.println(Arrays.toString(huffman)); //测试一下我们的转换的二进制 Huffman2.decode(Huffman.huffmanCodes,HuffmanCodes.HuffmanZip(str)); System.out.println(new String(Huffman2.decode(Huffman.huffmanCodes,HuffmanCodes.HuffmanZip(str)))); } } //用来返回我们的要发送编码的数据的类 class HuffmanCodes { /** * * @param str 待处理的数据 * @return 经过处理过后的数组 */ public static byte[] HuffmanZip(String str) { //1、获得数据的字节数组 byte[] bytes = str.getBytes(); //创建一个Huffman来使用其方法 Huffman huffman = new Huffman(); //2、取得返回的数据：就是统计我们字符个数的方法：d： 1, y： 1，u： 1，j：2，v：2，o：2，l：4，k：4，e：4，i：5，a：5，空格：9` List<Node> nodeList = huffman.getNodes(bytes); //3、第三步制造我们的赫夫曼树 Node node = huffman.createHuffman(nodeList); //4、根据我们生成的赫夫曼树来生成赫夫曼表 Huffman.getCodes(node,"",Huffman.huffmanBuilder); //5、然后根据上面生成的表对数据进行压缩 // byte[] bytes1 = Huffman.zip(bytes,Huffman.huffmanCodes); return bytes1; } } //用来解压数据的类:思路如下 //1、将HuffmanCodeBytes 数组[-102, 59, -11, 29, -6, -114, -3, 74, -59, 100, 110, 79, 8, -17, -42, -91, 98, 1] //将上面的数组转换为对应的二进制“xxxxxxxxxx” //2、对照Huffman编码表转换为`I like like 。。。。。。` //3、所以分析后肯定要两个方法 class Huffman2 { /** * 方法一： * @param huffmanCodes 之前讲解的赫夫曼编码表 * @param huffmanBytes 其实就是我们之前压缩过后的byte数组[-102, 59, -11, 29, -6, -114, -3, 74, -59, 100, 110, 79, 8, -17, -42, -91, 98, 1] * @return 就是原来的字符串对应的数组 */ public static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes) { //1、先得到[-102, 59, -11, 29, -6, -114, -3, 74, -59, 100, 110, 79, 8, -17, -42, -91, 98, 1]对应的二进制字符串 StringBuilder stringBuilder = new StringBuilder(); //2、将byte数组转换为二进制的字符串 for (int i = 0; i < huffmanBytes.length; i++) { boolean flag = (i == huffmanBytes.length -1);//用于判断是否为最后一格数 String s = byteToBitString(!flag, huffmanBytes[i]); stringBuilder.append(s); } System.out.println("编码过后的二进制数据为：" + stringBuilder.toString()); //3、好啦，转换好了10011010001110111111010100011101111110101000111011111101010010101100010101100100011011100100111100001000111011111101011010100101011000101 //接下来我们要把二进制字符串进行转换解码：之前我们是 a --> 1001（随便写的），现在要把1001 -->a的一个过程 Map<String,Byte> map = new HashMap<>(); for (Map.Entry<Byte,String> entry: huffmanCodes.entrySet()) { map.put(entry.getValue(),entry.getKey()); } //测试看一下反向是否成功: {01=32, 1110=105, 1000=118, 0010=106, 000=108, 101=97, 1101=101, 0011=111, 1111=107, 10011=73, 11001=121, 10010=100, 11000=117} System.out.println("map = " + map); //4、创建一个集合，存放byte List<Byte> list = new ArrayList<>(); //这里的for循环时不能++的，因为我们在后面是借用count给我们移动 for (int i = 0; i < stringBuilder.length(); ) { //i可以理解为一个索引， int count = 1;//扫描我们的字符串stringBuilder，对应着赫夫曼编码的对应一个数据时，加1，相当于一个计算器 boolean flag = true;// Byte b = null; while (flag) { //取出stringBuilder的一个1或者0 String key = stringBuilder.substring(i,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); } System.out.println(new String()); return b; } /** * 将一个byte转换为一个二进制的的字符串，如果看不懂的话，可以去复习一下二进制源码反码和补码的东西 * @param flag : 标志着是否需要补高位，则是true，如果不需要则是false * @param b 传入的一个byte值 * @return 是该b对应的二进制的字符串（需要注意是补码来操作的），因为之前讲过想我们得到的二进制也就是补码来生成的 */ public static String byteToBitString(boolean flag,byte b) { /*//使用遍变量b int temp = b;//将b转换为int //首先测试一把-1： // 1） System.out.println(Huffman2.byteToBitString((byte) -1));是一个负数的时候：11111111，它本身是11111111111111111111111111111111 // 2） System.out.println(Huffman2.byteToBitString((byte) -1));是一个正数的时候 是直接报错了，这里就有二进制的转换问题了 //所以要针对是正数进行处理一下 temp |= 256;//这样就表示位与（|）运算的，就是要补个最高位，是二进制的一些内容 String str = Integer.toBinaryString(temp);//如果用Integer.toBinaryString(temp)返回的是temp对应的补码：11111111111111111111111111111111 String returnStr = str.substring(str.length() - 8); return returnStr;*/ //所以经过上面的讲解后代码应该这样写 int temp = b; //如果是正数需要补高位 if (flag) { temp |= 256;//即如果是负数不需要补高位 } String str = Integer.toBinaryString(temp); if (flag) { return str.substring(str.length() - 8);////如果是正数的话，位数太多，所以要截取一下：只要前面的几位11111111 } else { return str; } } } //第二就来看这个类 class Huffman { /** 第二步看这个方法 * 将我们数据转化为List的方法要到达这种效果`d： 1, y： 1，u： 1，j：2，v：2，o：2，l：4，k：4，e：4，i：5，a：5，空格：9` * @param bytes，待操作的数组 * @return */ public static List<Node> getNodes(byte[] bytes) { //1、创建一个ArraysList ArrayList<Node> nodes = new ArrayList<Node>(); //2、遍历bytes，统计存储每一个byte里面x数据出现的次数 --->map Map<Byte,Integer> counts = new HashMap<>();//Byte是数据，Integer是次数 for (byte b: bytes) { Integer count = counts.get(b); if (count == null) {