第十三课时 队列
package cn.czm0801;import java.util.List;import java.util.PriorityQueue;public class HuffmanTree {private Node root;//根节点private PriorityQueue<Node> pq;//优先队列public HuffmanTree(PriorityQueue<Node> pq){this.pq = pq;}/** * 添加节点方法 * @param n1 * @param n2 */public void add(Node n1,Node n2){Node n = new Node((char)(0),n1.getCount()+n2.getCount());n.setLeft(n1);n.setRight(n2);pq.add(n);}/** * 创建哈夫曼树方法 */public void createTree(){while(pq.size()>1){this.add(pq.poll(), pq.poll());}root = pq.peek();}public void ergodic(Node current,String str){if(current.getLeft()==null && current.getRight()==null){current.setCode(str);System.out.println(current + " 编码是 " + current.getCode());return;}this.ergodic(current.getLeft(), str + "0");this.ergodic(current.getRight(), str + "1");}/** * 还原内容 * @param str * @param list */public void restore(String strCode,List<Node> list,final int length){String str = "";int count = 0;int i =0;while(count <length){if(strCode.indexOf(list.get(i%list.size()).getCode())==0){count ++;strCode = strCode.substring(list.get(i%list.size()).getCode().length());str = str +list.get(i%list.size()).getCh();}i++;}System.out.println("恢复后的内容是 "+str);}public Node getRoot() {return root;}}

?

package cn.czm0801;public class Node {private char ch;//字符private int count;//次数private String code;//编码// 左子树节点private Node left;// 右子树节点private Node right;public Node(char ch, int count) {this.ch = ch;this.count = count;}public char getCh() {return ch;}public void setCh(char ch) {this.ch = ch;}public int getCount() {return count;}public void setCount(int count) {this.count = count;}public Node getLeft() {return left;}public void setLeft(Node left) {this.left = left;}public Node getRight() {return right;}public void setRight(Node right) {this.right = right;}public String toString(){return ch + "    出现次数是" + count;}public String getCode() {return code;}public void setCode(String code) {this.code = code;}}

?

package cn.czm0801;import java.util.ArrayList;import java.util.Comparator;import java.util.Iterator;import java.util.List;import java.util.PriorityQueue;public class Test {/** * @param args */public static void main(String[] args) {String str = "fdjhjfhvcvnlhvnbcvur";List<Node> list = new ArrayList<Node>();statistic(str,list);/** * 使用匿名类，创建比较器 */Comparator<Node> comparator = new Comparator<Node>(){public int compare(Node n1, Node n2) {if(n1.getCount() > n2.getCount()){return 1;}else if(n1.getCount()< n2.getCount()){return -1;}else{if(n1.getCh() > n2.getCh()){return 1;}else if(n1.getCh() < n2.getCh()){return -1;}else{return 0;}}}};//优先队列PriorityQueue<Node> pq = new PriorityQueue<Node>(list.size(),comparator);for(int i = 0;i<list.size();i++){pq.add(list.get(i));}//构建哈夫曼树HuffmanTree ht = new HuffmanTree(pq);ht.createTree();ht.ergodic(ht.getRoot(), "");//把字符串转换成编码格式char[] ch = str.toCharArray();String strCode ="";for(int i = 0;i<ch.length;i++){for(int j = 0;j<list.size();j++){if(ch[i]==list.get(j).getCh()){strCode = strCode + list.get(j).getCode();break;}}}System.out.println("转码后的内容是      " + strCode);ht.restore(strCode, list, str.length());//恢复内容}/** * 统计字符出现的次数 * @param str * @param list */public static void statistic(String str,List<Node> list){char[] ch = str.toCharArray();boolean isAppear = false;for(int i =0 ;i<ch.length;i++){for(int j = 0; j < list.size();j++){if(list.get(j).getCh() == ch[i]){list.get(j).setCount(list.get(j).getCount()+1);isAppear = true;break;}}if(!isAppear){list.add(new Node(ch[i],1));}isAppear = false;}}}

?